Dank at 02:01, 10 September 2011

2011-09-10T02:01:52Z

← Older revision		Revision as of 02:01, 10 September 2011
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.
	** 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)

Dank: 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..."

2011-09-10T02:00:32Z

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..."

New page

==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.
** 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:
<code>n1 * n2 = Diffprod
n1 + n2 = Diffsum</code>
via back-substitution.
** 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)

Interview Questions - revision history

Dank at 02:01, 10 September 2011

Dank: 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..."