Foobar with Google - предизвикателство за програмисти

TLDR или накратко за Google Foobar

• Какво е Google Foobar?
  - инструмент на Google през който набират потенциални кандидати за работа при тях;
• Как да участвам?
  - покана може да получите при търсене в Google, от приятел, който е участвал, от скрити линкове в сайтовете на Google;
• Какво трябва да знам за дa премина предизвикателството?
  - да можете да програмирате на Java или Python, да имате познания по основни алгоритми от дискретната математика - графи, комбинаторика и др.
• Ще ме вземат ли на работа в Google ако реша всички задачи?
  - само от вас зависи. Предизвикателсвото е само първата стъпка от серията интервюта, които трябва да преминете за да започнете работа в Google;

Известно е че от 2014 Google използват ключовите думи с които търсите на сайта им за да отсяват потенциални кандидати за работа при тях. Това ми се случи и на мен в началото на тази година и тук искам да разкажа какво става ако получите такава покана.

При едно съсвсем обикновено търсене на информация свързана с един от проектите по който работя екрана на на браузъра се промени и се появи надписът "Вие говорите нашия език. Готови ли сте за предизвикателство?"

При мен търсенето беше за "headless chrome", но през годините предизвикателството се е появявало при търсене на много различни думи като "mutex lock", "raft consensus", "arraylist java", "python list comprehension" и други. Линкове към Google Foobar са намирани и в документацията на Google Developers или скрити в Google Doodles.

Ако се съгласите отивате на нов сайт Foobar, който изглежда като обикновена UNIX/Linux конзола. Там имате ограничен набор от команди които може да видите като напишете help.

Когато сте готови можете да поискате задача за решаване. Задачите са разделени на 5 нива всяко от които има до 3 задачи които трябва да решите в рамките на определено време

Решенията трябва да са написани на Python или Java и трябва да отговарят правилно не само за случайте описани в условието, но и на още 8 скрити теста. Освен за вярност, решението се тества и за скорост, така че ако изпълнението на програмата отнема повече от секунда, най-вероятно няма да мине. Важно е да проверявате за гранични случаи. Не се изисква писане на много код - всички програми бяха под 100 реда код, като имаше случаи, в които решението беше на 2-3 реда.

Задачите са с нарастващата трудност - първите се решават сравнително бързо без нужда от по-специални алгоритми. На 4-то ниво пред мен се отвори цял нов свят от математически трудове, всеки от които решава точно определен клас проблеми или подобрява до някаква степен вече съществуващи алгоритми. Наложи се да прочета стотици страници с теория за всевъзможни вариации на един определен вид задачи за да открия необходимия ми алгоритъм.

Не мога да кажа със сигурност какво трябва да знаете за да решите всички проблеми, тъй като задачите не са еднакви за всички. В моя случай се наложи да мина бърз опреснителен курс по дискретна математика (графи и комбинаторика) и да прочета много за Partition, Алгоритъм на Белман-Форд,Travelling salesman problem, Burnside's lemma и др.

recruitme

След като решите първите 6 задачи Foobar ви дава възможност да изпратите детайлите си за кандидатстване за работа в Google. Аз лично в момента нямам интерес и не изразих желание, затова информацията за процеса е на база описаното от други участници. До един месец след като изпратите данните си с вас ще се свърже recruiter, след което започва серия от интервюта продължаваща 3-4 месеца и включваща допълнителни задачи за програмиране и много алгортимични въпроси. Ако се справите добре евентуално може да получите оферта. Това което Google Foobar ви дава е че ще ви имат предвид, но по-малко от 10% от хората преминали предизвикателството започват работа в Google. Все пак ако наистина искате да опитате да започнете работа в Google, по-добрият вариант според мен е да разгледате Google Careers.

След като реших всички задачи се появявиха ASCII анимирани зайчета и един криптиран текст (Base64 и XOR с username). Като цяло упражнението си заслужаваше, особенно като се има предвид факта че досега не бях писал нищо сериозно на Python. Припомних си комбинаториката и научих доста нови неща, които най-вероятно няма да ми потрябват никога повече ...

Съвети за тези които започват сега

• Не бързайте да започвате следващата задача - ако не изпратите валидно решение в срок всичко приключва. Спокойно можете да изчаквате по няколко дена между две задачи.
• Внимавайте за гранични случаи и нулеви параметри - решенията често се тестват и за тях.
• Ако използвате Python е разрешено да се използват определени библиотеки като itertools, math и fractions. Не е нужно да си пишете функция за генериране на пермутации като мен ...
• След като имате работещо решение и преди да го изпратите отделете малко време да направите кода по-лесен за четене и разбиране - добавете коментари и направете имената на променливите по-четими.
• Прочетете историята в journal.txt - цялото предизвикателство е представено като приключение, в което се изправяте срещу злия командир Ламбда за да освободите зайчетата и да спасите планетата им.