Здравствуйте, мои маленькие любители DS/ML! Сегодня поговорим про то, как мы с моим другом готовились к собеседованию в Fast-Forward. Недавно проходил полуфинал ICPC и мой друг был одним из участников. Как одному из участников, ему как и положено пришло предложение от рекрутера Fast-Forward (стандартная практика найма для хфт - хантинг на ICPC) пройти собеседование на позицию Quantative Researcher-а. Вышло так, что у моего друга маленький опыт собеседований, поэтому мы нашли ребят, у которых были собесы в эту компанию и они поделились материалами. Разберем 3 задачи, которые мы решали на днях в качестве подготовки (в прошлом попадались при собеседованиях в эту компанию на позицию кванта). 1) Glove-off: Есть 5 пар перчаток, каждая из которых пронумерована уникально 1-5. 10 перчаток рандомно пошафлили и рандомно попарно распределили. Посчитать вероятность того, что пары разбились так, что разница между каждой <= 1. Hint: Тут важно вспомнить про реккуренты. Посчитать реккурентно, сколько вариантов и поделить на общее количество вариантов. Пишите в комментариях, какие реккуренты вы придумали Hint Hint: P.S достаточно известная реккурента. 2) Lights: Есть 100 лампочек изначально черных (off). Есть цвет - черный (off) и белый (on). Каждый i-ый шаг меняют цвет каждой лампочки, кратной i. После 100 операций, какие лампочки будут белыми? Hint: Подумайте на маленьких примерах, порасписывайте, переведите задачу в битовую строку (может так будет проще),перейдите в модульную арифметику Hint Hint: Это известные числа) 3) Paths: Вы находитесь в точке (0, 0) на поле 66. Сколько всего вариантов добраться до (6, 6)? Двигаться можно только вправо и вверх. Hint: Какой длины путь всегда? Подумайте в этом направлении, заметьте, что всегда вправо и вверх нужно сделать одно и то же кол-во сдвигов, просто в разные моменты времени. 4) Paths Hard: Вы находитесь в точке (0, 0) на поле 66. Сколько всего вариантов добраться до (6, 6), если нельзя пересекать главную диагональ? Двигаться можно только вправо и вверх. Hint: Попробуйте подумать в сторону решения обратной, задачи - сколько есть путей, чтоб добраться, пересекая главную диагональ. Попробуйте отразить точку относительно главной диагонали. Как мне показалось, задачи были достаточно красивыми и не слишком гробовыми для собеса. В целом, до них можно додуматься в рамках собеседования. Решения оставлю в комментариях в случае обсуждения решений, любые предположения принимаюся! Лучше попробовать, чем не попробовать (это правило касается и собесов в крупные компании). Поздравляю всех причастных с 23 февраля, пишите комментарии, ставьте лавки. @zadachi_ds