CSE Blog - quant, math, computer science puzzles

An old classic that still trips people up in interviews. The obvious answer is not the best one. Problem: Four friends have to cross a rickety rope bridge at night with one torch; the bridge holds at most two people and cannot be crossed without the torch. They take 1, 2, 5 and 10 minutes to cross; a pair moves at the slower person's pace, and the torch must be carried back after each crossing. The obvious plan - let the 1-minute guy ferry everyone across - takes 19 minutes. Do better. Solution: Highlight the part between the * symbols for the answer. * 17 minutes. Send the slow pair together: 1 and 2 cross (2), 1 returns (3), 5 and 10 cross (13), 2 returns (15), 1 and 2 cross (17). The two slow walkers must share a trip, else they alone burn 15 minutes, and a fast walker must wait on the far side to return the torch, so 1 and 2 cross first; the rest is forced. *

Source: Alok Goyal (Stellaris VP, Ex-Helion VC) puzzle blog Problem: A fast food restaurant sells dimsums in boxes of 7 and 3. What’s the greatest number of dimsums a person cannot buy. Generalize it for p and q where p and q are relatively prime. I loved the puzzle. Hope you enjoy it too. Solution: Highlight the part between the * symbols for the answer. * Answer: 11 dimsums. In general for coprime box sizes p and q, the largest unattainable number is the Frobenius number pq - p - q. For 7 and 3: 11 = 7a + 3b has no non-negative solution (a = 0: 11 not divisible by 3; a = 1: 4 left, not a multiple of 3). But 12 = 4x3, 13 = 7 + 2x3, 14 = 2x7, and from then on every number is 12, 13 or 14 plus a multiple of 3 - so every n >= 12 is buyable and 11 is the answer. General proof sketch: since gcd(p, q) = 1, the numbers 0, q, 2q, ..., (p-1)q hit every residue class mod p. The smallest representable number in class r is t_r = k_r q for the unique k_r in 0..p-1 with k_r q = r (mod p)...

Problem: There are two maternity hospitals in a town with 50 and 500 beds. Given full occupancy on a particular day, which of these hospitals is more likely to have equal no of boys and girls given probability of boys = probability of girls ? ‪ What would the answer intuitively be by #‎LawOfLargeNumbers‬? You would see #LawOfLargeNumbers does not seem to work here. How should the statement be positioned for #LawOfLargeNumbers to work?  Solution: Highlight the part between the * symbols for the answer. * The SMALLER (50-bed) hospital is more likely to have an exactly equal split. P(exactly 25 boys in 50) = C(50, 25) / 2^50 = 11.2%; P(exactly 250 in 500) = C(500, 250) / 2^500 = 3.6%. The exact-split probability falls like 1/sqrt(pi*n) (Stirling), so it shrinks as the hospital grows. No contradiction with the Law of Large Numbers: the LLN is a statement about PROPORTIONS - P(|boys/n - 1/2| < epsilon) -> 1 for any fixed epsilon - not about hitting exact equality. The f...

Source:  Alok Goyal's Puzzle Page Problem: In a line up of 10 soldiers, what is the least number of soldiers that can be picked in order of either ascending or descending heights? Assume that no two soldiers have the same height. Soldiers can be picked from anywhere in the line, but their order of standing cannot be changed. Solution: Highlight the part between the * symbols for the answer. * Answer: 4. This is the Erdos-Szekeres theorem: any sequence of (a-1)(b-1) + 1 distinct numbers contains an increasing subsequence of length a or a decreasing subsequence of length b. With 10 = 3*3 + 1 soldiers, some monotone subsequence of length 4 always exists. Quick proof: label each soldier with (i, d) = (length of the longest increasing subsequence ending at him, longest decreasing one). If two soldiers got the same label, the taller-later / shorter-later comparison would extend one of the two subsequences - so all labels are distinct. If no monotone subsequence had length 4, all lab...

Source: Asked to me by Ankush Jain (CSE IITB 2011, Morgan Stanley Quant Associate). He took it from Algorithms Design book by Tardos and Kleinberg Problem: Easy case: You’re trying to buy equipments whose costs are   appreciating. Item i appreciates at a rate of r_i  > 1 per month, starting from  $100, so if you buy it t months from now you will pay 100*((r_i)^t) .  If you can only buy one item per month, what is the optimal order in which to  buy them? Difficult case: You’re trying to sell equipments whose costs are depreciating . Item  i  depreciates at a rate of  r_i  < 1 per month, starting from  $100, so if you sell it  t  months from now you will get  100*((r_i)^t) .  If you can only sell one item per month, what is the optimal order in which to sell  them? Solution: Highlight the part between the * symbols for the answer. * Buying (appreciating, r_i > 1):...

Source: Asked to me by a friend - who was asked this question in an interview at Facebook Problem: Given n points on a 2D plane, find the equation of the line with maximum number of collinear points. What is the time complexity of your algorithm? Solution: Highlight the part between the * symbols for the answer. * O(n^2) algorithm: the optimal line passes through at least two of the points (otherwise rotate/translate it until it does without losing collinear points). So for each point p, compute the slope from p to every other point and tally frequencies in a hash map (use exact rational slopes dy/dx reduced by gcd, plus a sentinel for vertical lines - avoid floating point). The most frequent slope from p, plus p itself, gives the best line through p. Take the maximum over all p. Complexity: n points x O(n) slope computations and hash updates = O(n^2) expected time, O(n) space per round. (Deterministic O(n^2 log n) via sorting slopes instead of hashing.) This is worst-...

Source: Australian Mathematical Society Gazette Puzzle Corner 34 Problem:  Begin with n integers x1, . . . , xn around a circle. At each turn, simultaneously replace all of them by the absolute differences Repeat this process until every number is 0, then stop. Prove that this process always terminates if and only if n is a power of 2. Shameless plug: Follow CSE Blog on CSE Blog - Twitter and CSE Blog on Quora . :-) Solution: Highlight the part between the * symbols for the answer. * These are Ducci sequences; the answer is driven by arithmetic mod 2. Step 1 (mod 2): over GF(2), absolute difference is just addition: x_i -> x_i + x_(i+1). After k steps the entries are given by binomial coefficients of (1+z)^k around the cycle. If n = 2^m, then (1+z)^n = 1 + z^n (mod 2), and around a cycle of length n, z^n = 1 - so after n steps every entry becomes x_i + x_i = 0: all even numbers. If n is not a power of 2, write n = 2^m * k with k odd > 1: the 3-cycle (0,1...

Source: Australian Mathematical Society Gazette Puzzle Corner 35 Problem: There are some weights on the two sides of a balance scale. The mass of each weight is an integer number of grams, but no two weights on the same side of the scale share the same mass. At the moment, the scale is perfectly balanced, with each side weighing a total of W grams. Suppose W is less than the number of weights on the left multiplied by the number of weights on the right. Is it always true that we can remove some, but not all, of the weights from each side and still keep the two sides balanced? Solution: Highlight the part between the * symbols for the answer. * Yes - in fact something stronger holds: some single weight sits on BOTH pans, so removing that one weight from each side keeps the balance. Proof (Govind's): let the left pan hold m weights a_1 < ... < a_m and the right pan n weights b_1 < ... < b_n, with both sums equal to W < mn. Suppose no weight value appears on both ...

Source: AUSTMS Puzzle Corner 35 Problem: Call a nine-digit number flawless if it has all the digits from 1 to 9 in some order. An unordered pair of flawless numbers is called harmonious if they sum to 987654321. Note that (a, b) and (b, a) are considered to be the same unordered pair. Without resorting to an exhaustive search, prove that the number of harmonious pairs is odd. Update (23 Oct 2014): Solution: Posted by me (Pratik Poddar) in comments!

Source:  Asked to me on quora (  cseblog.quora.com ) Problem: Given an array of n positive numbers (n ~ 100000), what is the algorithmic approach to find the minimum possible sum (>=0) by using all the numbers in an array? Example 1: 1 2 2 3 4 Answer : 0 (-1+2-2-3+4) Example 2: 2 3 4 7 13 Answer: 1 (+2-3-4-7+13) Solution: Highlight the part between the * symbols for the answer. * This is the partition problem: assigning +/- signs to use all numbers means splitting them into two groups; the minimum |sum| = S - 2T where S is the total and T is the largest subset sum not exceeding S/2. Algorithm: subset-sum DP. Compute reachable sums up to floor(S/2) with a bitset: start with bit 0 set, and for each number x shift the bitset left by x and OR it in. The highest set bit T <= S/2 gives the answer S - 2T. Time O(n * S / 64) with bitset words, O(S) memory - fine when the values are bounded (the problem is NP-hard in general, so no algorithm polynomial in n alone e...

Source:  Shared by Alok Mittal (Cannan Partners) Problem: A 3x3 tic tac toe has 8 "winning lines" (3 horizontal, 3 vertical and 2 diagonals). How many "winning lines" does the 3x3x3 3D tictactoe have? There is a brute force solution, and then there is the aha! solution. Update (23 Oct 2014) Solution:  Posted in comments by Anti, Taz, Javier, Shubham Gupta, Leela. Detailed solution and much more advanced problems in the document  http://library.msri.org/books/Book42/files/golomb.pdf

Problem / Observation: The friendship paradox is the phenomenon first observed by the sociologist Scott L. Feld in 1991 that most people have fewer friends than their friends have, on average. Prove it mathematically. Update (23 Oct 2014): Solution:  Posted by Mike Earnest and Taz in comments!

Source:  The super awesome puzzle blog by Gowtham Kumar  -  Puzzle Tweeter - Coin Problem  who got it from  Wolfram Mathematica Problem: Suppose you have an infinite stock of $a bills and $b bills such that g.c.d(a,b)=1. Find the largest amount of money (integer) that cannot be represented using $a and $b denominations. Shameless plug: If you have not done it already, please like / +1 / follow on:  Quora ,  Twitter ,  Facebook ,  G+ Update (21 June 2014): Solution: Posted by Raunak Kudesia, Sid Hollander and me (Pratik) in comments!

Source: Mailed by Sudeep Kamath (EECS PhD Student, UC Berkeley, EE IITB 2008 Alumnus) Problem: A is a 300 x 300 matrix with 17 on the diagonal, and the rest of the entries being 11. What is det (A) ? Update: (21 June 2014): Solution posted by Gowtham R (Stanford), Justin Rising, Pavan Bharadwaj, Hansaplatz and gaurushh in comments! Thanks

Source: IBM Ponder This Dec 12 ( http://domino.research.ibm.com/comm/wwwr_ponder.nsf/challenges/December2012.html ) - Mailed to me by Aashay Harlalka (Final Year Student, CSE, IITB) Problem: 36 people live in a 6x6 grid, and each one of them lives in a separate square of the grid. Each resident's neighbors are those who live in the squares that have a common edge with that resident's square. Each resident of the grid is assigned a natural number N, such that if a person receives some N>1, then he or she must also have neighbors that have been assigned all of the numbers 1,2,...,N-1. Find a configuration of the 36 neighbors where the sum of their numbers is at least 90. As an example, the highest sum we can get in a 3x3 grid is 20: 1 2 1 4 3 4 2 1 2 Update (24 June 2014): Solution:  Available on  IBM Research Ponder This - December 2012 Solution

Source: Mailed to me by Vashist Avadhanula (PhD Student at Columbia Business School, EE IITB 2013 Alumnus) Problem: Consider a case where you flip two fair coins at once (sample space is HH, HT, TH & TT) you repeat this experiment many times and note down the outputs as a sequence. What is the expected number of flips (one flip includes tossing of two coins) to arrive at the sequence HHTHHTT. Solution: Highlight the part between the * symbols for the answer. * Answer: 2^14 / 255 = 64 + 64/255 = 64.251 flips (each flip = both coins tossed together). Why it is not just 2^7/2 = 64 or 2^6 = 64: the 7-bit target HHTHHTT is not aligned to the coin-pair boundaries, and a flip is consumed even when the pattern completes on its first coin. Model it as a Markov chain on the longest suffix of the bit stream matching a prefix of HHTHHTT (7 transient states + absorbing). Each flip moves two bits at once; solving the 7 linear equations E_s = 1 + (1/4) * sum over the four two-bit outcome...

Source: Mailed to me by Smriti Mittal (Final year student, IIT Bombay) Problem: Green numbers indicate how many pieces could move to that square on the next move. Blue squares show the possible locations of the following five different chess pieces: King Queen Rook Bishop Knight How are the five pieces arranged? Lets mark the squares as (r,c) where r is the row number and c is the column number. So, the squares where the pieces are to be kept are: (1,1), (1,8), (5,8), (6,3), (8,2) Solution: Highlight the part between the * symbols for the answer. * The unique arrangement: (1,1) Knight, (1,8) Queen, (5,8) Rook, (6,3) King, (8,2) Bishop. Check against the green numbers: (1,2) and (1,6) are each attacked exactly once - by the queen along row 1 (the knight at (1,1) does not reach them). (4,5) is attacked once - by the queen on the long diagonal (1,8)-(5,4). (4,6) is attacked once - by the bishop on the diagonal (8,2)-(4,6). (3,3) is attacked by nobody. Every other candi...

Source: Posted by JDGM (James Miles) in comments on http://www.puzzletweeter.com ( A fanstastic blog by Gowtham Kumar , PhD Student, Stanford, IITM Alumnus) Problem: Prove that from the numbers 1 to 200 we cannot pick 101 of them such that none divide any other. Update (24 June 2014): Solution: Posted by Suman Datta, Stainless (Ameya Ranade, CSE IITB 2009 Alumnus, Microsoft, Google, Facebook Engineer) and Wei Chen in comments!

Source: Asked in an Amazon interview to a friend Problem: Given an array of size n , x[0 .. n-1] of integers sorted into ascending order with no duplicates, find an array item that is also its index, so that x[i] = i . For example, x[3] = 3 in the array shown below: i           0 1 2 3 4 5 x[i]     -3 0 1 3 5 7 Your task is to write a program that finds i . Disclaimer: Yes, its a very easy problem, as far as algorithm is concerned. Its here for people preparing for interviews to see if they can write code. Solution: Highlight the part between the * symbols for the answer. * Binary search in O(log n). Because the array is sorted with no duplicates, f(i) = x[i] - i is non-decreasing (x[i+1] >= x[i] + 1, so f(i+1) >= f(i)). So probe the middle index mid: - if x[mid] = mid, done; - if x[mid] > mid, then for every j > mid, x[j] >= x[mid] + (j - mid) > j - no fixed point to the right, go left; - if x[mid] < mid, symmetr...

Source: Asked for a data scientist position at a technology startup in financial services sector in London Problem: Given python code to calculate maximum in an array of integers x def find_max(x):          max_num = x[0]          for i in x[1:]:         if i > max_num:             max_num = i   << Expected number of times this expression  was evaluated     return max_num Calculate the expected number of times the expression max_num = i was evaluated, given that array x was taken from a uniform random distribution. Solution: Highlight the part between the * symbols for the answer. * Answer: H_n - 1 = 1/2 + 1/3 + ... + 1/n, which is about ln(n) - 1 + gamma (roughly log n updates). Reason: the line max_num = i executes on iteration i exactly when the i-th element is the largest of the first i elements. For i.i.d. draws (with ties having pr...