Как я выступил на Google Foobar Challenge, Twice!

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

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

Обратите внимание: я не буду делиться ни одним из вопросов или решений в этом сообщении, поскольку это убивает все удовольствие.

Как получить приглашение?

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

  1. Самый общий способ, т. Е. На странице Поиск Google.
  2. Некоторые люди получили приглашение, просматривая документацию для разработчиков Google. Где-то на экране появляется розовый логотип, и когда вы нажимаете на него, вы видите то же сообщение, которое приводит к вызову.
  3. Очень немногие люди находили ссылку на задачу в консоли JavaScript браузера при проверке определенного Google Doodle.
  4. Если у вас есть друг, получивший приглашение, после прохождения 2 и 4 раундов он / она получит реферальную ссылку. Вы можете попросить ее.

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

После того, как вы приняли приглашение, вы попадаете на портал с терминальным интерфейсом:

Соревнование

Давайте поговорим о том, что нас действительно интересует. Это начинается с истории, в которой злодей (командир Лямбда) пытается захватить планету кроликов и поработил их. Задача - спасти кроликов. Вы проникли на корабль злодея и теперь должны решить несколько задач, чтобы спасти кроликов и сбежать. В задаче 5 уровней с возрастающей сложностью.

  1. На первом уровне вы получите ОДИН довольно простой вопрос. Это может быть завершено в течение часа (максимум) или около того (но опять же, это зависит от обстоятельств). Когда я впервые принял вызов, мне дали 2 дня (48 часов) на выполнение задачи. Однако несколько месяцев спустя, когда я принял вызов во второй раз, у меня было ограничение по времени 7 дней (168 часов). Думаю, они обновили свои условия. После ответа на этот вопрос вы увидите прыгающего милого кролика (см. Гифку выше).
  2. На втором уровне нужно было решить ДВА вопроса. Это было немного выше, чем в 1-м раунде, но довольно легко. Вы можете ожидать базовых вариантов стандартных алгоритмов, таких как Поиск, Сортировка, или реализации базовых операций со структурой данных, таких как обход дерева или манипулирование стеком. Вы также можете ожидать простых задач линейной алгебры. У меня есть 3 дня (72 часа) на задачу, чтобы закончить уровень с первого раза. Однако во второй раз мне нужно было выполнить 7 дней (168 часов) на каждую задачу. После завершения этого раунда вы получите реферальную ссылку, которой сможете поделиться с другом.
  3. В третьем раунде могут быть вопросы уровня собеседования Google (я еще не участвовал ни в одном, прочтите это в Интернете). Есть ТРИ вопроса, на которые нужно ответить 7 дней (168 часов) на каждый вопрос. Здесь вы можете ожидать проблемы динамического программирования или проблемы, основанные на теории чисел или теории вероятностей и т. Д. Вы также можете столкнуться с расширенным деревом -проходные вопросы. Это уровень, на котором все действительно усложняется. Потребовалось время, чтобы понять и реализовать их, но это точно выполнимо. После завершения этого уровня вас спросят, открыты ли вы для приема на работу, чтобы рекрутер Google «МОЖЕТ» связаться с вами, если ваш профиль соответствует какому-либо из их требований.
  4. Четвертый раунд действительно заставляет попотеть. Вы можете рассчитывать на сочетание нескольких сложных алгоритмов или математических концепций. ДВЕ проблемы, которые нужно решить, 15 дней (360 часов) на каждую проблему. Маловероятно, что вам удастся встретить подобные вопросы на собеседовании. После этого раунда вы получите свою вторую реферальную ссылку.
  5. Вероятно, это будет самая сложная проблема, которую вы когда-либо решали (для меня так и было), и задача foobar не преминула меня удивить оба раза. Это будет вся математика. У вас будет 22 дня (528 часов), чтобы решить ОДИН вопрос. По моему опыту, мне потребовался целый день, чтобы разобраться в самой проблеме. Возможно, вам также придется читать исследовательские работы, чтобы понять, как решить определенные проблемы (не все будет легко доступно). Так что будьте готовы заняться серьезной математикой. После выполнения этой задачи вы увидите прыгающих кроликов, указывающих на завершение задачи:

После выполнения задания Google достаточно изобретателен, чтобы предоставить вам зашифрованное сообщение, которое при расшифровке гласит:

{
     'success' : 'great', 
     'colleague' : 'esteemed', 
     'efforts' : 'incredible', 
     'achievement' : 'unlocked', 
     'rabbits' : 'safe', 
     'foo' : 'win!'
}

Несколько советов

  • Вы найдете код почти на все вопросы в Интернете, но он действительно отнимет у вас все удовольствие. В моем случае после отправки решения я брал несколько кодов из Интернета и сравнивал их скорость выполнения с моей.
  • Задача не предполагает, что вы заранее знаете все алгоритмы. Это о том, как вы подходите к сложной проблеме; если вы можете найти подходящие концепции, относящиеся к проблеме, понять их и, конечно же, реализовать. Продолжайте и погуглите, что вам нужно, чтобы найти решение.
  • Не прикасайтесь к клавиатуре, если вы не нацарапали хотя бы базовое решение на бумаге или на доске.
  • Обратите внимание на угловые случаи. Они действительно могут разозлить вас. На их выяснение могут уйти дни, и во многих случаях вам придется переключаться на совершенно другой подход для работы с такими случаями. Потерпи.
  • Нет отдельных индикаторов для Превышен лимит времени (TLE) и неправильных ответов. Это либо «Тестовый набор пройден», либо «Тестовый набор не пройден».
  • Не импортируйте * ни в Python, ни в Java. Выдает ошибку «Внесен в черный список Код». Вы можете использовать только выбранный набор библиотек, чтобы упростить шаблонный код. Вы можете узнать, какие библиотеки вам разрешено использовать, в constraints.txt файле.
  • Нет ограничений по времени для запроса нового вопроса. Не торопитесь, прежде чем начинать новую. Убедитесь, что вы уделяете время своим домашним делам, и планируйте это соответствующим образом.

Заключение

Задача foobar - это действительно увлекательная поездка. Это определенно отличная платформа для проверки ваших навыков программирования. Я узнал на нем много нового. В целом отличный опыт.