# Interview Questions

From dankwiki

## Probability

- Three people have not colluded. You ask each the same yes-or-no question. Each has a 2/3 likelihood of telling the truth. The all say "yes". What's the probability of "yes"?
- 8/9 (88.9%). Truly independent trials would suggest 26/27 (96.3%), but though the people have not colluded, it is not possible that 1 or 2 have lied; all must be lying, or all telling the truth. The chance all three are lying is ((1 - p)/3)^3 or 1/9; likewise, the chance all three are telling the truth is (p/3)^3 or 8/9.

- red-and-blue marbles problem
*FIXME*

## Algorithms

- m and n are non-negative. You have all the numbers from m to n, unsorted, save one. Determine the missing one in constant space.
- r = n - m + 1. Sum the numbers in r operations (O(n)), and subtract this from the expected sum (n * (n - 1) / 2 if m is 1, obvious extension to m > 1)

- m and n are non-negative. You have all the numbers from m to n, unsorted, save two. Determine the missing two in constant space.
- (Observing the Hardy-Ramanujan number) n < r = n - m + 1. Sum the cubes of the numbers in r operations (O(n)), and subtract this from the expected sum (n * (n - 1) / 2)^2 if m is 1, obvious extension to m > 1).
- Calculate the expected product of the numbers (n! - (m - 1)!). Calculate the expected sum of the numbers. Perform the actual sum and product. Evaluate the two differences Diff
_{prod}and Diff_{sum}. Solve the system of equations:

`n1 * n2 = Diff`

_{prod}

`n1 + n2 = Diff`

via back-substitution.
_{sum}