CSE Blog - quant, math, computer science puzzles

Source: Interview Street CodeSprint (slightly modified) Problem: One of the basics of Computer Science is knowing how numbers are represented in 2's complement. Imagine that you write down all numbers between A and B inclusive in 2's complement representation using 32 bits. How many 1's will you write down in all ? Input: Two integers A and B Output: The number of 1s Constraints: -2^31 <= A <= B <= 2^31 - 1 Find the asymptotically optimal algorithm. Solution: Highlight the part between the * symbols for the answer. * Optimal algorithm: O(number of bits) - i.e. O(32), constant per query - using digit DP. Split the answer: countOnes(A, B) = F(B) - F(A - 1), where F(X) = total 1-bits in the 32-bit two's complement representations of all numbers from -2^31 to X (or 0 to X for X >= 0). For X >= 0 (plain binary): group numbers by their most significant bit. Group m has 2^m numbers, each contributing one m-th bit plus all the bits of the pre...

Source: Quora - Asked in a Google Interview Problem: Using only a four-minute hourglass and a seven-minute hourglass, measure exactly nine minutes–without the process taking longer than nine minutes. Bonus made-up Question: Can you come up with a generalized solution of the hour glass problem? This is a more involved version of  the "Die Hard III Problem: A classic water bottle riddle. How to produce exactly 4 gallons with a 3 and a 5 gallon pan" whose solution can be found here Update: (26/12/2012): Assume that equal amount of sand slipped down measures equal intervals of time, i.e. amount of sand slipped to measure the first minute is same as the last minute. Solution posted by Gold and Iron (Nikhil Pandey, CSE IITB 2009 Alumnus), Mohit Johari (Civil IITB 2011 Alumnus) , Nikhil Simha R (Amazon India SDE, CSE IITB 2012 Alumnus)  and Sravan Kumar (EE IITB Final Year Student) in comments!

Source: Posted at " Post a Question " Problem: Two players compete in the following game: There is a pile containing n chips; the first player removes any number of chips except that he cannot take the whole pile. From then on, the players alternate moves, each person removing one or more chips but not more than twice as many chips as the preceding player has taken. The player who removes the last chip wins. (For example, suppose that n = 11; player A removes 3 chips; player B may remove up to 6 chips, and he takes 1. There remain 7 chips; player A may take 1 or 2 chips, and he takes 2; player B may remove up to 4, and he picks up 1. There remain 4 chips; player A now takes 1; player B must take at least one chip and player A wins in the his next chance. What is the best move for the first player to ensure his win if possible if there are initially n chips? Solution: Highlight the part between the * symbols for the answer. * This is Fibonacci Nim (Whinih...