CSE Blog - quant, math, computer science puzzles

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

Problem 1: Consider the problem of picking K elements randomly from N elements. Suggest an algorithm. What is the time and space complexity of your algorithm? Problem 2: Now consider that the stream is infinitely long (i.e. N is unknown). Now how do we pick K elements randomly. Update (24 June 2014): Solution: Posted by Himanshu (Prob 1), PlacementIITB2014 (Prob2) and Sid (Prob1 and Prob2) in comments! Thanks claimtoken-52ac74fbddf1e

Source: http://thomer.com/riddles/ Problem: If you have an array with random odd and even numbers, what is the most efficient algorithm you can think of to put all even numbers on one side and all odd numbers on the other side in this array? What is the complexity of your algorithm? Update ( 21 June 2014) Solution posted by nick, Abhishek, Khalil Sawant, Sandeep, Stainless (Ameya Ranade - CSE IITB 2009 Alumnus, Google Engineer, Facebook Engineer), Piyush Sao, Sakshi, Kaushal and Pankaj Jindal in comments! Thanks. 

Source: Solved it during Algorithms Course under Prof Diwan , and discussed with Nikhil Jain (IT BHU 2008 Alumnus, Product Manager at AskLaila) Problem: 1. (Easy)  Consider a n x m rectangular grid. The problem is to find the number of shortest (or monotonic in this case) paths along the edges of the cell that start at (0,0) and end at (n,m). A monotonic path is a path always moving towards the goal, i.e. consists of moving up or right but not down or left. Figure 1 illustrates such a path for a grid of size 5 x 3. 2. (Difficult)  Now we need to print all monotonic paths that do not go above the diagonal y = x. Figure 2 shows such a path. Note that the path in figure 1 goes above the diagonal, hence not desirable in this case. How many such paths exist for n x m grid (n >= m)? Disclaimer: The first problem is too simple, and the second is very challenging. Have fun :-) Solution: Highlight the part between the * symbols for t...

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: Original problem adapted from the "Ants Problem" (Link removed) at "CMU ACM Programming Contest" . Extension to the 4 year old problem on CSE Blog - Walking Ants Puzzle  . Problem also available at  J. Paulson Programming Blog Problem: You have a bunch of ants on a meter stick, each walking 1cm/s in some direction. If an ant hits the end of the stick, it falls off. If two ants collide, they both reverse direction. Walking Ants Puzzle  earlier essentially asked: Given the starting positions and directions of all the ants, how long until the last ant falls off? The new problem is : Given the starting positions and directions of all the ants, which ant(s) are the last to fall off? Disclaimer: I do not have the solution to the problem. It just looks like an interesting problem to solve. ( Readers Please ignore: Technorati claim:  6QVZ8YSY6XSD ) Update (24 June 2014): Solution:  Posted by Strilanc and me in comments!

Source: Asked for a data scientist position at a technology startup in financial services sector in London Problem: What is the optimal algorithm to find the minimum element given a rotated sorted array of integers? A rotated sorted array of integers is the output array of a rotation operation performed on a sorted array. Eg: 3 5 6 1 2 Update (24 June 2014): Solution: Posted by Gaurav Bijay Kumar (CSE IITB 2006, Goldman Sachs Quant, Morgan Stanley Quant, Chicago Booth MBA, Credit Suisse IB, Goldman Sachs Strat), Sandeep, Khalil Sawant, Himanshu, ciddhi and gaurushh.

Source: http://people.csail.mit.edu/bdean/6.046/dp/ Problem:  Given two text strings A of length n and B of length m, you want to transform A into B with a minimum number of operations of the following types: delete a character from A, insert a character into A, or change some character in A into a new character. The minimal number of such operations required to transform A into B is called the edit distance between A and B. Given two strings A and B, what is the path from A to B with minimum edit distance? Solution: Highlight the part between the * symbols for the answer. * This is the classic Levenshtein DP. Let D(i, j) = edit distance between the first i characters of A and the first j characters of B. Then: D(0, j) = j, D(i, 0) = i, and D(i, j) = min of: D(i-1, j-1) + (0 if A[i] = B[j] else 1) (match or substitute) D(i-1, j) + 1 (delete A[i]) D(i, j-1) + 1 (insert B[j]) Fill the (n+1) x (m+1) table row ...

Source: Sent to me by Piyush Sao (EE IITM Alumnus, Georgia Tech Grad Student) Problem: Given a arbitrary binary string of length n, find three evenly spaced ones within the string if they exist. Write an algorithm which solves this in O(n * log(n)) time. Update (29th January 2013): Solution posted by JDGM in comments!

Source:  (Romanian Informatics Olympiad ONI'03, extended team selection) ( ^ Representative diagram of Huffman Encoding. No relevance in the problem) Problem: A telegraph machine can transmit only lines and dots; it takes 2 seconds to transmit a line, but only 1 second to transmit a dot. We generally want to transmit texts containing letters of the English alphabet, and digits (so we have  N<=36  symbols in total). Therefore, a prefix-free encoding using lines and dots is needed. Given the frequencies of the  N  symbols in a large text, find the minimum time it takes to transmit the text using a suitable encoding. The solution should run in  O(N^4)  time, and use  O(N^3)  space. Solution: Highlight the part between the * symbols for the answer. * Official solution (as posted by JDGM from the Olympiad authors): this is Huffman coding with unequal letter costs (dot = 1s, line = 2s), which - unlike the equal-cost case - has no known ...

Source:  Video of a course in Algorithms on Udacity - Asked by Prof. Peter Winkler Problem: A spy in an enemy territory is trying to convey information to her control, but the only means she has for conveying information is that there is a 15-bit radio broadcast every morning, and she has the ability if she wishes to alter 1 bit of that broadcast. But she doesn't know in advance what the broadcast will be. So, this is a case where, potentially, there are 16 different things she can do. There are 15 bits she can alter, or she can choose not to alter any bit, which means that in theory perhaps she could convey as many as 4 bits of information this way. Well, surprisingly, she can actually do that. Repeating the problem to make sure that we understand the setup here. So, I'm a spy, and I'm in enemy territory, and I've got a message --0110-- that I need to transmit to my boss. Now, that's going to be tricky to do, because I don't want anybody to know that I...

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: Asked to me by Piyush Sao (EE IITM 2011 Alumnus, Georgia Tech Grad Student). He got it from IBM Ponder This May 2012 ( http://domino.research.ibm.com/Comm/wwwr_ponder.nsf/Challenges/May2012.html ) Problem: There are six sets of jobs. Each set is performed on a different server and each set contains jobs that take 1,2,3,...,10 minutes to run. Obviously, all six sets would end up in 55 minutes. Schedule all the sets such that if all six servers start together, on minute 0, a job would end on every minute from 1 to 54, and all six servers would end on minute 55 together. Please supply the solution as six lines of ten numbers. A solution for a smaller problem of four sets of six jobs ending every minute from 1 to 20 is: 2 1 5 4 6 3 1 3 6 4 5 2 5 2 4 6 3 1 6 3 4 2 1 5 Update: (19-07-2012) Solution posted by Piyush Sao   (EE IITM 2011 Alumnus, Georgia Tech Grad Student) in comments! I could not solve it. 

Source: Asked to me by Anuj Jain (EE IITB 2010 Graduate, MFE Student at Baruch College NY) Problem: Given an array of n integers, find an algorithm to find triplets in the array such that sum of the three numbers is zero. What is the order of your algorithm? Make sure its quadratic in size of array. :-) Solution: Highlight the part between the * symbols for the answer. * O(n^2) algorithm: sort the array (O(n log n)). For each i from 1 to n, look for a pair (j, k) with i < j < k and a[j] + a[k] = -a[i] using two pointers: set j = i+1, k = n; if a[j] + a[k] equals the target, record the triplet and move both; if the sum is too small, j++; if too big, k--. Each pair-search is O(n) because the pointers only move toward each other, so the total is O(n^2) plus the one-time sort. Correctness: when a[j] + a[k] < target, no k' < k can work with this j (the array is sorted, sums only get smaller), so k is never needed again - and symmetrically for j - so no...

Source: Posted by Algo Muse on contact page . Also posted on Algo Muse (December 2011) http://www.algomuse.appspot.com Problem: Two definitions: 1) Contiguous t-sum problem Given an array A[1..n] and a number t as input, we want to find out if there exists a sub-array whose sum is t. For example, if the following array and t=8 is the input, the answer is YES since it contains the sub-array A[2..4] whose sum is t.  1 4 -1 5 -8 5 -6 3 10 3  2) Distinct-elements problem Given an array A[1..n], find out if all the elements in the array are distinct. Return YES if all the numbers are distinct NO otherwise. Real Problem: Suppose we are given an algorithm that solves the t-sum problem in O(n) time. Design an algorithm that solves the distinct-elements problem in O(n) time. Update (2nd January 2011): Solution: Posted by Yashoteja (CSE IITB Alumnus, Microsoft Research RA) and Pseudonymous in comment. Thanks

Source: Asked to me by Ankush Jain (CSE IITB 2011 Alumnus, Morgan Stanley Quant) Problem: You are given a pointer to a node (not the tail node) in a singly linked list. Delete that node from the linked list. Write code in C. Update (December 13, 2011): Solution posted by Siddhartha in comments! Interesting comment by me in comments!

Source: Problems on Algorithms (Ian Parberry and William Gasarch) Problem:  Let f be a function which takes a number x (number with say n digits, digit i represented by d_i ) as input and outputs sum of the 2001 powers of the digits. So, f(327)=3^2001 + 2^2001 + 7^2001 . Show that for any x , the set { f(x), f(f(x)), f(f(f(x))),.. } is finite. Update (31 January 2011) Solution: Posted by Sudeep Kamath (UC Berkeley PhD Student & EE IITB Alumnus) in comments!

Source: Introduction to Algorithms (by Cormen, Rivest, Leiserson) Problem: Suppose that you are given 'n' red and 'n' blue water jugs, all of different shapes and sizes. All red jugs hold different amounts of water, as do the blue ones. For every red jug, there is a blue jug that holds the same amount of water and vice versa. How can you find the grouping of the jugs into pairs of red and blue jugs that hold the same amount of water, in the minimum number of comparisons. The only operations allowed is compare between a red and a blue jar (no two reds, no two blues) Update (Dec 30, 2010): Problem statement changed a bit to make it more understandable. Solution: Posted by Nikhil Garg (CSE, IIT Delhi third year undergraduate student) and Vivek Chaurasiya (Software Eng Symantec & CSE, IITR Alumnus) in comments! Explained in detail by me in comments!