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

Source: (Romanian Informatics Olympiad ONI'03, extended team selection)

( ^ Representative diagram of Huffman Encoding. No relevance in the problem) Problem: A telegraph machine can transmit only lines and dots; it takes 2 seconds to transmit a line, but only 1 second to transmit a dot. We generally want to transmit texts containing letters of the English alphabet, and digits (so we have N<=36 symbols in total). Therefore, a prefix-free encoding using lines and dots is needed. Given the frequencies of the N symbols in a large text, find the minimum time it takes to transmit the text using a suitable encoding. The solution should run in O(N^4) time, and use O(N^3) space.

Problem:
Assume the following 3-player game consisting of several rounds. Players A and B build a team, they have one fair coin each, and may initially talk to each other. Before starting the first round, however, no more communication between them is allowed until the end of the game. (Imagine they are separated in different places without any communication infrastructure.)

A round of the game consists of the following steps:

(1) the team gives one dollar to player C.

(2) Both A and B toss their coins independently.

(3) Both A and B try to predict the other's coin by telling the guess to C. (No communication: A does not know the outcome of B's coin toss, and vice versa, nor the guess).

(4) If C verifies that both A and B guess the other's coin correctly, then C has to give 3 dollars back to the team.

Update: (29 Jan 2013)
Correct solution by: Takaki, Andre, Felix, JDGM in comments!
Correct strategy (but not so correct calculation) by Joshua, Shubham Mittal in comments!
If you are just looking for the solution, Perfect solution by Andre. Thanks

Problem:
The king of the universe has decided to play a game. To start, he selects 1 person. He then flips two fair coins - if they both come up heads, the person gets a free pizza and the game is over. For any other result, he sends the person home and selects 2 new people, where he does the same 2-coin flip to decide if they each get a pizza. If they don’t, he picks 4 people at random, then 8, and so on, doubling each round. If you are selected but don’t win, you can’t be selected again – and you can assume the population is extremely large so there’s no chance of running out of contestants.

You are sitting at home when you get a call – you have been selected to play the game. What is the chance that you will get a free pizza?

You don't know which round number it is, but if you ask, the king will tell you. Does it matter?

Disclaimer: Very easy problem!

Update (31 January 2013):
Title changed to "Pizza Distribution Puzzle" from "Pizza Paradox Puzzle" - as pointed out by Vivek Ranjan Nema in comments, there is no paradox. My mistake. Apologies.
Solution posted by Rushabh Sheth, Pratyush Rathore, Nathan Jacobson, Marjansek, Shyam Raj in comments!

Source: Asked to me by Pramod Ganapathi (PhD Student at Stony Brook University)

Problem:
A lion and a lion tamer are enclosed within a circular cage. If they move at the same speed but are both restricted by the cage, can the lion catch the lion tamer? (Represent the cage by a circle, and the lion and lion tamer as two point masses within it.)

Problem 2: Geometry Puzzle: Center of Square in Circle

Source: Asked to me by a lot of people from IIT Bombay on email and posted by a few on "Post a Question" page.

Problem:
What is the probability that two uniform random points (to be precise: i.i.d. with respect to Lebesgue measure) in the square are such that center of the square lies in the circle formed by taking the points as diameter.

Let's say A keep tossing a fair coin, until he get 2 consecutive heads, define X to be the number of tosses for this process; B keep tossing another fair coin, until he get 3 consecutive heads, define Y to be the number of the tosses for this process.

There are 100 coins on the table out of which 50 are tail-face up and 50 are head face up. You are blind folded and there is no way to determine which side is up by rubbing, etc. You have to divide the 100 coins in two equal halves such that both have equal number of coins with tails face up. (This obviously implies that the two have equal number of coins with heads face up)

Second part: There are 100 coins on the table out of which 10 are tail-face up and 90 are head face up. You are blind folded and there is no way to determine which side is up by rubbing, etc. You have to divide the 100 coins in two halves (not necessarily equal) such that both have equal number of coins with tails face up.

Problem:
There is a calculator in which all digits(0-9) and the basic arithmetic operators(+,-,*,/) are disabled. However other scientific functions are operational like exp, log, sin, cos, arctan, etc. The calculator currently displays a 0. Convert this first to 2 and then to 3.

Source: Flipkart Interview Question from Interview Street (taken from Chinmay - CSE IITB Blog)

Problem:

Find the smallest number of jumps (i.e. optimal number of dice throws) needed to win a snakes and ladders game. Assume you are given a board with all the necessary inputs like start/end positions of all ladders and snakes.

Source: Asked to me by Sankeerth Rao (EE IITB 4th year Student)

Problem:
Given any two triangles in a plane construct a line which bisects both their areas.

Background:
In fact the existence of such a line is true in a very general setting - for any two polygons in a plane there exists a line which bisects both their areas. In fact its true for any two Jordan measurable sets in a plane. Further generalized version is called the Ham Sandwich Theorem and is proved using Borsuk Ulam Theorem.

Source: Video of a course in Algorithms on Udacity - Asked by Prof. Peter Winkler

Problem:
A spy in an enemy territory is trying to convey information to her control, but the only means she has for conveying information is that there is a 15-bit radio broadcast every morning, and she has the ability if she wishes to alter 1 bit of that broadcast. But she doesn't know in advance what the broadcast will be. So, this is a case where, potentially, there are 16 different things she can do. There are 15 bits she can alter, or she can choose not to alter any bit, which means that in theory perhaps she could convey as many as 4 bits of information this way.

Well, surprisingly, she can actually do that.

Repeating the problem to make sure that we understand the setup here. So, I'm a spy, and I'm in enemy territory, and I've got a message --0110-- that I need to transmit to my boss. Now, that's going to be tricky to do, because I don't want anybody to know that I'm a spy in enemy territory. Fortunately, there is a radio broadcast tower in enemy territory, and everyday it sends out a 15-bit message. There's an example of a 15-bit message. Now, I can use that message to communicate with my boss, but I can't just change it arbitrarily to something completely different, because then people will know that something weird has happened. But I can flip just 1 bit. I can zap the message and change just one of the bits, and my boss then is going to hear that, and we'd like him to actually interpret that as the message that I want to send. How should I do that such that, when the boss receives the broadcast, he is like - Hmm...based on the 15-bit broadcast I'm hearing, and the protocol that my spy and I arranged in advance, I know that the message he is sending to me is 0110. Nice work, agent P.

Peter Winkler's video with Problem and Solution:

Update:
Peter Winkler gave the solution in the video. Wrote the solution in comments!

Source: Mailed to me by Sudeep Kamath (PhD Candidate UC Berkeley, EE IITB 2008 Alumnus)

Problem:

Suppose we have a portrait hung on a wall using one nail. Now, suppose we
hammer another nail next to the existing one and try to use both nails to
hang the portrait. If any nail breaks, the portrait continues to hang
safely. Can we hang the portrait in such a way that if any one nail breaks
the portrait must fall down?

Generalize to k nails: Hang a portrait on k nails such that if any one nail
breaks, the portrait must fall down.