Как-то раз я искал в гугле что-то насчёт Python, как вдруг всплыло приглашение принять участие в испытании по программированию от Google (так называемое foo.bar challenge). Я не фанат состязаний по написанию кода или симуляций собеседований на Leetcode по ряду причин. Однако любопытство взяло верх, и я решил попробовать. Далее я расскажу, как подготовиться и пройти первое испытание.
⚠️ Спойлер/Предупреждение: если вы получите приглашение и решите принять участие, старайтесь решить задание самостоятельно, иначе вы утратите возможность попасть на собеседование. При этом учтите, что каждое испытание сложнее предыдущего. Лично я достиг только третьего уровня (из 5) прежде, чем истекло отведённое время. Пришлось признать, что мне необходимо существенно повысить свои знания продвинутых возможностей Python и CS, чтобы пытаться решить последние задачи. Как бы то ни было, это интересный способ выяснить свои карьерные возможности и навыки с точки зрения Google. Эта изначальная сложность на самом деле относится только к введению и, вероятно, дальше всё будет иначе.
Настройка:
Вам предоставляется безусловно крутая IDE, работающая по принципу обычного терминала. Для вывода релевантных команд наберите help. Вы можете открыть редактор кода справа после запроса испытания и обращения к файлу решения solution.py…
ВНИМАНИЕ: вам не обязательно писать код своего решения в предложенном IDE. Я всё делал в Atom, а уже затем перекопировал туда. Имейте в виду, что ваша среда разработки должна отвечать требованиям, иначе у вас может не найтись подходящего решения. В данном случае требовался Python 2.7, я же использовал Python 3. Поэтому было решено создать новую среду на Python 2.7 и использовать её. Это легко можно сделать с помощью Anaconda, как я и поступил. Вы же можете пойти иным путём.
Предыстория:
Всё испытание представлено в виде sci-fi истории, которая очень забавная. Ознакомиться с ней необходимо для понимания задачи по написанию кода. Вот первая (мы ещё к ней вернёмся вместе с переводом):
Дополнительно вам даётся 2 тестовых случая и соответствующие им решения:
# solution('abcabcabcabc')
# 4# solution('abccbaabccba')
# 2Самый серьёзный подводный камень здесь в том, что есть и другие скрытые тестовые случаи, которые вы должны пройти, чтобы решить задачу. Что они из себя представляют выяснить или выдумать предстоит вам самим. Этот факт вкупе с запутывающим описанием задачи сильно усложняет испытание. Далее. Как только у вас появляется потенциальное решение, вы можете его verify (проверить). Конечное решение не будет принято до тех пор, пока не пройдут все тесты.
Последнее, но при этом решающее ограничение — это время. Вам даётся определённое время и устанавливается счётчик (в данном случае два дня). Если вы решите покинуть испытание и закрыть окно, то таймер продолжит отсчёт. Для восстановления доступа к испытанию и достигнутому прогрессу вам потребуется авторизоваться. Повторно найти страницу испытания вы сможете в гугле или через заранее сохранённую ссылку.
Задача
Давайте вернёмся к конкретной задаче, повторим (выделим жирным соответствующие части) и заново сформулируем её:
Честный торт.
===================== У командира Лямбды выдалась невероятно удачная неделя: она завершила первый тест своего устройства судного дня, захватила шесть ключевых участников Кроличьего восстания и побила свой личный рекорд в тетрисе. Чтобы это отпраздновать, она заказала торт на всех — даже для самых младших миньонов. Однако среди миньонов царит лютая конкуренция, и если вы не сможете отрезать каждому одинаковый кусок торта, то возникнут серьёзные неприятности. Торт круглый и украшен M&Ms с краю по кругу. Но, если вся основная часть торта однородна, то M&Ms нет: они имеют разные цвета, и каждый миньон должен получить одинаковую последовательность M&Ms. Командир Лямбда ненавидит отходы и не потерпит остатков, поэтому вам нужно обязательно разделить весь торт. Чтобы упростить его нарезание, вы преобразовали последовательность цветов M&Ms в строку: каждая возможная буква (между a и z) соответствует уникальному цвету, при этом M&Ms расположены по часовой стрелке (украшение формирует круг вдоль внешнего края торта). Напишите функцию с именем solution(s), которая получает непустую строку длиной менее 200 знаков, описывающую последовательность M&Ms, и возвращает максимальное число равных частей, на которые торт может быть порезан без остатка.
Не знаю как вы, но мой мозг лучше работает, когда всё представлено графически. Поскольку мы уже имеем два тестовых случая, то можем это сделать. Ниже приведён шаблон и то, как он выглядит при виде на торт сверху:
Пока что может быть непонятно. Теперь давайте отделим каждую букву:
И в завершении отделим повторяющийся шаблон:
О пограничных случаях мы поговорим позже. Теперь же, имея более-менее хорошее представление задачи, давайте приступим к написанию кода. Нам нужна функция, которая получает определённые буквы, находит шаблон и выдаёт число повторений указанного шаблона. Вот моё изначальное решение:
def solution(s):
sub = s[0:len(set(s))]
return(s.count(sub))
print(solution('abcabcabcabc'))
>> 4
print(solution('abccbaabccba'))
>> 2
Это работает для двух указанных примеров, т.к. set(s) получает повторяющиеся знаки abc, а затем находит их включения в обеих строках, но...
К несчастью, этот метод не прошёл все тесты, значит нам нужно углубиться и создать дополнительные пограничные случаи, чтобы найти оставшиеся решения. Тот факт, что точный шаблон также не извлекается, abccba во втором решении также должен быть рассмотрен.
Разделяй и властвуй
Чтобы перейти далее, нам нужно сначала выяснить, имеет ли шаблон чётное или нечётное число знаков. Это может показаться нелогичным, но при этом будет простым способом обнаружения пограничных случаев. Рассмотрите этот:
При наличии чётного числа кусков, должно быть чётное число делений без лишних остатков. Но, если взять нечётное число кусков как в этом случае, то могут остаться лишние куски. Вспомните, что задача требует найти максимальное число равных частей, которых в данном случае 2. Определение чётного/нечётного должно быть легко с помощью оператора модуля:
def solution(s):
if (len(s) % 2 != 0):
print('Odd')
else:
print('Even')solution('abcabcN')
>> ODD
solution('abcabc')
>> EVENСледующим в списке будет нахождение цельного шаблона, что можно сделать, выявив индекс, на котором шаблон повторяется. Этот индекс, в свою очередь, может быть найден удвоением строки, нахождением индекса и последующим извлечением шаблона по заданному индексу:
def solution(s):
print('INPUT:' + s)
i = (s+s).find(s,1, -1)
sub = s[:i]
print('Substring:', sub)
solution('abccbaabccba')
>> INPUT:abccbaabccba
>> Substring: abccba
solution(‘xyztxyztxyzt')
>> INPUT:xyztxyztxyzt
>> Substring: xyzt
// Единственное, что здесь странно - это индекс -1 в методе find(). Он будет использован для перехвата ситуации, в которой шаблон нечётный. Рассмотрите 2 следующих случая:
def solution(s):
print('INPUT:' + s)
i = (s+s).find(s,1, -1)
sub = s[:i]
print("i:", i)
print('Substring_1:', sub)
s2 = s
s2 = s2[:-1]
sub2 = s2[0:len(set(s2))]
print('Substring_2:' + sub2)
solution('wewewe')
>> INPUT:wewewe
>> i: 2
>> Substring_1: we
>> Substring_2:we
solution('weweweT')>> INPUT:weweweT
>> i: -1
>> Substring_1: wewewe
>> Substring_2:we
Подробности по методу find() вы можете узнать здесь https://www.programiz.com/python-programming/methods/string/findСледующим, требующим рассмотрения пограничным случаем будет один знак, повторяющийся согласно шаблону, приведённому ниже:
Это делается простым сравнением длины шаблона после предыдущего шага:
if len(set(s)) == 1:
Компоновка сценария:
Итак, на этом этапе у нас должно быть достаточно данных, чтобы создать завершающий сценарий со всеми случаями и условиями, через которые мы прошли. Вот его очень громоздкий вариант:
def solution(s):
print('-------')
print('INPUT:' + s)
i = (s+s).find(s, 1, -1)
print (i)if (len(s) % 2 != 0):
print('ODD')
if(len(set(s)) == 1):
print("CASE: ODD SINGLE CHARACTER")
print('pattern:' + (s[0]))
print('Divisions:' + str(len(s)))
return
else:
s = s[:-1]
if len(set(s)) == 1:
print('pattern:' + (s[0]))
print("CASE: ODD SINGLE CHARACTER EXTRA CHARACTER")
print('Divisions:' + str(len(s)))
return
elif i == -1:
sub = s[0:len(set(s))]
print('pattern:' + sub)
print('Divisions:' + str(s.count(sub)))
print("CASE: MULTI CHARACTER EXTRA CHARACTER")
return
else:
sub = s[:i]
print('pattern:' + sub)
print('Divisions:' + str(s.count(sub)))
print("CASE: ODD MULTI CHARACTER")
return
else:
print('EVEN')
if len(set(s)) == 1:
print('pattern:' + (s[0]))
print('Divisions:' + str(len(s)))
print("CASE: EVEN SINGLE CHARACTER")
return
else:
sub = s[:i]
print('pattern:' + sub)
print('Divisions:' + str(s.count(sub)))
print("CASE: EVEN MULTI CHARACTER")
returnВ нём присутствует 6 тестовых случаев:
solution('a')
solution('aa')
solution('abcabc')
solution('abcabcabc')
solution('aaT')
solution('ababT')И соответствующий вывод:
------
INPUT:a
-1
ODD
CASE: ODD SINGLE CHARACTER
pattern:a
Divisions:1
-------
INPUT:aa
1
EVEN
pattern:a
Divisions:2
CASE: EVEN SINGLE CHARACTER
-------
INPUT:abcabc
3
EVEN
pattern:abc
Divisions:2
CASE: EVEN MULTI CHARACTER
-------
INPUT:abcabcabc
3
ODD
pattern:abc
Divisions:2
CASE: ODD MULTI CHARACTER
-------
INPUT:aaT
-1
ODD
pattern:a
CASE: ODD SINGLE CHARACTER EXTRA CHARACTER
Divisions:2
-------
INPUT:ababT
-1
ODD
pattern:ab
Divisions:2
CASE: MULTI CHARACTER EXTRA CHARACTERПосле рефакторинга в более сжатый и менее многословный сценарий все тесты были пройдены. После этого вы получаете поздравление от кролика и можете переходить к следующему испытанию.
Покупатель несёт ответственность
Зоркие наблюдатели могли заметить ошибочный 4 случай abcabcabc, где мой сценарий утверждает, что максимальное число кусков 2, хотя ожидается 3. Я решил оставить эту ошибку, потому что обнаружил её только в процессе написания статьи (можете исправить её в качестве упражнения). Она также показывает, что вы можете пройти тесты, допустив ошибку, что ведёт к следующей проблеме…
Вы можете справиться с этой задачей несколькими способами. Я точно уже и не помню, какие из ответов со Stack Overflow использовал, но помню, что в какой-то момент вариантов было очень много. Это как раз и является ещё одной проблемой испытаний по программированию. Ваши познания в области (как языка, так и самой задачи) с течением времени увеличиваются, и ответы становятся лучше (если только не истекает время, как в моём случае). Это и многие другие испытания ставят на первое место быстрое создание кода для решения конкретных задач, к чему вы можете быть подготовлены или нет.
Я, может быть, напишу отдельную статью на эту тему, но как только близится дедлайн, а иногда и раньше, ваш уровень стресса поднимается, что негативно отражается на памяти и рассудительности.
Более того, если бы я оказался перед терминалом без доступа к интернету, то наверняка бы провалился. Вероятно, потому что мои повседневные задачи не связаны со строками (на данный момент я работаю с разработкой нейронных сетей, Python GUI и Quant). В любом случае, это и интересное наблюдение, и ориентир для подготовки к таким задачам и их решению (не поддавайтесь стрессу — практикуйтесь):
“Я люблю дедлайны, а в особенности этот свистящий звук, который они издают, пролетая.” ~Дуглас Адамс
Заключение
Я по-прежнему недолюбливаю испытания, даже если они обёрнуты в крутой IDE и дразнят потенциальным собеседованием в Google. Но независимо от моего мнения, они являются нормой, и я полностью понимаю, что большинство людей хотят побольше узнать о них и лучше к ним подготовиться.
Надеюсь, что эта короткая статья в достаточной мере продемонстрировала мой опыт и чего вообще ожидать, если вас вдруг пригласят на испытание Google (продолжайте искать в гугле информацию о Python, чтобы повысить шансы на это). Однако, вероятно, интереснее было узнать, как разобрать это испытание (или многие другие задачи) или вспомнить об этой очевидной, но упущенной из виду ситуации, когда вы становитесь тем лучше в какой-то области, чем больше тратите на неё времени. Не стоит также забывать, что иногда вы можете стать жертвой стресса, который всегда готов помешать вам решить те или иные задачи.
PS: Не стоит расстраиваться, если вы не можете:
а) изначально понять челлендж по программированию;
б) быстро найти оптимальное решение.
Иногда для этих вещей требуется время, а система, как известно, далека от совершенства.
Благодарю за чтение!
Читайте также:
- Вы умеете говорить на Python?
- Магические методы в Python
- Анализ аудиоданных с помощью глубокого обучения и Python (часть 1)
Перевод статьи Keno Leon: Google Python Challenge #1.
