×

Нужны ли программисту алгоритмы и структуры данных

Впервые я написал строчку кода 10 лет назад. С тех пор я каждый день удивляюсь, как много возможностей открыла для человечества разработка. В разработку же меня привело решение алгоритмических задач и участие в соревнованиях по программированию. Первый коммерческий проект я завершил 7 лет назад. Тогда осознал, что недостаточно написать рабочий эффективный код за короткое время. Инженер должен знать архитектурные подходы, придерживаться стиля и банально писать читаемый код.

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

Денис Цьоменко с докладом «Зачем мне знать алгоритмы, если они все уже реализованы?» на RunIT в Днепре, май 2019

Вечный холивар по теме «нужна ли программисту математика» подвергается изменению и превращается в более опасный для индустрии спор. Все чаще на форумах, конференциях и в головах мелькает мысль: «Нужно ли программисту знать алгоритмы и структуры данных?». И этот спор имеет место быть. Сомнительно, что разрабатывая продукт, придется самостоятельно реализовывать быструю сортировку или словарь. Продвинутые же структуры данных пригодятся не более чем 10-20% инженеров. И даже если человек входит в этот процент, он возразит: «Все гуглится и учится за пару дней».

Мысль противоположной стороны выражается так: «Через 5-7 лет 80% задач, которые необходимы при разработке продукта, смогут выполнять школьники 13-14 лет, которые закончили качественные курсы. Но компаниям нужны инженеры, способные решить остальные 20%». Это могут быть знания и в математической статистике, и в алгебре, и в теории программирования. Но фундамент, в любом случае, строится на знаниях алгоритмов и структур данных.

Поэтому собеседования в FAANG или MINT на 60%-100% состоят из Problem Solving задач, для решения большинства которых нужны знания алгоритмов. Сейчас этот тренд переходит и на middle-size компании в мире и в Украине. Из личного опыта могу сказать, что я писал на С++, .NET и Python. И вне зависимости от языка, я использовал знания алгоритмов.

«Нельзя доверять коду, который вы не написали полностью сами», — Кен Томпсон.

Алгоритмы на собеседованиях

В каждой компании есть свой подход к собеседованиям и оценке кандидатов. Также отличаются цели найма. Но есть вещи, которые их объединяют. Я проходил собеседования в различные компании разных размеров и направлений. Где-то алгоритмы и решение задач были ключевым фактором, где-то — вспомогательным. Задачи могут быть разных уровней сложности. Например, самая простая из тех, что мне встречались, — развернуть строку без использования дополнительной памяти. Одна из задач сводилась к умению быстро считать максимальное значение функции xor на префиксном дереве (бор). Ее сложность скорее заключалась в неочевидном решении, чем в реализации. Хорошая задача на собеседовании должна иметь несколько возможных решений, кроме оптимального. Невозможно знать все.

Пример плохой задачи, которую я встретил на собеседовании, это нахождения решения системы обычных дифференциальных уравнений. За вменяемое время невозможно приблизиться к решению, если ты не знаешь алгоритм Рунге-Кутты. Такого же типа собеседования обычно рассчитаны как раз не на проверку умения заучивать редкие алгоритмы, а на умение эффективно использовать стандартные. Чем же отличаются подходы в разных компаниях?

Большие корпорации

Компаниям-гигантам не важно, какой язык Вы знаете или сколько фреймворков выучили. Microsoft, Google или Tesla не нужны «исполнители», которых у них десятки тысяч. Этим компаниям нужны люди, которые смогут придумать и создать новый продукт, оптимизировать устаревший и дальше продвигать эти компании вверх. Умножьте это на количество кандидатов и необходимый ресурс для отбора. В итоге получим «алгоритмические» собеседования. Такой подход критикуют, пытаются изменить и усовершенствовать. Например, вопросами по софт скиллам или по дизайну систем. Подобные интервью иногда отсеивают достойных кандидатов, но продолжают проводиться и доказывать эффективность.

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

Пройти такое собеседование помогут даже не знания алгоритмов, а количество решенных типичных задач. Важно понимать, что правильное решение не всегда гарантирует успешное прохождение собеседования. Точно также, как и неоптимальное решение не гарантирует отказ. Люди хотят работать с людьми, а не с машинами для написания кода, поэтому хотят посмотреть, как Вы думаете и говорите. В развитии этого навыка очень помогают пробные интервью. Вы можете проводить их с другом, коллегой или на различных ресурсах, где можно провести и пройти интервью со случайными людьми. Классическим же мануалом по прохождению в большие корпорации является книга «Cracking the Coding Interview». И если Вы хотите попасть в одну из них, то советую прочитать.

Минимальный набор знаний для прохождения интервью в большие компании

Структуры данныхАлгоритмыКонцепты
Стэк/очередьБинарный поискБитовые операции
СпискиBFS/DFSПамять (Stack vs Heap)
Хэш-таблицыСортировки (quick, merge, stable, bucket)Рекурсия
СпискиBFS/DFSДинамическое программирование
Деревья, графыBig-O notation

Средние компании

Опыт лучших перенимают и организации, которые гонятся за ними. В Украине существует минимум 3 компании, которые фокусируются на problem solving interview (DataRobot, Ring Labs, Grammarly). Еще большая часть включают их в свой процесс собеседований как вспомогательные.

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

В некоторых компаниях среднего размера могут встречаться задачи, которые требуют точечной подготовки. Это возможно из-за конкретных требований проекта и ограничений в количестве набираемых кандидатов. Когда вы набираете 10 человек, а не 1000, тогда вы действительно хотите отобрать лучших из лучших.

Стартапы

Любой успешный стартап — это не только крутая идея, но и качественная реализация. В самом начале пути, когда пишется PoC (Proof of Concept), можно игнорировать и архитектуру, и оптимизацию. В таком случае при развитии и расширении стартапа придется выделить время на переписывание/ доработку/ рефакторинг.

Казалось бы, при чем здесь алгоритмы? Problem solving задачи развивают также умение быстро писать решение задачи, не задумываясь об архитектуре. И это часто то, что нужно для старта: написать «что-нибудь», что будет работать в кратчайшие сроки. Поэтому к «спортивным программистам» относятся с опаской. Да, они напишут для вашего продукта что угодно за минимальное время. Сможет ли этот код поддерживать кто-то другой? Ответ на этот вопрос размыт.

На этой волне можно вспомнить статью об украинском стартапе Looksery, который был основан людьми, связанными с олимпиадами. Они и набирали себе подобных: призеров и участников ACM ICPC (студенческая командная олимпиада), финалистов IOI (олимпиада для школьников), ребят с высоким рейтингом на CodeForces или TopCoder. Чем закончилась эта история, думаю, все осведомлены, или могут узнать по ссылке выше.

С другой стороны, собеседования в стартапы — самые непредсказуемые. Иногда это может быть и одно интервью об опыте и «чем хочешь заниматься», а после этого — офер. В другом случае, это может быть длительный процесс с 8+ интервью различной сложности.

Аутсорс

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

Я ни разу не встречал людей, у которых спрашивали problem solving в аутсорсе. В маленьком /среднем/ крупном — не важно.

Связано это с тем, что аутсорсу нужно сразу бросить разработчика в бой. Им важно, чтобы он понимал язык, фреймворки, которые используются на проекте. Также кандидат должен пройти интервью с заказчиком, которому также не выгодно даже 2-4 недели обучать сотрудника. Добавим сюда большой процент legacy-кода, который не то что оптимизировать, а сложно поддерживать. В итоге получим интервью, которое тестирует вашу память, опыт, что угодно, но не умение решать задачи. К тому же, у крупного аутсорса есть свои академии, где готовят Trainee, Junior-позиции под себя. Им выгодно впихнуть в голову ученика пару фреймворков, чем пытаться научить его решать бесполезные на проекте задачи.

Если у Вас есть истории о прохождении problem solving interview в аутсорсе — поделитесь в комментариях. Будем надеяться на лучшее.

Использование алгоритмов в реальной разработке

За свою карьеру в различных компаниях в трех странах (США, Германия, Украина) я, так или иначе, сталкивался с алгоритмами. Иногда это неявное использование с применением стандартных библиотек, иногда — явная реализация. Даже обычное наследование — это, по сути, граф взаимосвязей между классами. Получается, что каждый день на работе программисты используют какой-то алгоритм или структуру данных. Хэш-таблицы, сортировка, алгоритмы поиска и другие популярные алгоритмы уже реализованы в большинстве популярных языках. И чем лучше понимание как эти алгоритмы реализованы внутри, тем легче будет найти эффективное применение и не встретить неожиданные баги, которые сложно отследить. Два моих любимых примера, которые встречались не один раз, это возгласы: «Почему так долго?» при использовании хэш-таблиц. И второй пример — это флейк тестов при использовании сортировки.

Типичный пример 1

Дано: длинные строки примерно такой структуры: «{время}. {много информации о том, что произошло в этот момент времени}» (структура может отличаться). Для каждой строки нужно посчитать какое-то значение. Например: сколько раз ее просматривали, редактировали и т.д.

Программист решает использовать стандартный dictionary, HashTable, unordered_set, в зависимости от языка. Но «под капотом» — это и есть хэш-таблица.

Код написан, тесты проходят, апрув получили — мерджим и запускаем в продакшн.

И на проде получаем, что запрос исполняется долго, обновление данных так вообще происходит пару минут. Программист в растерянности и панике.

В чем проблема?

В том, что теоретически получение значения по хэшу в среднем занимает константное время работы. Но получение этого хэша от строки — линейно. И с большими строками это работает крайне паршиво. Это если не говорить о коллизиях, которые также могут возникать. В худшем случае, получение значения по хэшу занимает линейное время от размера хэш-таблицы.

Что делать?

Все зависит от конкретной задачи. Самое простое исправление в примере выше — это хранить хэш только от времени (считаем его уникальным), а остальную строку, при необходимости, как значение по этому ключу вместе с остальной нужной информацией. Может быть, выгоднее даже хранить данные в отсортированном виде и проходиться по массиву двоичным поиском. Например, если строки очень длинные, но довольно уникальные. Главное, это понимать и знать, как работает то, что вы используете, какой алгоритм и структуру оптимально выбрать под ваш случай.

Типичный пример 2

Программист достает данные из таблицы, модифицирует их и возвращает клиенту в отсортированном виде. Сортировка производится по ключу, который прислал клиент в запросе.

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

Тесты написаны, код уже давно в мастере. Об этой задаче давно забыли, добавили новые поля в таблицу, клиент присылает запросы с другими ключами — сервер работает как часы. В один прекрасный момент начинают не проходить тесты при проверке задач, которые никак не связаны с этим участком кода. Другие программисты жмут перезапуск тестов, и со второй-третьей попытки тесты проходят. Разработчик думает, что ему не повезло, и в этот момент возникли проблемы с базой, отвалился докер-контейнер или другой инструментарий. Но это начинает происходить все чаще и чаще на одном и том же тесте. Что произошло?

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

Что делать?

Сортировать по двум ключам: ключу, который нужен, и уникальному в структуре данных. Например, ID элемента таблицы. Тогда каждый раз результат будет одинаковым.

Также поможет использование стабильных сортировок. Например: stable_sort в С++, Enumerable.OrderBy в .Net, sorted в Python (после версии 2.2) или подобное на вашем любимом языке. Даже если стандартная библиотека не содержит стабильную сортировку, напишите сами.

Как итог, понимание, что Вы используете, поможет вам на таких этапах разработки:

  • оценка сложности программы на начальном этапе;
  • оценка количества необходимых мощностей и памяти;
  • возможность оптимизации в зависимости от специфики продукта;
  • не подгружать огромные библиотеки ради одного метода;
  • «крутой» зеркальный фотоаппарат не сделает из вас фотографа.

Хочешь сделать хорошо — сделай это сам

К сожалению или к счастью, не все алгоритмы уже реализованы. Некоторые реализованные сложные алгоритмы требуют модификации или гибкости в использовании. Ниже приводятся некоторые примеры использования из жизни. Они будут видоизменены и немного упрощены для статьи. Но главные идеи и применения алгоритмов описаны.

Задача 1

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

Для этой задачи можно придумать большое количество решений в зависимости от вашей инфраструктуры, хранилища и других факторов. Одним из подходящих будет использование дерева отрезков (segment tree).

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

Дерево отрезков дает возможность обновлять данные за O(logN), получать показатели для последовательной группы людей тоже за О(logN). Да, нагрузка на память увеличилась за счет того, что нужно хранить два таких дерева (для максимума и для суммы), и они занимают в 4 раза больше места, чем массив с данными. Но в моем случае это было не критично.

Почему не использовать готовую реализацию?

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

Планировалось, что могут потребоваться более сложные вещи вроде группового обновления данных. Например, при обнаружении подозрительной активности с аккаунтов, которые были зарегистрированы в одно время. Из доступных дополнений также возможны: получение порядковой статистики, сохранение предыдущих версий дерева.

Примитивное дерево отрезков для функции минимума

Результат

Как я знаю от бывших коллег, это работает и модифицируется до сегодняшнего дня. Хотя было написано меньше чем за день (вместе с тестами). Если бы в команде никто не слышал о таком алгоритме, то на его поиски и реализацию ушли бы недели.

Задача 2

Люди работают в большой корпорации. Необходимо оптимизировать бизнес-процессы и документооборот. У каждого сотрудника есть своя нагрузка, количество необходимых утверждений (подписей) для дальнейшей обработки документа/ товара. Нужно максимизировать эффективность и минимизировать время обработки и затраченные ресурсы.

Пример графа для поиска максимального потока

Решение

При решении схожей задачи у меня не было представления о линейной алгебре и транспортной задаче. Но я слышал об алгоритме Min Cost Max Flow.

По сути, каждого человека/ транспорт можно представить в виде вершины графа с показателями эффективности: количество обработанных единиц за время и затраты на них. Между вершинами есть последовательные взаимосвязи, которые известны.

С изменениями, но для решения этого применялся алгоритм поиска минимальной стоимости максимального потока.

Сомневаюсь, что данный алгоритм пригодится мне еще хоть один раз. Но он также интересен тем, что в базовом варианте объединяет три других: BFS, Форда-Фалкерсона и Белмана-Форда.

Результат

В свое время для меня это выглядело как шедевр. А в объединении с приятным UI, было еще и используемой вещью. Но проект завершил свое существование, а вместе с ним оборвалась жизнь и этого кода.

Задача 3. Разбор логов сервера

Дано: Файл логов 100 МБ+. Нужно наладить быстрый поиск по этому файлу. Слова и фразы поиска — это коды, тексты ошибок и ID пользователей (короткие строки).

Стандартные средства уже не удовлетворяли запросы проекта и нужно было придумать более быстрый способ. И снова помог алгоритм, который я видел до этого — Ахо-Корасик. Про результаты лучше всего расскажет график:

Результат

Это было не так давно, но есть подозрение, что эта реализация прослужит еще пару лет. Если инфраструктуру и процессы не изменят раньше.

Как я пришел к изучению алгоритмов и советы

Честно признаюсь, мне повезло. Я пришел в разработку и начал осваивать архитектурные и технические подходы после изучения алгоритмов и решения 1000+ задач на различных ресурсах. И мой путь выглядел примерно так: видишь задачу -> не знаешь, как решать -> изучаешь, реализовываешь, модифицируешь подходящий алгоритм.

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

При подготовке к прохождению интервью, два самых популярных ресурса — это:

  • LeetCode. Тут собрано много задач и подборок от easy до hard уровня. Для каждой задачи доступен discuss, где люди делятся идеями решений и реализацией на различных языках.
  • InterviewBit. Здесь задачи разделены по уровням и темам. Также можно установить количество дней до интервью и видеть свой прогресс. Плюс для каждой задачи представлены подсказки и решения.

Существуют также ресурсы, которые предлагают обучение в более игровой форме. Например: Codewars или Code in game.

Если же вы захотите перейти на следующий уровень, изучать продвинутые алгоритмы и решать связанные с ними задачи, то стоит взглянуть на соревновательные сайты, такие как Topcoder, Codechef и другие.

А также абсолютно всем советую ознакомиться с книгой «Алгоритмы. Построение и анализ» Томаса Кормена. В ней подробно описаны большинство популярных алгоритмов. К тому же, книга написана понятным языком и легко читается, как в оригинале, так и в переводе.

Выводы

Сейчас в работе вы можете не нуждаться в алгоритмах. Например, если вы верстаете страницы, разрабатываете API и имеете сотни других рутинных задач.

Когда вы работаете с архитектурой, хайлоадом, базами данных, то знания алгоритмов и структур данных вам однозначно пригодятся. Невозможно заниматься 3D-моделированием, машинным обучением, IoT-разработкой, не погружаясь в детали и нюансы алгоритмики. Любая отрасль, где нужна оптимизация памяти или времени, требует этого. Они помогут вам и в выборе архитектуры. Вы не сможете выбрать графовую базу данных для своего проекта, если не знаете, что такое граф.

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

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

Алгоритмы и структуры данных помогут вам продвинуться в карьере. На конференции RunIT в Днепре, где я выступал с этой темой, человек в зале привел простой пример: «Однажды за то, что я сумел решить задачу о перемещении шахматного коня из одной клетки в другую за наименьшее количество шагов, мне подняли зарплату на 500 $». Чего и вам желаю.

Все про українське ІТ в телеграмі — підписуйтеся на канал DOU

👍ПодобаєтьсяСподобалось2
До обраногоВ обраному7
LinkedIn

Схожі статті




Найкращі коментарі пропустити

И даже если человек входит в этот процент, он возразит: «Все гуглится и учится за пару дней».

Как-то раз мне на интервью разраб так и говорил, мол в случае чего все нагуглит. Я ему дал задание набросать на листочке merge sort, сначала сам по себе метод мерджа, потом как он будет применятся к неотсортированному массиву. Чувак набросал, вот только сложность итогового алгоритма сортировки была N^3. И человек считал, что это норм.
То есть проблема как раз в том, чтобы верно оценить свой код. Гугл не сделает за тебя код-ревью и не скажет тебе «эй, братишь, у тебя тут плохой алгоритм, погугли-ка лучший».

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

Нужны ли программисту алгоритмы и структуры данных

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

Зайшов сюди тільки, щоб почитати коментарі і побачити як у людей бомбить.

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

288 коментарів

Підписатись на коментаріВідписатись від коментарів Коментарі можуть залишати тільки користувачі з підтвердженими акаунтами.

Програмування стає потроху другою грамотністю, або вмінням читати. Тому, коли навчаю інших, то одразу кажу, що для того, щоб почати програмувати не те, що алгоритми, а навіть математику можна не знати. Мета — зацікавити людей, перш за все дітей більшості з яких від слова «математика» вже стає нудно.
Для дорослих, як тут часто кажуть «вайтішників», ІТ — це, як це не прикро, трохи не єдина можливість достойно заробляти чесною працею в нашій країні, і так, 90% з них теж не потрібні алгоритми для успішної роботи.
Дякую за вихід з алгоритмічно секти на живу проповідь, бажаю вам більше послідовників, щоб перемагати не лише к-тю, але і якістю ІТшників в Україні.

Имеет ли значение на каком языке решать такого рода задачки? Например если собеседование на позицию iOS Developer можно ли писать на Python (так как в вузе изучали структуры данных именно на нем) или это неправильно воспримут?

Если на позицию iOS Developer задают алгоритмические головоломки, можно желать хорошего дня :)

как-то предложил заменить вычисление количества комбинаций перебором(O(n!)) ради сравнения сравнение на больше-меньше с вычислением через логарифм(O(1)) — когда идеальная точность не нужна(бо сравнение), зато не будет переполнения от возведения в непредсказуемо большую степень.
сказали «ты молодец, но у нас в джава части так, менять не будем».
на этом мое применение данного скила закончилось, клепаю формочки и не высовываюсь.

«Нельзя доверять коду, который вы не написали полностью сами», — Кен Томпсон.

«Нельзя доверять коду, особенно тому который вы написали полностью сами», — Євген Шемет.

Хочешь сделать хорошо — сделай это сам

— это уже похоже на «вредные советы». Нет. Человек который умеет разрабатывать и реализовывать сложные алгоритмы, не зависит от того что он прочитает на DOU. Для остальных правильный совет однозначен: Надо использовать библиотеки при любом удобном случае.

1. У дельфина — длиннее
2. Да, АиС данных нужны.

В целом поддерживаю, примеры интересные и, наверно, показательные. Есть замечание:

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

Вот тут нечто очень странное. Обычные алгоритмы сортировки, даже неустойчивой, детерминированны. То есть если есть на входе 1A 1B 2, то такой алгоритм может всегда давать на выходе, например, 1B 1A 2, но не через раз. Недетерминированные иногда встречаются, но их в общем стараются избегать — ради воспроизводимости при диагностике. Или вы кривовато описали ситуацию, или мне уже интересно, где это вы такой случай нашли?

Про результаты лучше всего расскажет график:

По горизонтали неподписанные попугаи (3000, 5000). Это количество одновременных шаблонов для поиска?

Под устойчивостью имеется в виду порядок объектов с тем же значением. Например, есть коллекция объектов со значениями 1A. Штрихами я показываю маркеры объектов: 1A`, 1A``, 1A```. Первый вызов quick sort может вернуть коллекцию 1A``, 1A`, 1A```. Второй вызов на уже отсортированном массиве может венуть 1A```, 1A`, 1A``.

В чому принципова різниця між ["1A","1A","1A"] та ["1A","1A","1A"] для наступного коду, який буде використовувати ці масиви?

Суть в том, что порядок объектов с тем же значением после сортировки изменится. Для какого-то кода это может иметь значение, для другого — нет. stackoverflow.com/...​rt-algorithm-to-be-stable.

А можна мені привести реальний приклад, коли обробка масиву ["1A","1A","1A"] буде дійстно відрізнятися від обробки масиву ["1A","1A","1A"]?

Ну я же привел ссылку. Там есть примеры. Например, сортировака сначала по первому ключу, а потом по второму с сохранением порядка. Оттуда же.

Its useful when you don’t know the conditions ahead of time. Envision a listview where the user clicks on a column to sort, and then clicks on another column to sort further.

Так би б одразу сказав, що сортування робиться масиву об’єктів, а не примітивів. А хто забороняє сортувати по двох параметрах одразу, а не послідовно?

Так би б одразу сказав, що сортування робиться масиву об’єктів

Я так сразу и написал 🙂

есть коллекция объектов со значениями 1A
А хто забороняє сортувати по двох параметрах одразу, а не послідовно?

Никто, но ты прочитай еще раз процитированный коммент, вот он:

Its useful when you don’t know the conditions ahead of time. Envision a listview where the user clicks on a column to sort, and then clicks on another column to sort further.
Its useful when you don’t know the conditions ahead of time.

Попередні кондішини все одне можуть бути відомі. Тут більше схоже на теоретичну проблему більше ніж на практичну.

Если твой посыл, что тебе алгоритмы и структуры данных не нужны — ок. Мне нужны. Из недавнего: преобразование одного синтаксического дерева в другое, поиск дубликатов и fuzzy search там же.

Под устойчивостью имеется в виду порядок объектов с тем же значением.

Спасибо, кэп, но вопрос не в этом.

Второй вызов на уже отсортированном массиве может венуть 1A```, 1A`, 1A``.

В ваших же обозначениях: пусть есть 1A’, 1A’’, 1A’’’.
Есть распространённая реализация сортировки, что сделает, например, при одном вызове 1A’’, 1A’’’, 1A’, а при другом из того же входного набора (а не выходного первого запуска!) — 1A’’’, 1A’, 1A’’?

Да, quick sort. В нем pivot выбирается рандомно.

Где конкретно вы видели такую реализацию в продакшене? Прошу точного указания.
Например, GCC STL — рандома нет, есть медиана отрезка как pivot, и бюджет рекурсии (после которого переходит в heapsort).

Раньше я тоже думал, что рандомный выбор — универсальное лечение от впадания в O(N^2), но качественный пересчёт показал, что это не так.

Где конкретно вы видели такую реализацию в продакшене?

А где я писал, что видел? Мне достаточно знать какой метод сортировки используется. И если я знаю, что это quick sort, я не буду завязывать логику на то, что сортировка будет выдавать такой же результат для таких же входных данных. Тем более что реализация может поменяться в новой версии библиотеки. По-моему, как раз в ранних версиях .NET-а пивот и выбирался рандомно. Попробую быстро нагуглить, напишу дополнительно, если найду.

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

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

По-моему, как раз в ранних версиях .NET-а пивот и выбирался рандомно.

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

Про график, это суммарная длина поисковых запросов. Про сортировку несколько раз встречал подобный пример. Один из случаев можно в общем виде описать примерно так:
1. Метод возвращает отсортированный массив объектов.
2. Есть тест, который это проверяет, который генерирует случайные данные, но сразу в отсортированном виде. Потом записывает их базу.
3. Вызываем метод и сравниваем с нашим сгенерированным результатом. Они не совпадают.
Другой случай уже описал Андрей Литвинов.
Также я могу представить ситуацию, когда допустим отсортированные данные получаем сразу с базы с помощью orderBy, а в тесте сортируем проверяемые данные с помощью стандартной сортировки языка. В итоге две разные сортировки дадут разный результат. Но на уникальных данных этот тест будет упорно и долго проходить.

Про график, это суммарная длина поисковых запросов.

OK, спасибо. Если поставите подпись в основной статье, будет совсем хорошо.

описать примерно так:

Понял. В таком случае, да, проблема может вылезти влёгкую.

допустим отсортированные данные получаем сразу с базы с помощью orderBy

Ну это идентично по сути вашему примеру с генерацией случайных уже отсортированных данных.

Но на уникальных данных этот тест будет упорно и долго проходить.

Ну тут важнее хороший тестер, который не будет клинить себя на уникальных ключах :)

Подскажите подробнее про «Задача 2
Нужно максимизировать эффективность и минимизировать время обработки и затраченные ресурсы.» Это софт какой-то был? Интересует решение подобной задачи с целью оптимизации взаимодействия между департаментами

Крутий розробник не той, хто знає чужі алгоритми, а той, хто може написати свій.

Пропоную написати це гарним шрифтом на фоні картинки заходу сонця над океаном, і розшарити в фейсбуці :)

ПС. «чукча нє чітатель — чукча пісатель» :)

вот вот лучше на морько!

И ракушки на пляже сортировать )

Мерж сортом

скорее рандом сортом как морько делает ))

Пирамидальной )

о! я догнал! ))

Я б сказав, креативний скоріше. Вибачте, в мене алергія на слово «вчений»

Хатуль мадан.

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

И кто-то из зала
Вообще-то сварщики не знают начертательной геометрии.
А для таких случаев используют лекала.

Вот так и о «должен ли программист знать X»

(мне начерталка очень зашла, так что делал другим «рабочие тетради» — в удовольствие.
но про лекала — запомнилось)

И кто-то из зала
Вообще-то сварщики не знают начертательной геометрии.
А для таких случаев используют лекала.

потому что в этом некоторая путаница вайти между рабочими и инженерами а сегодня туда пытаются ещё и приткнуть «офис-менеджеров»

потому что в этом некоторая путаница вайти между рабочими и инженерами

не только.

у меня есть любимый пример разницы между математиками и инженерами в программировании

Есть задача, для которой явно нужно использовать «самобалансирующееся дерево поиска»
Математик придумает красно-черное дерево
Инженер — SkipList
SkipList да, чуть менее эффективен, и я бы не советовал его применять скажем для реализации индексов в реляционной БД, то есть там, где борьба за десятые доли процента эффективности.

Но в большинстве практических случаев разницей можно пренебречь.

И главное преимущество у SkipList, для меня:
Я вам сейчас расскажу как его реализовать, никуда не заглядывая.

А давайте попросим не преподавателей, а программистов с 3+ стажа бытенько рассказать о реализации красно-черного дерева. Сколько отсеются? Причем уверен что большинство из тех кто говорит о необходимости знания алгоритмов — тоже отсеются, и только сортировки смогут по памяти восстановить.

Вот и выходит, что опыт — это не знание начерталки, а умение решать задачу за приемлимое время и с приемлимым качеством.
А лекала это, или начерталка...

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

Реализация красно-черного дерева это как раз пример того, что нет смысла запоминать, если ты только не работаешь с этим деревом постоянно. Так как там куча этих занудных кейсов «мы вставляем ноду вон туда и теперь нужно повернуть поддерево так и сяк». Но инженеру достаточно помнить общее устройство дерева, что оно самобалансируется и для какого набора задач чаще всего используется.

Вот и выходит, что опыт — это не знание начерталки, а умение решать задачу за приемлимое время и с приемлимым качеством.

вообще-то поинт в том что задачи разные и решать им разным людям а не притворяться якобы инженер может и трубу заварить и лекала нарисовать и математику всего процесса из головы заново поднять тройными интегралами в пространстве Джозефа Стражински

но я так понимаю непонимание и противоречивание как раз только подчёркивает ))

Математик придумает красно-черное дерево

Или AVL-дерево, как оно было на 10 лет раньше. Или B-дерево. Причём я вообще не понимаю причины моды на красно-чёрное дерево: полно показаний, что AVL в среднем не хуже, но понимать его в разы проще (а красно-чёрное проще понять как растянутое B-дерево, чем само по себе).

не преподавателей, а программистов с 3+ стажа бытенько рассказать о реализации красно-черного дерева. Сколько отсеются?

А им обычно и не нужно. Нужно знать характеристики и ограничения. Так оно на практике и получается — не будут рассказывать про детали «тройного лево-левого поворота», но будут помнить, что O(log N) на операцию. И это ровно то, что нужно, если ты не автор ZFS или чего-то столь же специфического.

Инженер — SkipList

А вот тут проблема в ваших рассуждениях — в каком году был придуман skiplist, а? В 1989-м, когда уже были придуманы десятки других видов деревьев, и дети — ровесники красно-чёрных деревьев могли уже собственными детьми обзавестись, а в IT уже миллионы людей работали. И кем придумано — инженером? Аж никак, учёным в CS. Значит, что-то не так тут, мягко говоря: не очевидная это идея аж никак. И не придумает сам по себе инженер такое: ему надо где-то прочитать про такой метод.

Или вы под «придумали» имели в виду «выбрать из имеющегося при полной невозможности применить готовую реализацию»? Тогда я вообще не понимаю, где вы такие условия нашли.

Так что — плохой, негодный пример. Понятно, что вы пытались доказать, но как-то не достигли даже на 1/10...

в каком году был придуман skiplist, а?

не имеет значения.

И кем придумано — инженером? Аж никак, учёным в CS.

не имеет значения.

потому что пример этот для меня — в кардинальной разнице реализации.
а снаружи — «одно и тоже»

И не придумает сам по себе инженер такое: ему надо где-то прочитать про такой метод.

я даже инженером себя не считаю, а подобные штуки придумывал. менее обобщенные, не такие элегантные.
часто придумывал — посмотревши куски на стековерфлов, или в каких-то проектах, то есть да, не с чистого листа.
но на «красно-черное дерево» точно бы не тратился. взял бы что-то готовое, или... заменил бы на «skiplist».
взвесив конечно, и производительность, и будущий саппорт, и много чего.

Так что — плохой, негодный пример.

не настаиваю. потому что дело вкуса. вам не нравится, а мне мой пример — нравится :)

но как-то не достигли даже на 1/10...

ок, и вы не берите меня на работу никогда :D
меня, в смысле так рассуждающих.

я даже инженером себя не считаю, а подобные штуки придумывал. менее обобщенные, не такие элегантные.
часто придумывал — посмотревши куски на стековерфлов, или в каких-то проектах, то есть да, не с чистого листа.

В таком случае лучше было бы для примера показать как раз такую штуку. Хотя, боюсь, и в этом случае нашёлся бы аналог из более высоких сфер.

потому что пример этот для меня — в кардинальной разнице реализации.

Посыл ясен, ok (хотя если бы он был более явно озвучен, не было бы причины для круга обсуждений).

ок, и вы не берите меня на работу никогда :D
меня, в смысле так рассуждающих.

А это совсем другой вопрос. Если потребуется самопал — нужно будет, чтобы кто-то этот самопал сделал, да. Но если нет — то стандартное таки обычно лучше, пусть даже с лёгкой потерей характеристик.
Если человек этого не понимает — то с ним будет сложно работать. По вашим сообщениям непонятно, понимаете или нет:), но некая склонность к самопалам таки явно озвучена.

В таком случае лучше было бы для примера показать как раз такую штуку

а для того чтобы показать в чем фишка, нужно описать задачу, описать нюанс задачи, указать причины почему не использовалось нечто стандартное, и при этом, будет минимум 3 способа решения все правильные :)

Хотя, боюсь, и в этом случае нашёлся бы аналог из более высоких сфер.

конечно.

загадка только — если все уже есть в высших сферах, почему же программисты просто не конфигуруют на каких-то макросах, DSLях системы? а все пишут, пишут, пишут...

А это совсем другой вопрос.

это я к тому что мы, то есть «сварщики с лекалами» не встремимся в реале :)
кто дружит с головой — просто не пришлет вам своего резюме, почитав стек, требования, и типичные проекты
и наоборот, те что шлют вам, не шлют резюме в компании где обитают «сварщики с лекалами»

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

По вашим сообщениям непонятно, понимаете или нет:), но некая склонность к самопалам таки явно озвучена.

случайно вышло, что только недавно начал читать «Как пасти котов» — там вполне годная классификация программистов :)

причем, «инженеров» и «ученых» автор не жалует. а нахваливает как раз те типы, в которых я себя узнаю. вот с автором, когда он в качестве руководителя набирает сотрудников — мы явно встретимся
с теми кому нужны «инженеры» и «ученые» — нет.

ну а про самопалы — в вашей компании наверное их не пишут?
вообще, а что такое — писать код? зачем его пишут то?

«все уже написано», говорил мне один знакомый в конце 90ых.
так что ваша компания пишет? не самопал ли?

причем, «инженеров» и «ученых» автор не жалует. а нахваливает как раз те типы, в которых я себя узнаю.

«Сам себя не похвалишь — ходишь как оплёванный» ©

И он только нахваливает те типы, в которых вы «узнаёте себя»? Может, у нас разные книги с одним названием? А то в своей копии я не вижу вообще типов без недостатков...

«все уже написано», говорил мне один знакомый в конце 90ых.

Этот знакомый обладает каким-то авторитетом здесь или в общих кругах?
Если нет, то зачем вы ссылаетесь на какого-то заведомого... мнэээ... альтернативного мыслителя? Он вам чем-то дорог?

(присмотревшись к фото и расчесав весь затылок чтобы вспомнить) А зачем вы старый акаунт забросили?

это я к тому что мы, то есть «сварщики с лекалами» не встремимся в реале :)
кто дружит с головой — просто не пришлет вам своего резюме, почитав стек, требования, и типичные проекты
и наоборот, те что шлют вам, не шлют резюме в компании где обитают «сварщики с лекалами»

Ой не знаете вы, какие иногда странные люди присылают своё CV и с какими приходилось работать :) лишь бы они конструктивно подходили к работе и рабочему взаимодействию. Но с вашим подходом я уже в этом не уверен...

И он только нахваливает те типы, в которых вы «узнаёте себя»?

конечно не то только.

А то в своей копии я не вижу вообще типов без недостатков...

естественно
«Главное достоинство и есть главный недостаток»

Я же об том что типы программистов — раааазные.
и оснонвые их достиинствах — рааазные.
и остальное, что писал в теме.

но там даже не это главное, не типизация. а то что он аргументирует — почему такие-то качества типа хороши, а почему плохи.
и его критетии — мои!
были книги подобного плана чтение которых забрасывал, потому что ну совсем чужое мне пишет автор. может и трижды прав. но читать «тяжело» совсем. непонятно, «далеко» от меня

Этот знакомый обладает каким-то авторитетом здесь или в общих кругах?

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

Этот знакомый обладает каким-то авторитетом здесь или в общих кругах?

затем что там количество постов прикольное и он старый. или наоборот, на ваша выбор :)
но важнее конечно что там последние пара тысяч неинтересные :)
а посты должны быть все таки или информативные или интересные.
иначе зачем их вообще писать? «о работе» — так ее и на работе хватает.

Ой не знаете вы, какие иногда странные люди присылают своё CV и с какими приходилось работать :)

знаю. всем присылают.
и что, вы разве не поняли о чем я написал что привели «аргумент блондинки»? ;)

Но с вашим подходом я уже в этом не уверен...

«не берите меня на работу»
и все :)

и что, вы разве не поняли о чем я написал что привели «аргумент блондинки»? ;)

Понял, но не считаю тут настолько существенным. Но то, что вы тут увидели только «аргумент блондинки», показательно ;\

«не берите меня на работу»
и все :)

Ну, видимо, само собой получится :)

Ну, видимо, само собой получится :)

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

Это ж старый критерий — ориентироваться можно и нужно только на мнение непосредственных коллег и работодателя
а в интернетах да, тебе о тебе пораскажут, да, какое ты ...

об этом и остальные посты в этой и подобных темах, другим программистам:
если ваша область деятельности, тип и т.п. сильно не вяжутся с условным амазоном — то можете смело забить на критерии «приемки в амазон». вы же никогда не пошлете резюме в такую компанию, с таким профилем деятельности, и т.п. — так зачем вам слушать начальников этой компании — какие программисты им нужны?

тем более что — есть компании где важнее другие качества, склонности, и о, случайно не в такие компании вы рассылаете резюме?

Но то, что вы тут увидели только «аргумент блондинки»,

«ну вам, телепатам, виднее» :)

Причём я вообще не понимаю причины моды на красно-чёрное дерево

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

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

при вставке, существующие итераторы не меняются

На AVL такого не получится? Что-то очень слабо верится, проблемы балансировки у них идентичны, хоть и конкретные реализации различаются.

ув нас, если полгода работу искать, и собеседоватся раз в неделю, то хочешь не хочешь алгоритмы выучишь.

Хм, я на такое ещё не попадал — чтобы полгода искать. Хотя джентльменский набор алгоритмов знаю (без балансировок красно-чёрного;))

Зайшов сюди тільки, щоб почитати коментарі і побачити як у людей бомбить.

согласен под каждым словом из данной статьи. во времена университета не постинг этот дзен. сейчас осваиваю самостоятельно

За всю більш ніж десятирічну кар’єру найбільш задрочене з т. з. алгоритмів інтерв’ю в мене було в джунівські часи ще в ABBY (зрозуміло, це було до війни). Там були і шахи, і сортування, і ще щось, кшталту завдань на міській шкільній математичній олімпіаді. Але після шмату дебільних задачок, коли я нарешті побачив людину, виявилося, що розглядають мене на позицію «писати UI на Symbian» — найгірше, що я на той час (та й зараз) можу собі уявити по своїх плюсах.

Звісно, пізніше були місця, де алгоритми також знадобилися б (аналіз звуку, картографія тощо), але цікавинка в тому, що на співбесідах там таким не вантажили і це були здебільшого НЕ ТІ алгоритми, про які зазвичай згадують, коли радять соватися горою Фудзі.

Тож якщо комусь шахові коні дають +500 до зарплати — лишається лише порадіти за цих людей.

На вебчике — нет, не нужны

Вы не поверите, но в моей практике были случаи когда «страничка в вебчике», которую делали сеньоры, загружалась 2 и более минут! на смешном объеме данных из-за того, что эти сеньоры тоже думали, что алгоритмы и структуры данных им для вебчика не нужно знать.

Проставить индексы в БД — это не алгоритмы и структуры данных

Знаете, в некоторых проектах веб-апи иногда делают немного больше, чем просто прочитать что-то из бд. Кроме того, индекс по-вашему что? Чем вы руководствуетесь когда, например, вам нужно выбрать тип используемого индекса?

By default, the CREATE INDEX command creates B-tree indexes, which fit the most common situations

Это всё заумные слова, а вы тогда расскажите — что же конкретно такого делали те инженеры, для чего им нужны были алгоритмы и структуры данных?

что же конкретно такого делали те инженеры

Писали банальную бизнес-логику

для чего им нужны были алгоритмы и структуры данных

Хотя бы для того, чтобы оценить свой код, как он будет себя вести при выросших объемах данных.

Писали банальную бизнес-логику

Яку саме? Що ви називаєте бізнес-логікою?

Самий простий і досить поширений кейс: це коли вибираються данні з якогось сорса(база наприклад) — звичайно це все ООП і гарно запаковано в метод, потім по цих данних проходяться циклом — і в циклі викликається інший метод який теж вибирає данні з сорса, а в тому іншому методі подібна реалізація — і він теж в циклі вибирає данні з сорса і проходиться по них циклом де знову вибираючи данні з сорса :) В результаті один безневинний виклик дуже добре працює з тестовим мінімалістичним сетом на дев машині, але з ростом данних час виконання і кількість запитів — росте по експоненті.

Або складніший кейс:
В базі є табличка трейнінгів які має пройти кожен працівник, трейнінгів є декілька, і є трейніги які не можна взяти відразу, успішне проходження іншого трейнінга або кількох трейнінгів є умовою запису на трейніг. Також кожен трейнінг має певний розклад — тобто час коли його можна зарезервувати для конкретного працівника, і капасіті — кількість місць. Задача — в UI запропонувати менеджеру графік і розклад проходження тренінгів кржним працівником, з можливістю перемістити деяких працівників на конкретні дати.

Самий простий і досить поширений кейс: це коли вибираються данні з якогось сорса(база наприклад) — звичайно це все ООП і гарно запаковано в метод, потім по цих данних проходяться циклом — і в циклі викликається інший метод який теж вибирає дання з сорса, а в тому іншому методі подібна реалізація — і він теж в циклі вибирає данні з сорса і проходиться по них циклом тед вибираючи дання з сорса :) В результаті один безневинний виклик дуже добре працює з тестовим мінімалістичним сетом на дев машині, але з ростом данних час виконання і кількість запитів — росте по експоненті

Какой кошмар. Но где алгоритмы и структуры данных? Я вижу что исполнитель «не умеет готовить» БД. Но чтобы уметь готовить БД, нужно:

  • Понимать что запрос к БД — это дорого и при возможности их количество необходимо уменьшать (есть впрочем тонкая грань, например с одним-двумя лишними запросами по 1-5мс можно не париться, если в угоду простоте кода)
  • Уметь включить логи/отладку. Специфично для языка/фреймворка, гуглится легко
  • Иметь желание иногда отойти от «лучших практик» в угоду производительности. Например не использовать ОРМ в случаях, где оно не в состоянии оптимально работать с БД. Но знать меру и не превращать весь проект в говнокод

И я не вижу здесь ни мерж сорта, ни обхода красно-черных деревьев, ни даже каких-то структур данных. Думать просто надо, да и всё.

Або складніший кейс:
В базі є табличка трейнінгів які має пройти кожен працівник, трейнінгів є декілька, і є трейніги які не можна взяти відразу, успішне проходження іншого трейнінга або кількох трейнінгів є умовою запису на трейніг. Також кожен трейнінг має певний розклад — тобто час коли його можна зарезервувати для конкретного працівника, і капасіті — кількість місць. Задача — в UI запропонувати менеджеру графік і розклад проходження тренінгів кржним працівником, з можливістю перемістити деяких працівників на конкретні дати.

Вот тут уже да, может и знание алгоритмов понадобиться. Ну и всё равно думать, просто больше.

Перший приклад не про мерджсорт звичайно, а про вміння оцінити свій, щойно написаний код. А це вміння прививається і розвивається при вивченні алгоритмів. Так — такий простий кейс можна навчитись ідентифікувати і виправляти і просто з досвідом :)

А думати треба завжди ;)

Вот отличные примеры. Высокая runtime complexity, которая прячется за ООП фасадом — очень часто встречающаяся херня, которую творят не только джуны но и сеньоры, отрицающие важность навыка оценки сложности алгоритмов.

Чем вы руководствуетесь когда, например, вам нужно выбрать тип используемого индекса?

На части проектов этим вообще занимаются DBA. А синьоры и мидлы занимаются разной там всякой бизнес логикой.

Все верно, в определенной части проектов есть DBA, а там где DBA нет — его компетенции кто-то все равно должен закрывать: сеньйор, тим-лид, etc.

Вы не поверите, но из совсем свежего (август 2019) — из-за кривой особенности текущей сериализации результатов в Нептуне (AWS реализация гремлина) — все запросы на получение данных, где траверс идет более чем по двум уровням вложенности (аля друзья друзей и далее) — так вот все запросы выполняются какое-то неебическое количество времени. И в результате долгой переписки и танцев с бубном удалось обнаружить что проблема в кривой имплементации valueMap() - AWS обещались исправить в следующей версии движка forums.aws.amazon.com/...​a?messageID=912926#912926 После обнаружения обходится это банальной передачей всего перечня полей в запрос (и добавлением лишнего слоя к сериализатору уровня приложения). Это конечно не имеет никакого отношения к структурам данных и алгоритмам — так как для детектирования этого бага движка СУБД — основной требуемый навых именно бубенно-танцевальный, но даже проставить индексы в БД — задача не такая тривиальная, когда нагрузка и количество данных хоть в некоторой степени существенная, потому что необходимо найти оптимум между тем чтобы индексировать максимум полей и таблиц (если реляционная модель) и тем самым получить огромное время затрачиваемое на добавление и изменение инофрмации — в связи с построением и перестроением большого количества индексов, и тем чтобы индексировать минимум — ускорив ввод — но замедлив поиск и вывод. То есть для того чтобы правильно проставить индексы — необходимо понимание алгоритмов, а в некоторых случаях и структур данных — так как именно из понимания структуры данных — есть понимание ограничения индекса — аля после первого миллиона записей начнет тормозить поиск здесь и здесь, а после миллиарда записей — все надо переделывать напрочь. Еластиксерч — до поры до времени, конечно, пуля весьма серебрянная, но только до поры до времени и за хорошую цену.

Миллиарды записей в БД <> «страничка в вебчике»

На вебчике — нет, не нужны

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

Вебчик это когда ИЛИ

а) не distributed
б) не scientific (в самом широком смысле)
в) не embedded
г) не супер highload

г) не супер highload

Понятие более чем растяжимое ибо загрузка бывает на ввод и на вывод (и отличаться может на порядки) плюс — важен объем исторических данных, по которому если надо лопатить то и 1 запрос в день (непредсказанный) может занять неприятно большое количество времени. Но холиварить с вами не буду.

система для обслуживания больших массивов исторических данных с тяжелыми ad hoc запросами — это не вебчик ни разу.

MPP это как раз пункт а)

Разбор логов сервера — фигачишь все в логсташь и эластик серч пусть ищет за тебя

Ведь кто-то умный уже сделал эласктик и плагины к кибане со знанием алгоритмов....

Да еще и опен-сорс (я про lucene, который под капотом)

Потратив ресурсов в десятки раз больше, чем сам сервер?

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

Или у вас ресурсы халявные, или люди только копрокод умеют писать (причём он копрокод с момента его написания), но эта «сотка» не воспроизводится ни на процент, и приходится таки начинать думать об алгоритмах.

Или у вас ресурсы халявные, или люди только копрокод умеют писать (причём он копрокод с момента его написания)

ресурсы у всех платные, а лучший код — не написанный

но эта «сотка» не воспроизводится ни на процент, и приходится таки начинать думать об алгоритмах.

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

платить человеку за суппорт всегда дороже

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

и на деле то, брать к себе математико/инженера-программиста — оверквалифайд.
мало того что переплата, так он еще и киснуть начнет в том что для него рутина, и все равно уйдет от вас, в команду.... разработчиков тех самых классных тулзовин, библиотек, облаков

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

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

о, мы в одном флоте гребем :-) только в разных морях

Разница между программистом, умеющим в алгоритмы и «программистом», не умеющим в них, примерно такая же, как между менеджером по продажам в топовой компании и торгашом на базаре.

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

Так это решить проще. Трехзвенка, где приложение запоминает данные и обновляет их при запросе, если данные устарели на 10-60 секунд, а в остальное время берет из кеша, и сама трехзвенка делает sql запрос к базе, что-то типа (давно не писал на SQL) select Max(accesscount) as MAC, Summ(accesscount) SAC from *** where register_date between.

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

Сортировать по двум ключам: ключу, который нужен, и уникальному в структуре данных. Например, ID элемента таблицы. Тогда каждый раз результат будет одинаковым.

То есть для стабильности результатов надо добавить лишнюю сортировку?

ні, сортувати по двох ключах

Или заменить quicksort на mergesort, который стабилен.

Не могу ничего сказать, так как не использовал. Но как я вижу многие компании его используют, может быть неплохим ресурсом

Jedem das seine — каждому свое. Формашлепам и уебдевелоперам, пожалуй, не нужны — по личному опыту знаю (хотя и в уебе, бывало, приходилось обходиться без библиотек по причине отсутствия многих таковых 20 лет назад).

А вот сейчас я лично (пока что для себя) решаю такую задачу: трейдер покупает и продает акции, причем покупка и продажа не обязательно чередуются, может быть и, например, так:
+10, +15, −20, +5 акций по цене 100, 110, 120, 115
Как считать прибыли-убытки по промежуточным сделкам и как это визуализовать, чтоб мастерство (или ламерствО) трейдера было сразу видно?
Так вот — для того чтоб решить эту задачу, надо знать (или заново открыть) FIFO и LIFO принципы. В этой задаче по определенной причине последнее предпочтительнее, а значит программер, знающий алгоритмы и структуры данных сразу догадается воспользоваться Stack’ом.

И еще — по-моему, решать алгоритмические задачки — это отличная гимнастика для мозга. В отличие от «серьезного матана», где порой надо потратить годы только на усвоение базовых (часто контраинтуитивных) идей, большинство алгоритмов может понять и школьник.

Из операций купли-продажи собрать пары в противоположных направлениях (вход и выход из позиции), положить в базу, и уже их анализировать/визуализировать (используя возможности субд). Уровень задачи — «уеб», как вы изволили выразиться)

Из операций купли-продажи собрать пары в противоположных направлениях (вход и выход из позиции),

Когда каждой твари купле — по паре — тут над алгоритмом и думать нечего.
Над визуализацией все-равно надо покумекать, но в общем это решается, например, так:
yetanotherquant.com/...​500bestWorst100Weeks.html

Но даже в приведенном мной простейшем примере такой парности нет — у меня три купли (+10, +15, +5) и одна продажа (-20)

положить в базу

Можем предполагать, что данные уже там лежат :)
(И да, если данных много — то и тут без знания алгоритмов хранения и сортировки данных в БД никак).

визуализировать (используя возможности субд).

Это интересно. У какой СУБД есть (богатые) возможности визуализации?

Но даже в приведенном мной простейшем примере такой парности нет — у меня три купли (+10, +15, +5) и одна продажа (-20)

Варианта два:

  1. Не учитывать при расчетах открытые позиции (остатки) вообще. Если трейдер делает много операций в день, это приемлемо
  2. Использовать текущую цену актива и «виртуально» закрывать

У вас получается две пары +10 −10; +10 −10; и в остатке +5 и +5

И да, если данных много — то и тут без знания алгоритмов хранения и сортировки данных в БД никак

Что такое много? 125к записей — это много или мало? Индексы, explain select. Требует некоторых знаний, но не нужно быть DBA чтобы оптимизировать запросы.

Это интересно. У какой СУБД есть (богатые) возможности визуализации?

Здесь я некорректно выразился. Имел в виду что данные выбрать из БД умным запросом, а график можно построить любым инструментом, рисующим графики.

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

И сами расчеты результатов, если хочется чтобы они были точными — не самая простая задача (если сделку с фьючерсом открыли до дневного клиринга и закрыли после вечернего — уже результат скорее всего не совпадет до копейки с тем, что получилось на бирже)

Не учитывать при расчетах открытые позиции (остатки) вообще. Если трейдер делает много операций в день, это приемлемо

Ну почему ж неприемлемо, просто такой подход покажет realised PnL — реализованную прибыль (убыток). Но это — далеко не вся интересная инфа.

+10, +15, —20, +5 акций по цене 100, 110, 120, 115
У вас получается две пары +10 —10; +10 —10; и в остатке +5 и +5

Возьмем первый остаток: из чего он состоит — из 5 акций из 1-й десятки (т.е. 5 по 100) или из второй пятнашки (т.е. 5 по 150). Или 5 по средней цене? (чаще всего считают именно так, но так не интересно — менее информативно).

На самом деле трейдеры (не все, но многие) торгуют так: по какой-то акции открывают позицию вдолгосрок, но могут по ней же впоследствии и краткосрочно торгануть. Более того, если краткосрочно акция пошла вверх выше ожиданий, то трейдер может прикрыть и часть долгосрочной позы (собственно, поэтому и LIFO). Делать это в два трейда — не комильфо, ибо за каждый трейд платятся брокерские комиссии...

Большинство брокеров считают только сумму акций — т.е. в моем примере после первых двух трейдов в портфеле будет показано 25 акций по цене (10*100 + 15*110) / 25 = 106. Это просто в реализации и неудобно в использовании. Иные брокеры показывают как общую позицию, так и компоненты, но у них компоненту закрыть можно лишь целиком, т.е. +10, +15, —15, −10 или +10, +15, —10, −15 возможно, а вышеприведенное +10, +15, —20, +5 — нет.

Поэтому, если мы придерживаемся LIFO, то у нас алгоритм будет работать так:
шаг 1 — положи в стек 10 по 100
шаг 2 — положи туда 15 по 110
шаг 3 — вытащи 15 по 110, этого мало, поэтому вытащи еще 5 по 100 ; остаток в стеке 5 по 100
Визуализируя, рисуем стрелку от даты1 к дате3 с пометкой PnL = (120-100)*5
и от даты2 к дате3 с пометкой PnL = (120-110)*15

Да, а еще торговать можно и в шорт — т.е. продавать акции, которые не имеешь в наличии (с расчетом выкупить их потом дешевле). Алгоритма и визализации это принципиально не меняет, но несколько усложняет код.

Что такое много? 125к записей — это много или мало?

Это немного. Но вот если трейдер — робот, и торговля высокочастотная — то там данных будет чуть менее чем до хера. И тут уж — как при разработке, так и при пользовании такой БД — алгоритмы будут на каждом шагу.

И сами расчеты результатов, если хочется чтобы они были точными — не самая простая задача

Да, но это уже немного другая задача. Хотя в широком смысле — из той же оперы про алгоритмы. Ибо наивный девелопер будет исходить из того, что данные будут поставляться бесперебойно и безошибочно, ну а опытный знает, что так не будет — и подумает над тем, что ему делать в случае сбоя датафида (что не так сложно) и как распознать явно неверные данные (что куда сложнее).

Возьмем первый остаток: из чего он состоит — из 5 акций из 1-й десятки (т.е. 5 по 100) или из второй пятнашки (т.е. 5 по 150). Или 5 по средней цене? (чаще всего считают именно так, но так не интересно — менее информативно).

Первый остаток — это 5 акций из второй операции покупки

Первый остаток — это 5 акций из второй операции покупки

Т.е. получается, что мы открыли 1ю позицию вкраткосрок, вторую вдолгосрок, а на третьем трейде прикрыли краткосрок и часть долгосрока, так?!

Такое, конечно, теоретически тоже возможно, но на практике это обычно говорит, что трейдер недисциплинирован. Ибо 1й краткосрок перед открытием долгосрока следовало бы закрыть.

Ну или конечно, возможен, такой вариант, что трейдер увеличивал позу по тренду. В этом случае LIFO и FIFO в общем-то имеют равные права, но т.к. выше я привел пример, где LIFO имеет смысл, а FIFO — нет — то лучше придерживаться более универсального LIFO.

Т.е. получается, что мы открыли 1ю позицию вкраткосрок, вторую вдолгосрок, а на третьем трейде прикрыли краткосрок и часть долгосрока, так?!

Именно.

Вообще, я как-то подразумевал чистых спекулянтов, то есть

Ну или конечно, возможен, такой вариант, что трейдер увеличивал позу по тренду.
я как-то подразумевал чистых спекулянтов

Не все спекулянты торгуют по тренду. И не все, кто по нему торгуют — спекулянты.

Ок, буду знать

Только о(к)но не даст той инфы, которую даст более умный подход
dou.ua/...​s-and-structures/#1662849

что в нем такого умного?

См. выше :)
Лично мне это во многих случаях помогает с ходу оценить, систематически ли трейдер торгует али токо мечется.

что есть

мастерство (или ламерствО) трейдера

? )

Прибыль получил — молодец. Получил убытки — лох. Дальше уже детали. Например, какая доля убыточных/прибыльных сделок. Но тут мнения разделяются. В конце-концов, если прибыльные сделки приносят больше чем уносят убыточные — важно ли что убыточных много?

Прибыль получил — молодец. Получил убытки — лох. Дальше уже детали.

Верно! Но детали порой ох как важны. В конечном счете ведь мы хотим понять:
1. Получил ли трейдер прибыль благодаря своему дару-опыту-умению или просто рынок удачно пошел?
2. Будет ли такая стратегия работать в будущем?

Вот тут вот я разбирал пару примеров, где сначала трейдеры (непосвященным) казались такими молодцами, а в итоге оказались ну такими лохами (хотя нет, лохами оказались непосвященные инвесторы :))
letyourmoneygrow.com/...​greedy-german-pays-price

Вайтішніки, сер ©

Насправді той комент дуже чітко ілюструє, чому сучасний інтернет заповнений тотально глючними веб-ресурсами, лагаючими сайтами, вирвиглаз анімаціями і ще бозначим.
Якщо шльопати форми і забивати на якість, то можна справді не паритись про структури і оптимальні алгоритми.

А вот это, как раз, гораздо чаще не айтишниками диктуется, а заказчиками из серии «сделайте мне как попало, абы дешевле»

А то, что на такие проекты с днищенскими рейтами нанимают «вайтишников» — это уже следствие, в убыток себе-то работать никто не хочет...

глючними веб-ресурсами, лагаючими сайтами, вирвиглаз анімаціями і ще бозначим

И как это всё связано с алгоритмами, и тем более со структурами данных? Чтобы фронт был не глючный — нужно понимать что и как влияет на рендеринг страницы. Нельзя например зафигачить в тег select 10 тысяч опций и обернуть это в красивый плагин с поиском — будет просто невообразимо дико лагать. С вырвиглазными анимациями — это или к дизайнерам, или опять-таки к пониманию что замедляет рендеринг в браузере. И из этого ничего не связано с сортировкой пузырьком или кабанчиком или ещё чем.

Главная причина плохого качества — хорошего не требуют, и соответственно не выделяют на него времени.

Моя думка була більш ширшою.
Я вкладаю в скіл володіння алгоритмами перш за все вміння застосувати потрібний алгоритм у відповідний момент, а не хард-знання як цей алгоритм реалізувати.
Зараз є купа фреймворків, мов, бібліотек, які часто просто треба правильно застосовувати.
І тут нам приходять на допомогу алгоритми і структури даних.
Якщо в тебе є задача робити пошук, то є сенс проаналізувати які саме дані ти будеш шукати, зробити висновок чи є сенс тримати ці дані сортованими чи записи пов’язані між собою чи буде доступ до сховища одночасним для декількох потоків і ще купа всяких підводних каменів які б ти міг уникнути якщо б знав як працює структура саме твого сховища.

В моєму розумінні, людина яка опанувала на достатньому рівні CS зможе осознанно робити правильний вибір у мультикультуралізмі сучасних мов, фреймворків і бібліотек, а не просто юзати один раз вивчену «срібну кулю» для більшості задач.

зафигачить в тег select 10 тысяч опций и обернуть это в красивый плагин с поиском

Ну если поиск делать в цикле indexof’ом, то наверное да, а если через префиксное дерево + inverted index, то гораздо лучше. Но тут же «классический» разработчик скажет что быстрее полного перебора ничего придумать нельзя.

Проблема с 10 тысячей опций — это из моего личного опыта. Но она не об алгоритмах поиска совсем. Попробую описать подробнее. Было приложение (SPA) на Ember. В нем некий диалог для добавления какой-то сущности (жмешь кнопку — всплывает форма). В этом диалоге был выпадающий список с поиском. Реализовался он то ли при помощи selectize.js, то ли чего-то подобного (уже не помню). Есть два способа инициализировать selectize. Первый — сверстать select со всеми опциями и просто передать его id. Второй — сверстать пустой select, передать его id и массив с опциями. Я использовал первый. Это SPA, фреймворк создает DOM-элементы когда требуется (нажали кнопку «добавить»). Список опций приходил с бекенда. Работало все ок, пока в один день я не обнаружил что форма рендерится несколько секунд (неприемлемо долго), с всплеском активности процессора. Это был тот день, когда в базу запихали 10к записей. Решилось просто — рендерить пустой select, и передавать массив прямо в selectize. И я даже не знаю — то ли это браузер не терпит таких больших select’ов, то ли это фреймворк недостаточно быстро рендерит, но знания алгоритмов сортировки найти причину лага не помогли бы, как и предотвратить.

Понял, ну да, тут уже специфика как оно там dom-дерево строит или в таком роде.

Но поиски тоже могут доставлять, когда нажал букву, а оно долго думает на саджесте. Понятно что городить для 100 записей хитрости не стоит, но иметь представление куда копать при увеличении данных тоже неплохо. И тут уже эластик в браузер не встроишь (хотя на клиент всё это вываливать тоже смысла мало, а отдать с сервера только нужное).

хотя на клиент всё это вываливать тоже смысла мало, а отдать с сервера только нужное

Я такого же мнения. Просто в стартапах оно бывает по-глупому, на вчера, без вменяемых тз и т.д. Но вообще selectize хвастает в примерах поиском по 25к записей, просто нужно правильно применить.

Блокчейн-девелопа ответ

А вот тут я завис. Каким образом блокчейн девелопер может на знать алгоритмы и структуры данных? Нет я в курсе про развертывание эфириума 10 кликами в ажуре, но все же, как раз в блокчейне — ещё и криптоалгоритмы надо знать неплохо и кучу всяких других штук консенсусы и прочее прочее.

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

И даже если человек входит в этот процент, он возразит: «Все гуглится и учится за пару дней».

Как-то раз мне на интервью разраб так и говорил, мол в случае чего все нагуглит. Я ему дал задание набросать на листочке merge sort, сначала сам по себе метод мерджа, потом как он будет применятся к неотсортированному массиву. Чувак набросал, вот только сложность итогового алгоритма сортировки была N^3. И человек считал, что это норм.
То есть проблема как раз в том, чтобы верно оценить свой код. Гугл не сделает за тебя код-ревью и не скажет тебе «эй, братишь, у тебя тут плохой алгоритм, погугли-ка лучший».

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

тебе лучше не проводить интервью...

Если бы мы набирали в обычную галеру, где все, что нужно делать — вовремя заводить блокеры на индусов, то вы были бы правы.

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

Как бы тебе так сказать, чтоб ты понял...
То, что в твоем понимании сраный мердж сорт это какой-то хитрозадроченый алгоритм и является каким-то специфическим знанием а-ля «что делает вот та малоизвестная аннотация?» это лишь твоя личная особенность. В реальности же знание мердж сорта это по сути завуалированый вопрос «а читал ли ты хотя бы пару первых глав любой книги по алгоритмам?». Конкретно мердж сорт это настолько базовая, наглядная и затасканная тема, что человеку, которы указывает в своем CV «алгоритмы» не знать ее просто стыдно. И твой комментарий характеризует в первую очередь тебя.
Так что могу ответить в твоем стиле — тебе лучше не приходить на интервью. А то мало ли какие бессмысленные и беспощадные вопросы тебя ждут. Попросят, например, про цикл «for» рассказать или про оператор «if» — и нанесут непоправимый психологический урон.

В реальности же знание мердж сорта это по сути завуалированый вопрос "а читал ли ты хотя бы пару первых глав любой книги по алгоритмам?«

это можно спросить прямо и это будет более релевантный ответ, чем твои домыслы на основании ответа на намек

Конкретно мердж сорт это настолько базовая, наглядная и затасканная тема, что человеку, которы указывает в своем CV «алгоритмы» не знать ее просто стыдно

ты только подтверждаешь мои слова, правильный ответ на этот вопрос не дает тебе никакой информации о кандидате, ровно как и неправильный ответ, потому что всякое бывает

И твой комментарий характеризует в первую очередь тебя.

спасибо мамкиному психологу за анализ

Так что могу ответить в твоем стиле — тебе лучше не приходить на интервью. А то мало ли какие бессмысленные и беспощадные вопросы тебя ждут. Попросят, например, про цикл «for» рассказать или про оператор «if» — и нанесут непоправимый психологический урон.

это не в моем стиле, у меня не получаться писать так жалко :) и у меня нет проблем с собеседованиями, да и неопытный интервьювер это чуть ли не гарантия получить в его фидбеке максимум, даже по тем областям где я ничего не знаю, типа фронтенда, все из-за того что неопытные задают вопросы, ответы на которые ничего не скажут им обо мне, а отвечу я точно правильно так уж получается что неопытные, на то и неопытные что спрашивают одно и тоже и считают что они нашли в интернете уникальные вопросы, которые больше никто не задает

1. Так, приходиш ти на інтервю в гугл, і тебе там питають прямо:
вони: про алгоритми читав?
ти: читав!
вони: вітаєм ви прийняті!
:)))))

2.

ты только подтверждаешь мои слова, правильный ответ на этот вопрос не дает тебе никакой информации о кандидате, ровно как и неправильный ответ, потому что всякое бывает

Він дає чіткий результат — рівень знання і розуміння базових принципів програмування.

а отвечу я точно правильно

Ага, а якщо інтервюер не погодиться і захоче почути іншу відповідь — головне настоювати на своєму за будь-яку ціну, бажано відразу переходити на особистості і давити авторитетом :)

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

Я вот другого не пойму. Где сакраментальное «да ты просто самоутверждаешься на их фоне»? Давай уже, напиши это, тебе же хочется.

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

самый странный способ сказать что ты не согласен с моей оценкой твоих навыков проведения интервью

Я уж как пять лет собеседую людей, причем, в основном к себе на проекты и как-то так получается, что набранные мной люди в подавляющем большинстве отлично подходят на вакансии. От джунов до архитектов.

это небольшое достижение, в этом нет отличия от обычной галеры

Я вот другого не пойму. Где сакраментальное «да ты просто самоутверждаешься на их фоне»? Давай уже, напиши это, тебе же хочется.

я такого даже не думал, это тоже самое что самоутверждаться вопросам типа «какое число я загадал?»

это небольшое достижение

Это в принципе не достижение, это лишь факт опровергающий ваш «диагноз по аватарке».

Не знаю в курсе ты или нет, но это «ошибка выжившего» судить одной группе, не имея никакой инфы про вторую

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

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

_Возможно_, были бы лучше. И выяснить это можно только проведя исследования с фокус группами, на что ВНЕЗАПНО как-то не было времени и ресурсов. Но я рад, что ваш изначальный хамский безапелляционный апломб к концу рабочего дня как-то сдулся к «возможно».

Можливо, що результати таких досліджень навіть є в лідерах ринку(гугл, амазон і тд), можливо через те — в них скрінінг починається з алгоритмів, а не розпитування якими інструментами кандидат користувався.

а как можно утверждать то что неизвестно? известно только лишь что твое собеседование это подбрасывание монетки

известно только лишь что твое собеседование это подбрасывание монетки

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

их мантра — лучше случайно отсеять крутого чувака, чем нанять слабака. Ну они могут себе позволить.

лучше случайно отсеять крутого чувака, чем нанять того кто не знает на память мерж сорт

Мерж сорт на співбесіді в амазон чи гугл ніхто не питає. Там з ходу LRU кеш або регексп матчінг самописний.

+ яке визначення «крутий чувак»? Якщо це самовпевнений піжон з розміром его яке не дозволяє йому визнавати очевидні помилки, при тому не маючи базових знань — то його тоді треба відсіювати не випадково, а спеціально.

Мы с Алексом друг друга поняли, давать определения мне как-то вломы :)

Та всі знают шо ви з Алесом перші парубки на форумі :)

хочешь в клуб?) тебе до нас еще 5к комментов

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

Здесь согласен, но мерж сортом об этом не узнать

Вадім, алгоритми і структури данних на пямять знати не потрібно, потрібно розуміти їх принципи, для чого вони використовуються.
Також з твоїм висновком

эта инфа бесполезная

не погоджуються практично всі софтверні гіганти і лідери індустрії, такі як google, facebook, amazon, microsoft, oracle etc. Навіть більше скажу — більшість софтверних компаній на посаду інженера задають задачки, часто на дошці — якщо пощастило то на якомусь сервісі де їх можна заранити.
Це робиться не для того щоб безцільно потратити час інтервюєрів на беззмістову інформацію — це перевірка базових навиків програмування, і ця інфа не тільки корисна — вона в деяких випадках є необхідною.

Тобто алгоритм сортування — це не є необхідність — вони майже всі вже імплементовані. Необхідно знати самі принципи оцінки складності алгоритмів (а їх не так і багато — все зводиться до базових всього 7 штук) а незнання такого простого кейсу як мерджсорт — просто каже про те що знань в цьому напрямку просто нема.
Саме тому компанії задають задачки на алгоритми — вони просто таким чином міряють твої базові знання в алгоритмах і компютерних науках в принципі, а не переконуються що ти знаєш на память якийсь алгоритм.

ПС. Дивно пояснювати це .Net архітекту :)

Так посыл Вадима был в том, что этот вопрос проверяет частный случай — знание одного из видов сортировки, причём именно реализацию, а не big-O, устойчива она или нет.

Никак не показывает умеет ли человек думать и из простых алгоритмов и структур собирать более сложные.

Даже в статье сказано (с чем я согласен):

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

Лол, ну я же не спрашивал человека «процитируй-ка мне дословно первых 20 предложений из главы Кормена посвященных мердж сорту». По сути давал две несложных задачи:
1. Напиши алгоритм, который на вход принимает два упорядоченных массива, а на выходе дает упорядоченный массив, который содержит в себе элементы первых двух.
2. А теперь с помощью описанного тобой метода придумай как упорядочить неупорядоченный массив.

И, например, разраб упомянутый в моем первом комментарии решил первую задачу перебором, при этом у него не было даже намека на размышления «а может можно лучше?». Как вы думаете, это совсем бесполезная информация и никак не показывает, умеет ли человек думать или все же нет?)

Скажите, а на вашем проекте, или в вашей компании на практике применяется сортировка слиянием? С ней потенциальные кандидаты будут работать?

Вы совершенно зря воспринимаете сортировку слиянием как специфический дедикейтед алгоритм. Мердж сорт построен на двух принципах.
1. Слияние двух упорядоченных массивов в третий упорядоченный имеет линейную сложность.
2. Рекурсивное разбиение набора данных.

Оба этих принципа крайне полезно keep in mind, когда работаешь с условной бигдатой. Так что с самой сортировкой скорее всего нет, с ее составляющими — скорее всего да.

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

Вообще, подход «спрашивать ровно то, чем человек будет заниматься на работе», конечно же, имеет право на существование, но не всегда применим.
Как по мне, соискателя можно спрашивать об относительно отвлеченных задачах, просто чтобы посмотреть как человек будет вести себя в нетривиальной ситуации. На самом деле даже задачи типа «сколько теннисных шариков помещается в Боинг?» они не так уж плохи, если понимать их смысл. Правда, я не рискую такое спрашивать, так как опасаюсь, что вгоню в ступор соискателя. Такие задачи надо еще правильно уметь подавать.

Оба этих принципа крайне полезно keep in mind, когда работаешь с условной бигдатой.

да, идеальное собеседование обязано выявить автоматизм принятия решений программистом, который соответствует предметной области
именно автоматизм, keep in mind, — и есть показатель опыта. а не формальные 3+ лет

в том и некоторая бессмысленность споров о задачках на собеседованиях.
и сатира о несоответствии задачек:
на собеседовании спрашивали о балансировке красно-черных деревьев, а на работе *бусь с конфигами докера

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

веб студия пилящая лендинги на вордпрессе гуглит в интернете список вопросов для программиста условной бигдаты и задает эти вопросы соискателю

— конечно, бредовая ситуация. Вместе с тем, вы допускаете, что есть компании (и это далеко не только не FAANG), которые ищут в первую очередь человека с мышлением инженера и умеющего решать нестандартные задачи? И не потому, что карго-культ, а потому, что у них такие задачи действительно есть?

конечно допускаю. «Пять миров» Спольски никто не отменял
а их уже думаю и больше.
Как вот недавно в несколько однотипных холиваров встрял — коллеги с других областей программирования не врубаются, почему это красиво по книжке на практике не получается выделить абстрактный слой работы с персистентным хранилищем.

с мышлением инженера и умеющего решать нестандартные задачи?

ну, эт дефицитище.
даже просто с программерским мышлением — то есть «ленью», чувством кода, абстракций, да просто — с ясным мышлением — поискать еще нужно.

Но, кстати, мышление инженера — практичное.
А не математическое :)
А задачки часто на — математический уклон.
Конечно одно другое не отменяет.
Но автоматические подходы, навыки — разные.

И не потому, что карго-культ,

думаю в большинстве случаев — именно карго культ.

Ну смотрите, можно ли сказать нечто критичное в адрес математики? это же прозвучит как кощунство, толпы сразу предадут анафеме — не вникая в суть замечания.

Тоже с вопросом в топике.

Мое сугубое мнение
Алгоритмы и структуры данных — наверное единственная из компьютерных наук вещь, о которой хотя бы любопытствовать, и регулярно, все годы работы — должен «самый распоследний ремесленник с фриланс биржи починяющий опенкарт»

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

Є в цьому щось, але мерджсорт — це базовий алгоритм. Нерозуміння того як він працює каже тількт про одне — кандидат в принципі по алгоритмах незнає практично нічого. Тому порівняння специфічних запитань по якійсь технології і запитання на знання мерджсорта — не зовсім коректне :)

Є в цьому щось, але мерджсорт — це базовий алгоритм. Нерозуміння того як він працює каже тількт про одне — кандидат в принципі по алгоритмах незнає практично нічого

якщо вам каже — то не беріть такого кандидата на роботу, та й все :)

мені це нічого не каже, бо, хех, пішов дивитись вікіпедію. бо всі ці базові алгоритми давно випали з голови.
звісно, і мене тому не беріть на роботу. :)

мені інколи загальні висновкі по мерджсорт нагадають ветеринара якому довелося лікувати людей:
він починав з догляду зубів.

він починав з догляду зубів.

И правильно делал)

— доктор, а вы точно гинеколог?

Сергій, на проектах де я зараз працюю — знання алгоритмів є бажаним але не вирішальним. В нас треба вміти розвязати дуже просту задачку, бажано TDD методом, якщо ні — то покрити тестами. + Знання технологій які ми використовуєм.
Але, на гугл, ібей чи амазон вас без алгоритів і вміння розвязувати задачки не візьмуть, хоча далеко не факт що ви будете використовувати їх в повсякденній роботі.

Сергій, на проектах де я зараз працюю — знання алгоритмів є бажаним але не вирішальним.

на кожному проекті де я не бував та ж сама історія
найбільш мав потребу у знанні а. та с.д. — коли був у геймдеві.

звісно є гугли, амазони, яким треба відсіювати купу кандидатів.
бо в них вакансій набагато менше чим навала кандидатів.

я б так само вчинив.
а якщо всі добре знаються на алгоритмах, то додав би щось з теоркату та з машинного навчання.

Насправді ні — в них теж є проблема найму! Недавно був на мітапі в амазоні — то вони рекомендують практикувати задачки легкого і середнього рівня. А необхідність алгоритмів вони пояснювали задачами які вони виконують, на прикладах. Один з прикладів — розробка системи яка моніторить статус виконання черги замовлень на складах, з можливістю автоматично регулювати подачу замовлень на різні рівні, щоб часом не переповнити склад товаром :)

ну, якось на співбесіді мені дали подібне завдання.
я його зробив, за хвилин 15.

на що отримав — так, ваше рішення набагато загальніше чим потрібно, для цілого класу подібних задач, а тому не саме ефективне у рантаймі...
та отримав офер
бо то був не амазон.

ніяких алгоритмів я не використовував, просто «здоровий глузд» та досвід. і вони розуміли те ж саме що й я, і що просто цитую:

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

Иногда итоговое решение справляется с проблемой довольно хорошо, иногда вообще не работает, а в большинстве случаев «вроде как» решает проблему. При последнем варианте мы полируем решение до того состояния, чтобы оно справлялось с проблемой «довольно хорошо».

цитата з «Что вам не говорят о сфере разработки?»

і звісно, що у тих об’ємах які треба амазону, такє практичне рішення, загальне та надійне, але з поганенькою ефективністю коштуватиме чималі гроші. і треба більш вдале, якє, може статится я й за пару днів не придумав би

P.S.
цікаво що той програміст що дав мені те завдання та прийняв, вважався у компанії самим суворим до кандидатів.
та... через два рокі поїхав до Америки. та пройшовши співбесіди отримав роботу у тому самому Амазоні :)

Я за всю свою карьеру только однажды применил устойчивую сортировку в явном виде, и раз 5, наверно — просто сортировку. Учебные задачи, естественно, не в счёт. Зато всякие map/heap — в разы чаще.
Следует ли из этого вывод, что mergesort нужен только для экзамена?

По суті так — для екзамену на перевірку розуміння що таке divide and conquer алгоритм, рекурсія, вміння оцінити складність etc.
Ясно що на роботі ніхто не пише мерджсорт для продакшона :)

Ну вот в первом пункте задача вполне норм, но ожидать что человек сделает это исключительно через merge-sort лично мне кажется странно.

Мне сразу приходит на ум решение через 2 указателя, каждый на свой список, на каждой итерации сравниваем 2 числа из списка, меньшее добавляем в 3-й и сдвигаем указатель (если числа равны, то оба добавляем и сдвигаем 2 указателя).
Худшая сложность по идее O(n+m) для списков типа 1,3,5,7 и 0,2,4,8
По идее такой алгоритм должен работать норм, или если не merge sort, как ожидает спрашивающий то сразу fail?

Про мерже сорт и не подумал бы, но я ж в фаанги и не претендую.

Так вы по сути и описали классическую реализацию merge части алгоритма, лол.

или если не merge sort, как ожидает спрашивающий то сразу fail?

Я не понимаю, почему вы _мне_ задаете этот вопрос. Это правдоруб Vadim Kopanev приписал мне подобный подход. =)
Да пусть человек придумает какую-то реализацию, которая будет, допустим, по space, например, несколько хуже классической — без проблем, уже видно, что человек думает над задачей, пытается ее решить, критически относится к своей работе. А вот описанный мной случай — решение перебором за N^2 без тени сомнений — это красный флаг.

Так вы по сути и описали классическую реализацию merge части алгоритма

ну так вот и поставленная первая задача значит хорошая, когда даже не зная канонического алгоритма, можно самому прийти к решению.

Это один из вариантов шага merge в mergesort внезапно

И, что это говорит о кандидате?
Задачу решил, но не сказал что это частный случай merge sort’а — fail?

Ну на втором вопросе Сергея

2. А теперь с помощью описанного тобой метода придумай как упорядочить неупорядоченный массив.

я бы конечно слился и сказал — объеденить массивы и вызвать уже готовую сортировку.
Что-что, ну я понимаю написать бинарный поиск, крутить деревья, видеть где сразу стоит стек использовать или heap.

Но задрачивать реализации нескольких видов сортировок (не их характеристики и какие-то особенности типа если в память данные не влазят и т.д.) стал бы только действительно для фаангов или другой работы мечты. Притом что тема мне интересна в отличии от крудов.

Шаг 2. Делим рекурсивно неупорядоченный массив пополам аж до тривиальных случаев и применяем к кусочкам решение из шага 1. Профит.

Не, вот про эту часть не зная заранее, уже мало кто догадается.
Так то можно надеяться что на собес рано или поздно прийдёт Джон фон Нейман (автор merge sort’а), а остальных отсеивать.

Не, вот про эту часть не зная заранее, уже мало кто догадается.

Та не, многие отвечали. Принцип рекурсивного разбиения набора данных он достаточно распространенный и тривиальный. Мердж сорт потому и зачастую описывают в самом начале курсов/книг по алго, что она состоит из двух компонентов, которые широко используются и за пределами сортировок. Как по мне сами эти компоненты куда важнее сортировки как таковой.

Не, вот про эту часть не зная заранее, уже мало кто догадается.

Не соглашусь, невозможно пройти мимо divide-and-conquer, открыв хотя-бы одну книгу по алгоритмам.

Хм, ok, почти убедили )
В задачах на leetcode применял divide-and-conquer, но в данном случае ещё и рекурсивно, не щёлкнуло.

Если реально приходят на собесы в укр.конторы кандидаты, которые до такого с ходу додумываются, а не просто перебирают в уме реализации сортировок пока не встретится что-то похожее, тогда респект им.

решил первую задачу перебором

А можно подробностей? Я плохо понимаю, куда тут вообще для этой задачи воткнуть перебор :)

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

Спасибо, жуть :(

у 1С как-то было

их табличный вывод начинал дико тормозить что-то там после 10 тыс строк

стало общим местом на форумах 1Сников
но пофиксали только тогда (может просто совпало) когда на 1Сных форумах появился дизасемблированный код
по которому видно что там O(2^n)

вот и думай после этого, о кадровой политике, качестве разработки и — успехе продукта на рынке

видно что там O(2^n)

Наверно, таки O(n^2)?
Иначе
1) непонятно, как это могло доработать хотя бы до 100 строк
2) если там реально что-то типа O(2^(n/1000)), то всё равно интересно, как такое было написано — в копилку ужасов

Наверно, таки O(n^2)?

точно уже не помню конечно, но точно, что «долго ждать» после какого-то числа строк, довольно быстро превращалось в — «можно и не ждать уже» :) Хорошо хоть задачу не надо было снимать, ESC отрабатывал.
Погуглил даже, но это было где-то в версиях 2005 ±, глубоко уже в форумах, не нашел...

потому и «защищаю невежество», что из бизнес ПО — в копилку ужасов ложить не переложить

поэтому версии, как обычно такое случается, как часто встречал в коде, и да, сам подобные ужасы делал, причем часто зная, что рассказывать никому об этом в программерской тусовке низя :)

непонятно, как это могло доработать хотя бы до 100 строк ... интересно, как такое было написано

1. а пользователь обычно не замечает, ведь он сначала видит «первую сотню». «пока начнет скролить — все остальное выведется!»
2. «да кто в своем уме будет делать отчет на тысячи строк»
3. делаем «буфер», ну... с потолка на тыщу строк! ну а потом динамически будем его дополнять, если кому больше надо
4. сделали вывод, прошло время, надо и функцию СУММ, для «Итого:». Ой, модели нет, строки прибиты гвоздями к объектам UI... эм, тогда, О, все просто — вывели строку, пересчитали СУММ, вывели еще одну, пересчитали... Почему не в конце? ну потому что могут же Итого и вначале отчета поставить, а отследить окончание вывода... ой, там в недрах либы отловить окончание вывода надо, а он может завершиться в трех случаях, ..., а когда вывод закончен, к объектам UI не добраться...
5. Надо добавить вычисляемые ячейки, делово то! добавили. В итоге — см п4 СУММ пробегается каждый раз по столбцу, а там ячейки с формулами, пересчитываем каждую, потому что объект UI не хранит результат...
А отчеты где нет тяких ячеек, вполне себе на «паре тысяч» строк терпимо работают

так и SELECT N+1 появляются. Особенно когда все так правильно, по книжке, в «Rich domain model» спроектировано

их табличный вывод начинал дико тормозить что-то там после 10 тыс строк

Ну так))
Свой excel написать могут не только лишь не все)))
М$ до ума эту тему доводил десятилетиями...

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

Просто треба купити потіжніший компютер і не нити! Що дешевше? Тобі купити компютер чи 1С найняти розробника?

Звичайно що неможливо знати все, але я коли проводжу співбесіду — в мене не стоїть задача «загнати» кандидата а стоїть задача визначити:
1. що він знає і вміє
2. де його знання і вміння закінчуються
3. чи перспективний кандидат
4. чи вміє спілкуватись
5. який його підхід до вирішення задач

Відповідно, наприклад, в питаннях по реляційних базах данних, я починаю з запитань про джоіни, якщо людина незнає як працюють джоіни — то скоріш за все питати її про групування, особливості використанні індексів і реплікацію — змісту нема. Тобто підхід переходити від простого до складнішого, і там де кандидат починає «плавати» — зупинятись.

Так само алгоритми — запитання починаються з сортування і простого бінарного пошуку, якщо кандидат не може зробити це — то про яку більш складну комбінацію алгоритмів можна говорити? Який зміст давати задачку на A* search алгоритм чи на побудову LRU кешу? Щоб що? Довести кандидату що він чогось незнає?

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

Но как связаны реализации сортировок с A* search’ем или LRU кешем? )

Это хоть интересные алгоритмы, и как примерно работает, человек интрересующийся темой скорее всего представляет. А над реализацией lru-кеш’а можно поговорить, даже если он ранее не слышал он нём, но знает структуры данных.

Я вообще не спорю что знание алгоритмов это хорошо, сам порешиваю leetcode и читаю периодически всякое. Но никогда не возникало желания разбираться что внутри той или иной сортировки, как-то всё это всегда скипал, из-за того что это абсолютно везде реализовано и даже кастомайзить необходимости нет. Просто знаешь что O(n logn) и можно ли заменить кодом быстрее и желательно in place.

В общем, мы говорим об одном и том-же, просто у меня подгорело исключительно из-за необходимости знать как работают внутри сортировки, так это для меня просто не интересно было, в отличии от других алгоритмов )

Тому що алгоритми сортування — це якби те з чого починають вивчати алгоритми :)

Я их реализации осознанно пропустил, всякие path finding алгоритмы интереснее )

Ладно, нужно подтянуть знания, а то мало ли, ещё трактор заводить в свете последних событий )

можна будь ласка приклад того, що означає пасаж «де знання закінчуються»? знань повний інтернет, вони не можуть закінчитись, дві сторінки прочитав — і вже знаєш що три хвилини тому не знав. звичайно за наявності інтелекту та підготовки. але перевіряти їх наявність питаючи про сортування злиттям... це, вибачте мою французьку, трішки по-дебільному©

Звичайно можна — наприклад той же MySQL — припустим кандидат вміє робити запити, джоіни, групування і тд, а от про індекси знає поверхнево — знає що індеси є і що їх треба, що індекси сповілюнюють вставку і зміни але пришвидшують вибірку, але не знає як використовувати комбіновані індекси, не знає що на мастер-слейв реплікації можна мати різний набір індексів і тд. Тобто на данний момент — тут закінчуються знання кандидата в даний період часу. Звичайно можна це все підівчити, не за три хвилини звичайно, але при бажанні досить швидко. Тому існує ще оцінка «перспективності» кандитата (но це знов таки окрема тема).

І звичайно знанням мержсорту ніхто не перевіряє перспективність, чи «де закінчуються знання» як такі. Де ти бачив щоб це було написано в пості на який ти відповів?

Запитання про мерджсорт чи вміння користуватись бінарним пошуком — виконує одну чітку функцію — визначити чи кандитат в принципі дивився в сторону алгоритмів. На інші фактори це не впливає.

я плавно підводжу до того, що найбільш вагомою характеристиками кандидата є наявність інтелекту та вміння/бажання швидко вчитися. а «де його знання закінчуються» в даний конкретний момент часу особливого значення не має.
зазвичай недоцільно навічно тримати в голові деталі алгоритмів, достатньо (на мою думку) розуміти складність та типові випадки застосування, наприклад щодо сортувань (знову-таки на мою думку) достатньо пам`ятати, що типова складність n log n, і що якщо априорі про невпорядкованість нічого невідомо, то доцільно почати з швидкого сортування, яке майже завжди реалізоване в функціі типу «sort» (чи щось схоже) в твоїй робочій мові. все.

И как вы предлагаете определять на интервью умение и желание быстро учится?

нєнє, гражданін. для тебя — только после «отдельной статьи» :D

Когда интервьюер «взрослеет» он начинает понимать что исключительно техническое интервью хорошо работает на джунах и средне на мидлах, а после этого оно не показывает ничего ровным счётом, ну и каждый находит свой способ проводить полезное интервью.... или не находит и собеседует всех как джунов, по факту являясь просто случайным фактором для найма

Вадім, коли інтервюер дорослішає — то він розуміє що бувають кандидати які посильніше нього, розуміє що його модель розуміння світу може бути не остаточно правильно і він відкритий до нових знань і фактів, які скорегують цю модель :)

А безальтернативні заперечення цілком очевидних аргументів і фактів — це явно не ознака дорослішання інтервюера ;)

Вадім, коли інтервюер дорослішає — то він розуміє що бувають кандидати які посильніше нього, розуміє що його модель розуміння світу може бути не остаточно правильно і він відкритий до нових знань і фактів, які скорегують цю модель :)

А безальтернативні заперечення цілком очевидних аргументів і фактів — це явно не ознака дорослішання інтервюера ;)

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

А там і не планувалось протиріччя :)

Ок, а мені без статті можна відповісти як ти виявляєш наявність інтелекту, вміння та бажання швидко вчитись? А то «трішки по-дебільному©» виходить :) - я свій алгоритм описав — ти його розкритикував, але альтернативу тримаєш в секреті. Я весь увага і готовий вчитись в маестро!

ПС. Ну і навіть дуже перспективний і розумний кандидат не факт що реалізує свій потенціал, + як може не мати значення де закінчуються знання кандидата? От наймаю я мідла-сінйора на навантажений веб сервіс, а кандидат перспективний джун, наприклад, з деякими поняттями в якомусь фреймворку, практично без знань SQL — бо він користується ORM, базовими знаннями в JS і дуже початковими знаннями як працює вебсервер. То по твому як? Треба його брати бо він розумний? А решту довчить «по дорозі»? Якраз точку де закінчуються знання кандидати в окремих топіках треба міряти щоб розуміти що він може а чого ні в данний момент, бо тобі треба працівника вже, і не для того щоб він місяці вчився на проекті, а для того щоб працював.
А для розумних і перспективних — є компанії з трейнінг центрами.

До речі — ти в себе в лінкедіні пишеш що не проти релокейтнутись — так от, знання алгоритмів сильно збільшить шанси, я тренуюсь отут leetcode ;) І так я коли працював в Україні — мене ніколи ніхто не питав про алгоритми при прийомі на роботу, але коли довелось шукати роботу в США — майже всі топ компанії ставлять знання алгоритмів як метод відсіювання кандидатів на телефонному скрінінгу, а сортування це один з найпростіших кейсів. Тому рекомендую не доводити мені що цього нікому не потрібно а просто розібратись.

сарказм щодо маестри дещо недоречний, оскільки я ніде не писав, що спеціалізуюся на підборі персоналу, і не критикував алгоритм, а вказав на недосконалість одного з пунктів. «трішки по-дебільному» стосувалося іншого пацієнта, шо пишається сортуванням на співбесідах ;)

на жаль срібної кулі не існує. на мою думку найкращі результати можна було б отримати, організувавши кандидату пробну роботу на тиждень, в бою було б видно як швидко кандидат підхоплює те, що раніше не робив. на жаль, не у всіх проектах це можливо, але майже у всіх проектах є можливість посадити його на допоміжні задачі (якась автоматизація процесів, скажімо), не показуючи секретний проект і не лякаючи передчасно внутрішньою індусятиною. також і кандидату корисно було б побачити команду в роботі і оцінити розмір чсв «архітектора».

щодо інтелекту, то про нього можна робити якісь висновки за непрямими спостереженнями. наприклад, якщо кандидат пише з помилками, то це вказує на те, що він мало читав/читає, відповідно і рівень інтелекту страждає. є і інші показники, але мені ліньки про них писати, це більше предмет управлінських наук.

фундаментальна проблема українського аутсорсу полягає в тому, що компанії шукають повністю готових робітників, які з першої години почнуть веслати на повну потужність, тобто практикують чисто тактичний підхід без стратегії. в той час узагальнений фейсбук у вимогах зазвичай пише три вимоги типу «бакалавр, досвід від року, знання любої ОО мови», і все. люди мислять стратегічно.

Саме так, в фейсбуках, гуглах і амазонах — інструменти якими ти користувався значення не мають. Вони навіть language agnostic по відношенню до кандидатів.
Але, на співбесіді вони фокусуються якраз на алгоритмах :) - це і є їх спосіб міряти перспективність і потенціал кандидатів.

щодо інтелекту, то про нього можна робити якісь висновки за непрямими спостереженнями. наприклад, якщо кандидат пише з помилками, то це вказує на те, що він мало читав/читає, відповідно і рівень інтелекту страждає.

Тобто якщо перетворити написане в стратегію співбесіди, то вона має виглядати так:

1. Кандидат заходить на співбесіду.
2. Юрій дає йому маркер, і запрошує до дошки.
3. Юрій каже — а зараз, будем писати диктант!

це ідеальний варіант:)!

щодо інтелекту, то про нього можна робити якісь висновки за непрямими спостереженнями. наприклад, якщо кандидат пише з помилками, то це вказує на те, що він мало читав/читає, відповідно і рівень інтелекту страждає

это очень грубое наблюдение, я постоянно печатаю с ошибками, но не потому что не знаю как правильно писать, а потому что жму не туда, отвлекаюсь и редко перечитываю что написал

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

грубое канешно, там жэж и написано «делать какие-то выводы», а не «принимать окончательные решения» ;). опечатки от ошибок легко отличаются, случайно ведь не напишешь что-то типа «поедите ли Вы на корпоратив с Житомира, что скажите? От куда Вас заберать?»

Та легко, я не особо быстро печатаю, и когда мысль уже на 3м предложении, руки все ещё пишут первое, потом поднимаю глаза на экран и вижу «здись», вместо «здесь», так же ошибиться даже нельзя, просто сформировалась неправильная мышечная память, которая судя по всему основана на частоиспольемых сочетаниях букв

Ну от ти — пишеш речення, починаючи з маленької літери постійно, замість «що» — «шо», є купка пунктуаційних помилок.
Які можна з цього зробити висновки? :)

Незнаю, тому й питаю в того, хто такі висновки пропонує робити :)

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

И что выходит — я должен поверить на слово, что такой вот чувак не учился, не учился, а тут на нашей работе ВНЕЗАПНО резко начнет учится?)

это оценить уже текущие знания.

причем которые — рядом с основной работой.
ну типа — соискатель строго на бекенд
и где-то в собеседовании вопрос, причем с расслабляющим контекстом — а давайте «ни ап чем» немного — смотрели что-то с фронтенда?
— ну, ковырял я как-то ангуляр...
— и, как впечатления?
— да знаете... как-то у них там понаворочено/круто, вот эта штука ... как по мне какая-то мутная/крутая. но недолго пробовал, не уверен

и опа, вот она мелочь то, программист любознательный. полез не в свою область

«вайтишники» поэтому вызывают очень грустные чувства
эта их натужность с которой окончили курсы и мольба в глазах — ну дайте мне ящики которые нужно грузить! буду грузить!

а ты себе думаешь, да были б ящики, дал бы. но у нас не ящики... у нас не наука великая конечно, но все равно — думать надо...

Жаль что только один лайк поставить можно.
Сам несколько раз сталкивался с таким — причем в моем случае «пацанчики» уже были за тридцать годков.

Ннууу... бабло таки хороший мотиватор...

Я ему дал задание набросать на листочке merge sort

А нанимали джуна на то чтобы круд к апи написать? :)

Нет, нанимали мидла на проект с обработкой больших объемов данных :/

И в обязанности этого мидла реально входило написание мерж сортов? Постоянное? Вот приходит человек на работу и изо дня в день пишет сортировки и обходы бинарных деревьев?

В обязанности этого миддла входило написание MapReduce джоб, например. Но если бы я просил:
— на интервью;
— в 2к15;
— в Украине;
— писать мапредьюс джобы,
мы бы точно никого не наняли.
Потому мы в требованиях не указывали даже опыт Хадупа. Всему модному в тот момент бигдато стеку мы обучали сами, а базовые знания алгоритмов мы посчитали необходимыми, так как нам было важно, чтобы разработчик сам мог оценивать, насколько производительный код он написал.

базовые знания алгоритмов мы посчитали необходимыми

Наши взгляды конечно могут различаться, но базовые знания алгоритмов != мержсорт на листочке.
1) мало кто сидит и пишет днями мержсорты
2) даже если помнишь основную идею мержсорта, написать сходу алгоритм не так просто, тем более на листочке, тем более на интервью.

Имхо, базовые знания алгоритмов можно проверить вопросами об О-нотации и откуда возникает O(n2), откуда возникает O(nlogn), какими-то общими вопросами о сортировках и т.д. Эти вопросы достаточно вскрывают наличие/отсутствие алгоритмического понимания без необходимости вбивать человека в ступор написанием мержсортов на листочке.

См. выше мой ответ Valeriy Shvets

Мердж сорт один з найлегших алгоритмів. По рівню складності десь на рівні " реалізуйте бінарне дерево пошуку". Ти можеш не пам’ятати деталей, ок, скажи ідею, якшо ти Мідл ти з ідеї напишеш сам. Ніколи не писав мердж сорт не знаєш ідеї ? ( Важко в це повірити якшо ти вивчав алгоритми), окей, скажи що ти мердж не знаєш, запропонуй інше сортування з такою ж складністю. Я не дуже розумію що тоді вкладається в базові знання алгоритмів, якшо туди не влазять прості сортування?

Имхо, базовые знания алгоритмов можно проверить вопросами об О-нотации и откуда возникает O(n2), откуда возникает O(nlogn)

Плюсую!
Случай почти из моей практики — пришлось мне в начале карьеры работать с самописанным клоном STL (надо было, чтоб код и под легаси компиляторы шел). В этом клоне был реализован примитивный quicksort, который вызвал stackoverflow.
Так вот поскольку я помнил общие принципы алгоритмов сортировки (а деталей не помнил), я с ходу понял, откуда stackoverflow берется и довольно быстро заменил этот quicksort heapsort’ом.

Я поставил лайк, но считаю, что проверка быстрым тестом (типа лёгкого алгоритма) на глазах на ходу имеет смысл, в рамках такого интервью — и тогда merge как база такого теста — очень удобный вариант.

Как вариант «поговорить о мержсорте» — да.
Я против самой идеи написания алгоритмов, вне зависимости от алгоритма, на листочке, потому что считаю, что это мощный стресс-фактор на собеседовании.

Так листочек используется исключительно как вспомогательный инструмент для визуализации. Заставлять писать любой код на листочке/доске — так себе тема, такое только фаанги могут себе позволить.

А, ок, тогда понятно.
Я думал вы именно вот прямо код валить от руки на листе просили )

меня самого всегда вгоняло в стресс написание кода на бумажке на интервью. и хоть в итоге я себя приучил к этому, все же не чувствую никакого морального права требовать такое от других))

Ну это тоже спорный вопрос :)
Многие считают, что важно проверить и такой режим со стрессом, а некоторые — что это даже обязательно. Я поддерживаю в «лёгкой» форме — что умение работать в таких условиях это заметный плюс, хоть и не абсолютный.

Имхо, базовые знания алгоритмов можно проверить вопросами об О-нотации и откуда возникает O(n2), откуда возникает O(nlogn)

А разве написать многострадальный мержсорт псевдокодом на бумажке не проще, чем нормально объяснять своими словами без визуализации откуда там n*log(n) взялось?

Не проще. Объяснить можно и каракулями, а код надо вылизывать на кучу мелких огрехов типа off-by-one.

что для вас «фундаментальные знания»?

вы определение спрашиваете или перечислить?)

перечислить. пожалуйста :)

это тема для отдельной статьи)

но ведь такой опытный специалист по проведению техинтервью незамедлительно её напишет и даст почитать, да?

опытный специалист не входит в состав вашей личной армии, так что нет

слив засчитан©

А также абсолютно всем советую ознакомиться с книгой «Алгоритмы. Построение и анализ» Томаса Кормена. В ней подробно описаны большинство популярных алгоритмов. К тому же, книга написана понятным языком и легко читается, как в оригинале, так и в переводе.

Лучше начать с вот этой книги www.amazon.com/...​even-Skiena/dp/1849967202, а к Кормену/Кнуту/... обращаться «точечно» — когда нужно поглубже разорабраться в какой-то конкретной теме. Skiena пишет дружелюбнее и проще, много интересных практических war stories, вторая половина книги вообще специально написана в формате референс мануала по основным алгоритмическим проблемам/алгоритмам. Незаслуженно обделена вниманием в рунете, имхо.

Microsoft, Google или Tesla не нужны «исполнители»

хммм... это, мягко говоря, преувеличено.

Конечно, но среди всего количества людей которое они нанимают будет большой процент исполнителей. И смысл в том, что целенаправлено искать их не имеет смысла.

А що саме ви розумієте під словами «виконавець»?
Бо в компанії працюють виключно виконавці волі ради директорів.

Це дуже умовне позначення. В цьому контексті мається на увазі, що виконавець — той, хто бере завдання та виконує його. А є розробники, які підходять і кажуть, що я хочу займатись і реалізувати певну ідею, та можуть довести чому це вигідно для команди або компанії. Наскільки я чув таким способом з’явились наприклад Google Maps, TypeScript, React, .Net Core і інші розробки.

То називайте перших інноваторами, «головою», креативниками, а других — «руками», ботами, пасивними. Так простіше розуміти, де хто.

@Denys , это инициативные люди. Faang ищет инициативных. понятно, что много программистов , которые знают алгоритмы , но очень мало тех, кто может придумать что-то крутое

Да, конечно. Смысл просто в том, что вряд-ли можно придумать что-то новое, не знаю существующих решений и подходов

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

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

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

ИМХО основная польза от ботания алгоритмов состоит в том, что мозг — штука крайне пластичная и, загружая его подобной деятельностью, человек формирует его таким образом, что решение подобных задач у него не вызывает когнитивного диссонанса. Главный вопрос же не в том, знает ли человек в деталях определённый алгоритм (который он никогда в жизни так и не иплементит в реальной задаче), а как у человека сформировано мышление, умеет ли он мыслить как инженер.

исполнителей они набирают с контрактников )) вот свежая инфа более половины работников гугла контрактники ))

Для L3 SWE тоже приемлемо быть хорошим, надежным исполнителем.

более половины работников гугла контрактники

тобто, ФОПи по-нашому?

Или сотрудники епама

Странные вопросы из серии:
А нужен ли всаднику вальтрап?
А нужна ли сапожнику лапка?

скорее: нужна ли всаднику лапка?
а, что, если он по субботам немножко шьет обувь?

забавно что сам автор похоже подсознательно считает что алгоритмы не нужны, «официально» подменяя знание алгоритмов проблемсолвингом

Поэтому собеседования в FAANG или MINT на 60%-100% состоят из Problem Solving задач, для решения большинства которых нужны знания алгоритмов.

а дальше приводит примеры типичных галерных решений

Типичный пример 1

хешуем не все подряд, а то что нужно

Типичный пример 2

пользуйтесь фреймворком

Задача 1

оч скудно описано «сча тупит, а если бы сегмент три, то не тупило бы»

Задача 2

условие задачи «нужен оптимальный алгоритм», да без алгоритма решить действительно нельзя :)

Задача 3

давно решена эта задача, велосипедить не надо и алгоритмы не нужны. а если нет возможности использовать готовое решение типа эластиксерча, то следует задать себе вопрос: «зачем я столько логирую (еще и в один файл), что потом черт ногу сломит?»

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

Подмена знаний алгоритмов на проблем солвинг действительно может помочь пройти интервью, но такой подход вряд ли поможет в реальной разработке.
В разделе

Использование алгоритмов в реальной разработке

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

С посылом статьи полностью согласен. А в примере с Ахо-Корасик... это как бы типичная задача для ELK-стэка?

Да, абсолютно верно. Я говорил что примеры немного упрощены и адаптированы для статьи. Конкретно в этом случае нужно было сделать что-то для оптимизации здесь и сейчас. А для нормального использования ЕLK нужно еще и подготовить соответствующую архитектуру.

Нужны ли программисту алгоритмы и структуры данных

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

Ой все :)

_______
|______|—
° ° ° °

Конечно нужны! Как ещё отличить тру программиста от вайтишника?

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

Тру — это не способ попасть в IT, это способ мышления и интерес к IT

некорректно сравнивать производительность с++ и питона. можно сравнивать либо разные алгоритмы, реализованные на одном языке, либо одинаковые алгоритмы на разных языках.

Я сравнивал то как было и как стало именно для проекта. Конечно всё ещё зависит от данных и условий для которых будет использоваться алгоритм. Но например вот сравнение другой имплементации, которая использует Ахо-Корасик внутри для NLP задач. И график ещё более внушительный medium.com/...​ata-analysis-960a0dc96c6a

На графике явно прослеживается разница между runtime complexities O(n) vs O(log(n)). Я думаю разница в межязыковых имплементациях проявится максимум на уровне runtime complexity констант, которыми можно пренебречь.

на графике выполнения питон-программы продолжительностью 0.5 секунды вообще ничего не прослеживается. ахо-корасик разумеется будет работать быстрее, но делать выводы об этом на основании представленного графика — профанация.

Смысл как раз в том, чтобы показать зависимость и разницу даже на небольших величинах. И разница между < 0.1s и почти 0.5s дает возможность это говорить о приросте. Хорошие performance testы различных методов поиска в тексте достоен отдельной статьи.

У вас оба графика линейные. Это ни о чем по сути. Вот если б у вас второй выходил на данном куске на логарифм или константу — тогда да.

Т.е. вы хотите сказать что имплементация алгоритма Ахо-Корасика на С++ и на Python могут дать принципиально разную runtime complexity?
0.5 секунд или 0.005 — какая разница, если ясно видна зависимость времени выполнения от размера входных данных.

мы хотим сказать, что приводить график в том виде, в котором он приведен, по меньшей мере глупо. во-первых разные языки, во-вторых разные алгоритмы, в-третьих пол-секунды максимального времени выполнения для интерпретатора неведомой версии на неведомой платформе. все выводы хорошие и правильные, но график лучше выпилить.

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

Возможно, я не умею читать графики, но я и там и там вижу линейную зависимость с разными коэффициентами. Так что в плане runtime complexity графики ниачом.

Соглашусь, что для однозначных выводов имеет смысл сделать больше измерений на разных объемах данных.
И еще добавлю, что не хватает информации о том, какие именно регексы использовались, так как регекс регексу рознь.

Строка в таблице с

Списки BFS/DFS Память (Stack vs Heap)

продублирована

Підписатись на коментарі