**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?

A collection of ~225 Puzzles with Solutions (classified by difficulty and topic)

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?

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

Problem 1: How many points in

Problem 2: Given 12 random points in **F**_{3}^{4}, what is the probability that there exists a line among them?

We have not solved the problem yet. It can be very difficult or very easy.

It turns out to be a very very difficult problem.

Paper: http://www.math.rutgers.edu/~maclagan/papers/set.pdf

Links: http://www.setgame.com/teachers-corner/research

The answer to Problem 1 is 21.

What’s the expected number of times you will have to fill the cup?

Subscribe to:
Posts (Atom)