Posts

Scheduling Problem

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. 

Original Puzzle: Pattern Lock - Combinatorics Puzzle - Number of Possible Passwords

Source: Discussion with Ankush Jain (CSE IITB 2011 Alumnus, Morgan Stanley Analyst) a few months back. Discussion revived by Sangram Raje (CSE IITB 2008 Alumnus, Tower Research Analyst) today. Problem: Ever seen a pattern lock in Galaxy S2? Password is a series of connected line strokes. How many possible password combinations can you have? Some description about the problem: 1) Assuming the dots on the screen are like (1, 2, 3 in the first row), (4, 5, 6 in the second row) and (7, 8, 9 in the third row), you cannot go to 8 from 2, without going through 5. So, a password like * * 8 2 * * is not possible. 2) You cannot move over two lines twice  You can move to a used point, but you cannot move to another used point from a used point I do not see a simple way to solve this. But even coding this looks very difficult to me. Any takers? Update :  (19-07-2012) This is essentially an open ended question

Maxima Property Subset

Source: Asked to me by  Santosh Ananthakrishnan (EE IITB Fifth year undergraduate, To be Worldquant Analyst) Problem: At most, how many subsets can you find of the set A = {1, 2, ..., n} such that any two intersect in exactly one element?

Lion in a Circular Cage Puzzle

Source: Asked to me by Pramod Ganapathi (PhD Student at Stony Brook University) Problem: A lion and a lion tamer are enclosed within a circular cage. If they move at the same speed but are both restricted by the cage, can the lion catch the lion tamer? (Represent the cage by a circle, and the lion and lion tamer as two point masses within it.)

Algorithm Puzzle: Triplets in Array

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

Original Problem : ATM Money Withdrawal Puzzle

Source: One of the very few original problems on the blog. Remember ' Mathematics of Housie '? Please share if you like! Problem: Assumptions: a) I have infinite money in my account b) The daily limit of amount of money that can be withdrawn from an ATM is finite c) You can login into an ATM Machine only once a day d) If you login into the machine and enter a large number to withdraw, you will not get anything. And hence, you will not be able to withdraw anything from the ATM for the day. e) I do not know what the daily limit is. What strategy should I choose so that I can withdraw N rupees in minimum number of days? Of course, you can do it in N days (withdrawing only one rupee daily) you could do it in N-limit + ceiling(N/limit)-1 days (check N, check N-1, .. check limit. Once you know the limit, and you have already withdrawn 'limit' rupees, you will take ceiling ((N-limit)/limit) days more. Can you do better? Update: (19-07-2012) This is e...

Lazy Walking Strategy Puzzle

Source: Quantnet Interview Questions Problem: You are standing on the middle of a East-West street. A row of closed doors in front of you, and you have a key on hand which can only open one specific door. Compose a strategy so that X/N is least under the worst situation. X is the distance you covered when arriving at the correct door. N is the distance between the door and the original point.