Check out my first novel, midnight's simulacra!
Interview Questions: Difference between revisions
From dankwiki
(Created page with "==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 probabil...") |
No edit summary |
||
| Line 8: | Line 8: | ||
** 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) | ** 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. | * 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 [http://en.wikipedia.org/wiki/1729_%28number%29 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<sub>prod</sub> and Diff<sub>sum</sub>. Solve the system of equations: | ** 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<sub>prod</sub> and Diff<sub>sum</sub>. Solve the system of equations: | ||
<code>n1 * n2 = Diff<sub>prod</sub> | <code>n1 * n2 = Diff<sub>prod</sub> | ||
n1 + n2 = Diff<sub>sum</sub></code> | n1 + n2 = Diff<sub>sum</sub></code> | ||
via back-substitution. | via back-substitution. | ||
Latest revision as of 02:01, 10 September 2011
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.
