This was the question asked to Anirudh in his google interview. He could not do it (who cares! He got the job :D)
I could give a vague but correct answer :)
You have n points on a 2D plane. You have to execute the query, given a fresh point, which of these n points is closest to it. This is termed as gasstation problem or postman problem, as in asking the question which is the closest gasstation/postoffice from some place.
Of course, O(n) can be done {Compare bestsofar value for each point}
But since our set of n points is constant, we would want some preprocessing so that the query time is reduced.
:) Interesting problem. Interesting solution.
Quant, Math & Computer Science Puzzles for Interview Preparation & Brain Teasing
A collection of ~225 Puzzles with Solutions (classified by difficulty and topic)
Nov 25, 2009
Nov 23, 2009
Blind flipping
Four tumblers are placed at the corners of a square table. A blind gnome and an evil goblin take turns to play a game. The blind gnome gets to choose a subset of the four tumblers and flip them simultaneously. Effectively, he may choose “one tumbler”, “two diagonally opposites”, “two adjacent”, “three tumblers” or “four tumblers” lying in front of him. After flipping, if all four tumblers are upright, he wins the game! Otherwise, the game continues: the evil goblin rotates the table by an amount of his choice. Can the blind gnome win the game with a deterministic strategy?
Source: One of the questions in the placement paper of a quant company at another IIT
Update (11/12/09): Solution by Me, Jaadu and Ramdas in comments!!
Source: One of the questions in the placement paper of a quant company at another IIT
Update (11/12/09): Solution by Me, Jaadu and Ramdas in comments!!
Nov 14, 2009
Missing Digit
2^29, expressed in base 10, is a ninedigit number. All nine of its digits are different. Find the digit that is missing without explicitly calculating 2^29.
This question was posed to me by Dinesh Dharme (CSE, IITB). Simple but interesting puzzle!!
Update (11/12/09): Solution in comments!!
This question was posed to me by Dinesh Dharme (CSE, IITB). Simple but interesting puzzle!!
Update (11/12/09): Solution in comments!!
Nov 11, 2009
Polya's Urn Problem
Puzzle: There are two urns with one ball each. Each of subsequent n2 balls is placed into one of these urns, with probability proportional to the number of balls already in that urn. What is the expected number of balls in the smaller sized urn?
Source:P. Winkler's Puzzles book. (Chapter: Probability).
Solution:
Highlight the part between the * symbols for the answer.
*This problem can be reformulated as the following problem.
I am happy!! Happy Happy Joy Joy!! *
Source:P. Winkler's Puzzles book. (Chapter: Probability).
Solution:
Highlight the part between the * symbols for the answer.
*This problem can be reformulated as the following problem.
Suppose I have a stack of black cards and one red card. Initially I take red card in my hand. Now I add black cards randomly between any two cards (so, initially its either above or below red). Note that the probability that I add the card above the red card, when x1 is the number of cards above red and y1 is the number of cards below red is x/(x+y). Let the problem be if red card is dividing the black cards into two sets, what is the expected number of black cards in the smaller section. So, we see that the two problems are equivalent.
Now this way, we are getting all possible combinations in which one red and n black cards can be mixed, we see that the probability that the red card is at height h is independent of h. So, the probability that the smallest urn contains n/2 balls or 1 ball (or any number of balls between 1 and n/2) are all same. So, expected number of balls in the smaller urn is asymptotically n/4. :)
Nov 10, 2009
Flipping Bits in a Matrix
Puzzle: An 8×8 matrix contains zeros and ones. You may repeatedly choose any 3×3 or 4×4 block and flip all bits in the block (that is, convert zeros to ones, and ones to zeros). Can you remove all the ones in the matrix?
Source: Gurmeet Singh Manku's Blog where he said that he saw it in an old Russian problem book.
Solution:
Highlight the part between the * symbols for the answer.
* There are 36 3×3 blocks and 25 4×4 blocks. Given a sequence of blocks, the same effect is achieved no matter in what order the blocks are chosen. If the same block occurs two times in a sequence, their effect is nullified. Thus, a sequence of blocks is equivalent in effect to some subset of the 36 + 25 = 61 blocks. Starting with all zeros, at most 2^61 distinct configurations out of 2^64 possible configurations of the matrix can be reached. This means that we may not be able to remove all the ones from the original matrix. *
Fundoo question!!
Source: Gurmeet Singh Manku's Blog where he said that he saw it in an old Russian problem book.
Solution:
Highlight the part between the * symbols for the answer.
* There are 36 3×3 blocks and 25 4×4 blocks. Given a sequence of blocks, the same effect is achieved no matter in what order the blocks are chosen. If the same block occurs two times in a sequence, their effect is nullified. Thus, a sequence of blocks is equivalent in effect to some subset of the 36 + 25 = 61 blocks. Starting with all zeros, at most 2^61 distinct configurations out of 2^64 possible configurations of the matrix can be reached. This means that we may not be able to remove all the ones from the original matrix. *
Fundoo question!!
Lets Call 50
I saw this puzzle on the site http://www.crackpuzzles.com/
Suppose two players are playing a game where we call integers. The first person who calls 50 wins. The rules are that the first person calls a number between 1 and 10. After that any new number that is called must exceed the last number by at least one and no more than by 10. For example: If the last number called is 15, then the next number that is called must be between 1625.
I give you the first mover advantage, devise a strategy to win.
Update (11/12/09): Solution in comments!!
Suppose two players are playing a game where we call integers. The first person who calls 50 wins. The rules are that the first person calls a number between 1 and 10. After that any new number that is called must exceed the last number by at least one and no more than by 10. For example: If the last number called is 15, then the next number that is called must be between 1625.
I give you the first mover advantage, devise a strategy to win.
Update (11/12/09): Solution in comments!!
Minimum and Maximum
Source: IITM Friend (who did not want his name to be disclosed). Also read it once in CLR (Introduction to Algorithms)
Given an array of n numbers. Finding minimum takes n1 comparisons. Finding maximum takes n1 comparisons. If you had to simultaneously find both minimum and maximum, can you do it in less than 2n2 comparisons?
Update (11/12/09): Solution by Ameya and Me in comments !!
Given an array of n numbers. Finding minimum takes n1 comparisons. Finding maximum takes n1 comparisons. If you had to simultaneously find both minimum and maximum, can you do it in less than 2n2 comparisons?
Update (11/12/09): Solution by Ameya and Me in comments !!
Nov 8, 2009
Weighing problems
These problems was posed to me by friends at NBHM Nurture Programme 2007 at IMSc Chennai
Problem 1:
A shopkeeper can only place the weights in one side of the common balance. For example if shopkeeper has weights 1 and 3 then he can measure 1,3 and 4 only. How many minimum weights and name the weights you will need to measure all weights from 1 to 1000.
Solution 1:
Highlight the part between the * symbols for the answer.
*The numbers 1,2,4,8,16... This is optimal as each number has exactly one binary representation. So for making 1000 kg we need up to 1, 2, 4, 8, 16, 32, 64, 128, 512. :) *

Problem 2:
Same as the first problem with the condition of placing weights on only side of the common balance being removed. You can place weights on both side and you need to measure all weights between 1 and 1000. For example if you have weights 1 and 3,now you can measure 1,3 and 4 like earlier case, and also you can measure 2, by placing 3 on one side and 1 on the side which contain the substance to be weighed. How many minimum weights and of what denominations you need to measure all weights from 1kg to 1000kg.
Solution 2:
Highlight the part between the * symbols for the answer.
* The numbers 1,3,9,27,81,243,729. This is true because each number now has exactly one ternary representation. Any 2*3^i can always be represented as 3^(i+1)  3^i. So, there is a unique way of representing a number in the form of sigma s_i*3^i where s_i belongs to {0, 1, 1}. So, this is optimal. *

Problem 3:
This is the most difficult one. You have to make 125 packets of sugar with first one weighing 1 kg, second 2 kg, third 3 kg etc ...and 125th one weighing 125kg.You can only use one pan of the common balance for measurement for weighing sugar, the other pan had to be used for weights i.e. weights should be used for each weighing.
It has come into notice that moving weights into and out of the pan of the balance takes time and this time depends on the number on the number of weights that are moved. For example  If we need to measure 4 kg using weights 1 and 3 only, it will take twice as much time needed to measure 1 kg. Lets say we want to make sugar packets of weights 1,3,4 using weights 1 and 3 only. For this first we measure 1 kg, with 1 unit of time, we place 3 kg along with 1 kg and measure 4kg with again 1 unit of time, and finally we move 1kg out of pan to measure 3kg in 1 unit of time. So in 3 units of time we could measure 1,3 and 4kg using weights 1 and 3 only.
Now you have to make sugar packets of all weights from 1 to 125 in minimum time, in other words in minimum movement of weights. The question here is to find out the minimum number of weighs needed and the weight of each the weights used and the strategy to be followed for the creation of 125 packets of sugar.
Solution:
Highlight the part between the * symbols for the answer.
* This is a problem to be solved by Gray code.
A naive method was taking ~ 2^7*7/2 = 448 shifts :) *
Problem 1:
A shopkeeper can only place the weights in one side of the common balance. For example if shopkeeper has weights 1 and 3 then he can measure 1,3 and 4 only. How many minimum weights and name the weights you will need to measure all weights from 1 to 1000.
Solution 1:
Highlight the part between the * symbols for the answer.
*The numbers 1,2,4,8,16... This is optimal as each number has exactly one binary representation. So for making 1000 kg we need up to 1, 2, 4, 8, 16, 32, 64, 128, 512. :) *

Problem 2:
Same as the first problem with the condition of placing weights on only side of the common balance being removed. You can place weights on both side and you need to measure all weights between 1 and 1000. For example if you have weights 1 and 3,now you can measure 1,3 and 4 like earlier case, and also you can measure 2, by placing 3 on one side and 1 on the side which contain the substance to be weighed. How many minimum weights and of what denominations you need to measure all weights from 1kg to 1000kg.
Solution 2:
Highlight the part between the * symbols for the answer.
* The numbers 1,3,9,27,81,243,729. This is true because each number now has exactly one ternary representation. Any 2*3^i can always be represented as 3^(i+1)  3^i. So, there is a unique way of representing a number in the form of sigma s_i*3^i where s_i belongs to {0, 1, 1}. So, this is optimal. *

Problem 3:
This is the most difficult one. You have to make 125 packets of sugar with first one weighing 1 kg, second 2 kg, third 3 kg etc ...and 125th one weighing 125kg.You can only use one pan of the common balance for measurement for weighing sugar, the other pan had to be used for weights i.e. weights should be used for each weighing.
It has come into notice that moving weights into and out of the pan of the balance takes time and this time depends on the number on the number of weights that are moved. For example  If we need to measure 4 kg using weights 1 and 3 only, it will take twice as much time needed to measure 1 kg. Lets say we want to make sugar packets of weights 1,3,4 using weights 1 and 3 only. For this first we measure 1 kg, with 1 unit of time, we place 3 kg along with 1 kg and measure 4kg with again 1 unit of time, and finally we move 1kg out of pan to measure 3kg in 1 unit of time. So in 3 units of time we could measure 1,3 and 4kg using weights 1 and 3 only.
Now you have to make sugar packets of all weights from 1 to 125 in minimum time, in other words in minimum movement of weights. The question here is to find out the minimum number of weighs needed and the weight of each the weights used and the strategy to be followed for the creation of 125 packets of sugar.
Solution:
Highlight the part between the * symbols for the answer.
* This is a problem to be solved by Gray code.
A Gray code represents each number in the sequence of integers {0...2^N1} as a binary string of length N in an order such that adjacent integers have Gray code representations that differ in only one bit position. Marching through the integer sequence therefore requires flipping just one bit at a time.
For this answer we need as many blocks as per Solution to Problem 1. For easy understanding let me describe the case where the packets range from 1 to 7 which can be easily extended to 1  125 range.
Now if we want to make packets of all weights from 1 to & we will do the following
001 We measure 1kg,using 1kg block.
011 We measure 3kg by placing 2 kg block also
010 We remove 1kg block and measure 2 kg.
110 We add 4kg weight and measure 6kg weight
and so on
Now we can see answer to our problem is Gray code of 7 bits. Now our range is 1 to 125 and not 1 to 127.This can be solved by using appropriate Gray code making the following numbers falling to the end of the sequence you are starting with
1111 110
1111 111
So, it means that I can weigh all packets from 1 to 125 with only 125 shifts
Nov 6, 2009
Choose the maximum of two number
Source: P. Winkler
I write two different numbers in the range [a,b], one on each hand. You choose one of my hands at random, I show you the number on that hand. You now guess whether the number you've seen is larger than the number you haven't seen.
Find a strategy for guessing such that, no matter what two numbers I write, you have GREATER THAN a 50% chance of being correct.
Solution:
Highlight the part between the * symbols for the answer.
* I would choose a number randomly in the range [a,b]. Add 0.5 to it and save the number as k in my memory. If the number I see in one hand is less than k, I would say that the number in the other hand is greater. In the other case, I will say that the number in the other hand is less.
One can prove that here, winning probability is greater than 0.5
Let the number that comes out is k'
If k' less than k,
I am doing well when other number is either greater than k or between k' and k
If k' greater than k
I am doing well when other number is either less than k or between k' and k
So, the probability is greater than half, though getting an epsilon is not possible.
Answer :) *
Update(05/02/10): Thanx to Aaditya Ramdas for pointing out a "mistake" in the problem (discussion in comments). Problem statement changed slightly and is correct now. :)
I write two different numbers in the range [a,b], one on each hand. You choose one of my hands at random, I show you the number on that hand. You now guess whether the number you've seen is larger than the number you haven't seen.
Find a strategy for guessing such that, no matter what two numbers I write, you have GREATER THAN a 50% chance of being correct.
Solution:
Highlight the part between the * symbols for the answer.
* I would choose a number randomly in the range [a,b]. Add 0.5 to it and save the number as k in my memory. If the number I see in one hand is less than k, I would say that the number in the other hand is greater. In the other case, I will say that the number in the other hand is less.
One can prove that here, winning probability is greater than 0.5
Let the number that comes out is k'
If k' less than k,
I am doing well when other number is either greater than k or between k' and k
If k' greater than k
I am doing well when other number is either less than k or between k' and k
So, the probability is greater than half, though getting an epsilon is not possible.
Answer :) *
Update(05/02/10): Thanx to Aaditya Ramdas for pointing out a "mistake" in the problem (discussion in comments). Problem statement changed slightly and is correct now. :)
Cyclic Strings
Found it in collection of Jian Li, CS Department, University of Maryland
Given 2 cyclic strings, both consisting n distinct letter,namely a permuatation of 1 to n.
the problem is to find a rotation of one string that minimize the swap distance.(i.e.the number of swaps of adjacent elements to bring one necklace to the other)
Can you give an O(nlogn) algorithm?
This is a difficult problem. So, think hard!!
Update (11/12/09): Solution in comments !!
Given 2 cyclic strings, both consisting n distinct letter,namely a permuatation of 1 to n.
the problem is to find a rotation of one string that minimize the swap distance.(i.e.the number of swaps of adjacent elements to bring one necklace to the other)
Can you give an O(nlogn) algorithm?
This is a difficult problem. So, think hard!!
Update (11/12/09): Solution in comments !!
Four Ants  HC Verma
Solved a more difficult problem in HC Verma 56 years back.. :)
Four bugs are on the corners of a 1 meter square. Each bug always faces the next bug (on the next clockwise corner). If they all walk forward at the same speed until they meet, how far does each bug travel?
Solution:
Highlight the part between the * symbols for the answer.
*Since the bugs always move perpendicular to each other, so when they meet at the center they have traveled a distance equivalent to their initial separation i.e. 1 m.
If some of you remember, in the HC Verma problem, the three ants were moving in a equilateral triangle of sidesize 1. The three ants were such that 1 is following 2, 2 is following three and three is following 1. By symmetry, they would meet at the centre. The time taken was 2/3v as you had to take components along the line joining the two ants. So, v(1+cos60) was the real relative speed along the line joining two ants. So, time taken was 2/(3v). So, the distance traveled was 2/3. :)*
Four bugs are on the corners of a 1 meter square. Each bug always faces the next bug (on the next clockwise corner). If they all walk forward at the same speed until they meet, how far does each bug travel?
Solution:
Highlight the part between the * symbols for the answer.
*Since the bugs always move perpendicular to each other, so when they meet at the center they have traveled a distance equivalent to their initial separation i.e. 1 m.
Chicken Nuggets
Heard this problem many times. This problem is everywhere.
You can go to a fast food restaurant to buy chicken nuggets in 6pack, 9pack or 20packs. is there such a number N, such that for all numbers bigger than or equal to N, you can buy that number of chicken nuggets?
Solution:
Highlight the part between the * symbols for the answer.
*Yes. The number is 44
You can go to a fast food restaurant to buy chicken nuggets in 6pack, 9pack or 20packs. is there such a number N, such that for all numbers bigger than or equal to N, you can buy that number of chicken nuggets?
Solution:
Highlight the part between the * symbols for the answer.
*Yes. The number is 44
All numbers can be written in the form 3n1, 3n or 3n+1. Now taking all nos. of the form 3n, all such numbers (except 3) can be formed by combination of 6 and 9.
Now let us take all numbers of the form 3n1 which are greater than 20, starting with 23, 26, 29.... now again using the same concept like in the last part if we subtract 20(i.e. including a 20 nugget pack) from these numbers, the rest can be formed by combination of 6 and 9 other than 23 which would be the largest such number so far.
Similarly we will take all numbers of the form 3n2 which are greater than 40, starting with 43, 46, 49.... and we will use the same concept like in the last part, if we subtract 40(i.e. including two 20 nugget packs) from these numbers, the rest can be formed by combination of 6 and 9 other than 43 which would be the largest number and so the answer to the puzzle is 44.*
Nov 5, 2009
IBM Ponder This November Challenge
I am happy.. I am amongst the first few people to solve IBM Ponder This November Challenge.. This puzzle, unlike the last one, is really challenging and requires mathematical skills.
I am posting the puzzle. IBM Guys would post the solution in a month's time.
IBM Page
What is the minimal number, X, of yes/no questions needed to find the smallest (but more than 1) divisor of a number between 2 and 166 (inclusive)?
We are asking for the exact answer in two cases:
In the worst case, i.e., what is the smallest number X for which we can guarantee finding it in no more than X questions?
On average, i.e., assuming that the number was chosen in uniform distribution from 2 to 166 and we want to minimize the expected number of questions.
* For example, the smallest divisor of 105 is 3, and of 103 is 103.
Update (26052011)
Solution:
First part: Posted by Abhishek Shukla (Indian Institute of Science Education and Research, Kolkata) in comments!
Second part: Posted by Siddhant Agarwal, EE IITB 2011 Alumnus in comments!
I am posting the puzzle. IBM Guys would post the solution in a month's time.
IBM Page
What is the minimal number, X, of yes/no questions needed to find the smallest (but more than 1) divisor of a number between 2 and 166 (inclusive)?
We are asking for the exact answer in two cases:
In the worst case, i.e., what is the smallest number X for which we can guarantee finding it in no more than X questions?
On average, i.e., assuming that the number was chosen in uniform distribution from 2 to 166 and we want to minimize the expected number of questions.
* For example, the smallest divisor of 105 is 3, and of 103 is 103.
Update (26052011)
Solution:
First part: Posted by Abhishek Shukla (Indian Institute of Science Education and Research, Kolkata) in comments!
Second part: Posted by Siddhant Agarwal, EE IITB 2011 Alumnus in comments!
Nov 3, 2009
Wikipedia Links for Algorithms and Probability
Algorithms:
Graph Algorithms
Search Algorithms
String Algorithms
NP Complete Problems
Polynomial Time Problems
Dynamic Problem
Longest Common Substring
Longest Increasing Subsequence
Longest Common Subsequence
Selection Algorithm
Some famous paradoxes:
Gambler's Fallacy
Ellsberg Paradox
Two Envelopes Problem
Neck Tie Paradox
Monty Hall Problem
Three Prisoners Problem
Bertrand's Box Paradox
Boy or Girl
Bertrand's Paradox
Anti martingale
St. Petersburg Paradox
Exchange Paradox
Graph Algorithms
Search Algorithms
String Algorithms
NP Complete Problems
Polynomial Time Problems
Dynamic Problem
Longest Common Substring
Longest Increasing Subsequence
Longest Common Subsequence
Selection Algorithm
Some famous paradoxes:
Gambler's Fallacy
Ellsberg Paradox
Two Envelopes Problem
Neck Tie Paradox
Monty Hall Problem
Three Prisoners Problem
Bertrand's Box Paradox
Boy or Girl
Bertrand's Paradox
Anti martingale
St. Petersburg Paradox
Exchange Paradox
Nov 2, 2009
No division operator and O(n)
Some site said that this is a google interview question:
There is an array A[N] of N integers. You have to compose an array B[N] such that B[i] will be equal to the product of all the elements of A[] except A[i].
B[i] = (product from j = 1 to N, j not equal to i) A[i]
Example:
Input:[4, 3, 2, 1, 2]
Output:[12, 16, 24, 48, 24]
Solve it without division operator and in O(n).
Update (11/12/09) : Solution provided by Subhasis (EE, IITB) in comments!!
Update (01/01/10) : Solution for another case provided by Shantanu Gangal, BCG (CSE, IITB alumnus) in comments!!
There is an array A[N] of N integers. You have to compose an array B[N] such that B[i] will be equal to the product of all the elements of A[] except A[i].
B[i] = (product from j = 1 to N, j not equal to i) A[i]
Example:
Input:[4, 3, 2, 1, 2]
Output:[12, 16, 24, 48, 24]
Solve it without division operator and in O(n).
Update (11/12/09) : Solution provided by Subhasis (EE, IITB) in comments!!
Update (01/01/10) : Solution for another case provided by Shantanu Gangal, BCG (CSE, IITB alumnus) in comments!!
Subscribe to:
Posts (Atom)
Fraction Brainteaser
Source: Sent to me by Gaurav Sinha Problem: Siddhant writes a Maths test and correctly answers 5 out of 6 Arithmetic questions and 20...

This is not a puzzle. So, for those of you who follow this puzzle blog, please bear with me for just one post. Interesting Math in this art...

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 tos...

Source: Sent to me by Gaurav Sinha Problem: Siddhant writes a Maths test and correctly answers 5 out of 6 Arithmetic questions and 20...