CSE Blog - quant, math, computer science puzzles

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.

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!!

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!!

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

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!!

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!!

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 !!

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

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

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 !!

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

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

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) Solution: First part: Posted by Abhishek Shukla (Indian Institute of Science Education and Research, Kolkata) in comments! Second part: Posted by Siddha...

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

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!!