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

Showing posts from 2014

- Get link
- Google+
- Other Apps

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

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/te…

- Get link
- Google+
- Other Apps

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

- Get link
- Google+
- Other Apps

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

- Get link
- Google+
- Other Apps

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.

- Get link
- Google+
- Other Apps

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.

Follow CSE Blog on CSE Blog - Twitter and CSE Blog on Quora. :-)

- Get link
- Google+
- Other Apps

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?

- Get link
- Google+
- Other Apps

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):

- Get link
- Google+
- Other Apps

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)

- Get link
- Google+
- Other Apps

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?

- Get link
- Google+
- Other Apps

Update (23 Oct 2014)

- Get link
- Google+
- Other Apps

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):

- Get link
- Google+
- Other Apps

- Get link
- Google+
- Other Apps

Update (18th June 2014):

Solution posted by me (Pratik Poddar) in comments

- Get link
- Google+
- Other Apps

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

- Get link
- Google+
- Other Apps

Update ( 21 June 2014 ) :

Solution by Varun and Adwait in comments!

- Get link
- Google+
- Other Apps

- Get link
- Google+
- Other Apps

Update ( 21 June 2014 ):

- Get link
- Google+
- Other Apps

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):

- Get link
- Google+
- Other Apps