CSE Blog - quant, math, computer science puzzles

Source: Asked to me by a friend - who was asked this question in an interview at Facebook Problem: Given n points on a 2D plane, find the equation of the line with maximum number of collinear points. What is the time complexity of your algorithm? Solution: Highlight the part between the * symbols for the answer. * O(n^2) algorithm: the optimal line passes through at least two of the points (otherwise rotate/translate it until it does without losing collinear points). So for each point p, compute the slope from p to every other point and tally frequencies in a hash map (use exact rational slopes dy/dx reduced by gcd, plus a sentinel for vertical lines - avoid floating point). The most frequent slope from p, plus p itself, gives the best line through p. Take the maximum over all p. Complexity: n points x O(n) slope computations and hash updates = O(n^2) expected time, O(n) space per round. (Deterministic O(n^2 log n) via sorting slopes instead of hashing.) This is worst-...

Source: Sent to me by Pritish Kamath ( http://www.mit.edu/~pritish/ ) Problem: Have you ever played "SET"? You have to play it. http://www.setgame.com/learn_play http://www.setgame.com/sites/default/files/Tutorials/tutorial/SetTutorial.swf Even if you have not played the game, the game can be stated in a more abstract way as follows: There are 12 points presented in  F 3 4  and the first person to observe a "line" amongst the 12 given points gets a score. Then the 3 points forming the line are removed, and 3 random fresh points are added. Problem 1: How many points in  F 3 4  are needed to be sure that there exists a line among them? Problem 2: Given 12 random points in  F 3 4 , what is the probability that there exists a line among them? Disclaimer: We have not solved the problem yet. It can be very difficult or very easy. Update (22/12/14): It turns out to be a very very difficult problem. Paper: http://www.math.rutgers.edu/~maclag...

Source:   Mind Your Decisions Blog Related Problem:   Expected Length of Last Straw - Breaking the back of a Camel - CSE Blog Problem: Your boss tells you to bring him a cup of coffee from the company vending machine. The problem is the machine is broken. When you press the button for a drink, it will randomly fill a percentage of the cup (between 0 and 100 percent). You know you need to bring a full cup back to your boss. What’s the expected number of times you will have to fill the cup? Example:  The machine fills the cup 10 percent, then 30 percent, then 80 percent–>the cup is full plus 20 percent that you throw away or drink yourself. It took 3 fills of the cup. Solution: Highlight the part between the * symbols for the answer. * Answer: e = 2.71828... fills. Let X_i be the fraction dispensed on press i (uniform on [0,1]) and S_k = X_1 + ... + X_k. You press a (k+1)-th time exactly when S_k < 1, so the expected number of presses is 1 + su...