Собеседование по алгоритмам - как подготовиться к нему за одну неделю? [закрыт]
1,00
р.
Закрыт. Этот вопрос не по теме. Ответы на него в данный момент не принимаются.
Вопросы-опросники запрещены на Stack Overflow на русском. Для получения ответа, перефразируйте ваш вопрос так, чтобы на него можно было дать однозначно правильный ответ.
Закрыт 8 лет назад.
Заблокировано. Этот вопрос и ответы на него заблокированы, так как он не соответствует тематике сайта, но имеет историческое значение. Для него недоступна публикация ответов и другие действия.
Здравствуйте.
Примерно через неделю мне предстоит собеседование по алгоритмам.
У меня незаконченное математическое образование, что означает, что я знаю, что такое, например, логарифм или факториал, но при этом совершенно не имею академической подготовки по этой теме (толкового курса по программированию и по этой теме в частности в течение 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) - Алгоритмическая "база" хорошего программиста. Вопрос по саморазвитию.
Спасибо.
Ответ
По этой теме как-то было обсуждение: Алгоритмическая "база" хорошего программиста. Вопрос по саморазвитию.
Приведу выжимку, которая мне кажется важной и подходит для креш-курса:
Сложность алгоритмов, O-нотация, нужно уметь сходу оценивать O-сложность алгоритма хотя бы для простых случаев. Туда же Θ-нотация. Структуры данных: деревья, обходы их, trie, куча, разрежённые матрицы и всё такое. Про них любят спрашивать. Сортировки. Про них, скорее всего, не спросят, так как все знают и готовятся. Но всё же. Графы, различные их представления и работа с ними. Поиск в ширину и в глубину, алгоритм Дейкстры и A*.
Обязательно попрактикуйтесь с разными задачами. Алгоритмы могут означать некую олимпиадную составляющую, но туда лучше не заглядывать, очень уж специфическая область умений (если вы только сами не оттуда).
На интервью не бойтесь сказать, что вы чего-то не знаете. (Это всё равно довольно сложно скрыть.) Но останавливаться и проваливать часть интервью не стоит, просто скажите, что вы попытаетесь сходу что-нибудь придумать. Ну и попробуйте придумать, это зачтётся.
Мне кажется, не стоит тратить последнюю неделю на поиск и усвоение новых знаний: новый багаж должен утрястить, прежде чем вы сможете его эффективно использовать. Поэтому лучше
систематизируйте имеющиеся знания, если есть видимые пробелы (например, та же «амортизированная сложность» в hashtable), заполните их. Вероятно, имеет смысл задать их отдельными вопросами здесь и на математике. прогоните хорошую серию задач, чтобы чувствовать себя уверенно. настройтесь на то, что не только работа нужна вам, но и вы — работе: адекватный работодатель возьмёт вас, если увидит, что вы интересуетесь темой и растёте над собой (даже если каких-то знаний на момент интервью нет), а неадекватный вам и не нужен.
