Interview Questions: Difference between revisions
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. | ||