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

What is the maximum number of pebbles Peggy can place on the chessboard?

There are several pebbles placed on an n × n chessboard, such that each pebble is inside a square and no two pebbles share the same square.

Perry decides to play the following game. At each turn, he moves one of the pebbles to an empty neighboring square. After a while, Perry notices that every pebble has passed through every square of the chessboard exactly once and has come back to its original position.

Prove that there was a moment when no pebble was on its original position.

Repeat this process until every number is 0, then stop. Prove that this process always terminates if and only if n is a power of 2.

There are some weights on the two sides of a balance scale. The mass of each weight is an integer number of grams, but no two weights on the same side of the scale share the same mass. At the moment, the scale is perfectly balanced, with each side weighing a total

of W grams. Suppose W is less than the number of weights on the left multiplied by the number of weights on the right.

Is it always true that we can remove some, but not all, of the weights from each side and still keep the two sides balanced?

Call a nine-digit number flawless if it has all the digits from 1 to 9 in some order. An unordered pair of flawless numbers is called harmonious if they sum to 987654321. Note that (a, b) and (b, a) are considered to be the same unordered pair.

Without resorting to an exhaustive search, prove that the number of harmonious pairs is odd.

Update (23 Oct 2014):

Example 1:

1 2 2 3 4

Answer : 0 (-1+2-2-3+4)

Example 2:

2 3 4 7 13

Answer: 1 (+2-3-4-7+13)

You are organizing a conference, with a festive dinner on the first day. The catering service has 1024 different dinner choices they know how to make, out of which you need to choose 10 to be in the dinner menu (each participant will choose one of these during the dinner). You send an email to the 6875 participants of the conference, with the list of all 1024 choices, asking them to rank the choices in linear order from their favorite to their unfavorite.

You want to find a list L of 10 choices, such that for any dinner choice d not in the list L, if we run a vote of d against L, at least half of people will favor one of the choices in L over d (it may be different dish for different people).

Is it always possible to produce such a list?

Update (23 Oct 2014)

A mad robot sets off towards the North East on a journey from the point (0,0) in a coordinate system. It travels in stages by moving forward and then rotating on the spot. It follows these pseudo-code instructions:

SUB JOURNEY

DISTANCE = 1000

WHILE (DISTANCE > 0.001)

MOVE DISTANCE

STOP

ROTATE(90, DEGREES, CLOCKWISE)

DISTANCE = DISTANCE / 2

END WHILE

EXPLODE

END SUB

Where does the robot explode?

Update (23 Oct 2014):

The friendship paradox is the phenomenon first observed by the sociologist Scott L. Feld in 1991 that most people have fewer friends than their friends have, on average. Prove it mathematically.

Update (23 Oct 2014):

Update (18th June 2014):

Solution posted by me (Pratik Poddar) in comments

Solution posted by me (Pratik Poddar) in comments

A square has a quarter in each corner. You are blindfolded and must get all quarters to be heads up or all to be tails up. You will be told when you have done this. You may flip however many you want, then ask if you are done (this constitutes a turn). The square is then rotated/spun an undisclosed number of times. You then get another turn and so on…

Is there a strategy that is guaranteed to work in a finite number of moves, and if so, what is that smallest number of moves you need to be 100% you’ll be able to have all heads up or all tails up?

The same problem is there on the blog - in a different form - asked more than 50 months back :-) - Blind Flipping - CSE Blog

Update ( 21 June 2014 ) :

Solution by Varun and Adwait in comments!

Estimate the value of pi using a dice

Solution posted by Tushar Makkar, 'My first amateur attempt', Satadip, Gaurav Bajaj and me (Pratik) in comments. Thanks

Update ( 21 June 2014 ):

Suppose you have an infinite stock of $a bills and $b bills such that g.c.d(a,b)=1. Find the largest amount of money (integer) that cannot be represented using $a and $b denominations.

If you have not done it already, please like / +1 / follow on: Quora, Twitter, Facebook, G+

Update (21 June 2014):

**Solution: **Posted by Raunak Kudesia, Sid Hollander and me (Pratik) in comments!

Subscribe to:
Posts (Atom)