Рубрика «Алгоритмы»

Направленный граф — это набор узлов, связанных стрелками (рёбрами). Как узлы, так и рёбра могут содержать данные. Вот несколько примеров:

Охота на недостающий тип данных - 1

Все графы созданы с помощью graphviz (источник)

В сфере разработки ПО графы используются повсеместно:

  1. Зависимости пакетов, как и импорт модулей, формируют направленные графы.
  2. Интернет — это граф, состоящий из ссылок между веб-страницами.
  3. При проверке моделей анализ выполняется путём изучения «пространства состояний» всех возможных конфигураций. Узлы — это состояния, а рёбра — это допустимые переходы между ними.
  4. Реляционные базы данных — это графы, в которых узлы являются записями, а рёбра — внешними ключами.
  5. Графы — это обобщение связанных списков, двоичных деревьев и хэш-таблиц.1

Кроме того, графы также широко используются в бизнес-логике. Научные работы со ссылками формируют графы цитат. Транспортные сети представляют графы маршрутов. Социальные сети — это графы связей. Если вы работаете в сфере разработки, то рано или поздно встретитесь с графами.

Я вижу графы повсюду и использую их для анализа всевозможных систем. В то же время я побаиваюсь использовать их в коде. Какой из популярных языков программирования ни возьми, поддержка графов в них практически отсутствует. Ни в одном её нет в виде встроенного типа, очень мало где они прописаны в стандартной библиотеке, и у многих языков нет для этой функциональности надёжного стороннего пакета. Чаще всего мне приходится создавать графы с нуля. Существует большой разрыв между тем, как часто инженерам ПО могут понадобиться графы и тем, в какой степени экосистема их поддерживает. Где все графовые типы?Читать полностью »

Как мы оцифровали футбольные матчи с помощью CV - 1

Привет! Меня зовут Владимир Цуканов, я СТО спортивного направления в Яндекс Плюсе. Мы занимаемся съёмкой, обработкой и стримингом спортивных событий. В этом посте я расскажу о работе с технической съёмкой и анализом футбольных матчей.

Читать полностью »

Переворачивающиеся при умножении числа - 1

Здравствуйте!

Расскажу о серии задач, которая случайно возникла в процессе решения другой задачи. Мне на глаза попалось равенство:

81 * 27 = 2187

– Интересно, – подумал я. – А бывают ли ещё такие числа, чтобы цифры слева и справа повторялись?

Всего нашлось 7 двузначных пар, включая одну с теми же цифрами:

15 * 93 = 1395
21 * 60 = 1260
21 * 87 = 1827
27 * 81 = 2187
30 * 51 = 1530
Читать полностью »

Дал ему подборку книг, он приходит месяца через два, и с порога такой сразу:
-я с друзьями не могу разговаривать.
-Ну да есть такой, недостаточек.

интервью Жака Фреско

Читать полностью »

Неожиданное взаимодействие предсказания ветвлений и подсистем памяти - 1


Это 15-я статья в серии, посвящённая оптимизации подсистем памяти. Остальные доступны здесь (англ.).

В ней мы изучим взаимодействие механизма предсказания ветвлений с подсистемой памяти. В повествовании мы будем исходить из предположения, что вам знаком принцип предсказания ветвлений и работы подсистем памяти в современных процессорах.Читать полностью »

Размышления о структурном программировании - 1

Изначально я хотел назвать статью как нибудь вызывающе, например, "Как наука может превращаться в религию", "В ловушке искажений смыслов структурного программирования" или "О чем вам забыли рассказать про структурное программирование", но в результате все же оставил текущее название и надеюсь, оно не вызывает раздражения у читателей. И хотя другие заголовки являются более кликбейтными, тем не менее они все же в больше степени отражают смысл статьи, чем нейтральные "размышления".

А поводом к этой статье послужил один из комментариев к предыдущей публикации Управление памятью и разделяемыми ресурсами без ошибок, где написали "было доказано математически". А я сразу вспомнил свое небольшое расследование, когда пытался разобраться в одном из "математических доказательств", про которое нам всем рассказывают еще в школе на уроках информатики.

Все наверно помнят, что любой алгоритм можно представить в виде трех видов алгоритмических конструкций, следование, ветвление и повторения? А иногда еще добавляют, что эту теорему выдвинул и доказал Э. Дейкстра в 70-х гг. прошлого века, в том числе, включая широко распиаренный якобы запрет на использование операторов goto.

Читать полностью »

Мой опыт собеседования в Google [оффер на L5] - 1


Предупреждение: я не смогу привести в статье конкретные вопросы из-за подписанного соглашения о неразглашении (NDA).

Работая в лондонском офисе Facebook в команде Instagram*, я начал задумываться о возвращении в Индию. В ноябре 2022 года со мной связался рекрутер Google. Он сообщил об открытии в Бангалоре должности уровня L5 и спросил, интересно ли мне это.

Так как я уже раздумывал о переезде в Индию, то ранее собеседовался в Google, но мне предложили более низкую должность (L4), чем я хотел; потом я устроился в META* на уровень E5.

Я ответил рекрутеру, что хочу запланировать собеседование на март 2023 года, потому что готовился стать отцом и хотел в этот важный период выделить время для своей семьи.

Рекрутер согласился на мою просьбу и предоставил материалы для подготовки к собеседованию. Он сообщил, что свяжется со мной в марте. До этого момента он регулярно писал мне, чтобы узнать, как проходит моя подготовка.

На этот раз в процессе подготовки возникла уникальная для меня сложность — счастливое пополнение в моей семье, дочка. За моё внимание боролись подгузники и кодинг, было очень сложно выделить время на сосредоточенную подготовку! У меня было примерно 25-30 дней на освоение и искусства ухода за ребёнком, и прохождения собеседования.Читать полностью »

Традиционное определение для операции возведения в натуральную степень (или целую положительную) вводится примерно следующим образом:

Возведе́ние в сте́пень — арифметическая операция, первоначально определяемая как результат многократного умножения числа на себя.

На первый взгляд, это определение затруднительно обобщить для целых показателей степени меньших единицы

    ...
x^3  = x*x*x
x^2  = x*x
x^1  = x
x^0  = ?????
x^-1 = ?????
    ...

Читать полностью »

Современная разработка охватывает широкий диапазон от работы с алгоритмами до системного дизайна. По большей части разработка ПО укладывается в эти рамки. Основная масса разработчиков занимается созданием приложений, что ближе с системному дизайну, чем к низкоуровневым алгоритмам.

Большинство вакансий рассчитано на что-то между разработкой приложений и системным дизайном. Но при этом многие из тех, кто проводит технические собеседования, уделяют время только задачам на знание алгоритмов и системного дизайна – и ничему больше.

Такой подход основан на идее, что, если человек знаком с алгоритмами и системным дизайном, то и на разработку приложений ему хватит способностей. Это спорное утверждение. Создание приложений требует обширного набора навыков. Они не нарабатываются сотнями часов заучивания паттернов в решениях задач на алгоритмы. Да и рассматриванием сильно упрощенных версий системного дизайна Netflix, Uber или Twitter Threads делу не поможешь. Навыки разработки приложений оттачиваются путем… ну, разработки приложений. Но часто на технических собеседованиях они даже не принимаются в расчет.
Читать полностью »


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js