puzzles & interview

http://stackoverflow.com/questions/900798/programming-interview-preparation-book

http://www.programming-interviews-exposed.com/

http://www.careercup.com/

http://www.programminginterview.com/

http://www.rampant-books.com/shadow_prog_int.htm

http://technicaljobsearch.com/interviews/technical-interview-tips.htm

http://en.wikipedia.org/wiki/Birthday_paradox

http://betterexplained.com/articles/understanding-the-birthday-paradox/

http://en.wikipedia.org/wiki/Monty_Hall_problem

http://www.mmonline.ru/problems.php

http://www.braingames.ru/

http://en.wikipedia.org/wiki/Simpson%27s_paradox

http://www.ocf.berkeley.edu/~wwu/riddles/intro.shtml Interview pazzles

http://golovolomka.hobby.ru/links.shtml

http://golovolomka.hobby.ru/probability.shtml

http://malaya-zemlya.livejournal.com/494950.html#cutid1

Lucky tickets http://falcao.livejournal.com/123609.html

http://en.wikipedia.org/wiki/Coupon_collector%27s_problem

Two envelopes

http://en.wikipedia.org/wiki/Two_envelopes_problem

http://yigal-s.livejournal.com/387072.html

Passenger taking wrong place.

There are 100 numbered seats an corresponding 100 tickets. One person by mistake occupied wrong seat. All others passengers are trying to follow the rules (take the seat accordingly the ticket#). What is the probability that the last person will sit on the right seat?

Meet the girl

Romeo and Juliet have a date at a given time, and each will arrive at the meeting place with a delay between 0 and 1 hour, with all pairs of delays being equally likely. The first to arrive will wait for 15 minutes and will leave if the other has not yet arrived. What is the probability that they will meet?

The Monty Hall Problem

http://en.wikipedia.org/wiki/Monty_Hall_problem

http://avva.livejournal.com/1980790.html

You are told that a prize is equally likely to be found behind any one of three closed doors in front of you. You point to one of the doors. A friend opens for you one of the remaining two doors, after making sure that the prize is not behind it. At this point, you can stick to your initial choice, or switch to the other unopened door. You win the prize if it lies behind your final choice of a door. Consider the following strategies:

(a) Stick to your initial choice.

(b) Switch to the other unopened door.

(c) You first point to door 1. If door 2 is opened, you do not switch. If door 3 is opened, you switch.

Which is the best strategy?

Lets calculate the probability of winning under each of the three strategies.

Under the strategy of no switching, your initial choice will determine whether you win or not, and the probability of winning is 1/3. This is because the prize is equally likely to be behind each door.

Under the strategy of switching, if the prize is behind the initially chosen door (probability 1/3), you do not win. If it is not (probability 2/3), and given that another door without a prize has been opened for you, you will get to the winning

door once you switch. Thus, the probability of winning is now 2/3, so (b) is a better strategy than (a).

Consider now strategy (c). Under this strategy, there is insufficient information for determining the probability of winning. The answer depends on the way that your friend chooses which door to open. Let us consider two possibilities. Suppose that if the prize is behind door 1, your friend always chooses to open

door 2. (If the prize is behind door 2 or 3, your friend has no choice.)

If the prize is behind door 1, your friend opens door 2, you do not switch, and you win. If the prize is behind door 2, your friend opens door 3, you switch, and you win. If the prize is behind door 3, your friend opens door 2, you do not switch, and you lose.

Thus, the probability of winning is 2/3, so strategy (c) in this case is as good as strategy (b).

Suppose now that if the prize is behind door 1, your friend is equally likely to open either door 2 or 3. If the prize is behind door 1 (probability 1/3), and if your friend opens door 2 (probability 1/2), you do not switch and you win (probability 1/6).

But if your friend opens door 3, you switch and you lose. If the prize is behind door 2, your friend opens door 3, you switch, and you win (probability 1/3). If the prize is behind door 3, your friend opens door 2, you do not switch and you lose.

Thus, the probability of winning is 1/6 + 1/3 = 1/2, so strategy (c) in this case is

inferior to strategy (b).

Suppose you're on a game show, and you're given the choice of three doors: Behind one door is a car; behind the others, goats. You pick a door, say No. 1, and the host, who knows what's behind the doors, opens another door, say No. 3, which has a goat. He then says to you, "Do you want to pick door No. 2?" Is it to your advantage to switch your choice?

http://en.wikipedia.org/wiki/Monty_Hall_problem

My intuition says there is no need to change doors. The probability to win a car is obvious and it is 1/3. But the mathematical solution says the probability to win a car if you change doors is 2/3. Amazing if it is true! So lets find out who is right? How? Will make a simulation, will run it many many times and will get the average. This is the Python program that solves the problem:

from __future__ import division

from random import shuffle, choice

def get_random_doors():

doors = ["goat","goat","car"]

shuffle(doors)

return doors

def get_host_open(doors, guest_pick1):

host_open = 0

remaining_doors = [ k for k in [0,1,2]

if k != guest_pick1]

if doors[guest_pick1] == "car":

host_open = choice(remaining_doors)

else:

[host_open] = [d for d in remaining_doors

if doors[d] != "car"]

return host_open

def simulation(strategy):

N = 100000

cars_won = 0

for _ in range(N):

doors = get_random_doors()

guest_pick1 = choice([0,1,2])

host_open = get_host_open(doors, guest_pick1)

if strategy == "stay":

guest_pick_final = guest_pick1

elif strategy == "change":

[guest_pick_final] = [ k for k in [0,1,2]

if k != guest_pick1 and k != host_open]

else:

raise ("Unknown strategy")

if doors[guest_pick_final] == "car":

cars_won += 1

print strategy, cars_won/N

simulation("stay")

simulation("change")

This is a Python 2.4 and 2.5 code. The problem is written with the goal to be easy to read and verify and is not optimized for performance. Lets run it. The result is:

stay 0.33478

change 0.66407

So change doors, definitely change doors if you can!

Drop the ball

есть k одинаковых стеклянных шарика (яиц если хотите)

- есть N этажей

Нужно найти способ определить этаж с которого шарики НАЧИНАЮТ разбиваться МИНИМАЛЬНЫМ количеством бросков при WORST CASE

- n это количество попыток

*************************************************

Для двух шариков всё понятно: если есть 100 этажей то начинаем бросать первый с 14-го, потом с 14+13=27-го, 39, 50....

Если к примеру первый разобьётся на 50-м останется 10 попыток с 40-го до 49-го. В любом случае получится не более 14 попыток.

То есть сумма арифм. прогрессии с 1-го до n должна дать не менее N. S(n)=(1+n)*n/2 > N при минимальном n. То есть решаем уравнение 1/2*n^2+1/2*n-N=0 и округляем положительный корень ВВЕРХ до целого.

******************************************

Теперь для неизвестного кол-ва шариков k:

По той же логике обозначим S(k,n) и составим СУММУ СУММ арифм. прогрессий:

S(2,n)=(1+n)*n/2

S(3,n)=(1+S(2,n))*n/2

S(4,n)=(1+S(3,n))*n/2.......

Тот кто не поленится расписать получит:

S(k,n)=1/(2^(k-1))*n^k + 1/(2^(k-1))*n^(k-1) + 1/(2^(k-2))*n^(k-2) + 1/(2^(k-3))*n^(k-3) + ... +1/2*n

Сумма расписывается только до того члена где n в оказывается в степени 1. Всё что осталось - это найти корни полинома и выбрать подходящий.

Пример 1:

k=1 (есть только один шарик)

S(1,n)=1/(2^(1-1))*n^1 = n = N то есть нужно столько попыток сколько этажей.

Пример 2:

k=3, N=1100

S(3,n)=1/4*n^3 + 1/4*n^2 + 1/2*n = 1100 решаем и получаем

n= -8.5100 +14.2211i

-8.5100 -14.2211i

16.0199

округляем 16.0199 вверх и получаем n = 17 попыток.

Проблема в том что промежуточные суммы не целые, поэтому на самом деле нужно n = 18 бросков.

Получается увеличение кол-ва шариков очень эффективно для очень высоких зданий.

=============

сколько нолей в конце n! ?

x = n div 5 + n div 25 + n div 125 +...

N!=2^A₂*3^A₃*5^A₅*7^A₇*...,

где A_p - показатель степени, с которой простое число р входит в разложение. Видно, что нулей в конце числа столько же, сколько нулей в конце произведения 2^A₂*5^A₅, но так как, очевидно, что A₂>A₅, то количество нулей равно A₅.

Для того, чтобы найти A₅, необходимо вычислить сумму

+... ,

где - целая часть числа,

т.к. каждое пятое число в произведении N! делится на 5, каждое двадцать пятое число еще раз делится на 5, каждое 5³ число, еще раз делится на 5, и т.д. То есть в (*) мы находим, сколько чисел в произведении N! делится на 5. Фрагмент программы выглядит следующим образом :

k:=5;

s:=0;

repeat

s:=s+N div k;

k:=k*5;

until (k>N);

фильтр Блюма

Дана функция

f(0) = 0

f(1) = 1

f(n) = 2*f(n-1) + 3*f(n-2)

требуется:

а) подсчитать f(n) за O(n) операций

б) подсчитать f(n) за O(log(n)) операций