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 2-D plane. You have to execute the query, given a fresh point, which of these n points is closest to it. This is termed as gas-station problem or postman problem, as in asking the question which is the closest gas-station/post-office from some place.

Of course, O(n) can be done {Compare best-so-far value for each point}

But since our set of n points is constant, we would want some pre-processing so that the query time is reduced.

:) Interesting problem. Interesting solution.

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 nine-digit 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 n-2 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.

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 x-1 is the number of cards above red and y-1 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!!

### 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 16-25.

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 16-25.

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 n-1 comparisons. Finding maximum takes n-1 comparisons. If you had to simultaneously find both minimum and maximum, can you do it in less than 2n-2 comparisons?

Update (11/12/09): Solution by Ameya and Me in comments !!

Given an array of n numbers. Finding minimum takes n-1 comparisons. Finding maximum takes n-1 comparisons. If you had to simultaneously find both minimum and maximum, can you do it in less than 2n-2 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^N-1} 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. :)

### 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 5-6 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?

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 side-size 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 6-pack, 9-pack or 20-packs. 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?

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 6-pack, 9-pack or 20-packs. 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 3n-1, 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 3n-1 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 3n-2 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 (26-05-2011)

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 (26-05-2011)

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