Quant, Math & Computer Science Puzzles for Interview Preparation & Brain Teasing
A collection of ~225 Puzzles with Solutions (classified by difficulty and topic)

Dec 25, 2010

Water Jug Problem

Source: Introduction to Algorithms (by Cormen, Rivest, Leiserson)

Problem:
Suppose that you are given 'n' red and 'n' blue water jugs, all of different shapes and sizes. All red jugs hold different amounts of water, as do the blue ones. For every red jug, there is a blue jug that holds the same amount of water and vice versa.

How can you find the grouping of the jugs into pairs of red and blue jugs that hold the same amount of water, in the minimum number of comparisons.

The only operations allowed is compare between a red and a blue jar (no two reds, no two blues)

Update (Dec 30, 2010):
Problem statement changed a bit to make it more understandable.
Solution: Posted by Nikhil Garg (CSE, IIT Delhi third year undergraduate student) and Vivek Chaurasiya (Software Eng Symantec & CSE, IITR Alumnus) in comments! Explained in detail by me in comments!

Dec 19, 2010

Equal zeroes and ones

Source: Asked to me by Dinesh Dharme (CSE IITB Fifth year student)

Problem:
You have a array of 0's and 1's. e.g. 0001011101001010100101010101100111
Find the maximum contiguous subsequence of the above sequence so the number of 0's and 1's in that subsequence are equal

Update (21 Dec 2010):
Solution: Posted by Nikhil Garg (Third year student, CSE IIT Delhi) in comments!

Dec 8, 2010

Locks and Switches

There is a lock which is an N by N grid of switches. Each switch can be in one of two states (on/off). The lock is unlocked if all the switches are on. The lock is built in such a way that, if you toggle some switch, all the switches in its row and its column toggle too

Give an algorithm which, given N and a configuration of the N^2 switches, will tell you whether the lock can be unlocked by a sequence of switch toggles

Note 1: Can be done in O(N^2) time and O(1) space.
Note 2: You just need to tell if a sequence which unlocks the lock exists (and not the actual sequence)

Update (Dec 20, 2010):
Complete solution posted jointly by Siddhant Agarwal (EE, Final year student, IITB) and Gaurav Sinha (IITK 1996 CSE Alumnus, IRS Officer). Thanks a lot

Dec 6, 2010

Order of cards

Source: Asked to me by Prateek Srivastava (CSE IITB Alumnus & Yahoo! Software Engineer)

Problem:

I have ten cards, Ace,2,3,4,5,6,7,8,9,10. The value of the Ace is 1.

They’re shuffled, then dealt one by one, face up. For the first card, you automatically win $10. For the next 9 cards, if the card face-up is greater than every previous card, you win $10 more.

What is the expected winning amount?

Clarification:
1) Game does not end when you draw a card that is not a winning card. ie, if I pick a 5 first, then a 6, then a 4, the game is not over. I keep drawing until all of the cards are gone
2) It might be useful to know that the chance of winning $100 is 1/10!, because the cards will have to be drawn in the order: {A, 2, 3, 4 … , 9, 10}.

Update (Dec 08, 2010)

Solution: Posted by Goutham Valeti (Aero IITB Alumnus, Fair Issac Research Scientist) in comments! A more mathematical solution posted by me in comments!

Stick Broken Into Three Pieces

Source: http://www.cut-the-knot.org/

Problem:
Assume a stick is broken at random into three pieces. What is the probability that the pieces can form a triangle?

Solve it in following cases:
  1. Two break points are selected randomly (and distributed uniformly) on the stick.
  2. The stick is first broken into two pieces. The longest (or rather, not the shortest) is then broken into two.
  3. The stick is first broken into two pieces. A piece randomly selected with probability 1/2 is then broken into two.
  4. The stick is first broken into two pieces. A piece randomly selected with the probability proportional to its length is then broken into two. 
Update (Dec 22, 2010)
Solution posted by me in comments!

    Dec 4, 2010

    The Social Network (2010) - FaceMash Algorithm

    (Disclaimer: This post does not contain any puzzle, but it has sufficient math to keep you interested)


    I saw Social Network three times in 1 week. Not for entertainment. Not because I had nothing better to do. But because I wanted to understand the math and computer science fundae used in the movie. I would like to discuss one particularly interesting scene from the movie.

    You may remember Mark inviting his friend Eduardo to give him his chess algorithm at the beginning of the movie (Mark was drinking, blogging and hacking simultaneously and creating Facemash.com). You may also remember the scribbles on the window:

    and

    What is this? This is actually the math behind Elo Rating System. Elo rating system is a method for calculating the relative skill levels of players in two-player games such as chess. It is named after its creator Arpad Elo, a Hungarian-born American physics professor.

    As explained in the movie, Facemash was quite simple. Not unlike hotornot.com, students went to a page and 2 random images of girls were picked and presented to them. The students then had to click on the hottest girl presented to them and then another set of two girls would be presented asking the students to repeat the same actions they had done. The difference with hotornot was that the girls presented were all Harvard students. In other words, the students were rating girls of Harvard based on their looks (You can imagine why Mark got into trouble).

    The algorithm used - The Elo Rating system - insured a fair rating and ranking of the girls. A hot girl A winning over hot girl B girl would gain more points than winning (or being picked) against ugly girl C. Same goes for the following: ugly girl C wins over ugly girl D. ugly girl C gains some points in her general ranking. If ugly girl C wins over hot girl A then ugly girl C gains more points because the ranking of hot girl A is much higher than ugly girl D. The previous scenario is roughly what the algorithm implemented by Mark was doing. It was somewhat insuring a level of fairness despite the misogynistic nature of the product.

    In today’s society, the Elo Rating system is used by many rating and ranking system to predict the outcome of matches but also insure a level of fairness between teams of different levels playing against each others.  FIFA uses it to rank football teams.

    You can read more about the system on wikipedia page(http://en.wikipedia.org/wiki/Elo_rating_system).

    Probability of Grade A or B

    Source: Homepage of Tejaswi Navilarekallu, Post Doctoral Fellow, Vrije Universiteit, Amsterdam

    Problem:

    A professor decides the following grading scheme in his class. After the final exam is graded, he keeps all the papers upside down on his table in a random order so that no student can recognize his own paper. Each student during his turn can overturn at most n/2 of these papers (where n is the total number of students in the class) and guess whether he received an A or a B on the final (there are only two grades given). Obviously the student doesn't know which paper is his, so it is not guaranteed that he will find his own score by looking at n/2 scores. The papers are then turned back and kept in the original order. The students cannot pass any information to others. All the students pass the course if "everyone" guesses their grade correctly, and they fail otherwise. Come up with a strategy that the students can decide on beforehand, so that the probability that they all will pass is more than a positive constant independent of n.

    Solution: 
    The solution discussed in a problem before at http://pratikpoddarcse.blogspot.com/2009/10/find-your-number.html