Пользователь
0,0
рейтинг
17 января в 03:16

Управление → Как получить работу в Google?

image
Очевидно, что способов много, но этот, на мой взгляд, является оптимально простым, дешевым и интересным.

Алгоритм:
  1. Поступить в магистратуру в США.
  2. Сделать не кривое резюме.
  3. Найти реферал.
  4. Подготовится к интервью.
  5. Не слиться на интервью и подписать оффер.

И всё!

Теперь про каждый шаг подробнее.

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, на которую, после еще одного тех. интервью, я и подписал оффер.

Успехов!
Александр Сало @Alexsalo
карма
5,0
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Управление

Комментарии (51)

  • +2
    Саша, расскажите за бабосы? Сколько дали на старт… ну и прочие мелкие радости — какое меню в столовой как часто пользуетесь прачечной. Насколько ситуация описанная в сериале Silicon Valley соответствует реальности на местности.
    • 0
      Никто вам этого не расскажет, во всех крупных компаниях, насколько я знаю, такая информация относится к особо конфиденциальной и за её разглашение легко лишиться работы.
      • 0
        Все верно, но это касается точных деталей. Ориентировочно нормальные люди всегда говорят :)
      • 0
        Недавно смотрел Adam Ruins Everything про США, так там обсуждалось что-то вроде, что скрытие уровня зарплаты ведет к дискриминации и запрещать ее озвучивать — незаконно. Разве не так?
      • +1
        Ой, я вас умоляю.
        j.mp/salaries-list
        • 0
          Подскажите, откуда данные?
          • 0
            Они доступны в открытом виде на сайтах flcdatacenter.com и data.gov.
            Нужно только извлечь для интересующих компаний.
      • 0
        по российским законам, уровень заработной платы нельзя отнести к коммерческой тайне, как нельзя наказывать за распространение этой информации (своей зп), поэтому это вопрос рынка трудоустройства, а не «всех крупных компаний»
    • +1
      Про деньги без проблем находится на GlassDoor, зарплаты в гугл. Моя позиция Resident Engineer, зп чуть выше потому что в Калифорнии, а там средняя по разным штатам.

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

      Мелких радостей очень много: бесплатная хорошая еда, например, в столовых в любое время — для меня самое главное. Вообще про это я как нибудь отдельный пост напишу.
  • +1
    Насчет первого не соглашусь. Тут я получаю BS Computer Science (бакалавр короче) и меня пригласили. Хотя интервью я завалил :) Подучу алгоритмы, и попробую ещё раз через годик.

    Вопрос был таким:
    Есть сортированный массив с цифрами, которые могут повторяться. Найти число которое повторяется N/4 (где N это размер массива) раз. Я довольно быстро дал решение в polynomial time (n^2). Но мне сказали это сделать в constant time. Там то я и не смог найти решение :)

    А так, я их зацепил своим резюме. Довольно обычное резюме со всеми скилами и опытом, которыми я владею. Реферал не обязателен, но с ним 100% шанс получить интервью
    • 0
      Задачка довольно простецкая — делаете проход и складываете количество цифр листом в хешмеп все это делается за O(n) потом когда узнаете размер массива то вытягиваете свой лист одним заходом.
      Я по приколу обычно для разогрева когда ищу новую работу прохожу интервью в Гугл всего получилось три раза.
      • +2
        Решу быстрее Вас в три раза и без хешмапов. Ключевое слово в условии — Сортированный массив цифр
        • 0
          Интересная задачка. По идее, зная длину массива, можно решить в один проход, но сложность алгоритма все равно не будет O(1)…
          • 0
            А хотите О(1)? Так как там одинаковых чисел четверть массива, то достаточно проверить всего 8 чисел — из них пару раз попадем в участок с одинаковыми.
            • 0
              Да, но я бы взял тысячу или десять тысяч, чтобы точно убедиться что одинаковых чисел не меньше и не больше N/4. Все равно же будет O(1), даже если проверим миллион, так как от N это не зависит.
              • 0
                Ну если сомневаться в корректности условия, то тогда конечно. Но я так понял пересказ условия, что мы можем не проверять, что такое число действительно существует и единственное. И здорово сэкономить на проверках.
            • 0
              То есть, мы разбиваем массив на 8 равных частей и смотрим, есть ли в парах соседних точек одинаковые элементы (и при этом следующие граничные точки не содержат это же значение)? Но при этом, если я правильно понимаю, мы можем только гарантировать, что найденная последовательность имеет длину >= N/8, но не можем гарантировать, что в найденной последовательности ровно N/4 чисел.
              Возможно, я в чем-то ошибаюсь.
              И даже если рассмотреть случай, когда точек разбиения можно взять больше (миллион! :), то, с одной стороны, это все равно только повышает вероятность нахождения правильного решения, а с другой стороны такая зависимость количества точек разбиения от возможной длины массива уже не может рассматриваться как решение с константной сложностью. То есть, грубо говоря, на каждый вариант разбиения на N точек можно найти массив с кол-вом элементов >= 8 * N.
              • 0
                Чтобы найти абсолютно точно, можно использовать следующий алгоритм:
                1. Разбиваем на N/1000 элементов, считаем кол-во одинаковых последовательностей так чтобы они были от 248 до 250, При 250 проверяем ещё два элемента с краев и заканчиваем алгоритм, O(1)
                2. Бинарным поиском находим в отрезке N/1000 первый элемент перед последовательностью, O(logN/1000)
                3. Проверяем один элемент с N/4 от найденного в (2), O(1)

                Итого, получается пусть и не константное время, но очень близкое к нему O(log N).
                • 0
                  А почему именно 1000? Почему не 512, например? Вот с 8 понятно — меньше просто не имеет смысла. Давайте математическое доказательство или маркетинговое исследование на котором основан ваш выбор коэффициента.
                  • 0
                    На самом деле, коэффициент тут не важен, в любом случае будет сложность будет O(log(n)).
              • 0
                int 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 — то это она и есть. А если похожих больше — ну не судьба значит за константу.
                • 0
                  Если я правильно понимаю, данный алгоритм находит действительно одну последовательность, но не может гарантировать, что ее длина равна ровно N/4 элементов. Безусловно, мы можем дополнить условие задачи тем, что у нас имеется только один элемент в массиве, для которого выполняется условие, что он встречается от N/8 до 3N/8 раз, и других таких элементов в массиве нет. В этом случае согласен с вашим решением.
                  • 0
                    Вроде в условии не сказано, что число должно встречаться РОВНО N/4. Тогда за константу можно найти ВСЕ такие последовательности, сколько бы их не было. Максимум все 4 )
                    • 0
                      ===
                      Найти число которое повторяется N/4 (где N это размер массива) раз.
                      ===
                      Да, нет слова «РОВНО», но, по-моему, оно тут и не нужно, так как и без него условие очевидно.
                      • 0
                        Условие не очевидно, есть два варианта: 1) известно что такое число точно существует в массиве 2) такое число может существовать, а может и не сушествовать. И решения будет различны в этих случаях, в первом варианте возможно решение за константное время в 99.9% случаев, во втором не сумел придумать решения быстрее чем O(log N)
                        • 0
                          =) Даже если есть хоть 1 возможный вариант из миллиарда, когда алгоритм будет работать не по «константной» схеме, значит, он «неконстантный». Потому что ты не можешь гарантировать константное время его работы для любых произвольных данных. Это как если бы ты в произвольном алгоритме сортировки сначала всегда проверял все пары соседних элементов, а не находится ли входной массив уже в отсортированном порядке. Такие случаи вполне могут быть. Но это не значит, что сложность алгоритма сортировки станет считаться как O(N), верно?

                          • 0
                            Совершенно не верно, есть такие понятие как вычисли́тельная сложность алгоритма в худшем, наилучшем и среднем случае. Если есть хоть 1 возможный вариант из миллиарда, когда алгоритм будет работать не по «константной» схеме, значит, он «неконстантный» в худшем случае, но константный в среднем.

                            Многие современные алгоритмы в худшем случае имеют очень высокую сложность, но зато в среднем вполне нормальную и учитывая редкость этого самого худшего случая, их активно используют. Банально большинство хештаблиц в худшем случае имеют дают доступ к элементу со сложностью N (полный перебор), но так как это очень редкий случай, а в среднем сложность около O(1) на них построены все базы данных.
                            • 0
                              Понятно. Значит я имел ввиду вычислительную сложность для худшего случая.
                        • 0
                          Кстати, буду признателен, если вы приведете алгоритм, который в 99.9% будет иметь «константное» решение для случая, когда заранее известно, что некоторый элемент точно присутствует в массиве и встречается там N/4 раз. Просто почему я сомневаюсь в этом. Для того, чтобы алгоритм обеспечивал чаще константное решение, необходимо после разбиения на фиксированное кол-во точек и поиске цепочки подходящей длины, проверять только соседние точки (без переборов и двоичных поисков). Повысить вероятность этого можно только увеличением кол-ва точек разбиения (вырожденный случай, дающий 100% вероятность — когда количество точек разбиения равно размерности самого массива). В этом случае вероятность выше, но тогда нельзя сказать, что алгоритм «константен», потому как с увеличением размерности массива придется всегда увеличивать кол-во точек разбиения для получения высокой вероятности. А если число точек разбиения не увеличивать, то, соответствнно, и вероятность будет значительно ниже. Но я подожду вашего решения.
                          • 0
                            Смотрите, тут все зависит от распределения остальных чисел, но представим что оно более или менее случайно, то есть у нас есть один массив чисел N/4 и M массивов чисел со случайными длинами от 0 до 3N/4. Вероятность наличия последовательности M, которая больше или меньше N/4 на 1% длины пусть будет 1%, на 0.1% длины — 0.1% и т.д. (само значение вероятности не так важно, важен принцип). Тогда разделив все последовательность на 2000 точек по длине, мы сможем найти потенциальную последовательность и с вероятностью 0.1% она будет только одна. Разделив на 20 тыс — вероятность будет 0.01% и т.д. Само значение N тут роли не играет.

                            Проблема будет только в том что кто-то будет сознательно готовить плохие данные добавляя одну последовательность вроде N/4+1 или N/4-1, тогда придется один из концов искать быстрым поиском с log N. Но это уже из раздела обмануть алгоритм плохими данными. При любом относительно случайном распределении длин такое маловероятно.
                            • 0
                              Честно говоря, не совсем понял, откуда вы взяли все эти цифры, в частности 2000 точек и связанные с ними 0.1%. Ну ладно, не суть. Давайте по-простому. У нас есть массив из 80 точек (цифра взята просто для удобства последующего деления). В нем есть некоторая последовательность из 20 одинаковых элементов. Предположим, мы решили взять шаг разбиения в 10 элементов. Таким образом, наш массив поделен на 8 равных частей, каждая часть состоит из 10 точек. Мы перебираем пары соседних точек и смотрим, чтобы элементы массива в них имели одинаковые значения, а соседние с ними элементы были не равны им. Найдя такую пару точек мы можем предположить, что в этом месте расположена последовательность нужной нам длины. Искать реальные концы последовательности мы не можем, так как в этом случае будет нарушено требование «константной» временной сложности. Фактически же длина найденной нами последовательности может быть в дианазоне от 10 до 30 точек (то есть, от N/8 до 3N/8). И вероятность нашего «угадывания» составляет 1/20 (1 вариант из 20 возможных) или 5%.
                              Конечно, мы можем разделить массив с шагом не 10, а, например, 5, получая не 8, а 16 точек разбиения. В этом случае, вероятность угадывания составит уже 10%. Таким образом, увеличивая количество точек разбиения мы повышаем вероятность правильного ответа. Но в этом случае, как я уже писал ранее, наш алгоритм приобретает все более «линейную» сложность., так как для получения требуемой вероятности правильного ответа нам нужно будет постоянно увеличивать количество точек разбиения при увеличении количества элементов входного массива.
                              Ну и по поводу «плохих» данных. Разумеется, во входном массиве могут быть как N/4+1, так и N/4-1, N/4-2 и прочие последовательности указанных длин. В общем, любые последовательности длины от N/8 до 3N/8 включительно. Ничего противоестественного в таких наборах нет и говорить об исключительности этой ситуации весьма странно, на мой взгляд.
      • 0
        В любом случае это не const, а O(n). Что-то я не вижу решения за константу, даже у PapaBubaDiop оно линейное.
      • 0
        Оу оу оу. Извиняюсь, да я дал им linear time O(n) с hash tables. Довольно стыдно давать polynomial time в такой задаче для четверокурсника :D

        Я потом у интервьювера спросил правильный ответ: Он быстро рассказал, что нужно модифицировать binary search, и оно каким-то образом будет показывать первую ячейку повторяющейся цифры и последнюю (и просто вычетаем последнюю от первой и сравниваем c N/4). Он не вдавался в детали, но примерно так. Это занимает constant time
        • 0
          binary search не может найти даже один элемент быстрее чем O(log N)
          • +1
            Ну, от чего же — а если угадать?! Видимо этот ответ подразумевал проводивший интервью :)
            Так или иначе в чувстве юмора обоим сторонам не занимать.

            Тем не менее спасибо Daniar94 за то, что оживил секцию вопросов-ответов.
    • +1
      За constant time — не получится (будет интересно, если переубедите). Можно сделать, чтоб было минимум O(log n) и максимум O(n), с константной дополнительной памятью.
      • 0
        Получится, ключевое слово число повторяется N/4 раз, то есть если размер массива 1 млн. элементов, то таких чисел 250 тыс. и они отсортированы. Алгоритм: делим массив на тысячу частей, считаем кол-во одинаковых чисел, то число которое повторится в нашем массиве от 248 до 250 раз и будет с большой вероятностью искомым. O(1).
        • 0
          Да, соглашусь. Вот почему я в гугле и не работаю. Можно, наверное, взять 8 равноудалённых индексов в массиве. Там где значения совпадают — там и ответ. Так что да, О(1).
        • 0
          если в массиве есть последовательности длиннее чем N/4, а нужно нейти именно N/4 — то примерные попадания в диапазон могут дать ложные срабатывания
          • 0
            Могут, возможно вопрос звучал как не менее чем N/4, тогда это решается за константное время в большинстве случаев. Тут я написал как найти точно за log N в худшем случае (чаще за константное время).
        • 0
          А зачем делить на тысячу-то? Если последовательность одинаковых чисел имеет длину N/4, то хватит и гораздо меньшего числа. Наверняка можно вывести минимальное количество таких проверок элементов в массиве, при последовательном попадании последовательности в которые можно 100% утверждать, что такая последовательность — имеется.
          • 0
            Смотрите, я вижу там три разных задачи (нужно уточнять у спрашивающего):
            1. В массиве есть число, которое повторяется точно N/4 раз. Известно что оно точно есть и такое число только одно.
            2. В массиве есть число, которое повторяется не менее чем N/4 раз, найти любое такое число.
            3. В массиве может быть число, которое повторяется точно N/4 раз. Найти это число, либо доказать что такого числа в массиве нет.

            Первые два решаются в большинстве случаев за константное время (взяв тысячу проверок можно найти эту последовательность с допуском 1% по длине, взяв 10 тыс — с допуском 0,1% и т.д. мало вероятно наличие нескольких подобных последовательностей), третий вариант за O(log N).

            Наверняка можно вывести минимальное количество таких проверок элементов в массиве, при последовательном попадании последовательности в которые можно 100% утверждать, что такая последовательность — имеется.

            К сожалению, 100% точно решить в третьем случае можно только O(log N) вариантов, за константное количество проверок решить не получится (если я ошибаюсь, расскажите как).
            • 0
              Моя идея в основном заключалось в том, что:
              1) надо пользоваться тем, что массив отсортирован
              2) надо хочется проверить как можно меньше элементов
              Я бы разбивал массив сначала на меньшее число частей (допустим, на 8) и проверял элементы на их краях — их будет ровно 9.
              Если нашлись элементы с одинаковыми числами — значит есть вероятность, что искомая последовательность как раз их содержит
    • 0
      > Насчет первого не соглашусь.
      Я не имел ввиду обязательность маги; любая степень, конечно, сработает, но просто в магу гораздо проще поступить при отсутствии денег, чем на бакалавра.

      > Реферал не обязателен, но с ним 100% шанс получить интервью
      Вот тут не соглашусь — был у меня реферал в FB, и резюме же нормальное, но на интервью не пригласили.
    • 0
      сортированный массив с цифрами

      Найти число


      Так в массиве цифры или числа? Если только цифры, то можно придумать за O(1), если числа, то вероятно всё-таки O(logN)
      • 0
        Вы не могли бы описать суть «константного» алгоритма, если массив состоит исключительно из цифр от 0 до 9? Я надеюсь, это будет интересно не только мне.
        • 0
          Гм, по ходу я заблуждался. Посидел расписал алгоритм, и понял, что найти ответ об индексе начала и конца числа (или цифры), встречающегося N/4 раз, за константу невозможно. В какой-то момент показалось, что как-то можно подшаманить, если будут только 10 различных значений в массиве. А так O(logN). Извините, кого обнадёжил.
    • +1
      Есть сортированный массив с цифрами, которые могут повторяться. Найти число которое повторяется N/4 (где N это размер массива) раз Цифры десятичные? То есть массив чисел [0..9]? Количество раз ровно N/4? N кратно 4?
  • +1
    >> Правила просты: никаких опечаток, грамотный… попросите знакомого [native speaker] проверить

    >> инжинера

    Да хватило бы и обычной автоматической проверки орфографии в редакторе.

    А так — очередной «How to draw an owl».
    • 0
      Спасибо за ошибку.

      Кстати, инженер — очень интересное слово: engineer — чтобы запомнить как писать его на английском, я пришел к проверочному — engine — и дальше просто добавляешь -er. На русском же оно «словарное», и почему пишется именно так, вопреки оригиналу, для меня загадка.

      > How to draw an owl
      Даже не знаю что ответить. Если какие то вопросы остались не отвеченными — задавайте, сделаю UPD.
      • +1
        Есть информация, что один из вариантов происхождения слова «инженер» — это латинское слово ingenium (врожденная способность).

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