Задачи на собеседовании гугл: Разбор задачи с собеседования в Google: синонимичные запросы / Хабр

Разбор задачи с собеседования в Google: синонимичные запросы / Хабр

Это новая статья из разбора задач с собеседований в Google. Когда я там работал, то предлагал кандидатам такие задачи. Потом произошла утечка, и их запретили. Но у медали есть обратная сторона: теперь я могу свободно объяснить решение.

Для начала отличные новости: я ушёл из Google! Рад сообщить, что теперь работаю техническим руководителем Reddit в Нью-Йорке! Но эта серия статей всё равно получит продолжение.

Дисклеймер: хотя собеседование кандидатов является одной из моих профессиональных обязанностей, в этом блоге я делюсь личными наблюдениями, историями и личным мнением. Пожалуйста, не считайте это официальным заявлением Google, Alphabet, Reddit, любого другого лица или организации.

После двух последних статей о ходе конём в наборе телефонного номера мне пришли критические замечания, что это не реалистичная проблема. Как ни полезно изучить навыки мышления кандидата, но вынужден признать: задача действительно немного нереалистичная. Хотя у меня есть некоторые мысли по поводу корреляции между вопросами на собеседованиях и реальностью, но я пока оставлю их при себе. Будьте уверены, я везде читаю комментарии и мне есть что ответить, только не сейчас.

Но когда задачу про ход конём запретили несколько лет назад, я принял критику близко к сердцу и попытался заменить её вопросом, который немного больше относится к сфере деятельности Google. А что может актуальнее для Google, чем механика поисковых запросов? Так я нашёл этот вопрос и долгое время его использовал, прежде чем он тоже попал в паблик и был запрещён. Как и прежде, я сформулирую вопрос, погружусь в его объяснение, а затем расскажу, как использовал его на собеседованиях и почему он мне нравится.

Итак, вопрос.

Представьте, что вы управляете популярной поисковой системой и в логах видите два запроса: скажем, «рейтинги одобрения Обамы» и «уровень популярности Обамы» (если я правильно помню, это реальные примеры из базы вопросов, хотя сейчас они немного устарели…). Мы видим разные запросы, но все согласятся: пользователи ищут по сути одну и ту же информацию, так что запросы следует считать эквивалентными при подсчёте количества запросов, показа результатов и т. д. Как определить, что два запроса являются синонимами?

Давайте формализуем задачу. Предположим, есть два набора пар строк: пары синонимов и пары запросы.

Если говорить конкретно, вот пример входных данных для иллюстрации:

SYNONYMS = [
  ('rate', 'ratings'),
  ('approval', 'popularity'),
]

QUERIES = [
  ('obama approval rate', 'obama popularity ratings'),
  ('obama approval rates', 'obama popularity ratings'),
  ('obama approval rate', 'popularity ratings obama')
]

Нужно выдать список логических значений: являются ли синонимичными запросы в каждой паре.
На первый взгляд, это простая задача. Но чем дольше думаете, тем сложнее она становится. Может ли у слова быть несколько синонимов? Имеет ли значение порядок слов? Являются ли синонимичные отношения транзитивными, то есть если А синонимично B, а B синономично С, то является ли А синонимом С? Могут ли синонимы охватывать несколько слов, как «США» является синонимом для фраз «Соединённые Штаты Америки» или «Соединённые Штаты»?

Такая неоднозначность сразу даёт возможность проявить себя хорошему кандидату. Первое, что он делает — выискивает такие двусмысленности и пытается их разрешить. Все делают это по-разному: одни подходят к доске и пытаются вручную решить конкретные случаи, а другие смотрят на вопрос и сразу видят пробелы. В любом случае, выявление этих проблем на раннем этапе имеет решающее значение.

Фаза «понимания проблемы» имеет большое значение. Я люблю называть программную инженерию фрактальной дисциплиной. Как у фракталов, приближение раскрывает дополнительную сложность. Вы думаете, что понимаете проблему, потом смотрите поближе — и видите, что упустили какую-то тонкость или деталь реализации, которую можно улучшить. Или другой подход к проблеме.

Множество Мандельброта

Калибр инженера во многом определяется тем, насколько глубоко он может понять проблему. Преобразовать расплывчатую постановку задачи в подробный набор требований — первый шаг в этом процессе, и умышленная недосказанность позволяет оценить, насколько хорошо кандидат подходит к новым ситуациям.

Оставим в стороне тривиальные вопросы, вроде «Имеют ли значение заглавные буквы?», которые не влияют на основной алгоритм. На эти вопросы я всегда даю самый простой ответ (в этом случае «Предположим, что все буквы уже предварительно обработаны и приведены к строчным»)

Если кандидаты задают вопросы, я всегда начинаю с самого простого случая: у слова может быть несколько синонимов, порядок слов имеет значение, синонимы не транзитивны. Это даёт довольно ограниченную функциональность поисковой системе, но в ней достаточно тонкостей для интересного собеседования.

Высокоуровневый обзор выглядит следующим образом: разбейте запрос на слова (например, по пробелам) и сравните соответствующие пары для поиска идентичных слов и синонимов. Визуально это выглядит так:

В коде:

def synonym_queries(synonym_words, queries):
    '''
    synonym_words: iterable of pairs of strings representing synonymous words
    queries: iterable of pairs of strings representing queries to be tested for 
             synonymous-ness
    '''
    output = []
    for q1, q2 in queries:
        q1, q2 = q1.split(), q2.split()
        if len(q1) != len(q2):
            output.append(False)
            continue
        result = True
        for i in range(len(q1)):
            w1, w2 = q1[i], q2[i]
            if w1 == w2:
                continue
            elif words_are_synonyms(w1, w2):
                continue
            result = False
            break
        output.append(result)
    return output

Легко, правда? Алгоритмически это довольно просто. Никакого динамического программирования, рекурсии, сложных структур и т. д. Простая манипуляция стандартной библиотекой и алгоритм, который работает за линейное время, верно?

Но здесь больше нюансов, чем кажется на первый взгляд. Безусловно, самым сложным компонентом является сравнение синонимов. Хотя компонент прост в понимании и описании, существует много способов ошибиться. Расскажу о наиболее распространённых ошибках.

Для ясности: никакие ошибки не дисквалифицируют кандидата; если что, я просто указываю на ошибку в реализации, он исправляет, и мы идём дальше. Однако собеседование — это, прежде всего, борьба со временем. Вы будете делать, замечать и исправлять ошибки, но это отнимает время, которое можно потратить на другое, например, на создание более оптимального решения. Практически все совершают ошибки, это нормально, но кандидаты, которые делают их меньше, показывают лучший результат просто потому, что тратят меньше времени исправления.

Вот почему мне нравится эта проблема. Если ход конём требует озарения в понимании алгоритма, а затем (надеюсь) простой реализации, то здесь решение — это множество шажков в правильном направлении. Каждый шаг представляет крошечное препятствие, через которое кандидат может либо изящно перепрыгнуть, либо споткнуться и подняться. Хорошие кандидаты благодаря опыту и интуиции избегают этих маленьких ловушек — и получают более подробное и правильное решение, в то время как более слабые тратят время и энергию на ошибки и обычно остаются с ошибочным кодом.

На каждом собеседовании я видел разное сочетание успехов и провалов, вот самые распространённые ошибки.

Случайные убийцы производительности

Во-первых, некоторые кандидаты реализовали обнаружение синонимов с помощью простого обхода списка синонимов:

...
elif (w1, w2) in synonym_words:
  continue
...

На первый взгляд, это кажется разумным. Но при ближайшем рассмотрении идея оказывается очень, очень плохой. Для тех из вас, кто не знает Python, ключевое слово in — синтаксический сахар для метода contains и работает над всеми стандартными контейнерами Python. Это проблема, потому что synonym_words — список, который реализует ключевое слово in с помощью линейного поиска. Пользователи Python особенно чувствительны к этой ошибке, потому что язык скрывает типы, но пользователи C++ и Java тоже иногда делали похожие ошибки.

За всю карьеру я всего несколько раз писал код с линейным поиском, и каждый по списку длиной не более двух десятков элементов. И даже в этом случае писал длинный комментарий с объяснением, почему выбрал такой, казалось бы, неоптимальный подход. Подозреваю, что некоторые кандидаты использовали его просто потому что не знали, как работает со списками ключевое слово in в стандартной библиотеке Python. Это простая ошибка, не фатальная, но плохое знакомство с любимым языком — не очень хорошо.

На практике этой ошибки легко избежать. Во-первых, никогда не забывайте типы своих объектов, даже если используете нетипизированный язык, такой как Python! Во-вторых, помните, что при использовании ключевого слова in в списке запускается линейный поиск. Если нет гарантии, что этот список всегда останется очень маленьким, он убьёт производительность.

Чтобы кандидат опомнился, обычно достаточно напомнить ему, что входная структура является списком. Очень важно наблюдать, как кандидат реагирует на подсказку. Лучшие кандидаты сразу пытаются как-то предварительно обработать синонимы, что является хорошим началом. Однако этот подход не лишён своих подводных камней…

Используйте правильную структуру данных

Из приведённого выше кода сразу видно, что для реализации этого алгоритма в линейное время необходимо быстро находить синонимы. А когда мы говорим о быстром поиске, это всегда карта или массив хэшей.

Мне не важно, выберет кандидат карту или массив хэшей. Важно то, что он туда вложит (кстати, никогда не используйте dict/hashmap с переходом в True или False). Большинство кандидатов выбирают какой-то dict/hashmap. Самая распространённая ошибка — подсознательное предположение, что у каждого слова не больше одного синонима:

...
synonyms = {}
for w1, w2 in synonym_words:
  synonyms[w1] = w2
...
elif synonyms[w1] == w2:
  continue 

Я не наказываю кандидатов за эту ошибку. Задача специально сформулирована так, чтобы не заострять внимание на том, что у слов может быть несколько синонимов, а некоторые кандидаты просто не сталкивались с такой ситуацией. Большинство быстро исправляет ошибку, когда я на неё указываю. Хорошие кандидаты замечают её на раннем этапе и обычно не тратят много времени.

Чуть более серьёзная проблема — неосознание, что отношения синонимов распространяются в обоих направлениях. Заметьте, что в приведённом выше коде это учитывается. Но встречаются реализации с ошибкой:

...
synonyms = defaultdict(set)
for w1, w2 in synonym_words:
  synonyms[w1].append(w2)
  synonyms[w2].append(w1)
...
elif w2 in synonyms.get(w1, tuple()):
  continue

Зачем выполнять две вставки и использовать в два раза больше памяти?

...
synonyms = defaultdict(set)
for w1, w2 in synonym_words:
  synonyms[w1].append(w2)
...
elif (w2 in synonyms.get(w1, tuple()) or
    w1 in synonyms.get(w2, tuple())):
  continue

Вывод: всегда думайте, как оптимизировать код! В ретроспективе перестановка функций поиска является очевидной оптимизацией, в ином случае можно сделать вывод, что кандидат не думал над вариантами оптимизации. Опять же, я рад дать подсказку, но лучше догадаться самому.
Некоторые умные кандидаты хотят отсортировать список синонимов, а затем использовать двоичный поиск. На самом деле у такого подхода есть важное преимущество: он не требует дополнительного пространства, кроме списка синонимов (при условии, что допускается изменение списка).

К сожалению, мешает сложность по времени: сортировка списка синонимов требует Nlog(N) времени, а затем ещё log(N) для поиска каждой пары синонимов, в то время как описанное решение предварительной обработки происходит в линейном, а затем постоянном времени. Кроме того, я категорически против того, чтобы заставлять кандидата реализовать сортировку и двоичный поиск на доске, потому что: 1) алгоритмы сортировки хорошо известны, поэтому, насколько я знаю, кандидат может выдать его не думая; 2) эти алгоритмы дьявольски сложно правильно реализовать, и часто даже лучшие кандидаты будут делать ошибки, которые ничего не говорят об их навыках программирования.

Всякий раз, когда кандидат предлагал такое решение, я интересовался временем выполнения программы и спрашивал, есть ли вариант лучше. Для информации: если интервьюер спрашивает вас, есть ли вариант лучше, почти всегда ответ «да». Если я когда-нибудь задам вам этот вопрос, ответ точно будет таким.

Наконец, решение

В конце концов кандидат предлагает что-то правильное и достаточно оптимальное. Вот реализация в линейном времени и линейном пространстве для заданных условий:

def synonym_queries(synonym_words, queries):
    '''
    synonym_words: iterable of pairs of strings representing synonymous words
    queries: iterable of pairs of strings representing queries to be tested for 
             synonymous-ness
    '''
    synonyms = defaultdict(set)
    for w1, w2 in synonym_words:
        synonyms[w1].add(w2)

    output = []
    for q1, q2 in queries:
        q1, q2 = q1.split(), q2.split()
        if len(q1) != len(q2):
            output.append(False)
            continue
        result = True
        for i in range(len(q1)):
            w1, w2 = q1[i], q2[i]
            if w1 == w2:
                continue
            elif ((w1 in synonyms and w2 in synonyms[w1]) 
                    or (w2 in synonyms and w1 in synonyms[w2])):
                continue
            result = False
            break
        output.append(result)
    return output

Несколько быстрых замечний:

• Обратите внимание на использование dict.get(). Вы можете реализовать проверку, находится ли ключ в dict, а затем получить его, но это усложнённый подход, хотя таким образом вы покажете свои знания стандартной библиотеки.
• Я лично не поклонник кода с частыми continue, и некоторые руководства по стилю запрещают или не рекомендуют их. Я сам в первой редакции этого кода забыл оператор continue после проверки длины запроса. Это не плохой подход, просто знайте, что он подвержен ошибкам.

У хороших кандидатов после решения задачи остаётся ещё десять-пятнадцать минут времени. К счастью, есть куча дополнительных вопросов, хотя вряд ли мы напишем много кода за это время. Впрочем, в этом нет необходимости. Я хочу знать о кандидате две вещи: способен ли он разрабатывать алгоритмы и умеет ли кодировать? Задача с ходом конём сначала отвечает на вопрос о разработке алгоритма, а затем проверяет кодирование, а здесь мы получаем ответы в обратном порядке.

К тому времени, когда кандидат завершил первую часть вопроса, он уже решил проблему с (удивительно нетривиальным) кодированием. На этом этапе я могу с уверенностью говорить о его способности разрабатывать рудиментарные алгоритмы и переводить идеи в код, а также о знакомстве со своим любимым языком и стандартной библиотекой. Теперь разговор становится намного интереснее, потому что требования к программированию можно смягчить, а мы погрузимся в алгоритмы.

С этой целью вернёмся к основным постулатам первой части: важен порядок слов, синонимы нетранзитивны и для каждого слова может быть несколько синонимов. По мере продвижения интервью я изменяю каждое из этих ограничений, и в этой новой фазе у нас с кандидатом происходит чисто алгоритмическое обсуждение. Здесь я приведу примеры кода, чтобы проиллюстрировать свою точку зрения, но в реальном интервью мы говорим только об алгоритмах.

Прежде чем начать, объясню свою позицию: все последующие действия на этом этапе интервью — в основном, «бонусные баллы». Мой личный подход заключается в выявлении кандидатов, которые точно проходят первый этап и подходят для работы. Второй этап нужен для выделения самых лучших. Первый рейтинг уже очень сильный и означает, что кандидат достаточно хорош для компании, а второй рейтинг говорит, что кандидат превосходен и его найм станет для нас большой победой.

Сначала я люблю снять ограничение на транзитивность, так что если синонимами являются пары A−B и В−С, то слова A и C тоже являются синонимами. Сообразительные кандидаты быстро поймут, как адаптировать своё предыдущее решение, хотя при дальнейшем снятии других ограничений основная логика алгоритма перестанет работать.

Тем не менее, как его адаптировать? Один из распространённых подходов — поддерживать полный набор синонимов для каждого слова на основе транзитивных отношений. Каждый раз, когда мы вставляем слово в набор синонимов, мы также добавляем его в соответствующие наборы для всех слов, находящихся в этом наборе:

synonyms = defaultdict(set)
for w1, w2 in synonym_words:
    for w in synonyms[w1]:
        synonyms[w].add(w2)
    synonyms[w1].add(w2)
    for w in synonyms[w2]:
        synonyms[w].add(w1)
    synonyms[w2].add(w1)

Обратите внимание, что создавая код, мы уже углубились в это решение

Это решение работает, но далеко не оптимально. Чтобы понять причины, оценим пространственную сложность этого решения. Каждый синоним нужно добавить не только к набору начального слова, но и к наборам всех его синонимов. Если синоним один, то добавляется одна запись. Но если у нас 50 синонимов, придётся добавить 50 записей. На рисунке это выглядит следующим образом:

Обратите внимание, что мы перешли от трёх ключей и шести записей к четырём ключам и двенадцати записям. Слово с 50 синонимами потребует 50 ключей и почти 2500 записей. Необходимое пространство для представления одного слова квадратично растёт с увеличением набора синонимов, что довольно расточительно.

Есть и другие решения, но не буду слишком углубляться, чтобы не раздувать статью. Наиболее интересное из них — использование структуры данных синонимов для построения ориентированного графа, а затем поиск в ширину для нахождения пути между двумя словами. Это прекрасное решение, но поиск становится линейным по размеру набора синонимов для слова. Поскольку мы выполняем этот поиск для каждого запроса несколько раз, такой подход не оптимален.

Оказывается, поиск синонимов возможен за (почти) постоянное время благодаря структуре данных под названием непересекающиеся множества (disjoint set). Эта структура предлагает несколько иные возможности, чем обычный набор данных (set).

Обычная структура набора (hashset, treeset) представляет собой контейнер, который позволяет быстро определить, находится объект внутри или вне его. Непересекающиеся множества решают совсем иную проблему: вместо определения конкретного элемента они позволяют определить, принадлежат ли два элемента одному набору. Более того, структура делает это за с ослепительно быстрое время O(a(n)), где a(n) — обратная функция Аккермана. Если вы не изучали продвинутые алгоритмы, то можете не знать эту функцию, которая для всех разумных входов фактически выполняется за постоянное время.

На высоком уровне алгоритм работает следующим образом. Наборы представлены деревьями с родителями у каждого элемента. Поскольку у каждого дерева есть корень (элемент, который сам себе родитель), мы можем определить, принадлежат ли два элемента одному набору, проследив их родителей до корня. Если у двух элементов один корень, они принадлежат одному набору. Объединение множеств тоже легко: просто находим корневые элементы и делаем один из них корнем другого.

Пока всё хорошо, но пока не видно ослепительной скорости. Гениальность этой структуры — в процедуре под названием сжатие. Предположим, у вас есть следующее дерево:

Представьте, что вы хотите узнать, являются ли синонимами слова speedy и hasty. Идёте по родителям каждого — и находите одинаковый корень fast. Теперь предположим, что мы выполняем аналогичную проверку для слов speedy и swift. Опять идём вверх до корня, причём от speedy мы идём тем же маршрутом. Можно ли избежать дублирования работы?

Оказывается, можно. В некотором смысле, каждому элементу в этом дереве суждено прийти к fast. Вместо того, чтобы каждый раз проходить по всему дереву, почему бы не изменить родителя для всех потомков fast, чтобы сократить маршрут к корню? Этот процесс называется сжатием, и в непересекающихся множествах он встроен в операцию поиска корня. Например, после первой операции по сравнению speedy и hasty структура поймёт, что они синонимы, и сожмёт дерево следующим образом:

Для всех слов между speedy и fast обновился родитель, то же самое произошло с hasty

Теперь все последующие обращения будут происходить в постоянном времени, потому что каждый узел в этом дереве указывает на fast. Здесь не очень просто оценить временную сложность операций: на самом деле, она не постоянна, потому что зависит от глубины деревьев, но близка к постоянной, потому что структура быстро оптимизируется. Для простоты будем считать, что время постоянное.

С этой концепцией реализуем несвязанные множества для нашей проблемы:

class DisjointSet(object):
    def __init__(self):
        self.parents = {}

    def get_root(self, w):
        words_traversed = []
        while self.parents[w] != w:
            words_traversed.append(w)
            w = self.parents[w]
        for word in words_traversed:
            self.parents[word] = w
        return w

    def add_synonyms(self, w1, w2):
        if w1 not in self.parents:
            self.parents[w1] = w1
        if w2 not in self.parents:
            self.parents[w2] = w2

        w1_root = self.get_root(w1)
        w2_root = self.get_root(w2)
        if w1_root < w2_root:
            w1_root, w2_root = w2_root, w1_root
        self.parents[w2_root] = w1_root

    def are_synonymous(self, w1, w2):
        return self.get_root(w1) == self.get_root(w2)

Используя эту структуру, можно предварительно обработать синонимы и решить задачу за линейное время.
К этому моменту мы достигли предела того, что кандидат может показать за 40−45 минут собеседования. Всем кандидатам, которые справились с вводной частью и добились значительного прогресса в описании (не реализации) несвязанных множеств, я присваивал рейтинг «Настоятельно рекомендуется принять на работу» и позволял им задавать любые вопросы. Никогда не видел, чтобы кандидат зашёл так далеко и у него осталось много времени.

В принципе, ещё есть варианты задачи с транзитивностью: например, убрать ограничение на порядок слов или на несколько синонимов для слова. Каждое решение будет сложным и восхитительным, но оставлю их на потом.

Достоинство этой задачи в том, что она позволяет кандидатам ошибаться. Ежедневная разработка ПО состоит из бесконечных циклов анализа, выполнения и уточнения. Эта проблема даёт возможность кандидатам продемонстрировать свои способности на каждом этапе. Рассмотрим навыки, необходимые для получения максимальной оценки по этому вопросу:

• Проанализируйте постановку задачи и определите, где она недостаточно чётко сформулирована, разработайте однозначную формулировку. Продолжайте делать это по мере решения и возникновения новых вопросов. Для максимальной эффективности производите эти операции как можно раньше, потому чем дальше зашла работа, тем больше времени займёт исправление ошибки.
• Сформулируйте проблему таким образом, чтобы к ней было легче подойти и решить. В нашем случае самым важным является наблюдение, что соответствующие слова в запросах выстраиваются друг относительно друга.
• Реализуйте свое решение. Это включает в себя выбор оптимальной структуры данных и алгоритмов, а также проектирование логики, читаемой и легко изменяемой в будущем.
• Вернитесь назад, попытайтесь найти баги и ошибки. Это могут быть фактические ошибки, как я забыл вставить оператор continue выше, или ошибки производительности, как использование неправильной структуры данных.
• Когда определение проблемы изменится, повторите весь процесс: адаптируйте своё решение, где это необходимо, или откажитесь от него, если оно не подходит. Понимание, когда нужно сделать одно или другое, является критически важным навыком и в собеседовании, и в реальном мире.
• Осваивайте структуры данных и алгоритмы. Непересекающиеся множества — не очень известная структура, но на самом деле не такая уж редкая и утончённая. Единственный способ гарантировать знание инструментария для работы — как можно больше учиться.

Ни один из этих навыков нельзя освоить по учебникам (за исключением, возможно, структур данных и алгоритмов). Единственный способ приобрести эти их — регулярная и обширная практика, которая хорошо согласуется с тем, что нужно работодателю: опытные кандидаты, способные эффективно применять свои знания. Смысл собеседований — найти таких людей, и задача из этой статьи долгое время хорошо мне помогала.
Как вы могли понять, задача в конце концов стала известна общественности. С тех пор я использовал несколько других вопросов, в зависимости от того, что спрашивали прошлые интервьюеры и от моего настроения (задавать всё время один вопрос скучно). Некоторые вопросы использую до сих пор, так что их буду держать в секрете, но некоторые нет! Можете узнать их в следующих статьях.

На ближайшее время я планирую две статьи. Во-первых, как и обещал выше, объясню решение двух оставшихся проблем для этой задачи. Я их никогда не задавал на собеседованиях, но они интересны сами по себе. Кроме того, поделюсь своими размышлениями и личным мнением о процедуре поиска сотрудников в IT, что мне особенно интересно сейчас, потому что я ищу инженеров для своей команды в Reddit.

Как всегда, если хотите узнать о выходе новых статей, следите за мной в твиттере или на Medium. Если вам понравилась эта статья, не забудьте прогголосовать за неё или оставить комментарий.

Благодарю за чтение!

P. S.: Можете изучить код всех статей в репозитории GitHub или поиграться с ним вживую благодаря моим добрым друзьям из repl.it.

15 Вопросов на собеседовании в Google, из-за которых вы можете почувствовать себя глупым

Google снова набирает людей.
Это отличная новость для тысяч начинающих менеджеров и разработчиков ПО, желающих найти спокойную пристань в эти сложные дни.
Теперь плохие новости:

• Google предпочитает людей из «Лиги Плюща»
• Им интересны ваши оценки (в институте), даже если вам уже за 30
• Они ищут людей, которые хотят изменить мир

Хуже того, если вы подходите по всем этим параметрам, вам все равно надо проходить собеседование.
Льюис Пин (Lewis Pin), тренер по поиску работы из Сиэтла, собрал 140 вопросов, которые в Google спрашивали его клиентов.

Сколько шариков для гольфа поместится в школьный автобус?

Позиция: Менеджер проекта

За сколько денег вы помоете все окна в Сиэтле?

Позиция: Менеджер проекта

В стране, где люди хотят, чтобы у них были дети-мальчики…

… каждая семья продолжает рожать детей до тех пор, пока не появится мальчик. Если у них девочка, они заводят ещё одного ребёнка. Если у них мальчик, они останавливаются. Каково соотношение мальчиков и девочек в такой стране?

Позиция: Менеджер проекта

Сколько настройщиков пианино во всём мире?

Позиция: Менеджер проекта

Фото: delgaudm

Почему крышка люка круглая?

Позиция: Разработчик ПО

Фото: brunkfordbraun

Разработайте план эвакуации из Сан Франциско

Позиция: Менеджер продукта

Сколько раз за день стрелки часов пересекаются?

Позиция: Менеджер продукта

Объясните значение выражения “dead beef”

Позиция: Разработчик ПО

Человек направил свой автомобиль на отель, но потерпел неудачу. Почему?

Позиция: Разработчик ПО

Вам надо проверить, правильно ли записан ваш телефон у Боба…

… но вы не можете его спросить об этом прямо. Вам надо написать вопрос на бумажке и отдать Еве, которая отнесёт её Бобу и принесёт обратно ответ от него. Что вы должны написать на бумажке, кроме прямого вопроса, так, чтобы Боб смог понять сообщение, а Ева не смогла узнать ваш номер телефона?

Позиция: Разработчик ПО

Вы — капитан пиратского судна…

… и ваша команда собирается голосовать, как разделить награбленное золото. Если с вами будет согласно меньше чем половина пиратов, вы умрёте. Как вы поделите золото, так, чтобы получить хорошую часть добычи, но всё же остаться в живых?

Позиция: Технический Менеджер

У вас есть 8 шаров одинакового размера…

…7 из них одинакового веса, а один весит чуть больше остальных. найти мяч, который тяжелее остальных, используя баланс и только два взвешивания?

Позиция: Менеджер продукта

У вас есть 2 яйца…

… и у вас есть доступ на 100-этажное здание. Яйца могут быть либо очень крепкими, либо очень хрупкими, это значит, что они могут разбиться, скинутые с первого этажа, либо не разбиться даже скинутые с 100-го этажа. Оба яйца абсолютно идентичные. Вам нужно выяснить самый высокий этаж 100-этажного здания, с которого яйца могут быть скинуты и не разбиться. Вопрос в том, сколько попыток вам надо сделать. Вы можете разбить только два яйца.

Позиция: Менеджер продукта

Объясните что такое База Данных в трёх предложениях, так как это сделал бы ваш 8-летний племянник

Позиция: Менеджер продукта

Вы были уменьшены до размеров 5-центовой монеты…

… и ваша масса была пропорционально уменьшена соответственно вашей плотности. Теперь вас бросили в пустой стакан блендера. Ножи начнут движение через 60 секунд. Что делать?

Позиция: Менеджер продукта

UPD
Ответы, для тех, кто не осилил.

пошаговое решение задач на собеседовании Google / Блог компании Skillbox / Хабр

В прошлом году последние пару месяцев я потратил на подготовку к собеседованию для стажировки в Google (Google Internship). Все прошло хорошо: я получил и работу, и отличный опыт.

Теперь, спустя два месяца после стажировки, я хочу поделиться документом, который использовал для подготовки к собеседованиям. Для меня это было чем-то типа шпаргалки перед экзаменом. Но процесс создания документа и постоянная пошаговая проверка по нему помогли мне запомнить все самое важное.

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

Моей шпаргалки вам хватит для подготовки к любому техническому интервью, будь то Google, стартап или ваша первая стажировка. Она поможет чувствовать себя более уверенно и во время подготовки, и на самом собеседовании.

Рекомендуем бесплатные интенсивы по программированию для начинающих:
Основы Java всего за 3 дня — 8–10 августа;
Пишем первую модель машинного обучения — 12–14 августа;
Разработка мессенджера на Python — 15–17 августа

Шпаргалка для технического интервью

Сайты

Pramp

На этом ресурсе вы можете потренироваться проходить собеседования. Участники по очереди интервьюируют друг друга (там есть аудио- и видеоканалы) и могут пользоваться общим редактором кода. Скорее всего, на первых таких собеседованиях вам будет непросто, и чувствовать себя вы будете неловко. Но чем больше вы тренируетесь, тем увереннее их проходите, а настоящее интервью после этого покажется несложным.

Codesignal

Хорошие вопросы с реальных собеседований в Facebook, Google, Microsoft, etc. Я советую использовать этот сайт вместе с ресурсами по практике кодинга, включая изучение алгоритмической сложности.

Книги

Cracking the Coding Interview

Мои любимые части: Interview Preparation Grid (стр. 32), раздел, посвященный поведению на собеседовании, а также Interview Questions: Data Structures (стр. 88–107). Если вы ранее не сталкивались с термином «алгоритмическая сложность», то сейчас самое время, книга отлично вводит в тему.

А что делать на собеседовании?

• Не выключайтесь из коммуникации и отвечайте честно. Когда обдумываете вопрос, размышляйте вслух, описывайте ход своих мыслей.;
• Добавьте немного юмора в общение, не бойтесь шутить. Попробуйте получить удовольствие от общения.;
• Записывайте важную информацию.;
• Задавайте вопросы и старайтесь использовать то, что узнали от интервьюера.

Собеседование шаг за шагом

А вот чек-лист для подготовки к ответу на собеседовании. Не обязательно использовать все пункты, пропускайте те, что кажутся вам ненужными. Главное — опирайтесь на здравый смысл. Даже если вы не дошли до самого конца списка, ничего страшного не случится.

1. Прочитайте вопрос.
2. Разберите все данные, как входные, так и выходные, и обратите внимание на побочные эффекты.
3. Уточните суть задания и озвучьте ваши предположения, чтобы интервьюер понимал ход ваших мыслей. Например, какие будут объемы данных и кто станет пользователем.
4. Подыщите пример и озвучьте его интервьюеру, чтобы быть уверенным, что вы верно понимаете задачу. Не бойтесь потратить время, вникая в условия задачи. Чем лучше вы ее поймете, тем быстрее найдете оптимальное решение.
5. Разработайте алгоритм. Постарайтесь решить похожую, но менее сложную задачу. Записывайте мысли, разбирайте в черновике примеры.
6. Пройдитесь по своему алгоритму с примерами, чтобы убедиться, что код работает верно. Проверьте все критические и пограничные случаи.
7. Оцените сложность алгоритма как по времени, так и по памяти.
8. Если вам удалось придумать более эффективное решение проблемы, то вернитесь к пункту 4.
9. Напишите решение, используя выбранный алгоритм. Разбейте проблему на несколько методов, если это допустимо в конкретном случае.
10. Проверьте код на ошибки.
11. Подумайте, как реализация алгоритма справляется с критическими и пограничными случаями.
12. Проверьте реализацию на примере, просмотрите код на ошибки.
13. Как только убедитесь, что код выполняется правильно, проверьте его чистоту и стиль.

Вот, собственно, и все!

Разбор задачи с собеседования Google: поиск соотношения / Хабр

Добро пожаловать в очередную из серии статей с разбором задачек, которые я задавал на собеседованиях в Google, прежде чем их запретили после утечки. С тех пор я оставил работу инженера-программиста в Google и перешёл на должность менеджера по разработке в Reddit, но у меня всё ещё осталось несколько замечательных тем. К настоящему моменту мы разобрали динамическое программирование, возведение матриц в степень и синонимичность запросов. На этот раз совершенно новый вопрос.

Но сначала два замечания. Во-первых, работа в Reddit была потрясающей. Последние восемь месяцев я строил и возглавлял новую команду Ads Relevance и занимался организацией нового офиса разработки в Нью-Йорке. Как бы это ни было весело, к сожалению, я обнаружил, что до недавнего времени у меня не оставалось времени или энергии на блог. Боюсь, что я немного забросил эту серию. Извините за задержку.

Во-вторых, если вы следили за статьями, то после последнего выпуска могли подумать, что я начну копаться в вариантах синонимичности запросов. Хотя я хотел бы когда-то вернуться к этому, но должен признаться, что из-за смены работы потерял должный интерес к этой проблеме и пока решил отложить её. Впрочем, оставайтесь на связи! За мной должок, и я намерен его вернуть. Просто, ну знаете, чуть позже…

Быстрый отказ от ответственности: хотя собеседование кандидатов является одной из моих профессиональных обязанностей, этот блог представляет мои личные наблюдения, личные истории и личное мнение. Пожалуйста, не принимайте это за какое-либо официальное заявление от Google, Alphabet, Reddit или любого другого лица или организации.

Поиск нового вопроса

В предыдущей статье я описал один из своих любимых вопросов, который использовал в течение длительного времени, до неизбежной утечки. Предыдущие вопросы были увлекательными с теоретической точки зрения, но я хотел выбрать проблему, чуть более актуальную для Google как компании. Когда этот вопрос запретили, то я хотел найти замену с учётом нового ограничения: чтобы вопрос был проще.

Теперь это может показаться немного удивительным, учитывая печально известный процесс собеседований в Google. Но в то время более простая проблема имела смысл. Мои рассуждения состояли из двух частей. Первая прагматичная: кандидаты обычно не очень хорошо справлялись с предыдущими вопросами, несмотря на многочисленные намёки и упрощения, и я не всегда был полностью уверен, почему. Вторая теоретическая: процесс собеседования должен разделять кандидатов на категории «стоит нанимать» и «не стоит нанимать», и мне было любопытно, можно ли сделать это с вопросом немного попроще.

Прежде чем разъяснить эти два пункта, хочу указать на то, что они не означают. «Я не всегда уверен, почему у человека возникают проблемы» не означает бесполезность вопросов и что я хотел упростить собеседование по этой причине. Даже с самым сложным вопросом многие хорошо справлялись. Я имею в виду то, что когда у кандидатов возникали проблемы, мне бывало трудно понять, чего им не хватает.

Хорошие интервью дают широкую картину сильных и слабых сторон кандидата. Для комитета по найму недостаточно просто сказать, что «он провалился»: комитет определяет, есть ли у кандидата специфические для компании качества, которые они ищут. Точно так же слова «он крут» не помогают комитету принять решение по кандидату, который силён в некоторых областях, но сомнителен в других. Я обнаружил, что более сложные вопросы слишком часто разделяют кандидатов по этим двум категориям. В этом свете «я не всегда уверен, почему у человека возникают проблемы» означает «неспособность продвинуться в этом вопросе сама по себе не рисует картину способностей этого кандидата».

Классификация кандидатов как «стоит нанимать» и «не стоит нанимать» не означает, что процесс собеседования должен отделять глупых кандидатов от умных. Я не могу вспомнить ни одного кандидата, который не был бы умным, талантливым и мотивированным. Многие пришли из отличных университетов, а остальные явно были исключительно мотивированы. Проход через телефонные собеседования — уже хорошее сито, и даже отказ на этом этапе не является признаком отсутствия способностей.

Однако я могу вспомнить многих, кто не был достаточно подготовлен к интервью или работал слишком медленно, или требовал слишком большого надзора для решения проблемы, или общался неясным образом, или не смог перевести свои идеи в код, или придерживался позиции, которая просто не привела бы его к успеху в долгосрочной перспективе и т. д. Определение «стоит нанять» размытое и варьируется в зависимости от компании, а процесс собеседования и заключается в том, чтобы определить соответствие каждого кандидата требованиям конкретной компании.

Я прочитал много комментариев reddit с жалобами на излишне сложные вопросы собеседования. Мне стало любопытно, можно ли по-прежнему сделать рекомендацию «достоин/не достоин» на более простой задаче. Я подозревал, что это даст полезный сигнал без лишней трепли нервов кандидата. Расскажу о своих выводах в конце статьи…

С этими мыслями я искал новый вопрос. В идеальном мире это достаточно простой вопрос, чтобы решить его за 45 минут, но с дополнительными вопросами, чтобы более сильные кандидаты проявили свои навыки. Он также должен быть компактным в реализации, потому что многие кандидаты по-прежнему пишут на доске. Большой плюс, если тема будет как-то связана с продуктами Google.

Наконец, я остановился на вопросе, который какой-то замечательный гуглер тщательно описал и вставил в нашу базу данных вопросов. Сейчас я проконсультировался с бывшими коллегами и убедился, что вопрос по-прежнему запрещён, поэтому вам его точно не зададут на собеседовании. Представляю его в таком виде, в каком он кажется мне наиболее эффективным, с извинениями перед оригинальным автором.

Вопрос

Поговорим об измерении расстояний. Хэнд — это единица измерения в четыре дюйма, которая обычно используется в англоязычных странах для измерения высоты лошадей. Световой год — ещё одна единица измерения, равная расстоянию, которое частица (или волна?) света пройдёт за определённое количество секунд, примерно равное одному земному году. На первый взгляд, у них мало общего друг с другом, кроме того, что они используются для измерения расстояния. Но оказывается, что Google может довольно легко их конвертировать:

Это может показаться очевидным: в конце концов, они обе измеряют расстояние, поэтому ясное дело, что есть преобразование. Но если подумать, немного странно: как они вычислили этот коэффициент конверсии? Ясно, что никто на самом деле не считал количество хэндов в световом году. На самом деле не нужно считать это напрямую. Вы можете просто использовать общеизвестные преобразования:

• 1 хэнд = 4 дюйма
• 4 дюйма = 0,33333 фута
• 0,33333 фута = 6,3125e−5 миль
• 6,3125e−5 миль = 1,0737e−17 световых лет

Цель задачи — разработать систему, которая выполнит это преобразование. В частности:

На входе у вас список коэффициентов пересчёта (отформатированный на выбранном вами языке) в виде набора начальных единиц измерения, конечных единиц и множителей, например:

фут дюйм 12
фут ярд 0,3333333
и т. д.

Таким образом, что ORIGIN * MULTIPLIER = DESTINATION. Разработайте алгоритм, который принимает два произвольных значения единиц измерения и возвращает коэффициент преобразования между ними.

Обсуждение

Мне нравится эта проблема, потому что у неё интуитивно понятный и очевидный ответ: просто конвертировать из одного единицы в другую, потом в следующую, пока не найдёте цель! Не могу вспомнить ни одного кандидата, который столкнулся с этой проблемой и был полностью озадачен, как её решить. Это хорошо соответствует требованию «более простой» проблемы, поскольку предыдущие обычно требовали длительного изучения и размышлений, прежде чем находился хотя бы базовый подход к решению.

И всё же многие кандидаты не смогли реализовать интуицию в виде рабочего решения без явных намёков. Одно из достоинств этого вопроса в том, что он проверяет способность кандидата сформулировать проблему (сделать фрейминг) таким образом, чтобы она поддавалась анализу и кодированию. Как мы увидим, здесь есть одно очень интересное расширение, которое требует нового концептуального скачка.

Для контекста, фрейминг — это акт перевода проблемы с неочевидным решением в эквивалентную проблему, где решение выводится естественным путём. Если это звучит совершенно абстрактно и неприступно, простите, но так и есть. Я объясню, что имею в виду, когда представлю начальное решение этой проблемы. Первая часть решения будет упражнением в разработке и применении алгоритмических знаний. Вторая часть будет упражнением в манипулировании этим знанием, чтобы прийти к новой и неочевидной оптимизации.

Часть 0. Интуиция

Прежде чем копнуть глубже, давайте полностью исследуем «очевидное» решение. Большинство требуемых преобразований просты и понятны. Любой американец, который путешествовал за пределами США, знает, что большая часть мира для измерения расстояний использует таинственную единицу «километр». Для преобразования нужно всего лишь умножить количество миль примерно на 1,6.

С такими вещами мы сталкиваемся на протяжении большей части жизни. Для большинства единиц измерения уже есть предварительно вычисленное преобразование, так что нужно лишь посмотреть его в соответствующей таблице. Но если нет прямого преобразования (например, из хэндов в световые годы), есть смысл построить путь преобразования, как указано выше:

• 1 хэнд = 4 дюйма
• 4 дюйма = 0,33333 фута
• 0,33333 фута = 6,3125e−5 миль
• 6,3125e−5 миль = 1,0737e−17 световых лет

Это было совсем просто, я просто придумал такое преобразование, используя своё воображение и стандартную таблицу преобразований! Однако остаются некоторые вопросы. Есть ли более короткий путь? Насколько точен коэффициент? Всегда ли возможно преобразование? Можно ли его автоматизировать? К сожалению, здесь наивный подход ломается.

Часть 1. Наивное решение

Приятно, что проблема имеет интуитивное решение, но на самом деле эта простота является препятствием для решения проблемы. Нет ничего труднее попыток понять по-новому то, что вы уже понимаете — не в последнюю очередь потому, что вы часто знаете меньше, чем думаете. Для иллюстрации, представьте, что вы пришли на интервью — и у вас в голове этот интуитивный метод. Но он не позволяет решить ряд важных проблем.

Например, что делать, если нет преобразования? Очевидный подход ничего не говорит, действительно ли возможно преобразование из одной единицы в другую. Если мне дадут тысячу коэффициентов конверсии, мне будет очень трудно определить, возможно ли оно в принципе. Если меня просят сделать преобразование между незнакомыми (или выдуманными) единицами укачки и уколки, то я без понятия, с чего начать. Как здесь поможет интуитивный подход?

Должен признать, что это своего рода надуманный сценарий, но есть и более реалистичный. Видите, что моя постановка задачи включает только единицы расстояния. Это сделано специально. Что, если я попрошу систему перевести из дюймов в килограммы? И вы, и я знаем, что это невозможно, потому что они измеряют разные типы, но входные данные ничего не говорят о «типе», который измеряет каждая единица.

Именно здесь тщательная постановка вопроса позволяет проявить себя сильным кандидатам. Перед разработкой алгоритма они продумывают крайние случаи системы. И такая постановка проблемы целенаправленно даёт им возможность спросить меня, будем ли мы переводить разные единицы. Это не такая огромная проблема, если она встретится на ранней стадии, но всегда хороший знак, когда кто-то заранее спрашивает меня: «Что должна вернуть программа, если преобразование невозможно?» Постановка вопроса таким образом даёт мне представление о способностях кандидата, прежде чем он напишет хотя бы одну строку кода.

Представление в виде графа

Очевидно, что наивный подход не подходит, поэтому мы должны подумать, как можно произвести такую конверсию? Ответ — рассмотреть единицы как граф. Это первый скачок понимания, необходимый для решения этой задачи.

В частности, представьте, что каждая единица является узлом в графе, и существует ребро от узла A до узла B, если A можно преобразовать в B:

Рёбра помечены коэффициентом конверсии, на который вы должны умножить A, чтобы получить B.

Я почти всегда ожидал, что кандидат придумает такой фрейминг, и редко давал серьёзные подсказки для него. Я могу простить кандидата, который не замечает решения проблемы с использованием непересекающихся множеств или не слишком глубоко знаком с линейной алгеброй, чтобы реализовать решение, сводящееся к повторному возведению в степень матрицы смежности, но на любой учебной программе или курсе по программированию преподаются графы. Если у кандидата нет соответствующих знаний, это сигнал «не стоит нанимать».

В любом случае

Представление в виде графа сводит решение к классической проблеме поиска графа. В частности, здесь полезны два алгоритма: поиск в ширину (BFS) и поиск в глубину (DFS). При поиске в ширину мы исследуем узлы в соответствии с их расстоянием от начала координат:

Более тёмные синие цвета означают более поздние поколения

А при поиске в глубину мы исследуем узлы в том порядке, в каком они встречаются:

Более тёмные синие цвета также означают более поздние поколения. Обратите внимание, что мы на самом деле не посещаем все узлы

Любой из алгоритмов легко определяет, существует ли преобразование из одной единицы в другую, достаточно просто выполнить поиск по графу. Начинаем с исходной единицы и ищем, пока не найдём единицу назначения. Если не удаётся найти пункт назначения (как при попытке преобразовать дюймы в килограммы), мы знаем, что пути нет.

Но подождите, чего-то не хватает. Мы не хотим искать, существует ли путь, мы хотим найти коэффициент конверсии! Именно здесь кандидат должен совершить скачок: оказывается, вы можете модифицировать любой алгоритм поиска для вычисления коэффициента конверсии, просто сохранив дополнительное состояние по мере прохождения. Вот где иллюстрации перестают иметь смысл, так что давайте погрузимся прямо в код.

Во-первых, нужно определить структуру данных графа, поэтому используем это:

class RateGraph(object):
    def __init__(self, rates):
        'Initialize the graph from an iterable of (start, end, rate) tuples.'
        self.graph = {}
        for orig, dest, rate in rates:
            self.add_conversion(orig, dest, rate)

    
    def add_conversion(self, orig, dest, rate):
        'Insert a conversion into the graph.'
        if orig not in self.graph:
            self.graph[orig] = {}
        self.graph[orig][dest] = rate


    def get_neighbors(self, node):
        'Returns an iterable of the nodes neighboring the given node.'
        if node not in self.graph:
            return None
        return self.graph[node].items()
        

    def get_nodes(self):
        'Returns an iterable of all the nodes in the graph.'
        return self.graph.keys()

Затем приступим к работе над DFS. Существует много способов реализации, но на сегодняшний день наиболее распространённым является рекурсивное решение. Начнём с такого:

from collections import deque

def __dfs_helper(rate_graph, node, end, rate_from_origin, visited):
    if node == end:
        return rate_from_origin

    visited.add(node)

    for unit, rate in rate_graph.get_neighbors(node):
        if unit not in visited:
            rate = __dfs_helper(rate_graph, unit, end, rate_from_origin * rate, visited)
            if rate is not None:
                return rate

    return None

def dfs(rate_graph, node, end):
    return __dfs_helper(rate_graph, node, end, 1.0, set())

В двух словах, этот алгоритм начинается с одного узла, перебирает его соседей и немедленно посещает каждого, выполняя рекурсивный вызов функции. Каждый вызов функции в стеке сохраняет состояние своей собственной итерации, поэтому, когда возвращается одно рекурсивное посещение, его родитель немедленно продолжает итерацию. Мы избегаем повторного посещения одного и того же узла, поддерживая набор посещённых узлов во всех вызовах. Мы также вычисляем коэффициент, назначая каждому узлу коэффициент преобразования между ним и источником. Таким образом, когда мы сталкиваемся с целевым узлом/блоком, мы уже создали коэффициент преобразования от исходного узла, и можем просто вернуть его.

Это прекрасная реализация, но она страдает от двух основных недостатков. Во-первых, она рекурсивная. Если окажется, что нужный путь состоит из более тысячи прыжков, мы вылетим со сбоем. Конечно, это маловероятно, но если и есть что-то неприемлемое для долговременного сервиса, так это сбой. Во-вторых, даже если успешно закончим, у ответа некоторые нежелательные свойства.

Я на самом деле уже дал подсказку в начале поста. Вы заметили, как Google показывает коэффициент конверсии 1.0739e-17, но мой расчёт вручную даёт 1.0737e-17? Оказывается, все эти перемножения с плавающей запятой заставляют уже думать о распространении ошибки. Здесь слишком много нюансов для этой статьи, но суть в том, что нужно свести к минимуму умножения с плавающей запятой, чтобы избежать ошибок, которые накапливаются и вызывают проблемы.

DFS — прекрасный алгоритм поиска. Если решение существует, оно его найдёт. Но ему не хватает ключевого свойства: он не обязательно находит самый короткий путь. Для нас это важно, потому что более короткий путь означает меньше прыжков и меньшую ошибку из-за умножений с плавающей запятой. Чтобы решить проблему, мы обращаемся к BFS.

Часть 2. Решение BFS

На этом этапе, если кандидат успешно реализовал рекурсивное решение DFS и остановился на нём, я обычно даю хотя бы слабую рекомендацию по найму этого кандидата. Он понял проблему, выбрал подходящий фрейминг и реализовал рабочее решение. Это наивное решение, поэтому я не настаиваю на его найме, но если он хорошо справился с другими собеседованиями, то не буду рекомендовать отказ.

Это стоит повторить: если сомневаетесь, то напишите наивное решение! Даже если оно не совсем оптимально, наличие кода на доске — уже достижение, и часто на его основе можно найти правильное решение. Скажу иначе: никогда не работайте впустую. Скорее всего, вы подумали о наивном решении, но не хотели его предлагать, потому что знаете, что оно не оптимально. Если вы прямо сейчас готовы выложить лучшее решение, это прекрасно, но если нет, то зафиксируйте достигнутый прогресс, прежде чем переходить к более сложным вещам.

С этого момента поговорим об улучшениях алгоритма. Основные недостатки рекурсивного решения DFS заключаются в том, что оно рекурсивно и не минимизирует количество умножений. Как мы скоро увидим, BFS минимизирует количество умножений, и его тоже очень сложно реализовать рекурсивно. К сожалению, нам придётся отказаться от рекурсивного решения DFA, поскольку для его улучшения потребуется полностью переписать код.

Без дальнейших церемоний, представляю итеративный подход на основе BFS:

from collections import deque

def bfs(rate_graph, start, end):
    to_visit = deque()
    to_visit.appendleft( (start, 1.0) )
    visited = set()

    while to_visit:
        node, rate_from_origin = to_visit.pop()
        if node == end:
            return rate_from_origin
        visited.add(node)
        for unit, rate in rate_graph.get_neighbors(node):
            if unit not in visited:
                to_visit.appendleft((unit, rate_from_origin * rate))

    return None

Эта реализация функционально сильно отличается от предыдущей, но если внимательно посмотреть, она делает примерно то же самое, с одним существенным изменением: в то время как рекурсивный DFS сохраняет состояние дальнейшего маршрута в стеке вызовов, эффективно реализуя стек LIFO, итеративное решение сохраняет его в очереди FIFO.

Отсюда вытекает свойство «кратчайший путь / наименьшее число умножений». Мы посещаем узлы в том порядке, в котором они встречаются, и таким образом получаем поколения узлов. Первый узел вставляет своих соседей, а затем мы посещаем этих соседей по порядку, всё время прикрепляя их соседей и так далее. Свойство кратчайшего пути вытекает из того, что узлы посещаются в порядке их расстояния от источника. Поэтому, когда мы сталкиваемся с местом назначения, мы знаем, что нет более раннего поколения, которое могло бы к нему привести.

В этот момент мы почти закончили. Сначала нужно ответить на несколько вопросов, и они заставляются вернуться к первоначальной постановке проблемы.

Во-первых, самое тривиальное, что делать, если исходная единица измерения не существует? То есть мы не можем найти узел с заданным именем. На практике нужно выполнить некоторую нормализацию строк, чтобы Фунт, ФУНТ и lb указывали на один узел «фунт» (или какое-то другое каноническое представление), но это выходит за рамки нашего вопроса.

Во-вторых, что делать, если между двумя единицами нет преобразования? Напомним, что в исходных данных только преобразования между единицами, и оно не даёт никаких указаний на то, можно ли получить из одной конкретной единицы другую. Это сводится к тому, что преобразования и пути прямо эквивалентны, поэтому если между двумя узлами нет пути, то нет преобразования. На практике вы в конечном итоге получаете несвязанные острова единиц измерения: один для расстояний, один для весов, один для валют и т. д.

Наконец, если внимательно посмотреть на граф выше, оказывается, что вы не можете произвести конверсию между хэндами и световыми годами с таким решением. Направление связей между узлами означает, что от хэнда к световым годам нет пути. Впрочем, это довольно легко исправить, потому что преобразования можно обратить в другую сторону. Мы можем изменить наш код инициализации графа следующим образом:

def add_conversion(self, orig, dest, rate):
    'Insert a conversion into the graph. Note we insert its inverse also.'
    if orig not in self.graph:
        self.graph[orig] = {}
    self.graph[orig][dest] = rate

    if dest not in self.graph:
        self.graph[dest] = {}
    self.graph[dest][orig] = 1.0 / rate

Часть 3. Оценка

Готово! Если кандидат дошёл до этого момента, то я с большой вероятностью буду рекомендовать его к найму. Если вы изучали информатику или прошли курс алгоритмов, то можете спросить: «И этого действительно достаточно, чтобы пройти собеседование у этого парня?», на что я отвечу: «По сути, да».

Прежде чем вы решите, что вопрос слишком простой, давайте рассмотрим, что должен сделать кандидат, чтобы достичь этой точки:

• Понять вопрос
• Построить сеть преобразований в виде графа
• Понять, что коэффициенты можно сопоставить с рёбрами графа
• Увидеть возможность использования алгоритмы поиска для достижения этой цели
• Выбрать свой любимый алгоритм и изменить его, чтобы отслеживать коэффициенты
• Если он реализовал DFS как наивное решение, осознать его слабые стороны
• Реализовать BFS
• Отступить назад и изучить крайние случаи:
  • Что, если нас cпросят о несуществующем узле?
  • Что делать, если коэффициент преобразования не существует?

• Осознать, что обратные преобразования возможны и, вероятно, необходимы

Этот вопрос легче предыдущих, но при этом так же труден. Как и во всех предыдущих вопросах, кандидат должен совершить мысленный прыжок от абстрактно сформулированного вопроса к алгоритму или структуре данных, которая открывает путь к решению. Единственное, что здесь итоговый алгоритм менее продвинутый, чем в других вопросах. Вне этого алгоритмического материала действуют те же требования, особенно в отношении крайних случаев и корректности.

«Но подождите!, — вы можете спросить. — Разве Google не одержима сложностью рантайма? Вы даже не спросили о временной или пространственной сложности этой проблемы. Да ну!» Вы также можете спросить: «Погодите, вы же давали оценку «настоятельно рекомендую к найму»? Как её получить?» Очень хорошие вопросы, оба. Это приводит нас к нашему заключительному дополнительному бонусному раунду…

Часть 4. Можно ли сделать лучше?

В этот момент я хотел бы поздравить кандидата с хорошим ответом и дать понять, что всё дальнейшее — просто бонус. Когда давление исчезнет, мы сможем начать творить.

Итак, какова сложность выполнения BFS? В худшем случае мы должны рассмотреть каждый отдельный узел и ребро, что даёт линейную сложность O(N+E). Это поверх такой же сложности O(N+E) построения графа. Для поисковой системы это, вероятно, хорошо: тысячи единиц измерения достаточно для большинства разумных приложений, а выполнение поиска в памяти по каждому запросу не является чрезмерной нагрузкой.

Тем не менее, можно сделать лучше. Для мотивации рассмотрим, как этот код вставляется в поисковую строку. Преобразования некоторых нестандартных единиц встречаются чуть чаще, поэтому мы будем вычислять их снова и снова. Каждый раз выполняется поиск, вычисляются промежуточные значения и т. д.

Часто предлагают просто кэшировать результаты вычисления. Всякий раз, когда вычисляется преобразование единиц, мы всегда можем просто добавить ребро между двумя преобразованиями. В качестве бонуса, мы получим обратное преобразование, причём бесплатно! Готово?

Действительно, это даст нам асимптотически постоянное время поиска, но будет стоить хранения дополнительных рёбер. Это на самом деле становится довольно дорогим: со временем мы будем стремиться к полному графу, поскольку все пары преобразований постепенно вычисляются и сохраняются. Число возможных рёбер в графе составляет половину квадрата числа узлов, поэтому для тысячи узлов нам понадобится полмиллиона рёбер. Для десяти тысяч узлов — около пятидесяти миллионов и т. д.

Выходя за рамки поисковой системы, для графа из миллиона узлов мы стремимся к половине триллиона рёбер. Такое количество просто неразумно хранить, плюс мы тратим время на вставку рёбер в граф. Мы должны сделать лучше.

К счастью, есть способ добиться постоянного времени для поиска коэффициентов, без квадратичного роста пространства. На самом деле, почти всё необходимое уже у нас прямо под носом.

Часть 4. Постоянное время

Итак, тотальное кэширование на самом деле близко к оптимальному решению. В этом подходе мы (в конечном итоге) получаем рёбра между всеми узлами, то есть наше преобразование сводится к поиску одного ребра. Но действительно ли нужно хранить преобразования из каждого узла в каждый узел? Что, если мы просто сохраним коэффициенты преобразования от одного узла ко всем остальным?

Взглянем ещё раз на решение BFS:

from collections import deque

def bfs(rate_graph, start, end):
    to_visit = deque()
    to_visit.appendleft( (start, 1.0) )
    visited = set()

    while to_visit:
        node, rate_from_origin = to_visit.pop()
        if node == end:
            return rate_from_origin
        visited.add(node)
        for unit, rate in rate_graph.get_neighbors(node):
            if unit not in visited:
                to_visit.appendleft((unit, rate_from_origin * rate))

    return None

Посмотрим, что здесь происходит: мы начинаем с исходного узла, и для каждого узла, с которым сталкиваемся, вычисляем коэффициент преобразования от источника к этому узлу. Затем, как только прибываем в пункт назначения, мы возвращаем коэффициент между исходным и конечным пунктами и отбрасываем промежуточные коэффициенты.

Эти промежуточные коэффициенты являются ключевыми. А что, если мы их не выбросим? А что, если вместо этого мы их запишем? Все самые сложные и непонятные поиски становятся простыми: чтобы найти отношение A к B, сначала найдём отношение X к B, затем разделим его на отношение X к A, и всё готово! Визуально это выглядит так:

Обратите внимание, что между любыми двумя узлами не больше двух рёбер

Оказывается, для вычисления этой таблицы нам почти не нужно изменять решение BFS:

from collections import deque

def make_conversions(graph):
    def conversions_bfs(rate_graph, start, conversions):
        to_visit = deque()
        to_visit.appendleft( (start, 1.0) )

        while to_visit:
            node, rate_from_origin = to_visit.pop()
            conversions[node] = (start, rate_from_origin)
            for unit, rate in rate_graph.get_neighbors(node):
                if unit not in conversions:
                    to_visit.append((unit, rate_from_origin * rate))

        return conversions

    conversions = {}
    for node in graph.get_nodes():
        if node not in conversions:
            conversions_bfs(graph, node, conversions)
    return conversions

Структура преобразований представлена словарём единицы A в двух значениях: корень для связанного компонента единицы A и коэффициент преобразования между корневой единицей и единицей A. Поскольку мы вставляем единицу в этот словарь при каждом посещении, то можем использовать пространство ключей этого словаря в качестве набора посещений вместо использования выделенного набора посещений. Обратите внимание, что у нас нет конечного узла, и вместо этого мы перебираем узлы, пока не закончим.

За пределами этого BFS есть вспомогательная функция, которая перебирает узлы в графе. Всякий раз, когда она сталкивается с узлом вне словаря преобразования, то запускает BFS, начиная с этого узла. Таким образом, мы гарантированно свернём все узлы в их связанные компоненты.

Когда нужно найти соотношение между единицами, мы просто используем структуру преобразований, которую только что вычислили:

def convert(conversions, start, end):
    'Given a conversion structure, performs a constant-time conversion'
    try:
        start_root, start_rate = conversions[start]
        end_root, end_rate = conversions[end]
    except KeyError:
        return None

    if start_root != end_root:
        return None

    return end_rate / start_rate

Ситуация «нет такой единицы» обрабатывается прослушиванием исключения при доступе к структуре преобразований. Ситуация «нет таких преобразований» обрабатывается сравнением корней двух величин: если у них разные корни, значит, они обнаружены через два разных вызова BFS, то есть находятся в двух разных связанных компонентах, и поэтому никакого пути между ними не существует. Наконец, мы выполняем преобразование.

Вот так! У нынешнего решения при предварительной обработке сложность O(V+E) (не хуже, чем у предыдущих решений), но она также ищет с постоянным временем. Теоретически, мы удваиваем требования к пространству, но бóльшую часть времени нам больше не нужен исходный граф, поэтому мы можем просто удалить его и использовать только этот. При этом пространственная сложность на самом деле меньше, чем исходный граф: тот требует O(V+E), потому что должен хранить все рёбра и вершины, а эта структура требует только O(V), потому что нам больше не нужны рёбра.

Результаты

Если вы продвинулись так далеко, то можете вспомнить, что изначально один из вопросов был в том, чтобы проверить, сможет ли более простая проблема по-прежнему оставаться полезной в выборе достойных кандидатов и может ли она дать лучшую картину способностей. Я хотел бы дать какой-то окончательный научный ответ, но у меня есть только истории из личного опыта. Тем не менее, я заметил некоторые положительные результаты.

Если разбить решение этой задачи на четыре препятствия (обсуждение фрейминга, выбор алгоритма, реализация, обсуждение выполнения за постоянное время), то к концу собеседования почти все кандидаты дошли до «выбора алгоритма». Как я и подозревал, обсуждение фрейминга стало хорошим фильтром: кандидаты либо сразу выводили граф, либо никак не могли к нему прийти, несмотря на существенные подсказки.

Это уже сразу полезный сигнал. Я могу понять, когда человек не знает продвинутых или неясных структур данных, потому что будем честными, вам нечасто придётся реализовывать непересекающиеся множества. Но графы — фундаментальная структура данных и преподаётся в рамках практически любого вводного курса по этой теме. Если кандидат изо всех сил пытается понять их или не может их легко применить, вероятно, ему будет трудно добиться успеха в Google (по крайней мере, в моё время там, не знаю как сегодня).

С другой стороны, выбор алгоритма оказался не особенно полезным источником сигнала. Люди, которые прошли стадию фрейминга, обычно без особых проблем добирались до алгоритма. Подозреваю, это связано с тем, что алгоритмы поиска почти всегда преподаются вместе с самими графами, поэтому, если кто-то знаком с одним, то знает и другое.

Реализация оказалась непростой. У многих людей не было проблем с рекурсивной реализацией DFS, но, как я уже упоминал выше, эта реализация не подходит для продакшна. К моему удивлению, итеративные реализации BFS и DFS, похоже, не очень знакомы людям, и даже после явных подсказок они часто плавали в теме.

В моём представлении любой, кто прошёл этап реализации, уже заслужил от меня рекомендацию «Нанимать», а этап обсуждения постоянного времени выполнения просто бонусный. Хотя в статье мы подробно рассмотрели решение, на практике обычно более продуктивным является устное обсуждение, а не написание кода. Очень немногие кандидаты сразу могли высказать решение. Мне часто приходилось давать существенные подсказки, и даже тогда многие люди не могли его найти. Это нормально: как и предполагалось, рейтинг «настоятельно рекомендую» трудно заслужить.

Но подождите, это ещё не всё!

В основном, мы рассмотрели проблему целиком, но если вы заинтересованы в её дальнейшем изучении, то есть целый ряд расширений, в которые я не буду погружаться. Оставляю следующие упражнения для читателя:

Во-первых, разминка: в решении для постоянного времени, которое я выложил, я произвольно выбрал корневой узел каждого подключённого компонента. В частности, я использую первый узел компонента, с которым мы сталкиваемся. Это не оптимально, потому что для всех известных значений мы выбрали какой-то узел, хотя какой-то другой узел может быть ближе к центру с более короткими путями ко всем другим узлам. Ваша задача состоит в том, чтобы заменить этот произвольный выбор на тот, который минимизирует количество требуемых умножений и минимизирует распространение ошибки с плавающей запятой.

Во-вторых, во всех рассуждениях предполагалось, что все равные пути через граф равны изначально, что не всегда так. Один из интересных вариантов этой проблемы — конвертация валют: узлы — это валюты, а рёбра от A до B и наоборот — это цены на предложение/спрос каждой валютной пары. Мы можем перефразировать вопрос о конверсии единиц как вопрос о валютном арбитраже: реализовать алгоритм, который, учитывая граф конвертации валюты, вычисляет через граф цикл, который даст трейдеру больше денег, чем начальная сумма. Не учитывайте никаких комиссий за транзакции.

Наконец, настоящая жемчужина: некоторые единицы выражаются в виде комбинации различных базовых единиц. Например, ватт определяется в системе СИ как кг•м²/с³. Последняя задача заключается в расширении этой системы для поддержки преобразования между этими единицами, учитывая только определения основных единиц СИ.

Если у вас есть вопросы, не стесняйтесь обращаться ко мне на reddit.

Заключение

Когда я начал задавать эту задачу на собеседованиях, то надеялся, что она будет немного легче предыдущих. Эксперимент был в значительной степени успешным: если кандидат сразу видел решение, то обычно быстро справлялся с задачей, так что у нас оставалось много времени, чтобы поговорить о продвинутом решении с постоянным временем. Люди, которые испытывали затруднения, как правило, спотыкались в местах, отличных от алгоритмического концептуального скачка: кандидат не мог подходящим способом полностью сформулировать проблему или набросал хорошее решение, но не смог перевести его в рабочий код. Независимо от того, где и когда они испытывали затруднения, я обнаружил, что могу получить значимую информацию о сильных и слабых сторонах кандидатов.

Надеюсь, вы нашли полезной эту статью. Понимаю, что здесь может быть не так много приключений с алгоритмами, как в некоторых предыдущих статьях. На собеседованиях разработчиков принято обильно обсуждать алгоритмы. Но правда в том, что значительные сложности возникают при использовании даже простого, хорошо известного метода. Весь код — в репозитории этого цикла статей.

Спорим, вы не сможете решить эту задачу с собеседования в Google

Разбираем решение задачи, которую блоггер TechLead давал на собеседовании на должность разработчика ПО в Google.

Разбиваем сложную задачу на простые шаги

Мне захотелось посмотреть видео о разработке программного обеспечения, и я начал запоем смотреть TechLead на YouTube. Следующие несколько дней я потратил на то, чтобы найти разные варианты решения задачи, который он давал кандидатам, когда проводил собеседование в Google.

Меня заинтересовало это видео

Как проходит собеседование в Google (на должность разработчика ПО), автор: TechLead

В своем видео TechLead упоминает задачу, которую он больше сотни раз задавал кандидатам, что проходили собеседование в Google. Мне захотелось придумать решение с помощью RxJS. В этой статье мы рассмотрим традиционные методы.

Настоящая цель этой задачи – узнать кандидата. Правильные ли вопросы он задает перед написанием кода? Впишется ли его решение в инфраструктуру проекта? Насколько он будет полезен команде, когда придет работать в Google? TechLead утверждает, что от кандидата не требуется правильный ответ: важнее выяснить, как он думает, и насколько хорошо понимает поставленную задачу.

Он привел два решения: одно рекурсивное (ограниченное размером стека), другое – итеративное (ограниченное объемом памяти). Мы рассмотрим и то, и другое!

Задача от TechLead

Вот условия задания: нужно взять эту сетку блоков, найти самый большой участок из смежных блоков одного цвета и вычислить, из скольких блоков он состоит.

Когда я услышал это условие и увидел картинку, я подумал: «Черт, придется делать моделирование 2D-изображения, это же почти невозможно выполнить на собеседовании».

Однако после того, как TechLead объяснил подробнее, я понял, что всё не так. Нужно не проанализировать изображение, а обработать уже имеющиеся данные. Теперь я понимаю, что моделировать 2D-изображение совсем не обязательно.

Моделирование данных

Прежде чем писать код, нужно определить модель данных – это крайне важный этап. С такими сложными задачами сначала выясните, с какими условиями придется работать.

В нашем случае TechLead задал такие условия:

• У нас есть цветные квадраты – для удобства назовем их блоками.
• В наборе данных есть 10 000 блоков.
• Блоки организованы в столбцы и строки (2D).
• Количество столбцов и строк может быть неравным.
• Блоки смежны между собой и окрашены в несколько цветов.

Также мы можем получить дополнительную информацию на основе данных, приведенных выше:

• Блоки не перекрывают друг друга.
• Блок не может быть смежным по отношению к самому себе.
• Параметры смежности не могут быть одинаковы у разных блоков.
• Блоки, которые находятся на сторонах и углах, будут иметь на один и два параметра смежности меньше, чем все остальные.

Чего мы не знаем:

• Соотношение количества строк к количеству столбцов.
• Количество возможных цветов.
• Каковы шансы, что во всей сетке присутствует всего один цвет.
• Как распределены цвета.

Чем профессиональнее разработчик, тем больше вопросов у него возникает. Однако здесь дело не в опыте. Да, он помогает, но даже опытного разработчика нельзя назвать профессионалом, если он не может определить, какие условия в задаче неизвестны. Умение задавать вопросы важно во всех компаниях, не только в Google.

Большинство людей, скорее всего, определит другие неизвестные. Пока я не начал думать над алгоритмом решения, я тоже не знал, что именно неизвестно: чтобы разобраться в этом, нужно время и много обсуждений с представителями бизнеса.

Глядя на это изображение, кажется, что распределение случайное. В условиях задачи в Google даны всего 3 цвета и не упоминается, что цветов может быть больше или меньше. Также предположим, что все блоки могут быть одного цвета.

Чтобы облегчить работу над алгоритмом, допустим, что мы работаем с сеткой 100×100. Так, нам не придется иметь дело с нетипичными случаями, в которых сетка состоит из 1 строки и 10 000 столбцов.

Обычно я ставлю перед собой все эти вопросы в течение первых нескольких часов после изучения данных. Задание с собеседования в Google показывает, как вы работаете над поставленными задачами: сначала пробуете писать код случайного решения или сперва пытаетесь разобраться в проблеме?

Да, в своей модели данных вы допустите несколько ошибок. Я так думаю, потому что сам попал в такую ситуацию, пока писал статью. Тем не менее, если у вас есть план действий, вы легче справитесь с этой проблемой. В итоге мне пришлось переписывать довольно небольшую часть кода.

Создание модели данных

Нам нужно точно знать, в каком формате нам поступают данные, и как мы будем их обрабатывать.

Поскольку у нас нет системы для обработки данных, нам нужно самим придумать визуализацию.

Основные параметры данных в нашем случае:

Зачем нужен ID? Чтобы не обрабатывать данные об одном и том же блоке по несколько раз. Если каждому блоку присвоить ID, с его помощью мы сможем отмечать уже обработанные блоки и предотвратим бесконечные циклы.

Кроме того, в подобных случаях данным, как правило, присваивается какой-либо ID, хэш или другой параметр. Это уникальный идентификатор, с помощью которого мы сможем отметить каждый конкретный блок. Чтобы найти самый большой участок одного цвета, нужно знать, из каких блоков он состоит.

Поскольку в нашем случает данные находятся в сетке, я предполагаю, что мы можем присвоить им значения по оси X и Y. Используя только эти параметры, я смог сгенерировать HTML, чтобы убедиться, что результат похож на задачу в Google.

Как и в задаче от TechLead, я использовал абсолютное позиционирование:

Ответ: 3

Это работает и с бо́льшим объемом данных:

Ответ: 18

Это код, которые генерирует сетку блоков:

const generateNodes = ({
  numberOfColumns,
  numberOfRows,
}) => (
  Array(
    numberOfColumns
    * numberOfRows
  )
  .fill()
  .map((
    item,
    index,
  ) => ({
    colorId: (
      Math
      .floor(
        Math.random() * 3
      )
    ),
    id: index,
    x: index % numberOfColumns,
    y: Math.floor(index / numberOfColumns),
  }))
)

Берем столбцы и строки, создаем одномерный массив, в котором указываем количество элементов, а затем генерируем блоки на основе этих данных.

Вместо color я использую colorId. Во-первых, потому что так проще рандомизировать. Во-вторых, так нам не придется отдельно находить значение параметра color.

На собеседовании в Google задают задачу с тремя цветами, но никто не говорит, что это обязательное условие. Тем не менее, я тоже ограничусь тремя цветами. Просто уточним, что даже если в схеме будут сотни цветов, в итоге переписывать алгоритмы не придется.

Более простой пример: сетка блоков 2×2:

[
  { colorId: 2, id: 0, x: 0, y: 0 },
  { colorId: 1, id: 1, x: 1, y: 0 },
  { colorId: 0, id: 2, x: 0, y: 1 },
  { colorId: 1, id: 3, x: 1, y: 1 },
]

Обработка данных

Независимо от того, какой метод мы собираемся использовать, сначала нужно узнать параметры смежности для каждого блока. Сами по себе значения X и Y не решают эту задачу.

Таким образом, зная параметры блока X и Y, нужно найти блоки со смежными значениями X и Y. Это довольно просто: мы находим все блоки со значениями +1 и –1 по оси X и Y.

Для этого я написал вспомогательную функцию:

С точки зрения математики, генерация блоков и определение ID каждого блока – это один и тот же процесс. Но я исхожу из того, что в нашей сетке блоки расположены в случайном порядке.

Я сделал ещё один проход по всем блокам, чтобы найти параметры смежности:

const addAdjacencies = (
  nodes,
) => (
  nodes
  .map(({
    colorId,
    id,
    x,
    y,
  }) => ({
    color: colors[colorId],
    eastId: (
      getNodeAtLocation({
        nodes,
        x: x + 1,
        y,
      })
    ),
    id,
    northId: (
      getNodeAtLocation({
        nodes,
        x,
        y: y - 1,
      })
    ),
    southId: (
      getNodeAtLocation({
        nodes,
        x,
        y: y + 1,
      })
    ),
    westId: (
      getNodeAtLocation({
        nodes,
        x: x - 1,
        y,
      })
    ),
  }))
  .map(({
    color,
    id,
    eastId,
    northId,
    southId,
    westId,
  }) => ({
    adjacentIds: (
      [
        eastId,
        northId,
        southId,
        westId,
      ]
      .filter((
        adjacentId,
      ) => (
        adjacentId !== undefined
      ))
    ),
    color,
    id,
  }))
)

В коде препроцессора я постарался избежать ненужных оптимизаций. Это не повлияет на финальную производительность и поможет упростить алгоритмы.

Я пошел еще дальше и заменил colorId на color. Это совершенно не обязательно для работы алгоритмов, но я хотел показать все нагляднее.

Для каждого набора смежных значений X и Y вызываем getNodeAtLocation и находим northId, eastId, southId и westId. Больше значения X и Y нам не понадобятся.

После того, как мы нашли количественные ID, конвертируем их в один adjacentIds-массив, что включает в себя только ID, у которых есть значение. Таким образом, нам не нужно дополнительно проверять угловые и боковые блоки, у которых некоторые идентификаторы будут со значением 0. Это позволит нам зациклить массив вместо того, чтобы вручную отмечать каждый количественный ID в алгоритмах.
Вот еще один пример сетки 2×2 с заново сгенерированными блоками, обработанными с помощью addAdjacencies:

[
  { adjacentIds: [ 1, 2 ], color: 'red',  id: 0 },
  { adjacentIds: [ 3, 0 ], color: 'grey', id: 1 },
  { adjacentIds: [ 3, 0 ], color: 'blue', id: 2 },
  { adjacentIds: [ 1, 2 ], color: 'blue', id: 3 },
]

Оптимизация предварительной обработки

Для этой статьи я решил значительно упростить алгоритмы, поэтому добавил еще один этап оптимизации. Он состоит в удалении смежных ID, не соответствующих по цвету с текущим блоком.

Переписал функцию addAdjacencies:

const addAdjacencies = (
  nodes,
) => (
  nodes
  .map(({
    colorId,
    id,
    x,
    y,
  }) => ({
    adjacentIds: (
      nodes
      .filter(({
        x: adjacentX,
        y: adjacentY,
      }) => (
        adjacentX === x + 1
        && adjacentY === y
        || (
          adjacentX === x - 1
          && adjacentY === y
        )
        || (
          adjacentX === x
          && adjacentY === y + 1
        )
        || (
          adjacentX === x
          && adjacentY === y - 1
        )
      ))
      .filter(({
        colorId: adjacentColorId,
      }) => (
        adjacentColorId
        === colorId
      ))
      .map(({
        id,
      }) => (
        id
      ))
    ),
    color: colors[colorId],
    id,
  }))
  .filter(({
    adjacentIds,
  }) => (
    adjacentIds
    .length > 0
  ))
)

Уменьшил addAdjacencies, добавил больше функциональности.

После отсеивания блоков, которые не совпадают по цвету, мы можем быть на 100% уверены, что все ID в adjacentIds – смежные блоки.

Затем я отсеял все смежные, но не совпадающие по цвету блоки. Это еще больше упростило алгоритм, и мы теперь работаем только с нужными блоками.

Неправильный способ – рекурсия

Для решения этой задачи в Google не рекомендуют применять рекурсию: она вызовет переполнение стека.

Однако есть два способа справиться с этой проблемой: итерирование и хвостовая рекурсия. Мы остановимся на итерировании, потому что хвостовая рекурсия больше не поддерживается в JavaScript.

Мы все еще можем эмулировать хвостовую рекурсию в JavaScript. Однако нам нужен простой способ, поэтому мы используем обычную рекурсивную функцию.

Прежде чем запустить код, нужно разобраться в алгоритме. В случае с рекурсией есть смысл применить «поиск в глубину». Не переживайте, если не знаете этот термин. Я узнал его от коллеги, которому показывал свои решения.

Алгоритм

Начнем с какого-нибудь блока и пойдем по алгоритму до конечной точки, затем вернемся и выберем следующий путь ветвления, пока не просканируем весь участок этого цвета.

Еще нужно отслеживать, какие блоки мы уже рассмотрели и из скольких состоял самый большой участок одного цвета.

Я разделил функцию на две части. В одной части хранится информация о самом большом участке и уже обработанных ID. Одновременно с этим каждый блок зацикливается хотя бы по одному разу. Другая часть алгоритма начинается с корневого блока без сканирования и выполняет поиск в глубину.

Вот как выглядят эти две функции:

const getContiguousIds = ({
  contiguousIds = [],
  node,
  nodes,
}) => (
  node
  .adjacentIds
  .reduce(
    (
      contiguousIds,
      adjacentId,
    ) => (
      contiguousIds
      .includes(adjacentId)
      ? contiguousIds
      : (
        getContiguousIds({
          contiguousIds,
          node: (
            nodes
            .find(({
              id,
            }) => (
              id
              === adjacentId
            ))
          ),
          nodes,
        })
      )
    ),
    (
      contiguousIds
      .concat(
        node
        .id
      )
    ),
  )
)

const getLargestContiguousNodes = (
  nodes,
) => (
  nodes
  .reduce(
    (
      prevState,
      node,
    ) => {
      if (
        prevState
        .scannedIds
        .includes(node.id)
      ) {
        return prevState
      }

      const contiguousIds = (
        getContiguousIds({
          node,
          nodes,
        })
      )

      const {
        largestContiguousIds,
        scannedIds,
      } = prevState

      return {
        largestContiguousIds: (
          contiguousIds.length
          > largestContiguousIds.length
          ? contiguousIds
          : largestContiguousIds
        ),
        scannedIds: (
          scannedIds
          .concat(contiguousIds)
        ),
      }
    },
    {
      largestContiguousIds: [],
      scannedIds: [],
    },
  )
  .largestContiguousIds
)

Это же безумие! Я сомневался, стоит ли показывать такой код – это черновая версия. Судя по этому черновику, меня бы не взяли в Google.

Давайте шаг за шагом его упростим.

Рекурсивная функция

getContiguousIds – это наша рекурсивная функция, она вызывается один раз для каждого блока. После каждого цикла список смежных блоков обновляется.

В этой функции есть всего одно условие: этот блок уже есть в списке? Если нет, снова вызываем getContiguousIds: так у нас появится обновленный список смежных блоков, который возвращается к редуктору и используется в следующем adjacentId.

Вы можете спросить: как добавляются значения к contiguousIds? Это происходит, когда мы используем concat, объединяя текущий блок в contiguousIds. Каждый раз, когда происходит рекурсия, нужно убедиться, что текущий блок добавляется в список contiguousIds, прежде чем зацикливать adjacentIds.

Постоянное добавление текущего блока гарантирует, что мы не столкнемся с бесконечной рекурсией.

Цикл

Вторая половина этой функции также проходит через каждый блок по одному разу.

У нас есть редуктор рекурсивной функции. Он проверяет, просканирован ли код. Если да, то цикл продолжается до тех пор, пока не найдется не просканированный блок, или пока мы не дойдем до конца цикла.

Если блок не был просканирован, вызовите getContiguousIds и подождите. Это происходит синхронно, но может занять некоторое время.

Как только мы получим список contiguousIDs, сравните его со списком largestContiguousIDs.Если он больше, сохраните это значение.

Чтобы отмечать просканированные данные, добавим contiguousIDs в список scannedIds.

Получилось довольно наглядно и понятно.

Выполнение

Даже обрабатывая 10 000 блоков трех случайных цветов, алгоритм не сталкивается с переполнением стека. Если бы блоки были одного цвета, возможно, переполнение стека могло произойти: рекурсивной функции пришлось бы проходить 10 000 рекурсий.

Последовательная итерация

Стек вызова функции меньше, чем память, поэтому следующий шаг – сделать все за один цикл.

Мы будем отслеживать список, состоящий из списков блоков и пополнять его до конца цикла.

В этом методе важно, чтобы всевозможные списки блоков хранились в памяти до конца цикла. В примере с рекурсией в памяти сохранялся только самый длинный список.

const getLargestContiguousNodes = (
  nodes,
) => (
  nodes
  .reduce(
    (
      contiguousIdsList,
      {
        adjacentIds,
        id,
      },
    ) => {
      const linkedContiguousIds = (
        contiguousIdsList
        .reduce(
          (
            linkedContiguousIds,
            contiguousIds,
          ) => (
            contiguousIds
            .has(id)
            ? (
              linkedContiguousIds
              .add(contiguousIds)
            )
            : linkedContiguousIds
          ),
          new Set(),
        )
      )

      return (
        linkedContiguousIds
        .size > 0
        ? (
          contiguousIdsList
          .filter((
            contiguousIds,
          ) => (
            !(
              linkedContiguousIds
              .has(contiguousIds)
            )
          ))
          .concat(
            Array
            .from(linkedContiguousIds)
            .reduce(
              (
                linkedContiguousIds,
                contiguousIds,
              ) => (
                new Set([
                  ...linkedContiguousIds,
                  ...contiguousIds,
                ])
              ),
              new Set(adjacentIds),
            )
          )
        )
        : (
          contiguousIdsList
          .concat(
            new Set([
              ...adjacentIds,
              id,
            ])
          )
        )
      )
    },
    [new Set()],
  )
  .reduce((
    largestContiguousIds = [],
    contiguousIds,
  ) => (
    contiguousIds.size
    > largestContiguousIds.size
    ? contiguousIds
    : largestContiguousIds
  ))
)

Еще один безумный код. Давайте в нем разберемся. Цикл проходит каждый блок по одному разу. Теперь с помощью contiguousIdsList мы должны проверить, находится ли наш ID в списке, состоящем из списков блоков.

Если какого-то блока еще нет ни в одном списке contiguousIds, мы добавим его и его adjacentIds. Таким образом, во время циклов какие-то еще блоки будет связаны с этим.

Если блок уже есть в одном из списков, возможно, он есть в нескольких из них. Свяжем все это вместе и удалим несвязанные блоки из contiguousIdsList.

Когда будет готов список, состоящий из списков блоков, мы проверяем, какой из них самый большой. Готово! 😉

Выполнение

В отличие от алгоритма с рекурсией, этот алгоритм справляется с сеткой из 10 000 блоков одного цвета.

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

Итерация случайным образом

Я решил взять методологию алгоритма с рекурсией и применить ее итеративно.

Я потратил целую ночь, пытаясь вспомнить, как динамически менять индекс в цикле, и пришел к while(true). Прошло так много времени с тех пор, как я писал традиционные циклы, что я практически все забыл.

Теперь у меня есть оружие, иду в атаку! Я потратил слишком много времени, пытаясь ускорить работу алгоритмов выше, поэтому решил использовать старый добрый метод мутации данных.

Цель этого алгоритма состояла в том, чтобы обработать каждый блок ровно один раз и сохранить информацию только о самом большом участке одного цвета:

const getLargestContiguousNodes = (
  nodes,
) => {
  let contiguousIds = []
  let largestContiguousIds = []
  let queuedIds = []
  let remainingNodesIndex = 0

  let remainingNodes = (
    nodes
    .slice()
  )

  while (remainingNodesIndex < remainingNodes.length) {
    const [node] = (
      remainingNodes
      .splice(
        remainingNodesIndex,
        1,
      )
    )

    const {
      adjacentIds,
      id,
    } = node

    contiguousIds
    .push(id)

    if (
      adjacentIds
      .length > 0
    ) {
      queuedIds
      .push(...adjacentIds)
    }

    if (
      queuedIds
      .length > 0
    ) {
      do {
        const queuedId = (
          queuedIds
          .shift()
        )

        remainingNodesIndex = (
          remainingNodes
          .findIndex(({
            id,
          }) => (
            id === queuedId
          ))
        )
      }
      while (
        queuedIds.length > 0
        && remainingNodesIndex === -1
      )
    }

    if (
      queuedIds.length === 0
      && remainingNodesIndex === -1
    ) {
      if (
        contiguousIds.length
        > largestContiguousIds.length
      ) {
        largestContiguousIds = contiguousIds
      }

      contiguousIds = []
      remainingNodesIndex = 0

      if (
        remainingNodes
        .length === 0
      ) {
        break
      }
    }
  }

  return largestContiguousIds
}

module.exports = getLargestContiguousNodesIterative2

Большинство кандидатов в Google написали бы точно такой же код: несмотря на это, код получился не очень читабельный. Я сам не могу сходу объяснить, что здесь происходит. Чтобы объяснить, сначала нужно посмотреть весь код целиком.

Вместо добавления новых ID в список уже отсканированных, мы выделяем значения из массива remainingNodes.

Все просто! Никому не рекомендую этот метод: сам я пришел к нему, потому что хотел попробовать какой-нибудь другой подход.

Разбиение

Я разбил алгоритм на три раздела, разделенные блоками if.

Давайте начнем со второго раздела. Проверяем queuedIds. Если есть queuedIds, мы делаем еще один цикл по элементам в очереди, чтобы увидеть, есть ли они в remainingNodes.

В третьем разделе все зависит от результатов второго. Если больше нет queuedIds, а remainingNodesIndex равен −1, то мы закончили с этим списком блоков, и нужно начать с нового корневого блока. Новый корневой блок всегда имеет индекс 0, потому что мы сращиваем remainingNodes.

Вернувшись в начало цикла, я мог бы использовать while(true), но мне захотелось найти вариант на всякий случай. Это удобно при отладке, потому что бесконечные циклы могут стать довольно сложной проблемой.

После этого мы сращиваем блок, добавляем его в contiguousIds и добавляем adjacentIds в очередь.

Выполнение

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

Оптимизация данных

Группировка блоков одного цвета

Поскольку нам нужны только блоки одного цвета, мы можем сгруппировать одинаково окрашенные блоки в алгоритме с последовательной итерацией.

Разделение его на три массива уменьшает используемый объем памяти и количество циклов в списке списков. Тем не менее, это не решает ситуацию с сеткой, где все блоки одинакового цвета, поэтому так не получится исправить алгоритм с рекурсией.

Это также означает, что можно выполнить многопоточную операцию, сократив время выполнения почти на треть.

При последовательном выполнении нужно сначала запустить самый большой из трех разделов. Если самый большой раздел больше двух других вместе взятых, ничего проверять не нужно.

Максимально возможный размер

Вместо того, чтобы через определенные интервалы проверять, нашли ли мы самый большой список, можно проверять это каждую итерацию.

Если самый большой участок больше или равен половине доступных блоков (больше 5 000), очевидно, что он и есть самый большой.

Используя алгоритм с произвольной итерацией, можно найти самый большой размер списка и посмотреть, сколько блоков осталось. Если их осталось меньше, чем блоков в самом большом списке, то мы нашли самый большой участок.

Используйте рекурсию

Да, у нее есть свои ограничения, но ее все равно можем использовать. Все, что нам нужно сделать, это проверить количество оставшихся блоков. Если число ниже предела стека, можно переключиться на более быстрый алгоритм с рекурсией. Рискованно, но это уменьшит время выполнения, поскольку мы продвинулись дальше в цикле.

Используйте цикл for

Так как мы знаем максимальное количество элементов, смена функции reduce на традиционный цикл for принесет небольшую пользу.

Почему-то методы Array.prototype намного медленнее циклов for.

Используйте хвостовую рекурсию

Я не рассматривал этот метод, потому что алгоритму с хвостовой рекурсией понадобилась бы отдельная статья.

Это большая тема, которую пришлось бы долго объяснить. Хвостовую рекурсию можно применить в алгоритме с рекурсивной функцией, однако вряд ли так будет быстрее, чем в случае с циклом while.

RxJS: обслуживание против производительности

Есть способ переработать все эти алгоритмы так, чтобы они стали понятнее и легче с точки зрения обслуживания. В качестве основного решения я использовал RxJS в стиле Redux-Observable, но без Redux.

Я решил сначала написать код стандартными способами, а затем передавать данные с помощью RxJS, чтобы увидеть, как далеко это зайдет.

Я сделал 3 версии в RxJS и позволил себе несколько допущений, чтобы ускорить время выполнения. Все три версии выдают результат медленнее, даже при увеличении количества строк и столбцов.

Всю неделю я придумывал возможные решения и прочесывал каждый сантиметр кода. Я даже лежал на полу, закрыв глаза, и думал, думал, думал. Идеи становились все лучше и лучше, но я все равно не укладывался в ограничения скорости JavaScript.

Я мог бы внести целый список оптимизаций, но тогда код получился бы нечитабельным, а мне этого не хотелось (но я все-таки внес одну оптимизацию).

Наконец-то я получил приемлемое решение – самое быстрое: работает за половину отведенного времени. В целом, это лучшая оптимизация кода.

Единственный раз, когда у меня получилась последовательная итерация наблюдаемых данных с большим объемом памяти, это в случае, где все блоки одного цвета. Это был единственный раз. Технически такое решение лучше, чем рекурсивное, потому что в том случае переполняется стек.

Посмотреть код можно на GitHub.

Финальная статистика

В общем, самый большой участок одного цвета составлял в среднем где-то от 30 до 80 блоков.

Сколько времени занимает каждый алгоритм:

## Random Colors

Time | Method
--- | ---
229.481ms | Recursive
272.303ms | Iterative Random
323.011ms | Iterative Sequential
391.582ms | Redux-Observable Concurrent
686.198ms | Redux-Observable Random
807.839ms | Redux-Observable Sequential


## One Color

Time | Method
--- | ---
1061.028ms | Iterative Random
1462.143ms | Redux-Observable Random
1840.668ms | Redux-Observable Sequential
2541.227ms | Iterative Sequential

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

Метод Redux-Observable Concurrent неэффективен в случае, если все блоки в сетке одного цвета. Я пробовал кучу способов ускорить его, но ничего не вышло.

Разработка игр

За все время работы я дважды сталкивался с подобным кодом. В гораздо меньших масштабах такое было в Lua и во время работы над моей инди-игрой Pulsen.

В первой ситуации я работал над картой мира. У нее был предопределенный список блоков, и я обрабатывал этот список в режиме реального времени. Так появилась возможность нажимать [ВЛЕВО], [ВПРАВО], [ВВЕРХ] и [ВНИЗ] и перемещаться по карте мира, даже если угол карты был немного смещен.

Я также писал генератор блоков для неизвестного списка элементов со значениями X и Y. Звучит знакомо? Еще мне пришлось центрировать эту сетку на экране. Это было гораздо проще сделать в HTML, чем на игровом движке. Хотя центрировать кучу абсолютно позиционированных элементов div тоже нелегко.

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

Хочу подчеркнуть, что задача TechLead может вам встретиться в работе. Это возможно, но обычно для приложений JavaScript скорость – не ключевой фактор.

Судя по другим видео, в Google TechLead работал с Java. Я предполагаю, что на собеседованиях, которые он проводил, была важна скорость исполнения. Вероятно, у них была куча рабочих задач, обрабатывающих огромные объемы данных, поэтому необходима скорость.

Но тогда это могла быть работа для специалистов по HTML и CSS, и он просто троллил собеседника: кто знает?

Заключение

Судя по финальной статистике, самый нечитаемый код работал быстрее всех и соответствовал всем требованиям. А теперь попытайтесь обслужить этот кошмар!

Я потратил довольно много времени на разработку не-RxJS версий. Скорее всего, это потому, что более быстрые версии требовали комплексного мышления. Redux-Observable позволяет думать небольшими порциями.

Это была действительно интересная и непростая задача. Сначала она показалась мне очень сложной, даже для собеседования в Google, но когда я разбил ее на отдельные шаги, все получилось 🙂

А какие сложные задачи приходилось решать вам? Пишите в комментариях 😉

10 заковыристых вопросов на собеседовании в Google

Компания Google известна во всем мире. И очень многие хотели бы там работать. Однако, не так-то просто устроиться в эту корпорацию. Помимо профессиональных качеств, необходимо обладать высокой эрудицией, иметь нестандартное мышление и быть готовым во время собеседования ответить на эти заковыристые вопросы. Проверьте и себя, получится ли у вас?

1. За сколько денег вы помоете все окна в Сиэтле?

Это один из вопросов, где надо проявить хитрость и дать самый простой ОТВЕТ: «Допустим, 10 $ за окно».

2. Сколько настройщиков пианино во всём мире?

Всё зависит от того, какова потребность в услугах настройщиков. Если пианино надо настраивать раз в неделю, и это занимает один час, а настройщик работает 8 часов в день в течение 5 дней в неделю, то получается, что он может настраивать 40 пианино каждую неделю.

ОТВЕТ: «Один настройщик на каждые 40 пианино».

3. Почему крышка канализационного люка круглая?

Ответ: «Круглая форма крышки позволяет гарантировать то, что сама крышка не провалится в люк при её монтаже или демонтаже (прямоугольная же крышка легко входит в корпус люка по диагонали)».

4. Можете ли вы разработать план эвакуации из Сан Франциско?

Интересный конечно вопрос. А вариант ответа такой: «А какое бедствие запланировано на сегодня»?

5. Сколько раз за день стрелки часов пересекаются?

ОТВЕТ: «22 раза»

00:00

1:05

2:11

3:16

4:22

5:27

6:33

7:38

8:44

9:49

10:55

12:00

13:05

14:11

15:16

16:22

17:27

18:33

19:38

20:44

21:49

22:55

6. Вам надо проверить, правильно ли Боб записал ваш номер телефона,

но вы не можете спросить его об этом прямо. Вам надо написать ему записку и отдать Еве, которая отнесёт её Бобу и принесёт обратно ответ от него. Что вы напишите в записке, чтобы Боб понял, что вы от него хотите, а Ева не смогла узнать ваш номер телефона?

ОТВЕТ: Поскольку вы всего лишь «проверяете», то в записке просто «Попросите его позвонить вам в определённое время».
Если он позвонит, значит ваш номер у него записан правильно.

Есть и второй вариант ответа: «Надо использовать контрольную сумму. В записке попросите Боба сложить все цифры вашего телефонного номера и написать на листе результат. Когда Ева принесет его ответ, вам надо будет лишь проверить полученную сумму.»

7. Вы — капитан пиратского судна,

и ваша команда собирается голосовать, как разделить награбленное золото. Если с вами согласится меньше половины пиратов, вы умрете. Как вы поделите золото так, чтобы получить хорошую часть добычи, но все же остаться в живых?

ОТВЕТ: «Надо разделить награбленное поровну между 51% всей команды».

8. У вас есть 8 мячиков одинакового размера,

7 из них одинакового веса, а один весит чуть больше остальных. Сможете ли вы найти мячик, который тяжелее остальных, используя весы только два раза?

ОТВЕТ: «Возьмите 6 из 8 мячей и положите по 3 на каждую чашу весов.

Если тяжёлого мячика в этой группе нет, то никакая чаша не перевесит. Теперь вам останется взвесить оставшиеся 2 мяча и решить задачу.

Если же одна из чаш с 3 мячиками перевесила другую, это значит, что тяжелый мячик в этой чаше. Возьмите 3 мячика из чаши, которая перевесила, и два из них положите на весы. Если один из них перевесит — он и будет мячиком, который вы искали. Если же они весят одинаково, то значит, мяч, который вы отложили – это и есть тот тяжелый мяч, который надо было найти.»

9. Объясните тремя предложениями, что такое база данных вашему 8-летнему племяннику?

Суть вопроса заключается в том, чтобы проверить, способен ли соискатель говорить о сложных понятиях на простом языке.

ОТВЕТ может быть таким: «База данных — это компьютер, который помнит много информации о разных вещах. Люди пользуются им, если кому-то нужна эта информация. А теперь иди поиграй на улице».

10. Человек направил свой автомобиль на отель, но потерпел неудачу. Что случилось?

ОТВЕТ: «Он застрял на бордюре».

Источник

JoinUs
2020-10-07

Техническое собеседование в Google на Software Engineer — мой опыт / Хабр

На этой неделе я проходила техническое собеседование в Google и, хоть и провалила, хочу поделиться опытом в этой статье.

HR из Google вышла на меня сама. Мне 25 лет, Junior Android developer, у меня есть свой простой сайт-визитка, 3 опубликованных довольно примитивных приложения в маркете, живой гитхаб профиль и 2к репутации на StackOverflow. Как именно меня нашли я не знаю. 1 раз я сама подавалась на вакансию к ним, давно — может это повлияло. Кроме этого я часто программирую для удовольствия — я гуглю очень много по теме и возможно мои поисковые запросы складывают обо мне хорошее впечатление. Остается только догадываться.

Первое собеседование с HR было очень легко пройти. Мы прошлись по моему резюме, она указывала на мои сильные стороны, а мне нужно было просто поддакивать. Ей понравилась что я люблю open-source разработку, Android и что у меня математическое мышление. Она так же задала мне пару простых вопросов на алгоритмы сортировки и их big-O, попросила явно указать линк на мой GitHub в CV. Она так же рассказала про процесc отбора.

Отбор состоит из нескольких собеседований. Мой следующий этап — техническое Phone-screen интервью. Оно проходит через Hangouts. Мне сообщили, что в случае найма я смогу выбрать страну (только EMEA) и город, где смогу работать, а следовательно и проект. Google вначале набирает сотрудников, а потом распределяет. Также сказали, что я сколько угодно долго могу готовиться к техническому интервью, но рекомендуют 2 недели. Я попросила 6 недель. Дату и время испытуемый выбирает сам. В Google готовы подстраиваться под Вас.

Для подготовки HR посоветовала прочесть книгу Cracking the Coding Interview Steve Yegge’s Blogspot. А так же практиковаться на https://codeforces.com/. Кроме этого меня попросили записаться на 1 часовой online тренинг для кандидатов — как правильно отвечать на вопросы тех интервью. На нем присутствует программист от Google и около 7 кандидатов. На этом тренинге рассматривается одна задача, все думают, кто хочет задает вопросы или предлагает решения. Потом тренер предлагает шаблон, как отвечать по задаче. Нам дали понять, что нормально и даже хорошо, если вы вначале выдаете наивное (не эфективное) решение. Вы сообщаете о проблемах вашего решения, назваете Run-time (Big-O) алгоритма и предлагаете улучшения. Но по факту на собеседовании вы не успеете закодить несколько решений — только одно. Так что примитивные обсуджайте вслух, а финальное начинайте кодить.

В переписке с HR я спросила про зарплату, зависит ли она от страны, которую я выберу. Мне не называли сумм, но сказали что разочарована я не буду, что компания входит в топ по зарплатам для всех стран. Вот в этом посте тема зарплат раскрыта более полно, и вообще хороший блог от сотрудника Google.

На техническом интервью было 2 вопроса. Один совсем простой про работу со String. По сложности — 1 курс универа. Второй вопрос сложнее (я предлагала Бинарный поиск и прочее) — субъективно 3 курс универа. Вопросы на сообразительность и знание университетской программы, в целом довольно простые, что меня удивило. Во время ответа важно сразу писать код (в Google doc). Код должен быть компилируемым. Псевдокод не подойдет.

Мне показалось, что я отвечала хорошо, хотя собеседование я не прошла. Сказали, что не хватает знаний в алгоритмах.

Вот выводы, которые я сделала:

— Хорошо перед собеседованием прочесть книгу, что советует HR (я читала лишь первые 20 страниц).

— Хорошо пройти пару курсов на Coursera по «Алгоритмам и структурам данных» — это дает ещё и технический английский.

— На тренинг нужно записаться как можно раньше, Ваши знания на нем не оценивают, зато вы получите больше времени для правильной подготовки.

— Самые важные темы — Big-O notation, алгоритмы, графы, большие данные. Это не полный список.

Если вы проходите phone-screen интервью, следующий этап — 5 интервью в офисе Google в 1 день с перерывом на обед.

Отбор очень жесткий. Давайте посчитаем. Если вы хорошо готовились к каждому интервью и имеете шансы на каждом собеседовании 80% из 100, что очень круто, то по теории вероятности после 6 технических интервью Ваши шансы равны 0.8^6 = 0.26. Короче Вас скорее не возьмут, чем возьмут. Но все равно пробовать стоит.

Следующая попытка собеседоваться может быть только через 1 год. Вот такие ограничения.

Update 2018: В этом году я снова проходила интервью в Google и снова они мне первые написали. Снова завалила на техническом. Давали 1 задачу на работу с текстом, типа на алгоритм MapReduce, парсинг строк, работа со String, объеденение данных по заданому правилу. Отвечать было сложно и был стрес. Сама бы решила задачу эту только в IDE и то за 2 дня. Я поняла, что лучший способ подготовки — сайт https://codeforces.com/. Решать задачи, подобные Google — отдельный навык, которой к вашей практике в офисе не имеет отношения. Codeforces даст этот навык.

Google Процесс собеседования на роль разработчика программного обеспечения в 2020 г. / Хабр

Здравствуйте! Я только что закончил интервью с Google и хотел быстро рассказать вам о некоторых интересных и разочаровывающих шагах процесса, чтобы вы могли понять, чего ожидать от собеседований в Google и связанных с ними шагов. Я также поделюсь некоторыми советами, как подготовиться к собеседованию и как избежать ошибок.

Если вы ищете историю успеха, эта публикация не для вас. На самом деле я провалил процесс собеседования, но весь этот опыт был для меня довольно интересным и привел меня к другому этапу моей карьеры.Подробнее об этом я расскажу в конце поста. Все имена и идентификационные данные были изменены для защиты конфиденциальности сотрудников Google.

Первоначальное отборочное интервью

Моя история начинается дождливым октябрьским утром. Я получил сообщение от Оливии, рекрутера Google, с темой «Заинтересованы в решении серьезных инженерных проблем в Google?». На тот момент я недавно закончил несколько проектов и искал новые задачи.Работа в Google показалась мне хорошей возможностью, которую я не хотел упускать, поэтому я быстро ответил: «Да, определенно» и записался на прием через Google Hangouts.

Наш чат состоялся через два дня через Hangouts. Оливия рассказала мне, как здорово работать в Google и как выглядит процесс приема на работу. Когда я спросил о деталях должности, она сказала мне, что они ищут кого-то для своего нового офиса в Варшаве, Польша, для поддержки и развития функций Google Cloud для корпоративных клиентов.Я спросил о точных обязанностях, которые будут входить в мою компетенцию, и о команде, частью которой я буду, но она сказала, что на данном этапе это не имеет значения — я могу выбрать желаемую команду и должность позже, когда все этапы собеседования процесс были завершены. Это был разочаровывающий момент №1 для меня, но я решил, что стоит продолжать.

Раздражающий момент №1. Что, если бы в Google не было команды, к которой я бы хотел присоединиться?

Из того, что мне сказала Оливия, процесс собеседования в Google состоит из трех этапов: во-первых, есть два удаленных собеседования по кодированию алгоритмов и структур данных.Если вы необыкновенный человек, у вас может быть всего одно собеседование, но для среднего программиста — два. Следующий этап — это собеседование на месте в одном из офисов Google, которое включает в себя несколько собеседований по кодированию (снова!), Собеседование по проектированию системы и, наконец, что не менее важно, «Гуглость и лидерство». Последний определяет, насколько хорошо вы впишетесь в компанию.

Наконечник №1. Процесс собеседования в Google сложен и займет несколько недель вашей жизни. Чтобы подготовиться к этому, нужно пойти ва-банк.

По словам Оливии, «даже если вы пройдете все собеседования и дойдете до финального этапа, это не гарантирует, что вы получите работу. Потому что в процессе приема на работу в Google есть еще один этап, который пройдет без вас. На этом последнем этапе несколько старших сотрудников Google (которые не знают вас и никогда с вами не разговаривали) изучат ваше резюме и отзывы интервьюеров и решат, впишетесь ли вы в Google или нет. Только с их одобрения вы сможете получить работу ». Хорошо, пора расстраивать момент №2.

Момент разочарования №2. Вы можете пройти каждое собеседование с оценкой A и все равно не получить работу, потому что старший сотрудник Google решит, что вы не тот человек, которого следует нанять.

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

Этап 1. Интервью с дистанционным кодированием

Позже Оливия записала меня на первое дистанционное собеседование по программированию. Тем временем я решил несколько проблем с алгоритмами на сайте geeksforgeeks и прошел «Курс подготовки к собеседованию».Я не могу его рекомендовать, потому что задачи в этом курсе очень абстрактны, а платформа содержит ошибки, но для первой задачи по кодированию этого было достаточно.

Звонок был через Google Hangouts. Интервьюер вкратце рассказал мне о себе и попросил решить задачу по кодированию. Я не могу рассказать вам подробности проблемы кодирования (это было бы несправедливо и в любом случае вам не сильно помогло бы). Единственное, чем я могу поделиться, так это то, что это был какой-то жадный алгоритм в среде шахматной игры. Я решил всю проблему за 50+ минут, практически без подсказок со стороны интервьюера.Решение включает тесты и код на Python. Все кодирование для этих типов интервью обычно делается в каком-то общем блокноте, и в данном случае это были Документы Google. Откровенно говоря, сам интервьюер и задача были интересными.

Я ждал результатов: хорошо я выступил или нет? Результаты были готовы только через неделю, и только тогда, когда я попросил рекрутера дать новую информацию. Это станет общей темой для всех следующих собеседований: результаты будут готовы только через неделю и сообщение рекрутеру.

Наконечник №2. Не стесняйтесь спрашивать рекрутера о результатах вашего последнего собеседования.

Оливия сказала, что результат моего интервью был «в большинстве случаев положительным». Единственным минусом было время, затраченное на решение задачи: оно должно было составить не более 45 минут. Поэтому Оливия попросила меня пройти еще одно дистанционное собеседование по программированию. В этот момент я понял, что в глазах Google я был средним разработчиком программного обеспечения, а не выдающимся.Но это нормально — я решил двигаться дальше.

Второе удаленное собеседование было через неделю, и оно было почти таким же, как и первое. Проблема кодирования была достаточно простой. Это была комбинаторная задача, и для ее решения вам нужно было придумать математическую формулу и тщательно продумать все крайние случаи. Решение заняло у меня всего 40 минут, и я был очень взволнован тем, что решил эту проблему так быстро и элегантно. Ждала окончательного отзыва от рекрутера. Следующим шагом будет поездка в Польшу для прохождения собеседования на месте.

Была неделя ожидания, в течение которой рекрутер не отвечал на мои сообщения. Затем Оливия ответила, что она в командировке и ответит мне, когда вернется в офис. Через две недели после моего последнего интервью мне позвонила Оливия. Она сказала, что мое последнее интервью было «в основном положительным». Единственным минусом было то, что я использовал много псевдокода. Она также упомянула, что я хорошо тестирую (возможно, это потому, что четыре года назад я прочитал книгу «Как Google тестирует программное обеспечение», кто знает?)

Совет № 3. Вы должны покрыть каждую строку кода тестами на собеседовании по кодированию. Просто произнесите это вслух, когда интервьюер попросит вас проверить вашу функцию, и только после этого приступайте к написанию тестов.

После столь многообещающего начала нашего разговора она сказала, что они не знают, какими должны быть следующие шаги, поэтому мне нужно немного подождать. Через неделю я получил сообщение от Оливии, в которой говорилось, что теперь моим рекрутером будет Джордж, еще один парень из лондонского офиса, и что мне нужно пройти еще два удаленных собеседования по кодированию.Я получу все подробности от Джорджа в свое время.

Позже в тот же день мне позвонил Джордж. Он сказал, что мои собеседования по кодированию будут проводиться удаленно через месяц, и что я должен выбрать дату. Он отказался сказать, почему эти собеседования будут проходить дистанционно, но упомянул, что эти проблемы с кодированием будут намного сложнее, чем предыдущие, и если я их прохожу, меня пригласят на оставшиеся собеседования в их офисе. Я решил, что уже начал этот процесс и должен довести его до конца.

Этап 2. Дополнительные собеседования с дистанционным кодированием

Я начал готовиться к еще двум интервью. На этот раз я использовал HackerRank и его «Комплект для подготовки к интервью». Очень рекомендую — это очень похоже на то, что произошло на собеседовании.

Наконечник №4. HackerRank и его «Комплект для подготовки к интервью» — лучшие ресурсы для подготовки к проблемам программирования Google.

Сразу после новогодних праздников я получил временные интервалы для собеседований — первое — 20 января в 11а.м. (продолжительность 45 минут), а следующий — через 15 минут. Вау, это было неожиданно. Я спросил Джорджа, можем ли мы разделить интервью по дням, и получил неожиданный ответ: «К сожалению, Илья, нам нужно будет провести их в тот же день, чтобы минимизировать количество шагов в процессе, который вы проходите, и чтобы максимально эффективно использовать время ». Это был еще один неприятный момент. Я ждал их несколько недель, а теперь они захотели «сэкономить время».

Момент разочарования №3. Google не уважает ваше время.

На этот раз мне пришлось нелегко. Первое интервью было о хитрых поисках по графику. Сначала я только придумал решение методом перебора и понял, что это можно будет сделать с помощью графика позже, но было уже слишком поздно.

Второе интервью было об «игре 2048». Это был первый раз, когда я не мог четко понять задачу, возможно, потому, что я вообще не играл в игру 2048 года. Вопросы касались стратегии победы в игре 2048 и элегантного решения для генерации следующего состояния доски.Только через два дня я понял, что игра 2048 — это своего рода «Игра пятнадцати» и решение можно найти с помощью алгоритма поиска A *.

Это была явно моя вина — я не уделял много внимания алгоритмам графиков во время подготовки. Так что не повторяйте моих ошибок — как я сказал ранее, вложите все свои силы в подготовку к собеседованию.

После недели ожидания Джордж позвонил мне и сказал, что я не прошел собеседование и мне нужно улучшить свои навыки в нотации большой буквы O и теории графов.Он упомянул, что я могу повторно подать заявку в Google в следующем году.

Что я вынес из процесса собеседования в Google?

Когда я начал проходить собеседование в Google, я ясно понял, что мои шансы получить работу не так уж высоки. Что я получил после всех этих интервью? Опыт — большой опыт — и немного понимания того, как работает Google внутри компании. У Google есть миф о том, что это рабочее место мечты. Может быть, но не для меня. После нескольких месяцев собеседований я понял, что Google — это просто еще одна крупная корпоративная компания, у которой есть все эти бюрократические проблемы, непрозрачные процессы и странные правила.Дополнительную информацию о другой стороне Google можно найти в сообщении Майкла Линча «Почему я ушел из Google, чтобы работать на себя».

Что дальше?

После сложного интервью с Google и нескольких собеседований с небольшими стартапами и компаниями я пришел к выводу, что работа — не для меня. Я хочу быть предпринимателем и создать свою компанию. Первый очевидный шаг для меня — фриланс. Я думаю, что хорошо разбираюсь в веб-разработке с полным стеком (я предпочитаю Node.js / Javascript / React / Docker, и вы можете проверить, что я уже сделал, на странице «Мои проекты»).

Сейчас я с нетерпением ищу клиентов и контракты. Если вы думаете, что у вас есть что-то для меня или вы знаете кого-то, кому нужен удаленный разработчик полного стека, давайте поговорим. Я рад поговорить о делах или просто дать вам бесплатный совет.

Первоначально опубликовано на ipirozhenko.com/blog/google-interview-2020

.

140 Google Вопросы для интервью | Impact Interview

ТОЛЬКО ОПУБЛИКОВАНО: более 60 сценариев согласования заработной платы KILLER, которые помогут вам получить более высокую зарплату.

Вот список из 140 вопросов для собеседования в Google. Многие из наших клиентов прошли собеседование и получили предложения о работе в Google. Свяжитесь с нами, чтобы получить бесплатный 15-минутный анализ интервью перед собеседованием в Google.

СМОТРИ ТАКЖЕ: собеседование с Google PM, собеседование с Google Software Engineer, собеседование с Google Product Marketing

Ссылка на вопросы интервью в Google для:

Google Вопросы для собеседования: менеджер по маркетингу продукта

• Почему вы хотите присоединиться к Google?
• Что вы знаете о продуктах и ​​технологиях Google?
• Если вы менеджер по продукту Google Adwords, как вы планируете продвигать это на рынке?
• Что бы вы сказали во время семинара по продуктам AdWords или AdSense?
• Кто конкуренты Google и как Google конкурирует с ними?
• Вы когда-нибудь пользовались продуктами Google? Gmail?
• Каков творческий способ продвижения бренда и продукта Google?
• Если вы являетесь менеджером по маркетингу продукта Google Gmail, как вы планируете продвигать его, чтобы за 6 месяцев привлечь 100 миллионов клиентов?
• Сколько денег, по вашему мнению, Google зарабатывает ежедневно на рекламе в Gmail?
• Назовите технологию, о которой вы недавно читали.А теперь расскажите мне о вашем собственном творческом исполнении для рекламы этого продукта.
• Допустим, рекламодатель зарабатывает 0,10 доллара каждый раз, когда кто-то нажимает на его объявление. Только 20% людей, посещающих сайт, нажимают на их рекламу. Сколько людей нужно посетить сайт, чтобы рекламодатель заработал 20 долларов?
• Оцените количество студентов, которые являются выпускниками колледжей, посещают четырехлетние школы и заканчивают обучение с работой в Соединенных Штатах каждый год.

Google Вопросы для собеседования: менеджер по продукту

• Как бы вы увеличили подписку на GMail?
• Как наиболее эффективно отсортировать миллион целых чисел?
• Как бы вы изменили позиции предложений Google для противодействия угрозам со стороны Microsoft?
• Сколько мячей для гольфа поместится в школьный автобус?
• Вы уменьшились до никеля, и ваша масса пропорционально уменьшилась, чтобы сохранить исходную плотность.Затем вас бросают в пустой стеклянный блендер. Лезвия начнут двигаться через 60 секунд. Чем ты занимаешься?
• Сколько стоит мыть все окна в Сиэтле?
• Как узнать, увеличивается или уменьшается стек машины в памяти?
• Объясните базу данных в трех предложениях своему восьмилетнему племяннику.
• Сколько раз в день стрелки часов пересекаются?
• Вам нужно добраться из пункта А в пункт Б. Вы не знаете, сможете ли вы туда добраться.Что бы вы сделали?
• Представьте, что у вас есть шкаф, полный рубашек. Очень сложно найти рубашку. Итак, что вы можете сделать, чтобы упорядочить свои рубашки, чтобы их было легче найти?
• Каждый мужчина в деревне из 100 супружеских пар изменил своей жене. Каждая жена в деревне мгновенно узнает, когда обманул другой мужчина, но не знает, когда ее собственный муж. В селе действует закон, запрещающий супружескую измену. Любая жена, которая сможет доказать, что ее муж неверен, должна убить его в тот же день.Женщины деревни никогда не нарушили бы этот закон. Однажды царица деревни приходит к ней и объявляет, что по крайней мере один муж изменил ей. Что происходит?
• В стране, где люди хотят только мальчиков, каждая семья продолжает иметь детей, пока у них не родится мальчик. Если у них есть девочка, у них будет еще один ребенок. Если у них будет мальчик, они остановятся. Какое соотношение мальчиков и девочек в стране?
• Если вероятность увидеть машину через 30 минут на трассе равна 0.95, какова вероятность наблюдения за автомобилем через 10 минут (при постоянной вероятности дефолта)?
• Если вы посмотрите на часы, и время покажет 3:15, то какой угол между часовой и минутной стрелками? (Ответ на это не ноль!)
• Четыре человека должны пересечь шаткий веревочный мост, чтобы ночью вернуться в свой лагерь. К сожалению, у них есть только один фонарик, и его хватает только на семнадцать минут. Мост слишком опасен для перехода без фонарика, и он достаточно прочен, чтобы выдержать одновременное движение двух человек.Каждый из отдыхающих идет с разной скоростью. Один может перейти мост за 1 минуту, другой — за 2 минуты, третий — за 5 минут, а переход на медленный тычок занимает 10 минут. Как туристы преодолевают путь за 17 минут?
• Вы на вечеринке с другом, и здесь 10 человек, включая вас и друга. друг делает вам пари, что за каждого найденного вами человека, у которого такой же день рождения, как у вас, вы получите 1 доллар; за каждого найденного человека, у которого не такой же день рождения, как у вас, он получает 2 доллара.вы бы приняли пари?
• Сколько в мире настройщиков пианино?
• У вас есть восемь шаров одинакового размера. 7 из них весят одинаково, а один весит чуть больше. Как найти мяч, который тяжелее, если использовать весы и всего два взвешивания?
• У вас пять пиратов, ранжированных от 5 до 1 в порядке убывания. Главный пират имеет право предложить, как разделить между ними 100 золотых монет. Но остальные получают право голосовать за его план, и если с ним соглашается менее половины, его убивают.Как ему распределить золото, чтобы получить максимальную долю, но жить, чтобы им наслаждаться? (Подсказка: один пират получает 98 процентов золота.)
• Вам дается 2 яйца. У вас есть доступ к 100-этажному зданию. Яйца могут быть очень твердыми или очень хрупкими, что означает, что они могут разбиться при падении с первого этажа или даже не сломаться при падении со 100-го этажа. Оба яйца идентичны. Вам нужно выяснить самый высокий этаж 100-этажного здания, из которого можно уронить яйцо, не разбившись. Вопрос в том, сколько капель нужно сделать.В процессе вы можете разбить 2 яйца.
• Опишите возникшую техническую проблему и способы ее решения.
• Как бы вы разработали простую поисковую систему?
• Разработать план эвакуации для Сан-Франциско.
• Проблема с задержкой в ​​Южной Африке. Диагностируйте это.
• Какие три долгосрочные задачи стоят перед Google?
• Назовите три веб-сайта, не принадлежащих Google, которые вы часто посещаете и которые вам нравятся. Что вам нравится в пользовательском интерфейсе и дизайне? Выберите один из трех сайтов и прокомментируйте, над какой новой функцией или проектом вы будете работать.Как бы вы его спроектировали?
• Если бы в здании всего один лифт, как бы вы изменили дизайн? А если в доме всего два лифта?
• Сколько пылесосов производится в США в год?

Google Вопросы на собеседовании: инженер-программист

• Почему крышки люков круглые?
• В чем разница между мьютексом и семафором? Какой из них вы бы использовали для защиты доступа к операции приращения?
• Мужчина подтолкнул свою машину к гостинице и потерял состояние.Что случилось?
• Объясните значение «мертвой говядины».
• Напишите программу на C, которая измеряет скорость переключения контекста в системе UNIX / Linux.
• Для функции, которая производит случайное целое число в диапазоне от 1 до 5, напишите функцию, которая производит случайное целое число в диапазоне от 1 до 7.
• Опишите алгоритм обхода графа в глубину.
• Создайте библиотеку классов для написания карточных игр.
• Вам необходимо убедиться, что у вашего друга, Боба, есть ваш правильный номер телефона, но вы не можете спросить его напрямую.Вы должны написать вопрос на карточке и передать его Еве, которая отнесет карточку Бобу и вернет вам ответ. Что вы должны написать на карточке, кроме вопроса, чтобы Боб мог закодировать сообщение, чтобы Ева не могла прочитать ваш номер телефона?
• Как файлы cookie передаются в протоколе HTTP?
• Разработайте таблицы базы данных SQL для базы данных по аренде автомобилей.
• Напишите регулярное выражение, соответствующее адресу электронной почты.
• Напишите функцию f (a, b), которая принимает аргументы из двух символьных строк и возвращает строку, содержащую только символы, найденные в обеих строках в порядке a.Напишите версию с порядком N в квадрате и версию с порядком N.
• Вам предоставлен источник приложения, которое дает сбой при запуске. Запустив его 10 раз в отладчике, вы обнаружите, что он никогда не дает сбоев в одном и том же месте. Приложение является однопоточным и использует только стандартную библиотеку C. Какие ошибки программирования могли вызвать этот сбой? Как бы вы протестировали каждую из них?
• Объясните, как работает контроль перегрузки в протоколе TCP.
• В чем разница между final, finally и finalize в Java?
• Что такое многопоточное программирование? Что такое тупик?
• Напишите функцию (со вспомогательными функциями, если необходимо), вызываемую в Excel, которая принимает значение столбца Excel (A, B, C, D… AA, AB, AC,… AAA..) и возвращает соответствующее целочисленное значение (A = 1, B = 2,… AA = 26 ..).
• У вас есть поток бесконечных запросов (например: поисковые запросы Google в реальном времени, которые вводят люди). Опишите, как вы могли бы найти хорошую оценку в 1000 выборок из этого бесконечного набора данных, а затем написать для него код.
• Алгоритмы поиска по дереву. Напишите код BFS и DFS, объясните время выполнения и требования к пространству. Измените код для обработки деревьев со взвешенными ребрами и циклами с помощью BFS и DFS, заставьте код распечатать путь к состоянию цели.
• Вам дается список номеров. Когда вы дойдете до конца списка, вы вернетесь в начало списка (круговой список). Напишите наиболее эффективный алгоритм поиска минимального # в этом списке. Найдите любой заданный # в списке. Числа в списке всегда увеличиваются, но вы не знаете, где начинается круговой список, например: 38, 40, 55, 89, 6, 13, 20, 23, 36.
• Опишите структуру данных, которая используется для управления памятью. (стопка)
• В чем разница между локальными и глобальными переменными?
• Если у вас есть 1 миллион целых чисел, как бы вы их эффективно отсортировали? (измените конкретный алгоритм сортировки, чтобы решить эту проблему)
• В чем разница между static, final и const в Java.(если вы не знаете Java, они спросят нечто подобное для C или C ++).
• Расскажите о проектах вашего класса или рабочих проектах (выберите что-нибудь простое) … затем опишите, как вы могли бы сделать их более эффективными (с точки зрения алгоритмов).
• Предположим, у вас есть матрица NxN положительных и отрицательных целых чисел. Напишите код, который находит подматрицу с максимальной суммой ее элементов.
• Напишите код для переворота строки.
• Выполните разделение (очевидно, без использования оператора разделения).
• Напишите код, чтобы найти все перестановки букв в определенной строке.
• Какой метод вы бы использовали для поиска слова в словаре?
• Представьте, что у вас есть шкаф, полный рубашек. Очень сложно найти рубашку. Итак, что вы можете сделать, чтобы упорядочить свои рубашки, чтобы их было легче найти?
• У вас есть восемь шаров одинакового размера. 7 из них весят одинаково, а один весит чуть больше. Как можно оштрафовать более тяжелый мяч, используя весы и всего два взвешивания?
• Что такое команда на языке C для открытия соединения с иностранным хостом через Интернет?
• Разработайте и опишите систему / приложение, которое будет наиболее эффективно создавать отчет о 1 миллионе самых популярных поисковых запросов Google.Вот подробности: 1) Вам дается 12 серверов для работы. Все они двухпроцессорные, с 4 Гб оперативной памяти, 4 х 400 Гб жестких дисков и объединены в сеть (в основном, это не что иное, как высокопроизводительные ПК) 2) Данные журнала уже были очищены для вас. Он состоит из 100 миллиардов строк журнала, разбитых на 12 файлов по 320 ГБ с 40-байтовыми условиями поиска в каждой строке. 3) Вы можете использовать только специально написанные приложения или доступное бесплатное программное обеспечение с открытым исходным кодом.
• Имеется массив A [N] из N чисел.Вы должны составить массив Output [N] так, чтобы Output [i] был равен умножению всех элементов A [N], кроме A [i]. Например, Выход [0] будет умножением A [1] на A [N-1], а Выход [1] будет умножением A [0] и от A [2] до A [N-1]. Решите его без оператора деления и за O (n).
• Есть связанный список чисел длины N. N очень велик, и вы не знаете N. Вам нужно написать функцию, которая будет возвращать k случайных чисел из списка. Числа должны быть полностью случайными.Подсказка: 1. Используйте случайную функцию rand () (возвращает число от 0 до 1) и irand () (возвращает либо 0, либо 1) 2. Это должно быть выполнено за O (n).
• Найти или определить отсутствие числа в отсортированном списке из N чисел, где числа находятся в диапазоне M, M >> N и N, достаточно больших, чтобы охватить несколько дисков. Алгоритм для получения O (log n) бонусных баллов для алгоритма постоянного времени.
• Вам дается игра в крестики-нолики. Вы должны написать функцию, в которой вы передаете всю игру и имя игрока.Функция вернет, выиграл ли игрок игру или нет. Сначала вам нужно решить, какую структуру данных вы будете использовать в игре. Сначала вам нужно сообщить алгоритм, а затем нужно написать код. Примечание: некоторые позиции могут быть пустыми в игре। Таким образом, ваша структура данных также должна учитывать это условие.
• Вам дан массив [a1 To an], и мы должны построить другой массив [b1 To bn], где bi = a1 * a2 *… * an / ai. вам разрешено использовать только постоянное пространство, а временная сложность — O (n).Деления не допускаются.
• Как эффективно разместить дерево двоичного поиска в массиве. Подсказка: Если узел хранится в i-й позиции, а его дочерние элементы находятся в 2i и 2i + 1 (я имею в виду порядок уровней), это не самый эффективный способ.
• Как найти пятый максимальный элемент в дереве двоичного поиска эффективным способом. Примечание. Не используйте лишнее пространство. т.е. сортировка двоичного дерева поиска и сохранение результатов в массиве с выводом пятого элемента.
• Данная структура данных содержит первые n целых чисел и следующие n символов. A = i1 i2 i3… iN c1 c2 c3… cN. Напишите алгоритм на месте для перестановки элементов массива ass A = i1 c1 i2 c2… в cn
• Для двух последовательностей элементов найдите элементы, абсолютное число которых увеличивается или уменьшается больше всего при сравнении одной последовательности с другой, считывая последовательность только один раз.
• Учитывая, что Одна из струн очень-очень длинная, а другая может быть разного размера.Окно приведет к решению O (N + M), но что может быть лучше? Может быть NlogM или лучше?
• Сколько линий можно нарисовать на двухмерной плоскости так, чтобы они были равноудалены от трех неколлинеарных точек?
• Допустим, вам нужно создать карты Google с нуля и направить человека, стоящего на Воротах Индии (Мумбаи), к Воротам Индии (Дели). Как ты делаешь то же самое?
• Учитывая, что у вас есть одна строка длины N и M маленьких строк длины L. Как эффективно найти вхождение каждой маленькой строки в большую?
• Для двоичного дерева необходимо программно доказать, что это двоичное дерево поиска.
• Вам дается небольшой отсортированный список чисел и очень-очень длинный отсортированный список чисел — настолько длинный, что его нужно было поместить на диск разными блоками. Как бы вы нашли эти короткие номера списков в большом списке?
• Предположим, вы дали N компаний, и мы хотим в конечном итоге объединить их в одну большую компанию. Сколько есть способов слиться?
• Как найти файл, содержащий 4 миллиарда 32-битных целых чисел, который встречается хотя бы дважды?
• Напишите программу для отображения десяти наиболее часто встречающихся слов в файле, чтобы ваша программа была эффективной по всем параметрам сложности.
• Создайте стопку. Мы хотим нажимать, выталкивать, а также извлекать минимальный элемент за постоянное время.
• Учитывая набор знаменателей монет, найдите минимальное количество монет, которое даст определенную сумму сдачи.
• Дан массив, i) найти самую длинную непрерывно возрастающую подпоследовательность. ii) найти самую длинную возрастающую подпоследовательность.
• Предположим, у нас есть N компаний, и мы хотим в конечном итоге объединить их в одну большую компанию. Сколько существует способов слиться?
• Напишите функцию для поиска среднего узла списка одиночных ссылок.
• Для двух двоичных деревьев напишите функцию сравнения, чтобы проверить, равны они или нет. Равенство означает, что они имеют одинаковую ценность и одинаковую структуру.
• Реализовать методы ввода / вывода кэша фиксированного размера с алгоритмом замены LRU.
• Вам даны три отсортированных массива (в порядке возрастания), вам необходимо найти триплет (по одному элементу из каждого массива), чтобы расстояние было минимальным.
• Расстояние определяется следующим образом: если a [i], b [j] и c [k] — три элемента, то distance = max (abs (a [i] -b [j]), abs (a [i] — c [k]), abs (b [j] -c [k])) »Пожалуйста, дайте решение с временной сложностью O (n)
• Как C ++ работает с конструкторами и деконструкторами класса и его дочернего класса?
• Напишите функцию, которая переворачивает биты внутри байта (на C ++ или Java).Напишите алгоритм, который берет список из n слов и целое число m и извлекает m-е наиболее часто встречающееся слово в этом списке.
• Что такое 2 в 64?
• Учитывая, что у вас есть одна строка длины N и M маленьких строк длины L. Как эффективно найти вхождение каждой маленькой строки в большую?
• Как найти пятый максимальный элемент в дереве двоичного поиска эффективным способом.
• Предположим, у нас есть N компаний, и мы хотим в конечном итоге объединить их в одну большую компанию.Сколько существует способов слиться?
• Имеется связанный список из миллионов узлов, и вы не знаете его длину. Напишите функцию, которая будет возвращать случайное число из списка.
• Вам необходимо убедиться, что у вашего друга, Боба, есть ваш правильный номер телефона, но вы не можете спросить его напрямую. Вы должны написать вопрос на карточке и передать его Еве, которая отнесет карточку Бобу и вернет вам ответ. Что вы должны написать на карточке, кроме вопроса, чтобы Боб мог закодировать сообщение, чтобы Ева не могла прочитать ваш номер телефона?
• Сколько времени нужно, чтобы отсортировать 1 триллион чисел? Сделайте хорошую оценку.z). Теперь мы не можем получить это вычислением значения (x, y, z) или другими косвенными вычислениями как lg (value (x, y, z)). Как это решить?
• Сколько градусов находится под углом между часовой и минутной стрелками часов, когда время идет без четверти третьего?
• Для массива, элементы которого отсортированы, вернуть индекс первого вхождения определенного целого числа. Сделайте это за сублинейное время. Т.е. не просто просматривайте каждый элемент в поисках этого элемента.
• Даны два связанных списка, вернуть пересечение двух списков: i.е. вернуть список, содержащий только элементы, которые встречаются в обоих входных списках.
• В чем разница между хеш-таблицей и хеш-картой?
• Если человек набирает по телефону последовательность цифр, какие возможные слова / строки могут быть образованы из букв, связанных с этими номерами?
• Как бы вы перевернули изображение на матрице n на n, где каждый пиксель представлен битом?
• Создать механизм быстрого кэширования хранилища, который, учитывая ограничение на объем кэш-памяти, будет гарантировать, что только наименее недавно использованные элементы будут отброшены при достижении кэш-памяти при вставке нового элемента.Он поддерживает 2 функции: String get (T t) и void put (String k, T t).
• Создайте модель затрат, которая позволит Google принимать решения о покупке, чтобы сравнивать затраты на приобретение дополнительной оперативной памяти для своих серверов и на покупку большего дискового пространства.
• Разработайте алгоритм для игры в Frogger, а затем закодируйте решение. Цель игры — направить лягушку, чтобы избежать машин при переходе через оживленную дорогу. Вы можете представить дорожную полосу в виде массива. Обобщите решение для N-полосной дороги.
• Какой тип вы бы использовали, если бы у вас был большой набор данных на диске и небольшой объем оперативной памяти для работы?
• Какой тип вы бы использовали, если бы вам требовались жесткие ограничения по времени и требовалась стабильная производительность.
• Как бы вы сохранили 1 миллион телефонных номеров?
• Создайте 2D-игру про ползание по подземельям. Он должен учитывать различные предметы в лабиринте — стены, предметы и персонажей, управляемых компьютером. (Основное внимание уделялось классовой структуре и тому, как оптимизировать опыт пользователя, путешествуя по подземелью.)
• Каков размер приведенной ниже структуры C в 32-битной системе? На 64-битном?

struct foo {

char a;

симв. * B;

};

Интервью Google: инженер-программист в тесте

• Эффективно объедините 3 стека в один массив.
• Учитывая массив целых чисел, который отсортирован по кругу, как найти заданное целое число.
• Напишите программу для определения глубины двоичного дерева поиска без использования рекурсии.
• Найдите максимальный прямоугольник (по площади) под гистограммой за линейное время.
• Большинство телефонов теперь имеют полноценную клавиатуру. До этого на кнопке с цифрой были привязаны три буквы. Опишите, как вы будете реализовывать варианты написания и варианты слов по мере того, как люди набирают текст.
• Описать рекурсивную сортировку слиянием и время ее выполнения. Напишите итеративную версию на C ++ / Java / Python.
• Как вы можете определить, выиграл ли кто-то в крестики-нолики на доске любого размера?
• Дан массив чисел, замените каждое число произведением всех чисел в массиве, кроме самого числа * без * деления.
• Создать кэш с быстрым поиском, в котором хранятся только N элементов, к которым осуществлялся последний доступ.
• Как разработать поисковую систему? Если каждый документ содержит набор ключевых слов и связан с числовым атрибутом, как строить индексы?
• Для двух файлов со списком слов (по одному в каждой строке) напишите программу, показывающую пересечение.
• Какую структуру данных вы бы использовали для индексации аннаграмм слов? например если в базе данных есть слово «вершина», запрос «горшок» должен указать это.

Интервью Google: аналитик по количественным компенсациям

• Какое годовое стандартное отклонение акции при месячном стандартном отклонении?
• Сколько резюме ежегодно получает Google по разработке программного обеспечения?
• Где бы в мире вы открыли новый офис Google и как бы вы рассчитали компенсацию для всех сотрудников в этом новом офисе?
• Какова вероятность разлома палки на 3 части и образования треугольника?

Google Интервью: технический менеджер

• Вы — капитан пиратского корабля, и ваша команда может проголосовать за распределение золота.Если с вами соглашается менее половины пиратов, вы умираете. Как вы порекомендуете распределить золото таким образом, чтобы получить хорошую долю добычи, но при этом выжить?

Интервью в Google: сотрудник AdWords

• Как бы вы работали с рекламодателем, который не видел преимуществ взаимодействия с AdWords из-за плохой конверсии?
• Как бы вы поступили с рассерженными или разочарованными рекламодателями по телефону?

Источники

http: // news.ycombinator.com/item?id=266663

http://tihomir.org/crazy-questions-at-google-job-interview/

http://www.drizzle.com/~jpaint/google.html

http://www.gamedev.net/community/forums/topic.asp?topic_id=299692

http://careers.cse.sc.edu/googleinterview

http://job-interview.blogspot.com/2005/02/google-interview-product-marketing.html

http://www.theregister.co.uk/2007/01/05/google_interview_tales/

http: // деньги.cnn.com/2007/08/29/technology/brain_teasers.biz2/index.htm

http://blogs.lessthandot.com/index.php/ITProfessionals/EthicsIT/google-interview-questions

http://placementsindia.blogspot.com/2007/09/google-top-interview-puzzles.html

http://linkmingle.com/user/interview_questions/google_interview_questions

http://discuss.joelonsoftware.com/default.asp?interview.11.626758.33

http://mindcipher.com/puzzle/78-clock-works

http: // www.glassdoor.com

http://bluepixel.ca/blog/?p=69

http://www.businessinsider.com/my-nightmare-interviews-with-google-2009-11

Если вам понравилась эта статья, дайте нам знать, нажав Like .

.

30-дневное руководство по подготовке к собеседованию с менеджером по продукту Google

Это 30-дневное пошаговое руководство по подготовке к собеседованию по управлению продуктами (PM) Google. Это одна из самых популярных статей из моей новой книги The Product Manager Interview ; Эта новая книга содержит более 160 практических вопросов для собеседований по управлению продуктом.

Я извлек из этого учебного пособия Google PM.

Желаем удачи и надеемся, что данное учебное пособие поможет в ваших собеседованиях по управлению продуктом!

Льюис

День 1.Знакомство с Google PM Interview

Задачи

Цель

Знайте объем и характер собеседования в Google PM.

День 2. Знакомство с интервью по дизайну продукта

Фоновое чтение

• Прочтите о методе проектирования CIRCLES в Decode and Conquer .
• Просмотрите примеры дизайна продукта из Decode and Conquer , чтобы увидеть, как применяется CIRCLES.

Упражнения

Выполните следующие упражнения на болевые точки в Интервью с менеджером по продукту :

• Детский 1 ^ул День рождения
• Лучший разнорабочий
• Болевые точки поиска работы
• Как найти человека для уплаты налогов

Выполните следующие упражнения с картой пути клиента в Интервью с менеджером по продукту :

• Expedia Journey
• AirBnB Путешествие
• Путешествие по онлайн-курсу
• Путешествие по поиску работы
• Путешествие по ремонту дома
• Путешествие по обслуживанию клиентов

Голы

• Узнайте о вопросах дизайна продукта.
• Понимание концепции дизайна продукта, CIRCLES.
• Понаблюдайте, как другие отвечают на вопросы собеседования с КРУГАМИ.
• Практикуйте две части структуры CIRCLES:
  1. Листинг (мозговой штурм) решений
  2. Отчетность о потребностях клиентов (карта пути клиента).

День 3. Объединение вопросов о дизайне продукта с помощью метода КРУГОВ

Упражнение

Выполните следующие упражнения по дизайну продукта в Интервью с менеджером по продукту:

• Знакомство с Disney с телефоном
• Улучшение Google Hangouts

Голы

• Как знаток вина, определите и определите, чем ваш ответ отличается от образца.По мере того, как вы настраиваетесь на различия, ваши собственные реакции улучшаются.
• На данный момент не беспокойтесь о качестве или скорости ответа. Начать с практики — это половина дела.

День с 4 по 10. Объединение вопросов о дизайне продукта с помощью метода CIRCLES

Упражнение

Заполняйте по одному примеру в день в течение следующих семи дней, выбирая из списка вопросов из Интервью с менеджером по продукту ниже.

1. Улучшение Google Play Store
2. Монетизация Google Maps
3. Дизайн мобильного приложения для Nest
4. Любимый продукт
5. Любимый сайт
6. Люди, которых вы можете знать
7. Автомобиль для слепых
8. Банкомат для пожилых людей

Голы

• Легко объяснить, почему КРУГИ позволяют получать более качественные ответы на интервью.
• Поймите, когда, как и почему нужно адаптировать КРУГИ.

День 11-13. КРУГИ в реальной жизни

Упражнение

Дальнейшее совершенствование своих навыков проектирования изделий, применяя метод КРУГОВ в реальной жизни. На каждый из следующих трех дней:

1. Прогуляйтесь по окрестностям.
2. Во время прогулки используйте метод КРУГОВ для улучшения повседневных вещей. Вот некоторые проблемы дизайна, над которыми стоит задуматься:

• Как можно улучшить тротуары?
• Как уличные фонари могут быть более эффективными?
• Создайте продукт для решения проблемы собачьих какашек.
• Какие новые продукты могут предотвратить прокол шин автомобилей или мотоциклов?
• Какие инновации могут сделать садоводство менее рутинным?
• Какой инновационный продукт может сделать собрания в парке более социальными с незнакомцами?

Цель

Формирование мышления о дизайне продукта 24 часа в сутки, как на собеседовании, так и в повседневной жизни.

День 14 *. Найдите практичного партнера по разработке продуктов

Упражнение

Запишитесь на группу по собеседованию по управлению продуктом на Slack: bit.ly / PMInterviewGroup

Разместите запрос на партнера или партнеров на канале # req-practice-ptr.

По очереди во время тренировки. То есть партнер A (интервьюер) дает дело партнеру B (интервьюируемому). Затем поменяйтесь ролями.

Заранее согласовать, какой случай получит каждый человек; Чтобы смоделировать обстановку интервью, интервьюируемый должен провести кейс, с которым он не знаком. Интервьюеру следует уделить время тому, чтобы ознакомиться с вопросом и образцом ответа.

* Повторяйте упражнение с партнером так часто, как хотите. Лучшие кандидаты отработают не менее 20 кейсов продуктового дизайна.

Цель

Пройдите собеседование по дизайну продукта. Это причина номер один, почему кандидаты не проходят собеседование в Google PM. Если вы посвятили себя вдумчивой практике, вы должны быть экспертом в решении вопросов, связанных с дизайном продукта. Воспользуйтесь приведенными ниже рекомендациями, чтобы оценить свои навыки в области дизайна продукта:

• Новичок подсказывает очевидное или копирует конкурентные особенности.Эксперт предлагает новые и запоминающиеся идеи. Эксперт предлагает идеи, которые заставляют интервьюера сказать: «Хм, я бы хотел подумать об этом; может мне стоит построить компанию на основе этой идеи ».
• Новичок упоминает поверхностные идеи пользователей. Новичка не интересуют пользователи или их мотивация. Новичку не хватает сочувствия к пользователю. Эксперт на протяжении всей жизни изучает психологию и поведение человека. Эксперт постоянно задает вопросы о том, что люди делают и почему они это делают.В результате эксперт легко указывает на важные, актуальные и неожиданные идеи.
• Новичок шаг за шагом следует методу CIRCLES, как домашний повар, впервые пытающийся приготовить изысканное суфле. Новичок боится ошибиться и крепко держится за установленные рамки. Новичок настолько занят, пытаясь вспомнить различные этапы структуры CIRCLES, что ответы новичка кажутся роботизированными и учебными. Эксперт понимает, что фреймворк — это контрольный список, а не рецепт.Эксперт понимает, что КРУГИ предназначены для предотвращения ошибок упущения. CIRCLES помогает обеспечить полноту впечатлений слушателя, удовлетворение и, возможно, даже развлечение.

День 15. Знакомство с интервью по метрикам

Фоновое чтение

• Прочтите о структуре AARM в Decode and Conquer .
• Прочтите примеры показателей в Decode and Conquer , чтобы познакомиться с вопросами о показателях во время собеседования.

Упражнения

Проведите мозговой штурм по следующим показателям в Интервью с менеджером по продукту :

• Метрики для электронной коммерции
• Метрики для двусторонних торговых площадок
• Метрики для SaaS
• Метрики для мобильных приложений
• Метрики для издателей
• Метрики для веб-сайта, созданного пользователями
• Метрики для заявок в службу поддержки

Выполните следующие упражнения по приоритизации показателей в Интервью с менеджером по продукту :

• Самый важный показатель: двусторонний рынок
• Самый важный показатель: мобильное приложение
• Самый важный показатель: электронная торговля

Цель

Получите больше знаний о придумывании и определении хороших показателей.

День 16. Диагностика проблем с метриками

Упражнения

Заполните следующие примеры в этой книге самостоятельно или с партнером:

• Корзина Конверсии
• Рейтинг мобильных приложений
• Reddit Сообщений

Голы

Получите навыки проведения мозгового штурма для получения полного и исчерпывающего списка проблем при устранении неполадок с метрикой.

День 17 и 18. Объединение задач метрики

Упражнения

Выполняйте по одному примеру в день в течение следующих семи дней самостоятельно и вместе с партнером по практике из этой книги.

• Ваш любимый продукт Google
• Выпадение просмотров
• Отклоняющиеся пользователи
• Медленная загрузка на Kindle
• Pinterest Метрики
• Выход на рынок и успех
• Метрики для Uber Pick-up

Голы

Повысьте навыки выявления, определения приоритетов и диагностики проблем с показателями.

День 19. Знакомство с оценочным интервью

Задачи

• Прочтите об оценочных вопросах в Interview Math .
• Прочтите следующие примеры оценки в Interview Math , чтобы ознакомиться.
  • Рынок женских сапог от дождя
  • Рынок чехлов для смартфонов
  • Продажи метро
  • Продажи по подписке Netflix

Голы

1. Узнайте об оценочных вопросах.
2. Узнайте, как настроить вопросы для оценки с помощью деревьев задач.
3. Научитесь делать предположения.
4. Попробуйте следующие вопросы для оценки:
   1. Автомобили в Сиэтле
   2. Сколько пользователей Google Apps
   3. Доход от YouTube Red

День 20.Вопросы для оценки практики

Задачи

Выполняйте по одному примеру в день из этой книги в течение следующих семи дней.

1. Самолеты в воздухе
2. Доход от рекламы Gmail
3. Автобусы Google
4. Gmail стоит
5. Беспилотных автомобилей, приобретенных в 2020 году
6. Хранение карт Google
7. Доход от рекламы Facebook

Голы

Мастер вопросов оценки. Важно не только качество ответа, но также вы должны ответить на большинство оценочных вопросов примерно за 10–15 минут.

День 22. Узнайте больше о стратегических вопросах

Задачи

Прочтите следующие главы в Decode and Conquer .

• Разработка стратегии: компромиссы
• Разработка стратегии: выход на новый рынок
• Разработка стратегии: вопросы на уровне генерального директора

Голы

• Узнайте об общих типах вопросов стратегии.
• Выясните, как подходить к вопросам стратегии, используя фреймворки.
• Посмотрите, как рамки применяются к общим вопросам стратегии управления проектами.

День 23. Вопросы стратегии практики

Задачи

Практикуйте следующие стратегические вопросы из этой книги самостоятельно или со своим партнером-практиком:

1. Служба кабельного телевидения Google
2. Эксклюзивное партнерство с iPhone

Голы

Дайте продуманный, логичный ответ, отвечающий целям компании. Дополнительные примеры продуманных стратегических ответов можно найти в популярном блоге Stratechery.com.

День 24. Подробнее о ценах.

Задачи

Прочтите главу «Цены» в Маркетинговое интервью .

Голы

• Узнайте о ценах, включая разницу между ценами на новые и существующие продукты.
• Выясните, как подходить к вопросам ценообразования с помощью структур
• Узнайте, как применить рамки ценообразования к популярным вопросам.

День 25.Вопросы по ценообразованию

Задачи

Практикуйтесь в следующих вопросах ценообразования самостоятельно или вместе со своим партнером-практиком:

• Цены Новые продукты
  • Google Цены на беспилотные автомобили
  • Google и телепортация
• Цены на существующие продукты
  • AWS Снижение цены
  • Kindle Ценообразование на уровне

Голы

1. Стратегия Google
2. Google vs.Microsoft
3. Google Moonshot Projects
4. Карты Google в Монголии
5. Google Store

День 26. Традиционные и поведенческие вопросы

Задачи

• Прочтите главу «Победа в поведенческом интервью» в Decode and Conquer .
• Составьте и доработайте свои ответы на следующие вопросы:
  • Расскажите о себе.
  • Почему Google?
  • Влияние на вашу команду
• Практикуйтесь и получайте отзывы от своего партнера по практике

Голы

Хотя Google любит задавать вопросы, вам следует потратить некоторое время на подготовку к традиционным и поведенческим вопросам.Интервьюеры Google обычно задают традиционные вопросы-ледоколы, такие как «Расскажите мне о себе» и «Почему Google?» Однако вопросы поведенческого собеседования, такие как «Назовите мне время, когда вы повлияли на команду», — явление новое. Отдел кадров Google с 2013 года просит своих PM-интервьюеров задавать больше вопросов поведенческого интервью.

День 27. Знакомство с вопросами технического интервью

Задачи

Просмотрите технические темы, предложенные в: bit.ly / PMPrepPlan

Голы

Ознакомьтесь с техническими концепциями и вопросами. В Google технические вопросы собеседования зарезервированы для собеседований на месте, обычно для кандидатов, которые преуспели в других частях собеседования, таких как вопросы дизайна продукта, аналитики и стратегии.

День 28. Первая попытка технических вопросов на собеседовании

Задачи

Попробуйте ответить на следующие технические вопросы собеседования:

• 100-этажный дом и два яйца
• Снижение потребления полосы пропускания

a
Голы

Попробуйте задать несколько технических вопросов на собеседовании, чтобы успокоить нервы, и подходите к вопросам с открытым любопытством.Вопрос «100-этажный дом и два яйца» — это пример вопроса об алгоритме. «Снижение потребления полосы пропускания» — это пример вопроса технической архитектуры.

29-30 день *. Вторая попытка технических вопросов на собеседовании

Задачи

Попытайтесь ответить на следующие технические вопросы интервью с The Product Manager Interview :

• Балансировщик нагрузки для Google.com
• Словарь для Scrabble
• Поисковые службы Google
• Байесовский vs.AI

* При необходимости повторите упражнение по техническому собеседованию.

Голы

Укрепляйте уверенность, отвечая на технические вопросы собеседования.

–

Фото предоставлено Google Inc

Если вам понравилась эта статья, дайте нам знать, нажав Like .

.

свежих историй интервью | Мое интервью с Google (Как я обманул свое интервью в Google)

Недавно я имел удовольствие брать интервью у Google. это было
очень интересно, так как я давно хотел поработать в Google,
и они открыли филиал рядом с моим домом за счет приобретения
относительно недавно. Я хотел поделиться процессом собеседования с Google,
не потому, что это было особенно примечательным, а потому, что мне было интересно
об интервью с Google до того, как я это сделал, и я подумал, что другие
может быть.Мне пришлось подписать соглашение о неразглашении, поэтому я буду очень осторожен
чем я делюсь в этом посте.

Я проходил собеседование на должность инженера-программиста в
офис в Боулдере, Колорадо (недалеко от того места, где я живу), но они все еще
проводят свои интервью из калифорнийского офиса. Потому что я не в
Калифорния, сначала мне пришлось пройти два телефонных интервью. В
Вопросы, которые задает Google, довольно интересны по ряду причин. я
Думаю, лучшее слово, которое я мог бы использовать для описания вопросов, — «честно».я
не получил никаких сложных вопросов-головоломок. Никто не спросил меня, что я буду делать
если бы меня уменьшили до пятак и бросили в блендер. Не
единственный вопрос был «а-ха!» типа головоломка. Практически каждый
вопрос был хорошим вопросом для выяснения, может ли кто-нибудь написать
код. Хотя я проходил собеседование на вакансию Java, у меня было только
один вопрос, относящийся к Java. Я действительно мог почувствовать из вопросов, что
Google не беспокоился о том, что я хорошо владею определенным языком;
они действительно хотели знать, был ли я просто хорошим кодером.

Когда рекрутер впервые сказал мне, что вопросы будут
основанный на алгоритмах, я беспокоился, что мне придется воспроизвести быструю сортировку или
что нибудь. На самом деле вопросы были гораздо более разумными (хотя
обзор алгоритмов сортировки БЫЛ хорошей идеей). Большинство из них участвовали
манипулирование данными в массиве с какой-либо целью. Я бы ответил, что
работал, и они спрашивали меня, есть ли какие-нибудь угловые случаи. меня спросили
решить проблему таким образом, чтобы избежать этих проблем.Тогда я был
попросили повысить эффективность использования пространства или эффективность работы
решение. «Сработавшего» решения всегда было недостаточно, интервьюеры
всегда толкал меня дальше, пытаясь выжать из производительности. Мне пришлось
скажите сложность выполнения почти для каждого решения, которое я предложил. я
НЕ рекомендовал бы проходить собеседование с Google без компьютерных наук
степень. Вы должны уметь смотреть на функцию и знать Big-O
за это немедленно. Конкретно нужно смотреть на СВОЮ
функционирует и сразу узнает Big-O.

После хороших результатов в обоих интервью Google действительно полетел
я поехал в Калифорнию на выходные, чтобы взять интервью на целый день
Кампус Google. Они заплатили за мой билет на самолет, номер в отеле, аренду автомобиля,
и немного еды. Я купил второй билет своей невесте, и мы сделали
туристическая чушь вокруг Сан-Франциско. В целом было очень весело, но я
не мог не держать затылок занятым мыслью о
интервью на весь день.

В понедельник я пошел в кампус Google.В главном вестибюле у них есть
проектор с прокручивающимся списком поисковых запросов Google. Я сидел в
вестибюль ждет начала моего интервью, с удовольствием наблюдая за поисками
пролистайте. Обыскивали многие женщины-знаменитости, и кто-то
искал «vista crack», что заставило меня громко рассмеяться,
администратор думала, что я идиот. Я отправил своей невесте текстовое сообщение
велел ей искать «Род потрясающий», но этого не было. Oни
также была аккуратная визуализация, показывающая, где люди ищут
на вращающемся глобусе.

Фотографии гуглеров со знаменитостями украшали стену рядом с
новая доска Google. Для тех, кто не знает, у Google есть гигантская доска.
которая была окончательно стерта не так давно. Перед тем, как стереть, кто-то
сделал фотографии и выложил их в Интернет. Новая доска была
к тому времени, когда я его увидел, почти полностью заполнен, и большая его часть была
посвящен жалобе на стирание платы.

Еще я пообедал в одном из кафе на территории кампуса.Кафе Google
все в виде шведского стола и совершенно бесплатно. Вы просто заходите, хватайте
как хочешь, и уходи. Мое «свидание за обедом» было одним из моих
телефонные интервьюеры, и он отвел меня в кафе здорового питания. Салаты,
буфет был заполнен тофу, ростками фасоли и другими подобными продуктами. я
отчаянно искал мяса и наполнил свою тарелку, когда я наконец
нашел это. Я определенно НЕ из Калифорнии. Люди смотрели на меня
как будто я лично на их глазах корову убил.

Собеседования на месте были очень похожи на телефонные. я имел
встречи один на один с горсткой людей, одну за другой. Каждый
человек задавал мне вопросы типа алгоритма. Я рисовал на доске, но
в основном мог писать ответы в блокноте, что было лучше
для меня, так как мне было гораздо легче следить за своим мозгом на бумаге, чем
на доске. Иногда было сложно сосредоточиться на вопросах
в то время как «О, МОЙ БОГ, Я ИНТЕРВЬЮ С FUCKING GOOGLE» пронеслось в моем
мозг снова и снова.К счастью, почти все были чрезвычайно
дружелюбный, что помогло мне успокоить немалые нервы.

Самая большая разница в вопросах по телефону и на месте
интервью — вот как должны были быть представлены мои ответы. По телефону это было
достаточно, чтобы я объяснил на высоком уровне, как решение
проблема будет работать. На месте мне пришлось это написать. Из моих четырех
интервьюеры, двое действительно хотели, чтобы это была действительная Java.

Я рано закончил с одним из моих интервьюеров, и он спросил меня анекдот
вопрос: если штурмовик стреляет в красную рубашку, он попадает? это было
смешным, насколько универсальным это казалось.Конечно, я бы знал, кем он был
о чем я пишу софт. К счастью, я был знаком с термином «красная рубашка».
Я был фанатом кино, и мне удалось придумать шутливый ответ
это не дало ему понять, что я никогда не видел ни одной серии
Звездный путь в моей жизни.

Худшей частью процесса было мое четвертое и последнее интервью с
день. Парень был из Москвы, и у него был очень сильный акцент. Все
В моей жизни у меня были огромные проблемы с акцентами, даже небольшими.Мой
у менеджера проекта на работе сильный акцент из Италии, и она
в основном для меня звучит как Чубакка. Я не жалуюсь, что Москва
У парня был акцент (во всех технологических компаниях есть люди с акцентом), но он
Конечно, остальная часть собеседования была для меня сложной. Мой
интервью с московским парнем напоминало один из тех спутников
интервью в новостях. Он что-то сказал мне, и было бы это
долгая пауза, прежде чем я ответил. Что еще хуже, он сказал мне, что его
первый вопрос должен был быть «легким», поэтому, когда я едва
понял, что он сказал вообще, я думаю, я выглядел как полный
слабоумный.«Что это было? Вы хотите, чтобы я ЧТО два числа вместе?
де уловка? Mah dah bu? О, размножайтесь! Правильно, дважды два — четыре. я
явно частично отсталый ».

Что еще хуже, парень из Москвы был единственным, с кем я разговаривал
на весь день, кто не был дружен. Он не был полным придурком или
что угодно, но он определенно не был таким теплым, как другие мои интервьюеры.
Прямо перед окончанием интервью он спросил меня, над чем я буду работать для своего
Проект «20% времени».Каждый сотрудник Google посвящает 20% своего времени дополнительному проекту,
именно поэтому существует так много проектов Google Labs (например, Gmail и
Поиск фильмов). У меня действительно был ответ на этот вопрос, так как я
думал об этом в самолете, который летел в Калифорнию. Был
побочный проект, над которым я хотел работать дома, но у меня не было
время. Я подумал, что если получу работу, я просто сделаю ее лабораторией Google
проект и сделайте это там. Я объяснил ему свою идею, и он мне ее рассказал
звучало интересно, затем приступил к записи прямо перед
мне.Все, что я мог думать, было: «Надеюсь, я получу эту работу, поэтому не жалею»
который.»

Я полагаю, что четыре письма с отзывами об интервью выглядели так:

1. «Кандидат знал свое дело, но выглядел ужасно нервным».
2. «Кандидат знал свое дело и выглядел относительно комфортно».
3. «Кандидат продолжал шутить, как будто я был его другом. Очевидно,
   недостаточно нервничал, учитывая, что он давал интервью в FUCKING GOOGLE «.
4. «Похоже, у кандидата мозг шимпанзе.Был удивлен он
   мог говорить, не забывая дышать. Интервьюер уверен
   кандидат ест клей. «

Я прилетел обратно в Колорадо, чувствуя себя довольно хорошо.
Однако, как оказалось, мне сказали по телефону (когда я пытался
вытолкнуть машину из снега во время метели в Денвере), что я не
получить позицию. Мне нужно поработать над своими навыками алгоритма, поэтому я думаю, что
был пристыкован за то, что не сразу подумал о лучшем решении.Google
Рекрутер сказал мне, что это был не последний парень, который меня убил, но я полагаю
если бы я пытался найти лучшее решение раньше (а не
наивный, чтобы я мог его улучшить) и если бы я получил другой
интервьюер для моего последнего интервью, я буду писать этот пост в блоге от
мой стол в Google.

Учитывая, насколько я хотел эту работу, признаю, что я очень расстроен
об этом. Мне разрешено подать повторное заявление через год, но я не могу представить
совершенствовать свои «навыки работы с алгоритмами» без дополнительной информации о том, где я
проблемные места были.Что действительно прискорбно, так это то, что я знаю,
нанял меня, я бы хорошо поработал. Если я увижу, что моя идея появится на
Google Labs в ближайшее время, я сойду с ума.

В целом, это было довольно приятное впечатление. Я разочарован,
но я горжусь собой, по крайней мере, меня серьезно рассматривают
Google. Честно говоря, было весело отвечать на их интервью.
вопросы. Вопросы напомнили мне о моей студенческой работе, и это
было приятно снова вспомнить о таком материале.Я расстроен, что мой
прогресс в мире Google резко остановился, но
путешествие определенно было веселым и интересным. И эй, у меня есть
бесплатная поездка в Сан-Франциско вне его.

Я также получил личную электронную почту. Это было от кого-то из Google. Он
объяснил, что мой пост распространялся по офису Google
и когда это дошло до него, это пробудило его интерес.

По сути, он хотел, чтобы я приехал работать на него в Маунтин-Вью.Он
искал для своей команды разработчиков Java, и он подумал, что я буду хорошим
поместиться. Я вскочил со стула, когда прочитал это, удивился некоторым дополнительным
Я вдохнул жизнь в мой набег на мир Google. Чем больше
Я подумал об электронном письме, тем не менее, большая часть меня хотела сказать
нет. Почему?

Его предложение, по сути, касалось некоторой внутренней разработки для
Google. Я хотел поработать над серверной частью их веб-приложений, чтобы
было немного разочаровывающим.Может быть, это причина, по которой я хотел повернуть его
вниз? Это казалось неправильным, я какое-то время шутил, что буду
с удовольствием убираю туалеты в Google. Написание кода — это написание кода.

Позиция также была по контракту, что мне не мешало.
вверх и вниз. Но я говорил, что как только я ступил в дверь,
Я буду в порядке. Я знал, что буду хорошо работать в Google, если буду работать там, поэтому
не был слишком обеспокоен, что меня не наняли бы на постоянной основе в конце
контрактная работа.Нет, меня беспокоил не аспект контракта.

Еще он сказал мне, что мне придется провести три месяца в Калифорнии.
делаю работу. Тогда мне пришлось бы провести три месяца в Калифорнии в
постоянное место для «культурной интеграции», прежде чем я смогу уйти
вернуться в Колорадо и работать в офисе в Боулдере. Это определенно
надоело мне. Поскольку я хотел бы продолжить жить в Колорадо, я бы
в основном приходится жить в отеле в Калифорнии, а Джулия (моя
невеста) прожила здесь, в Колорадо, 6 месяцев.Я только что обручился
месяц назад, и идея бросить семью, ради которой я только начинаю
Google казался совершенно несправедливым. Если бы я получил работу, я изначально
на собеседовании, мне нужно пробыть в Калифорнии всего одну неделю для обучения,
так что 6 месяцев были большим делом. Когда я сказал Джулии, она сказала мне, что
она могла выдержать 6 месяцев, и если бы я хотел занять эту позицию, я
должен. Она полностью поддерживала все, чем я хотел заниматься. Так что
не было даже шести месяцев вдали от дома, которые заставили меня повернуться
положение вниз.

Я думал об этом несколько дней. Я не мог понять, что насчет предложения, которое мне не понравилось, так разве я не должен его принять?

В конце концов я понял, что мне не нравится в ситуации, и
Я отказался. Не думаю, что смогу лучше объяснить свое объяснение
чем я написал в письме парню из Google, вот что я сказал
ему:

Я думал о твоем письме несколько дней и наконец
приняли решение.Это было решение, которое я принял нелегко.

Позвольте мне начать с благодарности за то, что вы отправили мне электронное письмо и дали мне
еще один потенциальный выстрел в Google. Надеюсь, ты не против, но я бы хотел
чтобы обновить историю моего блога этим дополнительным битом, хотя я не буду
используя ваше имя или любые другие данные.

Как я уже сказал по электронной почте и в блоге, я бы не
скорее работает, чем гугл. Google для меня — это Мекка программного обеспечения
Разработчики.Google делает потрясающую работу, улучшая весь мир.
Нет лучшего способа применить мои навыки разработки программного обеспечения
чем в Google, где я бы хорошо поработал, чтобы улучшить жизнь
бесчисленное количество людей.

Моя личность, мое желание учиться, моя цель улучшить мир —
все это говорит мне, что Google был бы лучшим местом, где я мог бы работать.
Я знаю, что Google подходит мне.

Но подхожу ли я к Google? Процесс собеседования завершился
громкое «нет».Google решил, что я не очень хорошо
компании, и отправил меня обратно в Колорадо. То, что я сделал смешной
сообщение в блоге, описывающее мое путешествие, не меняет того факта, что с
с технической точки зрения, Google считает меня ниже своих стандартов.

Несмотря на заключение интервью, я считаю, что я * AM * прав для
Google. Я считаю, что если я снова соберусь после того, как
навыки работы с алгоритмом и уверенность в собственных силах,
Google увидит, что я подхожу, и наймет меня.

Короче говоря, я хочу работать в Google больше, чем могу описать, но я
хочу там работать, потому что я это заслужил. Я хочу начать свой первый день в
Google, зная, что я принадлежу ему, и зная, что Google знает,
принадлежат там.

Каким бы заманчивым ни было ваше предложение, я чувствую, что оно проникает в Google
через черный ход. Я хочу войти в Google через парадную дверь.

Я намерен улучшать свои способности и изучать новые навыки, как и я
все время как разработчик.Когда буду готов, подам повторную заявку на
Google, и, надеюсь, встретимся с вами в кафетерии в течение моей недели
обучения в Калифорнии. 🙂

Еще раз спасибо за вашу электронную почту.

Я никогда не думал, что упущу шанс поработать в Google, но
вот оно. Я думаю, что могу оглянуться назад и пожалеть об этом, но для
в настоящее время я доволен своим решением.

На этом, я полагаю, и заканчивается история.По крайней мере, на некоторое время.

.