Очевидно, что способов много, но этот, на мой взгляд, является оптимально простым, дешевым и интересным.
Алгоритм:
- Поступить в магистратуру в США.
- Сделать не кривое резюме.
- Найти реферал.
- Подготовится к интервью.
- Не слиться на интервью и подписать оффер.
И всё!
Теперь про каждый шаг подробнее.
1. Поступить в магистратуру в США.
По ссылке описаны тех. детали. Повторю, что в США очень много бесплатных магистратур в STEM, просто нужно внимательно изучать сайты интересующих вузов. Желающих американцев идти в grad school по IT в США очень мало, потому что уж слишком высокая альтернативная стоимость их времени — можно сразу пойти работать за большие деньги. К тому же, у большинства американских Computer Science бакалавров за плечами $50-100к долга — никому не хочется жить в долгу.
Летом, за год до выпуска, нужно начинать подготовку. Чем позже начнете — тем тяжелее добиться результата.
2. Сделать не кривое резюме.
Никто не требует гениального, но кривое сразу улетит в овчарную печь, так никогда и не увидев реальных инженеров. Поэтому резюме — это очень важно, и должно быть good enough. Правила просты: никаких опечаток, грамотный английский (попросите знакомого [native speaker] проверить, ваш гуглоперевод sucks, поверьте, некоторые термины почти невозможно перевести — нужно использовать английские аналоги) и длина в одну страницу на 5 лет опыта, а лучше просто в одну страницу — выберите главное. Больше информации про резюме можно найти на CareerCup.
3. Найти реферал
В принципе, это опциональный шаг, однако я решил его выделить в отдельный пункт, потому что я никогда не слышу, что про него что-то говорили. Оказывается, найти реферал (приглашение через внутреннюю систему от инженера, работающего в компании) — это невероятно полезная опция. Нет, это не дает гарантированное приглашение на работу — всего лишь (с бОльшей вероятностью) приглашение на тех. интервью, однако именно этот шаг по опыту моему и моих коллег и есть самый затруднительный шаг во всем процессе.
4. Подготовится к интервью.
Это шаг архиважный. Мне, например, всегда тяжело готовиться к чему бы то ни было — мне кажется, что я «и так достастаточно умен» — но это серьезная ошибка, готовиться нужно обязательно если вы умны, как раз в альтернативном случае — не нужно, все равно ничего не получится.
Теперь про то, как готовится и к чему. В крупных IT компаниях, лидерах рынка, интервью примерно одинаковы — от вас ожидается знания фундаментальных алгоритмов и структур данных, ничего более.
Подготовку удобно разделить на две части: фундаментальные знания и практические задачи.
Для первого — лучшу всего подходит курс Седжвика на Coursera. Можно найти на рутрекере первую и вторую часть лекций, но первая гораздо интереснее и полезнее. Особое внимание уделите деревьям — нужно уметь на доске написать нормальный алгоритм по любому действию с любым простым деревом, например: «найдите медиану в binary search tree». Я не слышал, чтобы спрашивали про само-балансирующие деревья — так что это просто для развития, тем более что сам Седжвик Self-Balancing Left-Leaning Red-Black Trees и придумал.
Я не большой фанат книг по IT. Сказать точнее — терпеть их не могу. Но для практической подготовки к интервью очень сильно советую книгу Cracking the Coding Interview by Gayle Laakmann McDowell. Среди моих знакомых, все кто использовал эту книгу — получил оффер, никто кто бы не использовал — не получил. N, правда, в этой выборке около 10. В общем, просто купите эту книгу, и прорешайте все 169 задач. Мне одна попалась прямо из книги (правда я ее пропустил — и зря).
5. Не слиться на интервью и подписать оффер.
Если вы получили приглашение на тех. интервью — дело в шляпе! Сначала будет телефонное, с инженером, 45-60 минут; кодить в гуглодоке или другом онлайн блокноте. Тут, конечно, может не повезти, но в целом, ничего сложного. Задачи как в книге.
После этого, если все хорошо, приглашают на кампус, оплачивая все сопутствующие расходы. Там 4-6 тех. интервью с разным инженерами разного уровня. Интервью точно такие же, как и телефонное, только на доске, хотя все зависит от человека — один попросил меня кодить на его ноутбуке. Их фидбек идет в комиссию, которая и принимает решение.
Если вы всем очень понравились — получаете и подписываете оффер. Если понравились, но не до конца очень — возможны варианты. Иногда делают дополнительное интервью, иногда просят рекомендационное письмо. Мне предложили переходную позицию в Engineering Residency, на которую, после еще одного тех. интервью, я и подписал оффер.
Успехов!
Комментарии (43)
Daniyar94
17.01.2016 09:31+1Насчет первого не соглашусь. Тут я получаю BS Computer Science (бакалавр короче) и меня пригласили. Хотя интервью я завалил :) Подучу алгоритмы, и попробую ещё раз через годик.
Вопрос был таким:
Есть сортированный массив с цифрами, которые могут повторяться. Найти число которое повторяется N/4 (где N это размер массива) раз. Я довольно быстро дал решение в polynomial time (n^2). Но мне сказали это сделать в constant time. Там то я и не смог найти решение :)
А так, я их зацепил своим резюме. Довольно обычное резюме со всеми скилами и опытом, которыми я владею. Реферал не обязателен, но с ним 100% шанс получить интервьюSergunka
17.01.2016 10:32Задачка довольно простецкая — делаете проход и складываете количество цифр листом в хешмеп все это делается за O(n) потом когда узнаете размер массива то вытягиваете свой лист одним заходом.
Я по приколу обычно для разогрева когда ищу новую работу прохожу интервью в Гугл всего получилось три раза.
PapaBubaDiop
17.01.2016 13:45+2Решу быстрее Вас в три раза и без хешмапов. Ключевое слово в условии — Сортированный массив цифр…
tvolf
17.01.2016 14:16Интересная задачка. По идее, зная длину массива, можно решить в один проход, но сложность алгоритма все равно не будет O(1)…
soniq
17.01.2016 16:01А хотите О(1)? Так как там одинаковых чисел четверть массива, то достаточно проверить всего 8 чисел — из них пару раз попадем в участок с одинаковыми.
vedenin1980
17.01.2016 16:09Да, но я бы взял тысячу или десять тысяч, чтобы точно убедиться что одинаковых чисел не меньше и не больше N/4. Все равно же будет O(1), даже если проверим миллион, так как от N это не зависит.
soniq
17.01.2016 16:21Ну если сомневаться в корректности условия, то тогда конечно. Но я так понял пересказ условия, что мы можем не проверять, что такое число действительно существует и единственное. И здорово сэкономить на проверках.
tvolf
17.01.2016 17:26То есть, мы разбиваем массив на 8 равных частей и смотрим, есть ли в парах соседних точек одинаковые элементы (и при этом следующие граничные точки не содержат это же значение)? Но при этом, если я правильно понимаю, мы можем только гарантировать, что найденная последовательность имеет длину >= N/8, но не можем гарантировать, что в найденной последовательности ровно N/4 чисел.
Возможно, я в чем-то ошибаюсь.
И даже если рассмотреть случай, когда точек разбиения можно взять больше (миллион! :), то, с одной стороны, это все равно только повышает вероятность нахождения правильного решения, а с другой стороны такая зависимость количества точек разбиения от возможной длины массива уже не может рассматриваться как решение с константной сложностью. То есть, грубо говоря, на каждый вариант разбиения на N точек можно найти массив с кол-вом элементов >= 8 * N.vedenin1980
17.01.2016 17:46Чтобы найти абсолютно точно, можно использовать следующий алгоритм:
1. Разбиваем на N/1000 элементов, считаем кол-во одинаковых последовательностей так чтобы они были от 248 до 250, При 250 проверяем ещё два элемента с краев и заканчиваем алгоритм, O(1)
2. Бинарным поиском находим в отрезке N/1000 первый элемент перед последовательностью, O(logN/1000)
3. Проверяем один элемент с N/4 от найденного в (2), O(1)
Итого, получается пусть и не константное время, но очень близкое к нему O(log N).soniq
17.01.2016 18:05А почему именно 1000? Почему не 512, например? Вот с 8 понятно — меньше просто не имеет смысла. Давайте математическое доказательство или маркетинговое исследование на котором основан ваш выбор коэффициента.
vedenin1980
17.01.2016 18:09На самом деле, коэффициент тут не важен, в любом случае будет сложность будет O(log(n)).
soniq
17.01.2016 18:22int findX(int[] A) { int x, n = 0; for(int i = 1; i < 8; ++i) if(A[i*N/8] == A[(i-1)*N/8] && (i == 7 || A[i*N/8] != A[(i+1)*N/8])) { x = A[i*N/8]; n += 1; } if (n == 0) throw new Exception("No such element"); if (n > 1) throw new Exception(" Too many candidates"); return x; }
Вот такой вот алгоритм за константу. Сначала ищем все подпоследовательности длиннее N/8 и короче 3N/8. Если такая всего одна, а мы знаем что точно есть одна подпоследовательность длинной точно N/4 — то это она и есть. А если похожих больше — ну не судьба значит за константу.tvolf
17.01.2016 18:37Если я правильно понимаю, данный алгоритм находит действительно одну последовательность, но не может гарантировать, что ее длина равна ровно N/4 элементов. Безусловно, мы можем дополнить условие задачи тем, что у нас имеется только один элемент в массиве, для которого выполняется условие, что он встречается от N/8 до 3N/8 раз, и других таких элементов в массиве нет. В этом случае согласен с вашим решением.
Joshua
27.01.2016 18:50Вроде в условии не сказано, что число должно встречаться РОВНО N/4. Тогда за константу можно найти ВСЕ такие последовательности, сколько бы их не было. Максимум все 4 )
Ostrovski
17.01.2016 14:26В любом случае это не const, а O(n). Что-то я не вижу решения за константу, даже у PapaBubaDiop оно линейное.
Daniyar94
17.01.2016 16:53Оу оу оу. Извиняюсь, да я дал им linear time O(n) с hash tables. Довольно стыдно давать polynomial time в такой задаче для четверокурсника :D
Я потом у интервьювера спросил правильный ответ: Он быстро рассказал, что нужно модифицировать binary search, и оно каким-то образом будет показывать первую ячейку повторяющейся цифры и последнюю (и просто вычетаем последнюю от первой и сравниваем c N/4). Он не вдавался в детали, но примерно так. Это занимает constant timevedenin1980
17.01.2016 17:38binary search не может найти даже один элемент быстрее чем O(log N)
Sergunka
17.01.2016 20:43+1Ну, от чего же — а если угадать?! Видимо этот ответ подразумевал проводивший интервью :)
Так или иначе в чувстве юмора обоим сторонам не занимать.
Тем не менее спасибо Daniar94 за то, что оживил секцию вопросов-ответов.
Londoner
17.01.2016 14:16+1За constant time — не получится (будет интересно, если переубедите). Можно сделать, чтоб было минимум O(log n) и максимум O(n), с константной дополнительной памятью.
vedenin1980
17.01.2016 16:07Получится, ключевое слово число повторяется N/4 раз, то есть если размер массива 1 млн. элементов, то таких чисел 250 тыс. и они отсортированы. Алгоритм: делим массив на тысячу частей, считаем кол-во одинаковых чисел, то число которое повторится в нашем массиве от 248 до 250 раз и будет с большой вероятностью искомым. O(1).
Londoner
17.01.2016 16:14Да, соглашусь. Вот почему я в гугле и не работаю. Можно, наверное, взять 8 равноудалённых индексов в массиве. Там где значения совпадают — там и ответ. Так что да, О(1).
mib
17.01.2016 17:54если в массиве есть последовательности длиннее чем N/4, а нужно нейти именно N/4 — то примерные попадания в диапазон могут дать ложные срабатывания
vedenin1980
17.01.2016 18:01Могут, возможно вопрос звучал как не менее чем N/4, тогда это решается за константное время в большинстве случаев. Тут я написал как найти точно за log N в худшем случае (чаще за константное время).
cher11
18.01.2016 01:42А зачем делить на тысячу-то? Если последовательность одинаковых чисел имеет длину N/4, то хватит и гораздо меньшего числа. Наверняка можно вывести минимальное количество таких проверок элементов в массиве, при последовательном попадании последовательности в которые можно 100% утверждать, что такая последовательность — имеется.
vedenin1980
18.01.2016 13:47Смотрите, я вижу там три разных задачи (нужно уточнять у спрашивающего):
1. В массиве есть число, которое повторяется точно N/4 раз. Известно что оно точно есть и такое число только одно.
2. В массиве есть число, которое повторяется не менее чем N/4 раз, найти любое такое число.
3. В массиве может быть число, которое повторяется точно N/4 раз. Найти это число, либо доказать что такого числа в массиве нет.
Первые два решаются в большинстве случаев за константное время (взяв тысячу проверок можно найти эту последовательность с допуском 1% по длине, взяв 10 тыс — с допуском 0,1% и т.д. мало вероятно наличие нескольких подобных последовательностей), третий вариант за O(log N).
Наверняка можно вывести минимальное количество таких проверок элементов в массиве, при последовательном попадании последовательности в которые можно 100% утверждать, что такая последовательность — имеется.
К сожалению, 100% точно решить в третьем случае можно только O(log N) вариантов, за константное количество проверок решить не получится (если я ошибаюсь, расскажите как).cher11
18.01.2016 15:43Моя идея в основном заключалось в том, что:
1) надо пользоваться тем, что массив отсортирован
2) надо хочется проверить как можно меньше элементов
Я бы разбивал массив сначала на меньшее число частей (допустим, на 8) и проверял элементы на их краях — их будет ровно 9.
Если нашлись элементы с одинаковыми числами — значит есть вероятность, что искомая последовательность как раз их содержит
Alexsalo
17.01.2016 20:08> Насчет первого не соглашусь.
Я не имел ввиду обязательность маги; любая степень, конечно, сработает, но просто в магу гораздо проще поступить при отсутствии денег, чем на бакалавра.
> Реферал не обязателен, но с ним 100% шанс получить интервью
Вот тут не соглашусь — был у меня реферал в FB, и резюме же нормальное, но на интервью не пригласили.
yse
18.01.2016 10:59сортированный массив с цифрами
Найти число
Так в массиве цифры или числа? Если только цифры, то можно придумать за O(1), если числа, то вероятно всё-таки O(logN)tvolf
18.01.2016 12:29Вы не могли бы описать суть «константного» алгоритма, если массив состоит исключительно из цифр от 0 до 9? Я надеюсь, это будет интересно не только мне.
yse
18.01.2016 13:40Гм, по ходу я заблуждался. Посидел расписал алгоритм, и понял, что найти ответ об индексе начала и конца числа (или цифры), встречающегося N/4 раз, за константу невозможно. В какой-то момент показалось, что как-то можно подшаманить, если будут только 10 различных значений в массиве. А так O(logN). Извините, кого обнадёжил.
a_batyr
18.01.2016 22:34+1Есть сортированный массив с цифрами, которые могут повторяться. Найти число которое повторяется N/4 (где N это размер массива) раз Цифры десятичные? То есть массив чисел [0..9]? Количество раз ровно N/4? N кратно 4?
Maccimo
17.01.2016 14:11+1>> Правила просты: никаких опечаток, грамотный… попросите знакомого [native speaker] проверить
…
>> инжинера
Да хватило бы и обычной автоматической проверки орфографии в редакторе.
А так — очередной «How to draw an owl».Alexsalo
17.01.2016 20:16Спасибо за ошибку.
Кстати, инженер — очень интересное слово: engineer — чтобы запомнить как писать его на английском, я пришел к проверочному — engine — и дальше просто добавляешь -er. На русском же оно «словарное», и почему пишется именно так, вопреки оригиналу, для меня загадка.
> How to draw an owl
Даже не знаю что ответить. Если какие то вопросы остались не отвеченными — задавайте, сделаю UPD.alan008
17.01.2016 20:57+1Есть информация, что один из вариантов происхождения слова «инженер» — это латинское слово ingenium (врожденная способность).
Sergunka
Саша, расскажите за бабосы? Сколько дали на старт… ну и прочие мелкие радости — какое меню в столовой как часто пользуетесь прачечной. Насколько ситуация описанная в сериале Silicon Valley соответствует реальности на местности.
vedenin1980
Никто вам этого не расскажет, во всех крупных компаниях, насколько я знаю, такая информация относится к особо конфиденциальной и за её разглашение легко лишиться работы.
Alexsalo
Все верно, но это касается точных деталей. Ориентировочно нормальные люди всегда говорят :)
idiv
Недавно смотрел Adam Ruins Everything про США, так там обсуждалось что-то вроде, что скрытие уровня зарплаты ведет к дискриминации и запрещать ее озвучивать — незаконно. Разве не так?
shoumikhin
Ой, я вас умоляю.
j.mp/salaries-list
duxa
Подскажите, откуда данные?
shoumikhin
Они доступны в открытом виде на сайтах flcdatacenter.com и data.gov.
Нужно только извлечь для интересующих компаний.
numberfive
по российским законам, уровень заработной платы нельзя отнести к коммерческой тайне, как нельзя наказывать за распространение этой информации (своей зп), поэтому это вопрос рынка трудоустройства, а не «всех крупных компаний»
Alexsalo
Про деньги без проблем находится на GlassDoor, зарплаты в гугл. Моя позиция Resident Engineer, зп чуть выше потому что в Калифорнии, а там средняя по разным штатам.
Когда полный оффер получаешь, дополнительно стоки дают, об этом тоже на гласдоре есть.
Мелких радостей очень много: бесплатная хорошая еда, например, в столовых в любое время — для меня самое главное. Вообще про это я как нибудь отдельный пост напишу.