Здравствуйте.
Примерно через неделю мне предстоит собеседование по алгоритмам.
У меня незаконченное математическое образование, что означает, что я знаю, что такое
например, логарифм или факториал, но при этом совершенно не имею академической подготовк
по этой теме (толкового курса по программированию и по этой теме в частности в течение 3 лет, что я учился, не было). Мой суммарный опыт программирования - 4 года. Основные языки в настоящее время Objective-C и C.
Я пытаюсь продумать оптимальную стратегию для подготовки и поэтому интересуюсь: може
ли кто-нибудь набросать что-то вроде обзора этой темы "Алгоритмы" (quick overview), ориентируясь на который можно было бы более или менее направленно успеть за неделю пройти самые-самые основные в этой теме вопросы?
Вот навскидку то, что мне известно в связи с этой темой (точнее о чём имею боле
или менее чёткое представление, список неисчерпывающий):
O-notation
Хорошо знаю примерно треть алгоритмов из этого репозитория: EKAlgorithms и даже кое-чт
добавил туда сам, например, алгоритмы Indexes of maximum and minimum elements simultaneously, Quickselect, Partial selection sort, алгоритм бинарного поиска.
Например, хорошо теперь знаком с geo-spatial структурами и алгоритмами вроде: KD-деревья и двумерные K-деревья в частности, Quad-деревья, алгоритмами Grid clustering и K-means.
Например, хорошо знаю, как устроены массивы и словари в C и Objective-C, включа
circular buffer (который лежит в основе массивов NSMutableArray у Apple).
...
Одним словом, общее представление у меня точно есть, но всё-таки очень часто я сталкиваюс
с отсутствием академических знаний - например, только на днях узнал о таком понятии
как "амортизированная стоимость" или, например, недавно, понял, что не понимаю, почему при подсчёте алгоритмической сложности некоторых алгоритмов возникает именно десятичный алгоритм (то есть, откуда берётся именно 10 в основании).
Потенциальных авторов ответов я прошу именно об обзоре, а не об ответах со ссылкам
на известные многотомные работы по алгоритмам, осилить которые у меня по определению нет времени.
Буду благодарен за законченные, целостные и сбалансированные ответы, которые помогу
мне или другим потенциальным читателям этого топика, так как, уверен, тема эта актуальна всегда и везде.
P.S. Особо интересно было бы увидеть ответ @VladD.
Хороший соседний топик (из ответа @VladD) - Алгоритмическая "база" хорошего программиста. Вопрос по саморазвитию.
Спасибо.
Ответы
Ответ 1
По этой теме как-то было обсуждение: Алгоритмическая "база" хорошего программиста. Вопрос по саморазвитию.
Приведу выжимку, которая мне кажется важной и подходит для креш-курса:
Сложность алгоритмов, O-нотация, нужно уметь сходу оценивать O-сложность алгоритма хотя бы для простых случаев. Туда же Θ-нотация.
Структуры данных: деревья, обходы их, trie, куча, разрежённые матрицы и всё такое. Про них любят спрашивать.
Сортировки. Про них, скорее всего, не спросят, так как все знают и готовятся. Но всё же.
Графы, различные их представления и работа с ними. Поиск в ширину и в глубину, алгоритм Дейкстры и A*.
Обязательно попрактикуйтесь с разными задачами. Алгоритмы могут означать некую олимпиадну
составляющую, но туда лучше не заглядывать, очень уж специфическая область умений (если вы только сами не оттуда).
На интервью не бойтесь сказать, что вы чего-то не знаете. (Это всё равно довольн
сложно скрыть.) Но останавливаться и проваливать часть интервью не стоит, просто скажите, что вы попытаетесь сходу что-нибудь придумать. Ну и попробуйте придумать, это зачтётся.
Мне кажется, не стоит тратить последнюю неделю на поиск и усвоение новых знаний
новый багаж должен утрястить, прежде чем вы сможете его эффективно использовать. Поэтому лучше
систематизируйте имеющиеся знания, если есть видимые пробелы (например, та же «амортизированна
сложность» в hashtable), заполните их. Вероятно, имеет смысл задать их отдельными вопросами здесь и на математике.
прогоните хорошую серию задач, чтобы чувствовать себя уверенно.
настройтесь на то, что не только работа нужна вам, но и вы — работе: адекватный работодател
возьмёт вас, если увидит, что вы интересуетесь темой и растёте над собой (даже если каких-то знаний на момент интервью нет), а неадекватный вам и не нужен.
Ответ 2
Ну вы ж информируйте нас о том, как идёт подготовка, хорошо?
Пришло время написать немного о подготовке и результатах - конечно же я собиралс
это сделать и уже давно, просто ждал пока придёт ответ от компании. Теперь ответ пришёл, и я могу теперь спокойно закрывать гештальт.
Расскажу в нескольких частях. Ничего интересного не обещаю. Особенно более опытным, чем я, участникам ХК.
Итак,
I. Материалы и источники, которыми я пользовался.
Книга Cracking the code interview, 5th edition.
Лекции Яндекса: "Алгоритмы и структуры данных поиска. Бабенко Максим Александрович." (торрент)
Видео-курс "Robert Sedgewick, Kevin Wayne - Algorithms"(торрент) и их книга Algorithms (fourth edition).
Репозиторий с простейшими алгоритмами на Objective-C: EKAlgorithms, одним из контрибьюторо
которого я являюсь. В основном я больше привношу в этот репозиторий, чем беру из нег
- среди прочего я постоянно добавляю варианты к уже существующим там алгоритмам и добавля
к ним тесты так, чтобы можно было легко проверять как уже имеющиеся варианты, так и новые варианты и легко сравнивать их между собой, в том числе по производительности. Кроме того, я стараюсь максимально оптимизировать и гуманизировать (humanize) все находящиеся там алгоритмы, чтобы их можно было легко и быстро адаптировать для использования в реальных Objective-C/Cocoa программах.
II. Подготовка.
Подготовка происходила сумбурно и, имея в виду разумное напутствие VladD:
Мне кажется, не стоит тратить последнюю неделю на поиск и усвоение новых знаний
новый багаж должен утрястить, прежде чем вы сможете его эффективно использовать... (и далее весь раздел)
Я посмотрел первые три лекции Яндекса: "Сложность и модели вычислений", "Анализ учётны
стоимостей", "Функции быстрой сортировки и сортировки слиянием". Там я впервые узнал
например, про тета- и гамма- нотацию. Также внимательно слушал про "анализ учётных стоимостей
(амортизированная стоимость, метод банкира и др.). Послушал про сортировки - сравнение основных методов, стабильность, in-place, итд. Например, впервые узнал, но почти ничего усвоил - только смутное представление - про сортировку внешних данных External memory Merge Sort и K-way merge.
Прочитал около сотни страниц Cracking the code interview - особой пользы практическо
в связи с алгоритмами я, конечно, не получил, но зато появилось некоторое представлени
о том, что там происходит в компаниях "большой шестёрки" с точки зрения code interviews. Например, среднее количество собеседований в этих компаниях примерно 6-8 штук, но это все кроме меня тут наверняка знают.
Посмотрел выборочно несколько видео-лекций из курса Седжвика про сортировки и особенн
остановился на его разборе быстрой сортировки - видео мне показалось мало, и я прогляде
ещё и книгу, раздел про Quick Sort. Среди прочего удивило то, что только в 1990 год
некий инженер из Bell Labs заметил, что quick sort начинает работать очень затратн
на последовательностях с большим количеством одинаковых ключей (у него это были нули и единицы), и только после этого qsort в stdlib был исправлен для того, чтобы это учесть. Сюда же утверждение Серджвика о том, что в начале нужно делать рандомайз всего массива, чтобы гарантировать беспорядок, чтобы было N * log N. Словом, было интересно, и я все эти моменты отметил.
Во время прослушивания лекции Яндекса про merge sort меня привлекла идея о том, чт
при слиянии двух кусков можно обойтись N / 2 дополнительной памяти (external storage
вместо N (я думаю все кроме меня тут в курсе, о чём речь). Меня это сильно увлекло
и я решил закрепить этот принцип на практике и тут же поправил процедуру построения К-деревьев в библиотеке kingpin - там используется немного другая идея, но аналогия была очень точной и получилось сделать то самое сокращение temporary storage в 2 раза. Я квалифицирую это приключение, как решение задачи в количестве 1 штука в духе
прогоните хорошую серию задач, чтобы чувствовать себя уверенно.
как советовал @VladD.
Меня давно заинтересовала задача Иосифа (Josephus Problem), и я в течение двух-трё
дней из этой недели небольшими подходами пробовал решить её в качестве ещё одной и
задач для разминки перед собеседованием. Признаюсь честно, сделать efficient-верси
с O(K * log N) вместо O(N) ума не хватило даже совсем приблизительно, от чего до сих пор есть чувство собственной неполноценности - хватило только на наивную версию (как в Википедии) и версию, в которой используется "итератор-убийца" - она работает медленно, но зато позволяет хорошо визуализировать ход того, как происходят убийства.
Повторно изучал очень хороший, основанный на дизассемблировании, разбор того, ка
внутри устроен класс NSMutableArray - это класс для мутабельных массивов в Cocoa. В его основе лежит Circular buffer, но кроме этого простого факта в статье содержится ещё несколько деталей, которые очень полезно знать именно Objective-C разработчикам.
Добавил некоторое число алгоритмов в EKAlgorithms (главным образом, сортировки)
поправил реализацию уже существующих там (написанных не мной), написал несколько тестов для того, чтобы проверить некоторые нюансы изучаемого материала.
Так как кроме собеседования по алгоритмам ожидалось ещё одно собеседование по iOS
то я готовился ещё и по теме iOS - читал все основные источники в основном по двум темам: Run loops, Autorelease pools.
Основное вроде всё описал, двигаюсь дальше.
III. Собеседование.
Перед самым собеседованием настроение было такое, что меня уничтожат вопросами пр
деревья, графы, матрицы, про многочисленные изобретения Эдсгера Дейкстры и прочее. Вышл
же всё совсем просто, хотя я всё равно 1! раз умудрился продемонстрировать незнание самых простых именно азбучных основ [из-за их отсутствия я собственно и открывал этот вопрос пару недель назад].
Итак:
Первым вопросом было рассказать о общем о том, как измеряются сложность и эффективность алгоритмов. Я рассказал самые простые и тривиальные вещи. Вопрос был общий и простой.
Дальше было уточнение про O-нотации. Я тоже рассказал всё в общем адекватно и, как мне кажется, хорошо.
Следующим был задан вопрос про то, что именно обозначает O-нотация (подразумевалос
в сравнении с тета-, гамма-) - тут я честно застрял, так как эти детали у меня совершенн
вылетели из головы - я честно признался, что помню лишь, что одна из них "сверху", другая "снизу", третья "снизу и сверху", но какая из них какая, не знаю чётко. Считаю это главным своим недочётом во всём собеседовании.
Был вопрос именно про то, что мы обсуждали здесь про lg N, а именно: "А какой именн
логарифм имеется в виду, когда говорится о логарифмической сложности?". Я конечно ж
рассказал всё то, что мы успели затронуть здесь - и о строгой математической нотаци
и о том, что log2 и lg асимптотически отличаются друг от друга на константу, о том, что скорее всего lg N просочилось в массовое употребление с подачи нескольких классических работ по алгоритмам. Словом, ответ был очень развёрнутый. Можно считать это замечательным совпадением, так как открывался этот топик в том числе для ответа на этот вопрос - "почему встречается lg N, если имеется в виду log N или точнее log2 N?".
Дальше был общий вопрос рассказать про Quick Sort - я тут же восторженно рассказа
обо всём, что с большим интересом наизучал по видео и книге Седжвика и своим эксперимента
с имплементацией всего им описанного: про 1990 год, про рандомайз, чтобы убрать худши
случаи, про откат к insertion sort'у на малом числе элементов. Как мне показалось, свои
рассказом я "грузанул" своего собеседователя так, что следующим, что он предложил, было написать "что-нибудь попроще" на его компьютере в коллабедите (в котором присутствовал также второй собеседователь) простой Bubble Sort, что я и сделал мгновенно с использованием лаконичных Cocoa API. Меня попросили прокомментировать написанное, что я и сделал. Всё было правильно.
Дальше вступил второй собеседователь и спросил про худшие случаи для Bubble Sor
и спросил, как можно их смягчить. Я сходу, по следам рассказа про худшие случаи в Quic
Sort, ответил, что если такие худщие и редкие для Bubble Sort случаи действительно ожидаются
можно делать перед началом сортировки рандомайз. Мой ответ устроил спрашивающего, н
он спросил: "А ещё?". Я подумал некоторое время и понял, что сходу сказать не смог
(я всегда в таких случаях точно могу оценить, сколько времени мне точно не хватит для решения задачи, и это был такой случай). Оба собеседователя сошлись на "ладно, хорошо" и попросили рассказать на словах про Selection Sort и Insertion Sort. Я чётко рассказал про Selection Sort и начал рассказывать про Insertion Sort - начав немного путаться, я попросил времени подумать. Первый собеседователь сказал: "ладно, у нас остаётся мало времени, давайте решим задачу".
Задача оказалась такой: есть генератор random01(), который в случайном порядке выдаё
нули или единицы. Нужно на его основе написать random0123(), который выдаёт случайные 0 или 1 или 2 или 3.
Не успев даже подумать про первый и второй биты целого числа, в каждый из которы
записывается по random01() (это понимание уже пришло после собеседования), я сразу увиде
геометрическую аналогию с задачей про выбор квадранта, которую мы недавно разбирал
с @avp, @paulgri, @VladD и @mega, и тут же сказал, что нужно просто взять random01(
два раза в две переменные, а потом использовать двойное ветвление, и показал собеседовател
эту геометрическую аналогию. Я сказал, что будет честно считать, что я эту задачу зна
и что можно попробовать решить какую-нибудь ещё. Он спросил меня, "а как сделать на основе random01() троичный random012()?", то есть как из 2 получить 3 случайных числа, а не 4, как в первой задаче, но тут нас начали выгонять из переговорной. Я решил эту задачу уже дома, и понял, что будь на собеседовании больше времени, я бы не догадался о решении за отведённое малое время. Я отправил своему собеседователю это решение просто как follow-up, так как всегда выполняю нерешённые задачи в качестве "домашнего задания".
Вот и всё.
P.S.
А итог такой, что меня не взяли. Причины отказа не назвали, сославшись: "У нас н
принято сообщать о причинах отказов" и только: "Фидбэк о вас очень положительный, но продолжить общение мы не сможем".
Было 4 собеседования:
1) Вводное с ведущим разработчиком. Про это рассказывать долго, отмечу основное:
Я очень грамотно рассказал о наивных имплементациях NSMutableArray, NSMutableDictionar
в том виде, как они описаны Mike Ash в его известных постах "Let's build NSMutableArray
и "Let's build NSMutableDictionary" - я очень хорошо знаю эти реализации с С массиво
позади NSArray и простейшим словарём позади NSDictionary, так как делал кое-какие вещи на их основе. В процессе рассказа был вопрос про амортизированную стоимость - я на тот момент об этом не знал совершенно, даже слов таких не слышал, о чём и сказал прямо. Кстати, это "жесткое незнание" было одной из причин открытия этого вопроса.
Ещё была простейшая задача на матрицу вида N * N, которую я не решил в отведённо
время, запутавшись с индексами - я не предложил ответ, а так и сказал, что запутался
Это наверное, был единственный серьёзный прокол за все 4 собеседования. Мой ответ собеседовател
был такой: "я чётко понимаю, что мне нужно больше времени на эту задачу, в пределах этого времени у меня нет решения". В самом деле, придя домой, я решил эту задачу за 5 минут, так как в этой задаче для её быстрого решения нужно было "всего лишь" догадаться об одной очевидной мелочи (кавычки потому что "эх, если б сразу, вовремя").
2) Собеседование по iOS.
Типичные вопросы. Отмечу некоторые:
Вопросы про разницу instancetype и init.
Написать геттеры/сеттеры к данным @property (под MRC)
NULL, nil, Nil, NSNull - кто такие, и в чём разница.
Вопрос про блоки, в котором подразумевается знание о необходимости копировать блоки, чтобы копировать их содержимое на heap.
Проверка на знание Cocoa-паттерна:
(void)aMethod:(NSError * __autoreleasing *)error {
// do stuff, possibly assigning error if something went wrong
}
3) Алгоритмы (о них я рассказал выше).
4) "Архитектура". Я предполагал, что это будут вопросы про архитектуру, то есть устройств
iOS, оказалось, что это собеседование про проектирование - меня спросили как спроектироват
библиотеку для единой авторизации, которую смогут использовать несколько родственных между собой мобильных приложений. Чуть позже выяснилось, что мои собеседователи в этом интервью сами как раз являются разработчиками этой функциональности для всей экосистемы мобильных приложений в этой компании.
P.S. №2
Не уверен, зачем я написал этот длинный пост. Наверное цели три две: люблю печатно
слово первая - закрыть для себя вопрос с большим первым раундом подготовки по теме алгоритмы
вторая - возможно, вдруг кому-то хоть как-то написанное окажется интересным или полезным - лично я, пожалуй, был бы не прочь прочитать такой текст перед началом собственной подготовки к аналогичной цепи собеседований.
Ответ 3
Вдобавок к ответу @VladD:
Деревья: балансировка деревьев
Комбинаторика: способы оценки трудоемкости алгоритмов (отсюда и вытекает О-нотация)
Матрицы: обращение треугольной матрицы, обращение 2-3-х диагональных матриц (это хит)
Олскульные ребята (вроде меня) обожают вопросы связанные с решением задач на экономи
ресурсов (обычно память): кэширование, рекурсия vs. массив, LRU списки, битовые маски, хэши и проч.
Поищите в сети книжку Cracking Coding Interview - полезно полистать.
Ответ 4
Советую прочесть книгу - Карьера программиста. Она небольшая но очень познавательная и полезная в данном вопросе.
Комментариев нет:
Отправить комментарий