вопросы для интервью
(может быть интересно программистам)
Некий Grant Slatton написал в Твиттере список из задач, которые давал на интервью программистам в Амазоне (группа AWS). Привожу ссылку и пишу о них не потому, что это что-то из ряда вон выходящее, а просто любопытно, можно обсудить и сравнить впечатления.
Итак, три задачи:
1) проверить, что строка из скобок типа ((())()()())) правильно сбалансирована
2) дана матрица из нулей и единиц, где 0 - вода, а 1 - суша, найти кол-во "островов". Суша соединяется по 4 направлениям, не по диагонали
3) построить структуру данных, дающую insert(value), delete(value), sample_uniform_random() -> value, все операции быстрее, чем O(N).
Я не понял, это задачи на предварительное интервью (phone screen) или "настоящее". По моему опыту из Гугла, этот набор задач немного сложнее, чем типичное предварительное, и немного легче, чем настоящее. Но в принципе годные задачи, как мне кажется.
Про первую задачу: Грант написал, что самое быстрое решение было за 10 секунд, некий соревновательный программист из Казахстана. Я подумал: объяснил за 10 секунд? - ну так и я могу. Но оказалось, что чувал буквально за 10 секунд написал код, "a Python two-liner". Это, конечно, жесть. Мне стало любопытно, и я заморочился написанием двухстрочного решения на Питоне, и через пару минут (никак не 10 секунд, да), вымучил следующее:
def balanced(a):
cnt=0; b=[cnt:=cnt+(1 if i=="(" else -1) for i in a]
return not any([c<0 for c in b])
Про вторую задачу: можно делать DFS, но я бы обошелся простым проходом по матрице с слиянием островов. Если интересует только число островов, слияние можно сделать за O(1) через уровень индирекции, без сложных структур данных.
Третью задачу можно по-разному решать, напишу свой вариант в комментах.
Некий Grant Slatton написал в Твиттере список из задач, которые давал на интервью программистам в Амазоне (группа AWS). Привожу ссылку и пишу о них не потому, что это что-то из ряда вон выходящее, а просто любопытно, можно обсудить и сравнить впечатления.
Итак, три задачи:
1) проверить, что строка из скобок типа ((())()()())) правильно сбалансирована
2) дана матрица из нулей и единиц, где 0 - вода, а 1 - суша, найти кол-во "островов". Суша соединяется по 4 направлениям, не по диагонали
3) построить структуру данных, дающую insert(value), delete(value), sample_uniform_random() -> value, все операции быстрее, чем O(N).
Я не понял, это задачи на предварительное интервью (phone screen) или "настоящее". По моему опыту из Гугла, этот набор задач немного сложнее, чем типичное предварительное, и немного легче, чем настоящее. Но в принципе годные задачи, как мне кажется.
Про первую задачу: Грант написал, что самое быстрое решение было за 10 секунд, некий соревновательный программист из Казахстана. Я подумал: объяснил за 10 секунд? - ну так и я могу. Но оказалось, что чувал буквально за 10 секунд написал код, "a Python two-liner". Это, конечно, жесть. Мне стало любопытно, и я заморочился написанием двухстрочного решения на Питоне, и через пару минут (никак не 10 секунд, да), вымучил следующее:
def balanced(a):
cnt=0; b=[cnt:=cnt+(1 if i=="(" else -1) for i in a]
return not any([c<0 for c in b])
Про вторую задачу: можно делать DFS, но я бы обошелся простым проходом по матрице с слиянием островов. Если интересует только число островов, слияние можно сделать за O(1) через уровень индирекции, без сложных структур данных.
Третью задачу можно по-разному решать, напишу свой вариант в комментах.