Разбор задачек с собеседований vol. 2 🍏
В прошлый раз был SQL, сегодня Python + Тервер, посложнее 💪
Задачка с интервью в 🍏. В старые добрые ее также спрашивал 📱
➡️ Единственный источник случайности - это rnd2()
Никакого random() из коробки нет. Есть только возможность "бросить честную монетку", которая вернет 0 или 1. И любое решение мы будем собирать из этих "бросков".
➡️ Ключевое слово - "равновероятно"
Допустим, мы берем rnd2() + rnd2(), то есть дважды бросаем монетку (0 - решка, 1 - орел) и берем сумму - наиболее интуитивный шаг для первой попытки. Возможны 4 исхода, каждый с вероятностью 1/4:
• (0,0) → sum = 0
• (0,1) → sum = 1
• (1,0) → sum = 1
• (1,1) → sum = 2
Итого: вероятность получить 1 будет 1/2, а 0 или 2 - 1/4. То есть полученные значения не равновероятны ❌
➡️ Почему так выходит и что делать?
Мы бросаем монетку. Бросили 1 раз - есть 2 равновероятных исхода, 2 раза - 4 исхода, n раз - 2^n исходов.
Нам нужно, чтобы равновероятными были три исхода (0, 1 или 2), и так как 3 - не степень двойки, то когда мы начинаем распределять 2ⁿ исходов между этими тремя, кто-нибудь (0, 1 или 2) всегда получит больше 🐰
Так, в прошлом примере больше получила единичка, потому что (0,1) и (1,0) обе выдали в сумме единицу.
Отсюда идея - давайте использовать rejection sampling.
В нашем случае мы говорим, что 0, 1 или 2 равновероятно сгенерить не сможем, так как нам нужно генерить хотя бы 2ⁿ равновероятных исходов.
Тогда давайте скажем, что мы будем равновероятно генерировать 0, 1, 2 или 3 (4 = 2^2), и если выпадает тройка - то просто перезапускаем нашу функцию.
➡️ Так, окей, а как равновероятно генерировать 0, 1, 2 или 3?
Нам нужно равновероятно получать 4 исхода. Для этого будет достаточно 2 бросков монетки, тк 2^2 = 4. Если бы мы хотели равновероятно получать 5 исходов, нам бы уже понадобилось 3 броска, тк 2^3 = 8 > 5, но 2^2 = 4 < 5. И мы бы также использовали rejection sampling.
Но мы уже видели, что простое rnd2() + rnd2() не сработало. Значит, нужны веса a × rnd2() + b × rnd2(). Причем такие, что мы будем равновероятно получать 0, 1, 2 или 3 в следующих исходах:
• (0,0) → sum = 0
• (0,1) → sum = b
• (1,0) → sum = a
• (1,1) → sum = a + b
Тут уже можно догадаться, что a и b равны 1 и 2 (неважно, что подставить какой букве). А их сумма будет 3.
С тремя бросками было бы сложнее подбирать веса, поэтому обычно задачку дают именно с двумя бросками 🙃
➡️ А теперь кодим!
def rnd3():
while True:
x = 2 * rnd2() + rnd2() # Равновероятно 0, 1, 2, 3
if x < 3:
return x # Перебрасываем тройки
➡️ А это вообще завершится?..
Формально цикл может крутиться сколь угодно долго, но вероятность этого стремится к нулю, а матожидание числа вызовов конечно: в среднем ~8/3 ≈ 2.67 броска rnd2() на один результат (4/3 раунда по 2 броска). Так что на практике все ок.
🎁 БОНУС - похожая задачка с интервью в 📱
В теории мы можем применить здесь rejection sampling, как и в задачке выше. Только теперь нас интересуют степени шестерки, так как кубик равновероятно выбрасывает 6 значений, а не 2, как было с монеткой.
В коде это будет выглядеть так:
def d12():
while True:
x = 6 * (d6() - 1) + d6() # равновероятно 1..36, -1 внутри из-за сдвига, раньше мы начинали с нуля
if x
В прошлый раз был SQL, сегодня Python + Тервер, посложнее 💪
Задачка с интервью в 🍏. В старые добрые ее также спрашивал 📱
Есть функция rnd2(), которая равновероятно возвращает 0 или 1. Реализовать функцию rnd3(), которая равновероятно возвращает 0, 1 или 2.
➡️ Единственный источник случайности - это rnd2()
Никакого random() из коробки нет. Есть только возможность "бросить честную монетку", которая вернет 0 или 1. И любое решение мы будем собирать из этих "бросков".
➡️ Ключевое слово - "равновероятно"
Допустим, мы берем rnd2() + rnd2(), то есть дважды бросаем монетку (0 - решка, 1 - орел) и берем сумму - наиболее интуитивный шаг для первой попытки. Возможны 4 исхода, каждый с вероятностью 1/4:
• (0,0) → sum = 0
• (0,1) → sum = 1
• (1,0) → sum = 1
• (1,1) → sum = 2
Итого: вероятность получить 1 будет 1/2, а 0 или 2 - 1/4. То есть полученные значения не равновероятны ❌
➡️ Почему так выходит и что делать?
Мы бросаем монетку. Бросили 1 раз - есть 2 равновероятных исхода, 2 раза - 4 исхода, n раз - 2^n исходов.
Нам нужно, чтобы равновероятными были три исхода (0, 1 или 2), и так как 3 - не степень двойки, то когда мы начинаем распределять 2ⁿ исходов между этими тремя, кто-нибудь (0, 1 или 2) всегда получит больше 🐰
Так, в прошлом примере больше получила единичка, потому что (0,1) и (1,0) обе выдали в сумме единицу.
Отсюда идея - давайте использовать rejection sampling.
Rejection sampling - это прием, когда мы генерируем исходы как можем, а "неудобные" просто выбрасываем и пробуем заново. То, что остается после выкидывания, распределено равномерно.
В нашем случае мы говорим, что 0, 1 или 2 равновероятно сгенерить не сможем, так как нам нужно генерить хотя бы 2ⁿ равновероятных исходов.
Тогда давайте скажем, что мы будем равновероятно генерировать 0, 1, 2 или 3 (4 = 2^2), и если выпадает тройка - то просто перезапускаем нашу функцию.
➡️ Так, окей, а как равновероятно генерировать 0, 1, 2 или 3?
Нам нужно равновероятно получать 4 исхода. Для этого будет достаточно 2 бросков монетки, тк 2^2 = 4. Если бы мы хотели равновероятно получать 5 исходов, нам бы уже понадобилось 3 броска, тк 2^3 = 8 > 5, но 2^2 = 4 < 5. И мы бы также использовали rejection sampling.
Но мы уже видели, что простое rnd2() + rnd2() не сработало. Значит, нужны веса a × rnd2() + b × rnd2(). Причем такие, что мы будем равновероятно получать 0, 1, 2 или 3 в следующих исходах:
• (0,0) → sum = 0
• (0,1) → sum = b
• (1,0) → sum = a
• (1,1) → sum = a + b
Тут уже можно догадаться, что a и b равны 1 и 2 (неважно, что подставить какой букве). А их сумма будет 3.
С тремя бросками было бы сложнее подбирать веса, поэтому обычно задачку дают именно с двумя бросками 🙃
➡️ А теперь кодим!
def rnd3():
while True:
x = 2 * rnd2() + rnd2() # Равновероятно 0, 1, 2, 3
if x < 3:
return x # Перебрасываем тройки
➡️ А это вообще завершится?..
Формально цикл может крутиться сколь угодно долго, но вероятность этого стремится к нулю, а матожидание числа вызовов конечно: в среднем ~8/3 ≈ 2.67 броска rnd2() на один результат (4/3 раунда по 2 броска). Так что на практике все ок.
🎁 БОНУС - похожая задачка с интервью в 📱
В наличии только 6-гранный кубик, а нужен 12-гранный. Возможно ли его заменить?
В теории мы можем применить здесь rejection sampling, как и в задачке выше. Только теперь нас интересуют степени шестерки, так как кубик равновероятно выбрасывает 6 значений, а не 2, как было с монеткой.
В коде это будет выглядеть так:
def d12():
while True:
x = 6 * (d6() - 1) + d6() # равновероятно 1..36, -1 внутри из-за сдвига, раньше мы начинали с нуля
if x