## Posts

Showing posts from December, 2014

### Maximum Number of Collinear Points

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?

### Mathematics of SET game

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 F34 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 F34 are needed to be sure that there exists a line among them? Problem 2: Given 12 random points in F34, 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/~maclagan/papers/set.pdf

### Expected Number of Attempts - Broken Coffee Machine

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.