# Interview Questions

## 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 Diffprod and Diffsum. Solve the system of equations:

```n1 * n2 = Diffprod ```

`n1 + n2 = Diffsum` via back-substitution.