Comments 85
Мне кажется, важно упомянуть, что вставка в конец динамического массива — амортизированное О(1). И вообще упомянуть, что такое амортизированная сложность.
Сравнение поисков в ширину и в глубину
Выбирайте тип поиска в соответствии с размером и формой дерева.
Для широких, мелких деревьев используйте поиск в ширину.
Для глубоких, узких деревьев используйте поиск в глубину.
Почему?
Согласен с вопросом. Написана дичь. Способ обхода надо выбирать в зависимости от того, как ни странно, в каком порядке вы желаете обойти граф! Внимание, любой граф, а не только дерево.
Очень часто порядок обхода неважен. Думаю, имелись ввиду именно такие случаи. Впрочем, обход в глубину обычно проще, зачем использовать в ширину — не очень понятно. Если из-за расходов на вызов функции, то можно на вход принимать детей, а не вершину, а обработку вершины делать в цикле.
Фейсбук ищет обоими способами. Асинхронно. Но BFS работает быстрее и лучше. Тупа эмпирически на больших данных. Например, когда нужно найти кого-то в друзьях всех друзей. Всё зависит от данных и ситуации.
Поэтому есть 4 нерекурсивных обхода: preorder, inorder, postorder, BFS. И с ними нужно уметь работать из головы, сходу.
Поэтому есть 4 нерекурсивных обхода: preorder, inorder, postorder, BFS. И с ними нужно уметь работать из головы, сходу.
То, что нужно уметь обходить, это итак понятно. А при чём тут Фейсбук, я не понял.
Но BFS работает быстрее и лучшеТак почему быстрее то? Из-за вызова функции для всех рёбер (либо вершин)? Если да, то ок. Можно конечно сделать свой стек, но обход в ширину, думаю, проще. У меня просто не было задач, где важна такая микро-оптимизация при обходе, поэтому не могу сказать, что проще.
Ребята, прежде, чем городить вспомогательные структуры для ускорения поиска сначала убедитесь, что они не замедляют поиск. Это делается простым измерением времени.
А то бывали случаи, когда простой перебор занимает секунду, а построение структуры — 20 минут
А то бывали случаи, когда простой перебор занимает секунду, а построение структуры — 20 минут
Я так понимаю, минусуют потому, что всё очевидно, а на практике никто не проверяет. Сравните график ln(N) и N. На довольно большом участке ln(N) > N и простой перебор работает быстрее, чем создание или гуляние по дополнительным структурам.
Откуда взялся логарифм в алгоритмах BFS и DFS? Не могли бы вы пояснить свою мысль?
А почему натуральный логарифм (lnN)? Я так понимаю, что пытались донести мысль, что поиск простым перебором иногда быстрее, чем построение balanced tree и поиск по нему? А на каком участке logN > N?
Мне кажется, минусуют из-за того, что:
- обычно, перед тем, как «городить вспомогательные структуры», разработчики анализируют асимптотику и, соответственно, имплементят более сложный алгоритм только тогда, когда это понижает асимптотику (и когда при этом объемы данных такие, что это реально принесёт пользу, само собой). И для этого не надо имплементить два алгоритма и сравнивать реальный runtime
- что у вас за такая фантастическая задача, что простой перебор занимает секунду, а алгоритм с лучшей асимптотикой работает 20 минут?
Я думаю, имелось ввиду что-то такое.
К сожалению, сложность далеко не единственная вещь, описывающая алгоритм. Есть еще необходимая дополнительная память, время на подготовку. Да и та самая константа, которую все игнорируют по очевидным причинам (потому что на бесконечности она не решает) может играть роль на малых значениях непосредственно n. 100n^2 < 1000nlogn при n < 4. Во всяком случае, C# предпочитает использовать сортировку вставками при n < 16, что действительно имеет смысл, не смотря на большую алгоритмическую сложность.
К сожалению, сложность далеко не единственная вещь, описывающая алгоритм. Есть еще необходимая дополнительная память, время на подготовку. Да и та самая константа, которую все игнорируют по очевидным причинам (потому что на бесконечности она не решает) может играть роль на малых значениях непосредственно n. 100n^2 < 1000nlogn при n < 4. Во всяком случае, C# предпочитает использовать сортировку вставками при n < 16, что действительно имеет смысл, не смотря на большую алгоритмическую сложность.
Пишу потому что очень много народа загипнотизировано умными словами. Но отводить гипноз — дело неблагодарное, как показывает практика.
Для теории хорошо, но на практике лучше проверить с таймером.
Был просто случай. Посоветовал мне один профессор библиотеку, которая строит пространственный индекс. Хотел валить на защите за то, что я не использую индексы. Библиотека хорошая, но у меня тупым перебором матрицу инцедентности строило за несколько секунд простым перебором для миллиона объектов. А хитрый индекс оказался слишком долгим. Я до этого не подозревал, что тупые методы тащат за счет меньшего количества накладных расходов на весьма большом количестве объектов.
разработчики анализируют асимптотику
Для теории хорошо, но на практике лучше проверить с таймером.
алгоритм с лучшей асимптотикой работает 20 минут
Был просто случай. Посоветовал мне один профессор библиотеку, которая строит пространственный индекс. Хотел валить на защите за то, что я не использую индексы. Библиотека хорошая, но у меня тупым перебором матрицу инцедентности строило за несколько секунд простым перебором для миллиона объектов. А хитрый индекс оказался слишком долгим. Я до этого не подозревал, что тупые методы тащат за счет меньшего количества накладных расходов на весьма большом количестве объектов.
Я ещё раз повторю ключевую фразу «перед тем как».
Сударь, вы же осознаёте, что асимптотику двух алгоритмов можно прикинуть и сравнить до имплементации, а «с таймером», как вы выражается — это тоже однозначно важная проверка (и называется это performance testing чаще всего), но если вы хотите так сравнить два алгоритма, вам надо будет оба закодить?
Второй важный момент из моего комментария, который я повторю: само собой, только плохой разработчик ориентируется на одну лишь асимптотику. И, внезапно, именно для проверки подобного на собеседованиях задают вопросы в духе «когда merge sort/bubble sort/counting sort использовать выгоднее, чем quick sort?».
Сударь, вы же осознаёте, что асимптотику двух алгоритмов можно прикинуть и сравнить до имплементации, а «с таймером», как вы выражается — это тоже однозначно важная проверка (и называется это performance testing чаще всего), но если вы хотите так сравнить два алгоритма, вам надо будет оба закодить?
Второй важный момент из моего комментария, который я повторю: само собой, только плохой разработчик ориентируется на одну лишь асимптотику. И, внезапно, именно для проверки подобного на собеседованиях задают вопросы в духе «когда merge sort/bubble sort/counting sort использовать выгоднее, чем quick sort?».
но если вы хотите так сравнить два алгоритма, вам надо будет оба закодить?
Закодить один, но проверить, — на каком количестве он дает выигрыш. А то может и его не надо было кодить, так как количество объектов в системе такое, что вполне обрабатывается тупым методом. Вы например, можете назвать число элементов, на котором quck sort дает выигрыш? Я не думаю, что есть универсальное число. На каждой реализации надо измерять.
Мне кажется, что все эти вопросы про типы сортировок — пустая трата времени. С одной стороны о них все знают и, вероятно, кандидаты готовятся к таким вопросам заранее…
С другой стороны большинство разработчиков никогда в жизни не будут писать алгоритм сортировки вручную — для нас это уже сделали разработчики библиотек языка, поэтому в C# часто достаточно написать что-то в виде list.Sort().
То же самое могу сказать и про массивы/связанные списки. Я думаю, что никому не придётся реализовывать двусвязанные списки вручную… Хотя преимущества хранения в Хэш таблице по сравнению с массивом или двусвязанным списком спросить не вредно, т.к. знание этого позволяет программистам выбрать правильную структуру данных для хранения.
Первое правило технического интервью должно быть таким: не спрашивайте то, что вы не применяете в своей работе и не собираетесь применять в ближайшем будущем.
С другой стороны большинство разработчиков никогда в жизни не будут писать алгоритм сортировки вручную — для нас это уже сделали разработчики библиотек языка, поэтому в C# часто достаточно написать что-то в виде list.Sort().
То же самое могу сказать и про массивы/связанные списки. Я думаю, что никому не придётся реализовывать двусвязанные списки вручную… Хотя преимущества хранения в Хэш таблице по сравнению с массивом или двусвязанным списком спросить не вредно, т.к. знание этого позволяет программистам выбрать правильную структуру данных для хранения.
Первое правило технического интервью должно быть таким: не спрашивайте то, что вы не применяете в своей работе и не собираетесь применять в ближайшем будущем.
Я встречал сильно отличное от нуля количество людей претендующих на вакансию программиста, которые считали что ключу хэш-таблицы нужна операция сравнения на больше/меньше. Вопросы о базовых структурах хранения данных вполне полезны, они выступают «фильтром грубой очистки».
Да, знание базовых структур важно, но часто человек может не иметь хорошего теоретического образования, и из-за этого «плавать» в таких вопросах, но на практике он интуитивно знает, что, к примеру, хэш-таблицы работают быстрее, чем массивы/списки в случае хранения пары ключ-значение. И при этом ему совсем не обязательно знать за счёт чего они работают быстрее, и что для поиска записи в хэш-таблице вычисляется хэш и ищется точное совпадение в ключах. Если хотите спросить про теорию — спросите про передачу параметров по ссылке или по значению для требуемого языка, т.к. это намного более практический пример и многие делают трудноуловимые ошибки не зная этих принципов.
Вот считает он, что нужна операция сравнения на хэш-таблиц. А на результате-то это как скажется?
Особенно для тех, кто пишет прикладные вещи типа приложений, фронта и тп.
У меня просто всегда запекалось с таких вопросов на собеседовании. А потом в таких компаниях появляются продукты, где интерфейс весь сикось-накось, соединение теряется постоянно и батарейка утекает как не в себя. Зато вся команда может написать рекурсивный обход бинарного дерева за обедом одной рукой.
Вот и думай после этого, приносят ли подобные вопросы хоть какую-нибудь пользу.
Про батарейку — не соглашусь. Именно она утекает во время использования не подходящих задаче алгоритмов.
Он переопределит операцию сравнения вместо хеша, и у него неправильно будет работать код. Как это повлияет на работу программы?
Да как угодно:) В зависимости от того, как и зачем используется таблица:)
Тебя еще не спрашивали, как компилятор развернёт чисто виртуальный класс, какая у него будет виртуальная таблица и сколько она будет занимать места в памяти. То, что процессоры бывают не только х86 всем, конечно же, наплевать. И что размер указателя может быть разным тоже. И, наконец, что компиляторы могут себя вести по-разному тоже :)
а я встречал оптимизации кстати стандарт теперь в Java 8 когда одна ячейка в хеш таблице конвертируется в бинарное дерево где нужна функция сравнения по ключу
Реализовывать действительно, придется вряд ли — но разницу между .Any() и .Count()>0 кандидат понимать должен.
.Any() и .Count()>0
Это классический залет, встречающийся в продуктовом коде.
Но встречаются (реально встречаются!) образчики и посильнее:
List<SomeType> list = GetSomeTypeList();
foreach (var item in list)
{
int index = list.IndexOf(item);
// Do something with item and index
}for (int i ...), O(N) vs. O(N*N)? — не, не слышали.
Извините, а в чем разница?
В первом случае (Any) мы перебираем список, до первого совпадения (ну или вообще наличия элемента в списке), во втором случае (Count) мы полностью перебираем список чтобы посчитать количество.
Справедливости ради, стоит отметить, что это зависит от того, для какой коллекции вызывается.
К примеру, для конечных коллекций, которые хранят свой размер, вроде массива, Count() (который внутри Length) будет быстрее, чем Any(), т.к. не создаётся/уничтожается итератор.
Для условно бесконечных коллекций (вроде IEnumerable) Any() конечно будет быстрее.
К примеру, для конечных коллекций, которые хранят свой размер, вроде массива, Count() (который внутри Length) будет быстрее, чем Any(), т.к. не создаётся/уничтожается итератор.
Для условно бесконечных коллекций (вроде IEnumerable) Any() конечно будет быстрее.
Поправка: IEnumerable — не коллекция, а интерфейс. Правильнее говорить "для IEnumerable который не является ICollection"
Для тех, кто хранит свой размер, лучше использовать свойство Count вместо Linq-метода Count(). Это поможет избежать как минимум двух проверок: на null и на принадлежность к ICollection<T>.
any остановится на первом совпадении, а count пойдет весь список
Стоит отметить, что если бы методы были названы более мнемонически, то неподходящих вызовов было бы меньше даже у тех, кто не знает/кого не заботит сложность вызовов:
— и по смыслу этот метод гораздо ближе к уже имеющемуся
Когда разработчики работают не с IEnumerable, а с явными списком, коллекцией, или даже с массивом, то часто в в коде путают/пишут, не особо задумываясь, — Count, Count(), Length вперемешку.
!Any() -> на IsEmpty()Any(Func<TSource, bool> match) -> на Contains(Func<TSource, bool> match) или ContainsAny(Func<T, bool> match)— и по смыслу этот метод гораздо ближе к уже имеющемуся
Contains(TSource item)Count() -> на GetCount() или CalculateCount()Когда разработчики работают не с IEnumerable, а с явными списком, коллекцией, или даже с массивом, то часто в в коде путают/пишут, не особо задумываясь, — Count, Count(), Length вперемешку.
Шпаргалка для технического собеседования. Точно? А мне показалось, что это список вопросов по курсу Алгоритмы и Структуры данных.
Почему я должен знать DFS? А алгоритм А* — не нужно? Почему? Я либо буду использовать в работе все графовые алгоритмы, либо ни один из них.
Нужно знать жадные алгоритмы. А линейное программироваие не нужно? И так далее. Нужно выбирать алгоритмы по какому-то принципу, а не то, что все проходят в институте.
Почему я должен знать DFS? А алгоритм А* — не нужно? Почему? Я либо буду использовать в работе все графовые алгоритмы, либо ни один из них.
Нужно знать жадные алгоритмы. А линейное программироваие не нужно? И так далее. Нужно выбирать алгоритмы по какому-то принципу, а не то, что все проходят в институте.
А* используется только для поиска пути. А DFS используется для кучи других вещей. Например, на нем основана топологическая сортировка.
Вы точно не перепутали при сравнении линейное программирование и динамическое? Как-никак, динамическое программирование — это раздел алгоритмов, родственный жадным, а линейное программирование — это уже в математику и теорию оптимизаций.
И поэтому линейное программирование обычно программисту действительно знать не нужно, а вот жадные алгоритмы и динамику — было бы неплохо.
И поэтому линейное программирование обычно программисту действительно знать не нужно, а вот жадные алгоритмы и динамику — было бы неплохо.
Нет, не перепутал. Обе эти темы читаюстя в рамках курса алгоритмы и структуры данных, и обе из них могут понадобиться при решении прикладных задач.
Например, в рамках выпуска подкаста devzen.ru/episode-0180 Алексей twitter.com/paaleksey рассказывал, как linear programming solver можно использовать для написания build-тула.
С другой стороны, нам нужна и топологическая сортировка для build-тула. Хм, получается что обе эти темы могут появится и не появится в рамках практической жизни.
Например, в рамках выпуска подкаста devzen.ru/episode-0180 Алексей twitter.com/paaleksey рассказывал, как linear programming solver можно использовать для написания build-тула.
С другой стороны, нам нужна и топологическая сортировка для build-тула. Хм, получается что обе эти темы могут появится и не появится в рамках практической жизни.
И чем же похожи тогда линейное программирование и жадные алгоритмы, что их можно так приводить в качестве аналогии?
Плюс хотелось бы услышать, где их проходят в курсе алгоритмов и структур данных, потому что везде, где я вообще слышал про изучение линейного программирования, оно даётся либо в рамках отдельного курса, либо в рамках математических дисциплин.
Мой основной поинт — сравнение крайне некорректное, потому что линейное программирование дефолтный бекендщик никогда в своей карьере не встретит, а вот жадные алгоритмы, например, раз в пару лет могут и попасться.
Плюс хотелось бы услышать, где их проходят в курсе алгоритмов и структур данных, потому что везде, где я вообще слышал про изучение линейного программирования, оно даётся либо в рамках отдельного курса, либо в рамках математических дисциплин.
Мой основной поинт — сравнение крайне некорректное, потому что линейное программирование дефолтный бекендщик никогда в своей карьере не встретит, а вот жадные алгоритмы, например, раз в пару лет могут и попасться.
mit.spbau.ru — тут, например, проходят.
Я поясню свой инитный коммнетарий. Я не говорил, что это сравнимые темы. Я говорю, что это темы курса Алгоритмы и Структуры Данных, и в среднем можно взять от туда любые алгоритмы и сказать, что это темы для собеседования.
Мне же больше нравится позиция, что на собеседовании спрашивают то, что будет требоваться на данной вакансии.
Я поясню свой инитный коммнетарий. Я не говорил, что это сравнимые темы. Я говорю, что это темы курса Алгоритмы и Структуры Данных, и в среднем можно взять от туда любые алгоритмы и сказать, что это темы для собеседования.
Мне же больше нравится позиция, что на собеседовании спрашивают то, что будет требоваться на данной вакансии.
Спасибо за статью!
код на изображении в начале
он помешает мне сегодня уснуть.
Складывается впечатление, что надо знать, но понимать не надо. Не хотел бы я получить в команду «специалиста» прошедшего интервью по подобной шпаргалке.
А что, на простых программистов правда на собеседованиях спрашивают точные сложности операций по каждой структуре данных? Я думал, это больше каким-нибудь архитекторам надо, да и то не точные значения, а представлять, как работает.
Точные не спрашивают (учитывающие кэши процессора, prefetch и все такое). А big-O, почему бы и нет?
Знание BigO как раз и показывает базовое понимание работы структур данных.
Не надо это никаким архитекторам
А кому надо? Так, для общего развития?
Это нужно, когда у вас данных под миллиард приходит в функцию.
Например, вы пишите систему для Убер. Она определяет k ближайших к вам заказов. Нужно чтобы было ок на 100 000+. Так, для прикола. Типа ищем по всему миру. Такой тест-кейс. N*N не прокатит. Итого вы делаете квик селект по k, а потом ищите за N тех, кто ближе чем k. И получаете линейную сложность.
Например, вы пишите систему для Убер. Она определяет k ближайших к вам заказов. Нужно чтобы было ок на 100 000+. Так, для прикола. Типа ищем по всему миру. Такой тест-кейс. N*N не прокатит. Итого вы делаете квик селект по k, а потом ищите за N тех, кто ближе чем k. И получаете линейную сложность.
Система а-ля убер пилится при участии огромного количества сотрудников. Кому из них необходимо знать O-символику?
Обычному бэкенд разработчику, который будет имплементить какой-нибудь алгоритм для большого объема данных. И как правило имплементить приходится потому, что нельзя взять готовый алгоритм в чистом виде.
Открою маленькую тайну: подобные алгоритмы запиливает довольно небольшое количество программистов-рокстаров, счёт которых идёт на единицы, в крайнем случае на десятки.
Подавляющее большинство всех остальных разработчиков не изобретает велосипеды, а использует готовые реализации алгоритмов и программирует рутину.
Подавляющее большинство всех остальных разработчиков не изобретает велосипеды, а использует готовые реализации алгоритмов и программирует рутину.
Согласен, что на подавляющем числе проектов вообще не нужны алгоритмы.
Но, например, у нас в отделе(mail.ru) рядовому разработчику(не алгоритмистам и не звездам) приходится и классические алгоритмы, и ml время от времени использовать. И даже если есть готовая реализация чего-то, нужно подумать что именно готовое использовать.
Когда собеседовался как раз давали 5 алгоритмических задачек, и удивительно, но задачи релевантны тому, что приходится использовать в работе.
Но, например, у нас в отделе(mail.ru) рядовому разработчику(не алгоритмистам и не звездам) приходится и классические алгоритмы, и ml время от времени использовать. И даже если есть готовая реализация чего-то, нужно подумать что именно готовое использовать.
Когда собеседовался как раз давали 5 алгоритмических задачек, и удивительно, но задачи релевантны тому, что приходится использовать в работе.
Ну так одно дело — алгоритмы использовать, а другое — их писать. Единицы пишут алгоритмы, сотни — их используют, а тысячи просто пишут код.
В ML никакого rocket science нет. Немного теории в области статистики + навыки использования ML фреймворков — и всё, специалист по данным готов. Вообще, в ML в bigdata высока роль случая и простого везения — чем больше специалистов занимаются одним и тем же, чем более вероятно, что хотя бы один из них случайно получит хороший результат.
Аналогично с алгоритмами: на практике экзотика встречается довольно редко, подавляющее большинство алгоритмов — это хэш-таблицы, сортировка, возможно двоичные деревья поиска. Если вы — пользователь алгоритмов, а не их разработчик, то достаточно просто умений применять библиотечные алгоритмы в нужных местах.
В ML никакого rocket science нет. Немного теории в области статистики + навыки использования ML фреймворков — и всё, специалист по данным готов. Вообще, в ML в bigdata высока роль случая и простого везения — чем больше специалистов занимаются одним и тем же, чем более вероятно, что хотя бы один из них случайно получит хороший результат.
Аналогично с алгоритмами: на практике экзотика встречается довольно редко, подавляющее большинство алгоритмов — это хэш-таблицы, сортировка, возможно двоичные деревья поиска. Если вы — пользователь алгоритмов, а не их разработчик, то достаточно просто умений применять библиотечные алгоритмы в нужных местах.
Я не совсем понимаю в чем вы хотите меня убедить )
Человек хотел знать, кому из многочисленных разработчиков Убер нужна О-нотация. Рядовому бэкенд разработчку, который пишет под большие данные, нужно знать что такое О-нотация. Без этого знания, ни писать алгоритмы, ни использовать не получится.
Возможно в убере есть отдельные люди которые решают ВСЕ задачи связанные с алгоритмами(я сомневаюсь), но у нас на проекте и пишутся и используются алгоритмы рядовыми разработчиками, исследователей на всё не хватит, без О-нотации далеко не уйдешь.
Человек хотел знать, кому из многочисленных разработчиков Убер нужна О-нотация. Рядовому бэкенд разработчку, который пишет под большие данные, нужно знать что такое О-нотация. Без этого знания, ни писать алгоритмы, ни использовать не получится.
Возможно в убере есть отдельные люди которые решают ВСЕ задачи связанные с алгоритмами(я сомневаюсь), но у нас на проекте и пишутся и используются алгоритмы рядовыми разработчиками, исследователей на всё не хватит, без О-нотации далеко не уйдешь.
тем кто за алгоритмы отвечает и немного тем кто с базами данных вплотную работает
Не надо путать сеньоров с джуниорами. Среднему джуниору это очень даже пригодится на первых собеседованиях, поскольку хорошие собеседователи — большая удача и огромная редкость. А средний сеньор на третьем-четвертом таком вопросе встанет и уйдет, со словами «вас, ребята, похоже, в Гугле забанили»
Ваши аргументы очень слабые, реально.
Если кто выше не понимает смысл таких вопросов, то вот объяснение.
Если вы в жизни не писали с нуля системы на миллионы терабайт данных, то и не поймете зачем это нужно. Даже если взять Кормена, то это ничто. Кормен очень поверхностная книга. В Кормене даже SuffixTree/SuffixArray нету. Тоесть такой человек не напишет эффективный поиск. Инвертированного индекса тоже нет. Поиска k ближайших точек за O(N) тоже не напишет. Как говорил мой знакомый из гугла:«Если хотите понять сущность алгоритмов, то увеличите число данных до миллиарда на 1 машине. И придумайте эффективный способ работы». У вас сразу полезет наружу всё. И коллизии в хешах. И поиск в ширину-глубину. И вообще всё перестанет работать. А с этим нужно еще как-то жить и дружить.
Загуглите
Distributed Computing Principles, Algorithms, and Systems
Ajay D. Kshemkalyani and Mukesh Singhal
или
Principles of Distributed Computing
Roger Wattenhofer
Ну как читается? Легко?
Если кто выше не понимает смысл таких вопросов, то вот объяснение.
Если вы в жизни не писали с нуля системы на миллионы терабайт данных, то и не поймете зачем это нужно. Даже если взять Кормена, то это ничто. Кормен очень поверхностная книга. В Кормене даже SuffixTree/SuffixArray нету. Тоесть такой человек не напишет эффективный поиск. Инвертированного индекса тоже нет. Поиска k ближайших точек за O(N) тоже не напишет. Как говорил мой знакомый из гугла:«Если хотите понять сущность алгоритмов, то увеличите число данных до миллиарда на 1 машине. И придумайте эффективный способ работы». У вас сразу полезет наружу всё. И коллизии в хешах. И поиск в ширину-глубину. И вообще всё перестанет работать. А с этим нужно еще как-то жить и дружить.
Загуглите
Distributed Computing Principles, Algorithms, and Systems
Ajay D. Kshemkalyani and Mukesh Singhal
или
Principles of Distributed Computing
Roger Wattenhofer
Ну как читается? Легко?
Вот и синьеры из гуглов подъехали с минусами.
Кстати, DarkTiger, когда думаете догонять Амазон какой-нибудь?
Кстати, DarkTiger, когда думаете догонять Амазон какой-нибудь?
Вы прямо-таки гордитесь сложностью, а гордиться тут нечем, а слова ваши весьма оторваны от реальности. Писать с нуля системы на миллионы терабайт — это удел нескольких людей в мире. И дело даже не в уровне опыта, потребности такой нет, чтобы каждый человек с нуля писал новую Cassandra или Hadoop. В реальности есть рынок, некий мир реальных проектов, востребованных, нужных, и драйвится всё это бизнесом, увы. Вы можете знать миллион крутых алгоритмов и впадать в экстаз от того как они сложны (а вы — умны), но на деле вам нужно уметь быстро принимать правильные технические решения, иметь широкий кругозор в данной сфере, ведь часто «нужно сделать вчера!», при этом вам же этот код поддерживать, при этом сделать сильно крутой алгоритм будет банально дороже, чем докупить на сервер еще одну планку памяти (и на 2 недели дольше, что сорвет план внедрения, вас обгонят конкуренты и весь проект вообще потеряет смысл). Как и везде, нужна золотая середина. Статья о «техническом собеседовании», а не «техническом собеседовании супер-стар алгоритмиста-математика-разработчика на уникальную технологию в гугле или яндексе». Не нужны, не обижайтесь, просто поймите это — ну не нужны такие глубины мира алгоритмов в 99% случаев. Что считать глубиной, а что — необходимой для каждого программиста базой — это другой вопрос, но я основываюсь на вашем комментарии: Кормен — это более чем достаточно для тех самых 99%.
— Никак не могу найти себе помощника — пожаловался однажды Эдисон Эйнштейну, — Каждый день заходят молодые люди, но ни один не подходит.
— А как вы определяете их пригодность? — поинтересовался Эйнштейн.
Эдисон показал ему листок с вопросами.
— Кто на них ответит, тот и станет моим помощником.
«Сколько миль от Нью-Йорка до Чикаго?» — прочел Эйнштейн, — «Нужно заглянуть в железнодорожный справочник».
«Из чего делают нержавеющую сталь?» — «Об этом можно узнать в справочнике по металловедению».
Пробежав глазами остальные вопросы, Эйнштейн сказал:
— Не дожидаясь отказа, свою кандидатуру снимаю сам.
Никто не знает как нанимать программистов. Даже гугл признал нулевую корреляцию качества сотрудников со сложностью собеседования.
Если вы в жизни не писали с нуля системы на миллионы терабайт данных
… то скорее всего не скоро начнете их писать. Сколько этих систем нужно в мире? Не очень много. Типичная задача в типичной компании сегодня — та же самая, что и сорок лет назад: вот у нас есть госпиталь, нам нужно создать систему записи пациентов на прием к докторам. Только сорок лет назад эту систему писали для мейнфрейма на коболе, а сегодня — для облака на вебсервисах с ангуляром.
Недавно только наткнулся случайно на таких ребяток. Думал может на контрактной основе поработаем, не сразу понял что «у нас есть предложение» означает собеседование, но время было дай думаю побеседуем. Полчаса находился в непрерывном изумлении. Обычно ко мне обращаются так: вот база, работает медленно, хотим чтобы работала быстро. А тут вдруг вопросы по нисходящей с каждым вопросом на уровень ниже вплоть до systemd O_O
И мало того что в конкретном частном случае я не верю в объемы данных, которые бы требовали знаний устройства системного кеша (тем более что вне контекста я просто не помню). Дело в том что как правило во всех местах где меня просят оптимизировать какой то лютый треш в архитектуре бд, жуткие запросы, страшный оверхед орм и прочее. Я просто не могу себе представить где посреди всего этого дело вдруг может понадобицо знать «сортировку пузырьком».
Уж простите меня коллеги. Я правда верю, что то есть проекты с нормальным подходом над которыми работают профессионалы. Но видимо, чтобы это увидеть, нужно устроиться в гугл как минимум.
И мало того что в конкретном частном случае я не верю в объемы данных, которые бы требовали знаний устройства системного кеша (тем более что вне контекста я просто не помню). Дело в том что как правило во всех местах где меня просят оптимизировать какой то лютый треш в архитектуре бд, жуткие запросы, страшный оверхед орм и прочее. Я просто не могу себе представить где посреди всего этого дело вдруг может понадобицо знать «сортировку пузырьком».
Уж простите меня коллеги. Я правда верю, что то есть проекты с нормальным подходом над которыми работают профессионалы. Но видимо, чтобы это увидеть, нужно устроиться в гугл как минимум.
UFO just landed and posted this here
>Блог компании Mail.Ru Group
;-З
На какую должность с такими вопросами собеседуете?
;-З
На какую должность с такими вопросами собеседуете?
только мне кажется что на собеседовании в первую очередь спрашивают знание фреймворков, апи и прикладной скилл там обращения с бд, создание фронтенда, методы работы типа SCRUM и т.п.
Дерево — это такая структура данных, в которой каждый узел имеет как минимум два дочерних элемента.
Вы это серьёзно? Каждый узел, минимум два дочерних элемента? Оно бесконечное что-ли? А что тогда будет листом в таком дереве? Если речь идёт о дереве в общем, то там могут быть узлы и с одним дочерним элементом (вы даже дальше приводите пример вырожденного дерева). Если же о двоичном дереве (учитывая заголовок параграфа, из которого взята цитата), то там будет максимум два дочерних элемента.
Однозначно, очень вредная шпаргалка. Дальше читать не стал, простите.
Больше похоже на шпаргалку на втором курсе по теме Алгоритмы и структуры данных
Вопросы про алгоритмы, а на картинке пых и сырой SQL. Собственно, что ты и будешь делать следующие пять лет, ответив про сортировки и деревья.
Основная разновидность — линейные массивы, или одноразмерные.
Их размер статичен, то есть при объявлении линейного массива задаётся фиксированный размер.
Неясно, почему линейные массивы противопоставляются динамическим. Подразумевались, очевидно, статические массивы.
Вставка: линейный массив — недопустимо, динамический массив — O(n).
Действительно, вставка в динамический массив происходит за O(n), но эта информация не очень полезна без того факта, что в силу мультипликативной стратегии реаллокации амортизиованная сложность вставки получается O(1), то есть последовательная вставка n элементов произойдёт не за O(n^2), как можно было бы подумать, а за O(n).
Данные хранятся в узлах, указывающих на другие узлы.
Узел содержит один элемент данных и одну ссылку (на другой узел).
Связный список соединяет узлы друг с другом с помощью ссылок от одного узла к другому.
Под определение, которое дано в статье подходит всякая ересь, например:
Оптимизированный поиск: связный список — O(n).
Неясно, что такое оптимизированный поиск в связном списке.
(оффтоп: чутка развив идею списка можно делать на нём аналог двоичного поиска, гуглить skip list).
Этот процесс называется хэшированием: однозначным сопоставлением друг другу входных и выходных данных.
Вот это жесть, конечно. Конечно, хэширование не занимается однозначным сопоставлением, потому что значений хэшей должно быть меньше, чем значений хэшируемых объектов, чтобы это имело хоть какой-то смысл.
Хэш-коллизиями называются ситуации, когда для двух разных входных данных функция возвращает одинаковые выходные данные.
Эта проблема свойственна всем хэш-функциям.
Часто она решается с помощью увеличения хэш-таблиц до огромного размера.
Решается она не так, конечно, а с помощью использования стратегий разрешения коллизий. Гуглить цепочки, линейное разрешение, двойное хэширование, хэширование кукушки.
Двоичное дерево — это такая структура данных, в которой каждый узел имеет максимум два дочерних элемента.
Дочерние элементы бывают левым и правым.
При этом у каждой вершины не больше одного левого сына и не больше одного правого.
Индексирование: двоичное дерево поиска — O(log n).
Поиск: двоичное дерево поиска — O(log n).
Вставка: двоичное дерево поиска — O(log n).
Все эти операции работают за O(высота дерева). Если дерево сбалансированное, то тогда это действительно O(log N), но само по себе дерево сбалансированным навряд ли станет.
Существуют хитрые двоичные деревья, которые всегда остаются сбалансированными. Гуглить, например, красно-чёрное дерево, AVL-дерево, splay-дерево.
Поиск в ширину оптимален для поиска по дереву, чья ширина превышает глубину.
Это почему вдруг? С точки зрения времени алгоритм всегда обработает каждую вершину 1 раз, а каждое ребро – 2 или 1 раз (в зависимости от того, ориентированный граф или нет). Если же хочется пооптимизировать память, то поиск в ширину наоборот тратит меньше памяти на очередь на «глубоких узких» графах (потому что слои получаются маленькие).
В связи с использованием очереди такой метод поиска потребляет больше памяти, чем поиск в глубину.
Ну неясно. Поиск в глубину же стек поддерживает пока ходит (неявно, через рекурсию). Те же самые O(V) памяти.
E — количество рёбер (граней?).
Рёбер. Грань – область, ограниченная рёбрами в плоском графе и не содержащая внутри себя вершин и рёбер графа.
[Поиск в глубину] Алгоритм оптимален для поиска по дереву, чья глубина превышает ширину.
Аналогично, с точки зрения времени всё то же самое, а с точки зрения памяти всё ровно наоборот.
Сравнение поисков в ширину и в глубину
Выбирайте тип поиска в соответствии с размером и формой дерева.
Для широких, мелких деревьев используйте поиск в ширину.
Для глубоких, узких деревьев используйте поиск в глубину.
Если уж заморачиваться, то ровно наоборот.
Вообще, поиск в ширину и поиск в глубину – это базовые алгоритмы, из которых потом растут свои ответвления, например:
- с помощью поиска в ширину можно искать кратчайшие пути в невзвешенном графе
- с помощью поиска в глубину можно искать мосты и точки сочленения.
Сравнение данных с помощью алгоритма сортировки:
Весь набор данных делится минимум на две группы.
Пары значений сравниваются между собой, наименьшее перемещается влево.
После сортировки внутри всех пар, сравниваются левые значения двух левых пар. Таким образом, создаётся группа из четырёх значений: два наименьшие — слева, наибольшие — справа.
Процесс повторяется до тех пор, пока не останется только один набор.
Каша, мёд, говно и пчёлы. Сначала, я так понял, автор начал описывать рекурсивную реализацию, а потом описал итеративную.
«Весь набор данных делится минимум на две группы» – первый шаг рекурсивного алгоритма. Затем каждая часть рекурсивно сортируется и сливается.
Наилучший вариант сортировки: сортировка слиянием — O(n).
Средний вариант сортировки: сортировка слиянием — O(n log n).
Худший вариант сортировки: сортировка слиянием — O(n log n).
Сортировка слиянием всегда работает ровно за O(n log n).
Жадные алгоритмы используются для поиска оптимального решения данной проблемы.
Все алгоритмы в идеале используются для поиска оптимального решения конкретной проблемы. Специфика жадных алгоритмов в том, что их наоборот часто используют для поиска хоть каких-то решений в задачах, в которых искать оптимальное решение не представляется возможным.
Псевдокод жадного алгоритма для поиска самой большой разницы между двумя числами в массиве
Псевдокод жадного алгоритма для поиска самой большой разницы между двумя соседними числами в массиве.
:(
Замечание безотносительно статьи.
Из такого банального процесса как собеседование в последние лет 5 сделали какой-то культ — скоро будут в институтах преподавать. И мне чувствовать себя на собеседе как на экзамене в универе — тоже пришлось. Но иной раз, слушая вопросы оппонента, складывается впечатление, что пришёл в контору пишущую софт для управления реакторами а не банальные формочки на php.
За 20 лет работы, программировать приходилось в разном режиме (и как в виде основной деятельности и как вспомогательной) но вот ни разу мне не понадобилось знание работы алгоритмов сортировки. Видать я не правильный «сварщик».
Собеседовать кандидатов тоже приходилось. И не понимаю к чему весь этот ажиотаж? Извините за сумбур.
Из такого банального процесса как собеседование в последние лет 5 сделали какой-то культ — скоро будут в институтах преподавать. И мне чувствовать себя на собеседе как на экзамене в универе — тоже пришлось. Но иной раз, слушая вопросы оппонента, складывается впечатление, что пришёл в контору пишущую софт для управления реакторами а не банальные формочки на php.
За 20 лет работы, программировать приходилось в разном режиме (и как в виде основной деятельности и как вспомогательной) но вот ни разу мне не понадобилось знание работы алгоритмов сортировки. Видать я не правильный «сварщик».
Собеседовать кандидатов тоже приходилось. И не понимаю к чему весь этот ажиотаж? Извините за сумбур.
Вы будете смеяться, но… web.stanford.edu/class/cs9
UFO just landed and posted this here
Прочитав пост, подумал что это очень хороший тест: в каждом разделе есть по ошибке. Можно нарезать по разделу на страницу и распечатать. На собеседовании попросить кандидата найти ошибку.
Лично я нашел неточности, начиная с «Массив» и вплоть до сортировок. В каждом мелком подразделе. Прочитав комментарии, понял что там где я не нашел неточности — это скорее от моего незнания. Есть повод повторить сортировки и поиск в ширину/глубину — там сходу ошибок не нашел, есть куда расти. Так что спасибо за статью, получился неплохой тест :)
Лично я нашел неточности, начиная с «Массив» и вплоть до сортировок. В каждом мелком подразделе. Прочитав комментарии, понял что там где я не нашел неточности — это скорее от моего незнания. Есть повод повторить сортировки и поиск в ширину/глубину — там сходу ошибок не нашел, есть куда расти. Так что спасибо за статью, получился неплохой тест :)
Вопросы на общее представление о некоторых алгоритмах и их сложности действительно должны иметь место быть. Но в контексте конкретного ЯП, а не алгоритмов в целом. Потому что я довольно часто вижу, когда человек для поиска максимального элемента пишет `.Sort().Last()` вместо `.Max()`. Ну или рукожопит заливку (floodfill) так, что она работает на 3-4 порядка медленнее оптимальной реализации.
Но главное — не переусердствовать. Бинарные деревья на практике, скорее всего, никогда не встретятся. Сортировка пузырьком — тоже. Про всякую экзотику в виде RB, AVL, декартовых деревьев я вообще молчу.
А вот умение написать эффективную хэш-функцию, функцию сравнения — это важные умения.
Но главное — не переусердствовать. Бинарные деревья на практике, скорее всего, никогда не встретятся. Сортировка пузырьком — тоже. Про всякую экзотику в виде RB, AVL, декартовых деревьев я вообще молчу.
А вот умение написать эффективную хэш-функцию, функцию сравнения — это важные умения.
Массив
Определение:
Хранит элементы данных на основе последовательного индекса, чаще всего с нулевой базой.
Что значит "хранит на основе индекса"? Лучше возьмите определение из википедии.
В его основе лежат кортежи из теории множеств.
Откуда вы это взяли?? Массив и кортеж — совершенно разные понятия в контексте программирования.
Извините, но что за бред-то?
Рекурсивные алгоритмы
Определение:
Как следует из определения, этот алгоритм вызывает самого себя.
:)
Не давно проходил собеседование в Яндекс на разработчика интерфейсов. Собеседованием остался доволен, на первом этапе спрашивали солянку из html, css и особенностей javascript, ничего сверхъестественного и заковыристого. На следующем этапе было 4 интервью, которые были в виде практических задач. Совсем чуть-чуть теории спрашивали, а потом решали задачи. Считаю это самым правильным вариантом. Кандидат прекрасно может знать структуры данных, крутые алгоритмы и прочие теоретические вещи, но какой в этом толк, если он не может применить их на практике. Конкретные задачи как раз помогают выяснить, что умеет и знает кандидат. Как он подходит к решению проблемы, какие алгоритмы и структуры данных использует. Ведь в итоге именно за этим и ищут человека, что бы он решал конкретно поставленные задачи, а не хвастался, что знает все алгоритмы обхода графа
«Псевдокод» зачетный, конечно. Что в массиве делает nil? Это массив указателей? Нулевой указатель не может храниться в массиве? Зачем вызывается псевокейворд exit loop, если мы не в цикле?
на ios клиента в майле в одну команду про это спрашивали :) при этом по ios — практически ничего :)
Этот алгоритм предпочитают использовать в архитектурах вычислительных систем.
Что черт возьми должна означать эта фраза??
Если при работе рекурсивного алгоритма вы столкнулись с чем-то из перечисленного, значит, вы всё испортили.Я аж чаем поперхнулся. Спасибо за капельку позитива с утра пораньше! :)
Sign up to leave a comment.
Шпаргалка для технического собеседования