Для интересующихся
Сходила на собеседование в одну компанию. Там мне дали три алгоритмические задачки.
1. В центре круглого пруда сидит утка. По берегу бегает лиса. Утка умеет взлетать только с берега. Лиса бегает в 4 раза быстрее, чем утка плавает. Сможет ли утка улететь. Стратегия лисы наиболее выгодная для нее, но мысли утки она читать не умеет.
2. Есть массив целых чисел величины N диапазона 0-(N-1). Нужно придумать метод, который вернет -1, если все числа разные, или одно из повторяющихся, если таковые есть. Можно портить начальный массив. Нельзя тратить много памяти, сложность алгоритма = N. Короче говоря, отсортировать и пройтись пузырьком - не годится.
3. Есть N бензоколонок и машина с бездонным баком и известной мерой траты бензина. Двигаться можно по кругу от одной бензоколонки к другой в нужном порядке, то есть от 0 до 1, от N-2 к N-1. Нужно узнать с какой бензоколонки можно начать ехать. Сложность алгоритма = N.
1. В центре круглого пруда сидит утка. По берегу бегает лиса. Утка умеет взлетать только с берега. Лиса бегает в 4 раза быстрее, чем утка плавает. Сможет ли утка улететь. Стратегия лисы наиболее выгодная для нее, но мысли утки она читать не умеет.
2. Есть массив целых чисел величины N диапазона 0-(N-1). Нужно придумать метод, который вернет -1, если все числа разные, или одно из повторяющихся, если таковые есть. Можно портить начальный массив. Нельзя тратить много памяти, сложность алгоритма = N. Короче говоря, отсортировать и пройтись пузырьком - не годится.
3. Есть N бензоколонок и машина с бездонным баком и известной мерой траты бензина. Двигаться можно по кругу от одной бензоколонки к другой в нужном порядке, то есть от 0 до 1, от N-2 к N-1. Нужно узнать с какой бензоколонки можно начать ехать. Сложность алгоритма = N.