Комментарии 40
Ну и наконец, можно посмотреть на граф переходов и сообразить решение за логарифмическое время.
В силу симметрии, есть шесть видов кнопок (плюс бесполезная 5): {{0}, {2}, {8}, {1,3}, {4,6}, {7,9}}. Обозначая число ходов начиная с кнопки этого класса за A-F(n), имеем:
A(n+1) = 2*E(n)
B(n+1) = 2*F(n)
C(n+1) = 2*D(n)
D(n+1) = C(n) + E(n)
E(n+1) = A(n) + E(n) + F(n)
F(n+1) = B(n) + E(n)
Это линейное преобразование, размерность пространства 6. Иными словами, результат N преобразований - некоторая матрица в N-ной степени умноженная на единичный вектор. Быстрое возведение в степень справится за O(log(N)), а также можно прикинуть порядок результата за постоянное время по доминирующему собственному значению (~2.43828).
Ещё один шаг к идеалу - заметить что числа растут, быстро выходят за машинное слово, поэтому их сложение уже нельзя считать занимающим константное время, так что О(n) будет чуть другое. Это и к авторскому алгоритму относится конечно.
Для этого такие задачи дают "по модулю 10^9 + 7".
Понятие "время" при анализе алгоритмов является синонимом сложности, то бишь числа операций. Операция сложения является атомарной по определению. Так что "выход за пределы машинного слова" - бред, советую изучить теорию оценки алгоритмов и разобраться, почему там нету *c и +A.
Не покажете по каким определениям сложение больших чисел это атомарная операция?
Умножение тоже атомарное? И зачем тогда существует, скажем, алгоритм Алгоритм Тоома — Кука со сложностью О(n^1.46) если можно за одну операцию?
Время считается в элементарных операциях. Так-то можно объявить сортировку массива "операцией" и иметь сортировку за O(1).
Сложение является O(1) операцией только пока числа ограничены в размере. В противном случае надо это учитывать. В большинстве алгоритмов, даже если входные числа сколь угодно большие, сложность не поменяется, потому что N в O(f(N)) - обычно это размер входных данных. И на практике этот момент часто игнорируют. Но иногда это важно. Как в этой задаче.
Даже чуть проще: если развернуть граф на плоскости, сразу видно, что классов кнопок всего 4 (по тому, за сколько ходов кнопка достижима от 0). Для такой задачки, конечно, хочется вывести аналитическое решение, но, возможно, ничего лучше возведения матриц в степень и не получится...
Okay, so I said we were done, but it turns out this problem has one more solution. In all my time interviewing with this problem I’ve never seen anyone provide it. I didn’t even know it existed until one of my colleagues came back to his desk with a shocked look on his face and announced he had just interviewed the best candidate he’d ever seen.
I’ll post a detailed follow-up soon, but in the meantime I’ll leave you all to wonder how this problem can be solved in logarithmic time…
Это вы тот самый гениальный кандидат? 😁
А зачем там что-то программировать если есть возможность вывести формулу?
Всего 9 цифр и для каждой из них есть максимум 8 ходов чтобы вернуться к началу.
Значит существует такое число ходов для каждой цифры при котором любые последовательности ходов будут приводить обратно к ней и ситуация будет повторятся.
Это похоже на деление с остатком.
Сколько уникальных чисел можно набрать за N ходов из конкретной начальной позиции?
Вот такой вариант мне кажется тоже интересным:
Сколько уникальных цифр можно нажать за N ходов из конкретной начальной позиции?
Пардон если туплю, но сколько не перечитывал условие задачи так и не понял - каким образом можно начать с какой-то кнопки и получить неуникальное число?
Каждый ход конём всегда даёт разную цифру, а значит все набранные числа всегда будут уникальными. Как вариант, возможно, это слово используется для запутывания собеседуемого?
Я бы без рекурсии сделал список задач и накапливал сумму. Но имхо это брутфорс, лучше найти петли и в зависимости от глубины получать коэффициенты.
2 хода, одинаковый исход
и как вам такое в голову пришло? )
во-первых в самой статье нет абсолютно никакого указания на то, что вектор хода буквой "Г" через разные поля - это разные ходы.
во-вторых, вы сами поверх картинки автора когда рисовали - не заметили, что он стрелками отметил ход и он один.
в-третьих, в шахматах фигуры не ходят буквой "Г" по определенному вектору, они сразу из одной клетки попадают на конечную клетку.
Например, путь, чтобы набрать максимальное число уникальных цифр -- 9, надо сделать 10 ходов.
То есть я так понял речь в задаче идёт скорее про общее число уникальных цифр за весь путь и минимальное число ходов для их достижения.
Уважаемая, как могло прийти в голову автору статьи, что телефонный номеронабиратель не круглой формы? Нет же ни какого описания какой именно номеронабиратель используется для решения задачи.
Такое впечатление, что автор нам навязывает решение только для одной формы номеронабирателя. Зачем так сужать исходную информацию?
Уважаемая
Кто?
как могло прийти в голову автору статьи, что телефонный номеронабиратель не круглой формы? Нет же ни какого описания какой именно номеронабиратель используется для решения задачи.
Правда-правда? А картинка вас на мысли не наводит? А в названии статьи слово "кнопки"? Или этот текст: "Кнопки на номеронабирателе можно нажимать только ходом коня. Каждый раз, когда конь попадает на кнопку, мы нажимаем её и делаем ещё один ход"
Такое впечатление, что автор нам навязывает решение только для одной формы номеронабирателя. Зачем так сужать исходную информацию?
Потому что это статья автора, а не ваша, вы можете написать статью про дисковый номеронабиратель.
На то что это абсолютно верно не претендую, просто как вариант)
И самое главное правильного варианта среди этих функций них нет.
Часть выдает 0 на "count_sequences(_, 0)", другая выдает 0 на "count_sequences(5, 1)" (вместо единицы можно любое число больше 0)
Хотя в условии:
Начальная позиция тоже считается нажатой.
Число вариантов ~ (20/9)^n. Ну примерно там. плюс-минус. Это если я не совсем забыл математику.На величинах где n имеет маленькое значение, оно, конечно будет давать не самый точный ответ. Но чем больше n тем более точным значение будет. Ну если вам нужно именно возможное количество значений. Если точное количество значений, то только перебирать наверное. Но я не такой уж крутой программист, чтобы приводить решение за срок, который я готов на это потратить.
Хотя не. Есть алгоритм для точного значения. На обеде опишу в комментарий ниже. т.к. в этот уже не успею.
Я выше посчитал (с помощью Wolfram Alpha), основание чуть больше: 2.43828 ~ 22/9.
Почему 22/9? Я посчитал с помощью собственных знаний и понимаю что и откуда взялось. Не понимаю откуда у вас взялось 22/9.
Максимальный корень уравнения λ^6 - λ^5 - 7 λ^4 + 4 λ^3 + 14 λ^2 - 4 λ - 8 = 0
Аналитически это (1 + √5 + √(38+2√5))/4.
Не знаю зачем вы так усложняете. У нас есть девять чисел. у семерых из них есть два варианта перехода, у двух - три. Далее считаем опираясь на это. В этом случае абсолютно неважно какие у нас числа, матрицы и т.п. Считаем через вероятности и всё.
Я усложняю чтобы получить точный ответ. (Не то чтобы сильно усложняю: задаче "посчитать остаток от деления миллиардного числа Фибоначчи на 10*9+7" сто лет в обед, она решается так же.)
Интуитивно, при случайном блуждании вы будете чаще оказываться в узлах степени 3, поэтому ожидание числа вариантов перехода больше среднего арифметического степеней узлов. (Близкий родственник этого наблюдения - "парадокс дружбы" a.k.a. "у ваших друзей в среднем больше друзей чем у вас".) Как можно видеть, в данном случае поправка около 10%, не так уж мало.
Для начала нужна та самая мапа "М" ( 1: (6, 8),2: (7, 9),3: (4, 8),4: (3, 9, 0),5: tuple(),6: (1, 7, 0),7: (2, 6),8: (1, 3),9: (2, 4),0: (4, 6))
Далее нам нужна строка куда будем записывать вероятное количество цифер на этом шаге, пусть это будет "Х" (1:0, 2:0, 3:0, 4:0, 5:0, 6:0, 7:0, 8:0, 9:0) здесь первая цифра - обозначает собственно цифру, на которой мы вероятно стоим, вторая - вероятное количество сколько раз оно встречается на этом шагу.
А И ещё нужна переходная строка, куда мы будем писать значения между итерациями, чтобы всё не перемешалось. она будет схожа с "Х". Пусть это будет "У". в самом начале "У" = "Х"
Ход 1. На первом ходу просто смотрим на каком мы числе и сколько переходов и куда у нас есть по "М". К соответствующим цифрам в "У" прибавляем по +1. После чего приравниваем "Х"="У"
Ход 2 - N. На всех последующих: Берём каждое число по порядку из "Х", смотрим куда переходит и к тем цифрам прибавляем +1 в "У" умноженное на количество встреч этого числа в "Х" . В конце итерации приравниваем "Х"="У".
Повторяем Ход 2 - N. N-1 раз.
В конце берём "Х" и перемножаем на количество переходов из этого числа из "М", суммируем значения для каждого числа.
Вроде так можно точное значение получить. Надо проверить пока не проверял. вроде тоже точное значение получится уже если первая цифра известна.
def count_sequences(start_position, num_hops):
if num_hops == 0:
return 1
num_sequences = 0
for position in neighbors(start_position):
num_sequences += count_sequences(position, num_hops - 1)
return num_sequences
мне кажется, если запустить count_sequences(start_position = 5, num_hops >= 1), то будет интересный результат.
Вообще интересная задача. Что еще я заметил, что если начинаешь с 0,1,3,7,9 то до клавиш 4 и 6, которые имеют по три соседа, добираешься за один ход, а с клавиш 2,4,6,8 за два хода.
То есть, как только мы добрались до 4 или 6, дальше каждые 2 хода умножается на 6 кол-во уникальных комбинаций (3 возможных хода с кнопок 4 или 6, и 2 хода с их соседей, 3*2=6).
Мне кажется, тут формулу можно вывести.
Хотелось бы поинтересоваться:
Какие именно знания проверяет эта задача?
Действительно ли нужно отсеивать кандидатов не способных решить эту задачу за 45 минут?
Может 3 задачи попроще будет более репрезентативно чем одна, но сложная?
Эм. Вполне обычная задача на логику и алгоритмическое программирование. Гораздо, гораздо лучше дрочева “переверните дерево”, если решается не в формате олимпиады, а с собеседующим.
И вы неправильно понимаете необходимость отсева кандидатов. Когда вы маленькая компания, и у вас ни известности, ни большой зарплаты, то вы берете первого подходящего на рынке. Когда вы большая компания, и у вас зарплата и/или имя, у ваших дверей стоит толпа людей, которые хотят у вас поработать. Все сразу вам не нужны, поэтому нужен способ отсеять самых лучших. Вот эта задача — хороший способ. Алгодрочево “вспомните решение” — плохой.
Не хотелось бы влезать в глубокую дискуссию, но мне непонятно как конкретная задача связана с фразой "... нужен способ отсеять самых лучших"?
С точки зрения интервьюируемого всё просто, ты либо решил, либо нет. Вероятность подготовится к такого родам задаче всегда 50/50, т. е. ты либо знаешь как её решить либо нет. Т. к. круг вопросов ничем не ограничивается, то всегда есть вероятность, что тебе просто неповезёт с задачей (или повезёт). В любом случае, пойдешь на другое интевью и тебе обазательно, когда нибудь, попадётся адэкватный интервьюирующий.
А вот с точки зрения интервьюирующего (в частности компании, куда сотрудник будет принят), подобная задача либо бессмысленна, т. к. она ничего не проверяет (например любопытный и среднего уровня студен просто случайно читал про что-то такое и знает как её решать), либо деструктивна (например мы отсеим очень крутого и опытного спеца, только из-за того, что он с такого рода задачами не пересекался).
Моя мысль в том, что оценивать кандидата методом ва-банк (с помощью одной чисто теоретической/синтетической задачей) является неэффективным подходом. А вот 2-3 задачи попроще, взятых с реальных проектов, будет гораздо репрезентативней, с точки зрения оценки навыков кандидата.
есть вероятность, что тебе просто неповезёт с задачей (или повезёт
Поэтому в крупных компаниях вроде гугла дают несколько раундов разных задачек. И завалить 1 из них - не проблема вообще. При этом знание базы и умение мыслить алгоритмически повышают вероятность решить задачу гораздо больше, чем вызубривание решений. Для этого же, кстати, задачи часто меняют, особенно, если они утекают. Поэтому, кстати, задач нужно очень много.
например мы отсеим очень крутого и опытного спеца, только из-за того, что он с такого рода задачами не пересекался
Печально, но не проблема. За забором еще 10 крутых и опытных спецов, которые с такого рода задачами сталкивались или хотя бы готовились к интервью. Если спец такой крутой, то прочитать одну книжку, присланную ХРом и подумать потом над задачами он сможет запросто.
оценивать кандидата методом ва-банк (с помощью одной чисто теоретической/синтетической задачей) является неэффективным подходом.
См мой первый ответ выше
А вот 2-3 задачи попроще, взятых с реальных проектов, будет гораздо репрезентативней, с точки зрения оценки навыков кандидата.
Проблема тут в том, что вытащить и абстрагировать задачу с реального проекта для интервью весьма сложно. Вы же не можете 30 минут только давать кандидату контекст и объяснять, что сделать надо. Если же что-то можно выделить, то там либо получаются тривиальные вещи вроде fizzbuzz, что не подходит, ибо кандидатов надо отсеивать, или получится что-то посложнее, что ни по какому критерию никак не отличается от литкод medium-hard задачек. Плюс, тут специфика фаангов - там везде своя внутренняя кухня, свои фреймворки и решения (чаще всего потому, что они появились раньше популярных фреймворков), поэтому любая задача с настоящего проекта будет точно такой же абстрактной число дробилкой.
А вот с точки зрения интервьюирующего (в частности компании, куда сотрудник будет принят), подобная задача либо бессмысленна, т. к. она ничего не проверяет (например любопытный и среднего уровня студен просто случайно читал про что-то такое и знает как её решать), либо деструктивна (например мы отсеим очень крутого и опытного спеца, только из-за того, что он с такого рода задачами не пересекался).
Любопытные студенты отсеятся еще раньше. А опытных крутых спецов там 5 на одну вакансию, какая разница, как их отсеивать? Все что не "выбрасываем 4 резюме в урну со словами неудачники нам не нужны", уже лучше.
Вы все еще смотрите с позиции того, кого нанимают. А надо смотреть с позиции компании, причем большой компании. Она уже находится в условиях, когда спецов готовых у нее работать много, и части придется отказать.
Типа, это как ситуация в тиндере. Девушка пришла, лайкнула 50 парней, получила 30 метчей. Она не сходит на 30 свиданий, это займет больше месяца. Ей надо получить 5 самых прикольных и с ними уже куда-то идти. Можно ранжировать по привлекательности или еще по какому-нибудь критерию, но что делать, если наверху рейтинга будут 15 одинаково привлекательных парней? Они разные, конечно, но с точки зрения девушки незначительно отличаются в привлекательности. 10 штук придется отсеять. И тут уже имеют значение любые факторы, потому что альтернатива — выбирать, раскладывая таро. Давайте отберем всех, у кого есть татуировки. Давайте теперь всех, у кого есть машина. Давайте теперь всех, кто согласен в три часа ночи заказать пироженку. Все эти критерии не имеют большого значения в реальных отношениях, как и знание назубок алгоритмов не имеют особого значения в работе программиста, но с точки зрения этой девушки каждый фактор чуть-чуть повышает вероятность приятностей в отношениях, и если уж все равно фильтровать, то давайте по ним.
Вот и с компаниями так же. Все прекрасно понимают, что спрашивают на собесах ерунду. Но т.к. это не совсем полная ерунда, и программист знающий назубок алгоритмы будет в среднем чуть эфеективнее незнающего (или просто будет обладать чуть большей лояльностью компании), то ок. Скажите спасибо, что не таро.
то вы берете первого подходящего на рынке
я бы тут не совсем согласился - если брать в общем случае, то скорее корреляция обратная - т.е крупные компании берут веерно почти всех (это очень очень условно). Чтобы за первые 3-6 месяцев понять более детально насколько человек способен, может и т.д. (потому что отхватить малознающего, но быстрообучаемого и толкового - это почти как найти алмаз и уже делать его огранку:) ). У крупняков на это есть и бюджет и возможности.
А вот небольшие компании (если они нормальные и ценят свою команду) более щепетильно подходят к отбору - и поэтому иногда отсеивают не совсем подходящих, пропуская тех, кто может выстрелить в перспективе.
Плюс сильно зависит от позиции - одно дело джунов и трейни набирать, другое - тимлида или руководителя.
Сама задачка помимо логики и алгоритмики проверяет в принципе стиль, желание и умение мыслить. Я не HR, но очень много ребят собеседовал на разные позиции, и была задачка очень простая, у которой решение могло лежать и в плоскости алогритмики, и математики, и дизайна, и PR и т.д. И проверялось ей не конкретные знания, а то как кандидат, претендующий на определенную позицию подходит к её решению. Например, если кандидат на руководителя (среднего звена) через 10 сек. говорит - "Я не знаю", то к нему в ходе собеседования будет более пристальное внимание и более глубокое, потому что очень не хочется, чтобы твой подчиненный тимлид, например, когда встретит что-то простое, но ему не известное мыслил "я не знаю".
В любом случае задачки - это часть собеседования и они всегда лишь помогают раскрыть то, что по кандидату может быть не видно в силу его характера или чего-то подобного.
Мне, например, эту задачу очень тяжело было решать программированием. Хотя я знаю и про О(n), и про рекурсию, и про мемоизацию. Я в первую очередь решал её логическо-математически, разбивая все вожможные случаи и сужая их. Т.к количество различных вариаций начала и конечной формулы - мало, и половина случаев сводятся друг к другу:)
Решил сам порешать перед тем как читать ответ, и не нашел в предлагаемых в статье решениях оптимизации с тем, что у нас всего 4 класса кнопок выделяется. На ассимптотику это, конечно, не влияет, но почему бы и нет.
Решение
def solve_naive(start, steps=1):
if start == 5:
return 0
if steps == 1:
if start == 6 or start == 4:
return 3
return 2
moves = [(4,6), (6,8), (7,9), (4,8), (3,9,0), (), (1,7,0), (2,6), (1,3), (4,2)]
return sum(solve_naive(x, steps - 1) for x in moves[start])
def solve_optimized(start, steps=1):
if start == 5:
return 0
classes = {
8: 0, 2: 0,
1: 1, 3: 1, 7: 1, 9: 1,
4: 2, 6: 2,
0: 3,
}
hops = [2, 2, 3, 2]
for _ in range(steps - 1):
hops = [
hops[1] * 2,
hops[0] + hops[2],
hops[1] * 2 + hops[3],
hops[2] * 2
]
return hops[classes[start]]
for start in range(1, 10):
for steps in range(1, 10):
reference = tuple(solve_naive(start, steps) for x in range(1, 10))
attempt = tuple(solve_optimized(start, steps) for x in range(1, 10))
assert(reference == attempt)
Довольно топорный перевод - читать тяжело!😟
Не судите строго за топорное выполнение. Я только учусь.
Решение.
a = b = c = d = 1 # a - отвечает за цифры 1, 3, 7, 9, b - за 2, 8, c - за 4, 6, d - за 0
k = input()
for i in range(int(input())):
a, b, c, d = b + c, 2 * a, 2 * a + d, 2 * c
print(a if k in '1379' else b if k in '28' else c if k in '46' else d if k == '0' else 0)
Рисуем граф:
Забиваем его в исходные данные, а дальше стандартный обход дерева в ширину дает нам количество пройденных узлов для заданной глубины сканирования.
Можно получить явную формулу для решения.
Как уже отмечали в комментариях, есть четыре класса A={0}, B={4,6}, C={1,3,7,9}, D={2,8}, связанных рекуррентным соотношением
Если взять квадрат преобразования, то соответствующий граф разбивается на две части:
Это, кстати, следует из того, что граф переходов получается двудольный, то есть, рёбра есть только между двумя множествами вершин {0,1,3,7,9} и {2,4,6,8}
Получившиеся матрицы 2x2 легко диагонализуются (с собственными числами 
), и можно получить формулу, аналогичную Фибоначчи, для каждого класса. Например, количество путей из цифры 1:
Так как первое слагаемое меньше единицы, то можно формулу представить в таком виде:
Естесственно, как и для Фибоначчи, эти формулы быстро теряют точность даже для небольших n, так что быстрое возведение соответствующих матриц в степень n по-прежнему самый быстрый способ.
Анализ задачи с собеседования в Google: конь и телефонные кнопки