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 Diff_prod and Diff_sum. Solve the system of equations:

n1 * n2 = Diffprod

n1 + n2 = Diffsum via back-substitution.