CSE Blog - quant, math, computer science puzzles

Source: Asked to me by Suman Kalyan Bera (M.Tech  Student IIT Delhi) on contact page Problem: How many digits does the number 125^100 have? Very interesting problem and equally interesting solution :) Update (25 December 2011): You are not allowed to use your high school notes on values of log_10(2) or log_10(5) Solution: Posted by me in comments!

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: Quantnet Interview Questions Problem: If a car passes at the crosswalk on average every 10 seconds and you need 20 seconds to pass the road, how long does it take you on average to cross the road? Note that since the problem is not very well specified, make reasonable assumptions to solve it. It would be fun if before solving mathematically, you try and guess a time estimate. :-) Update (3rd January 2011): Solution posted by Santosh Ananthakrishnan (EE Final Year DD Student IIT Bombay) and Animesh Saxena (Manager at Karvy Private Wealth) in comments!

Source: Asked to me by Dinesh Krithivasan (IITM Alumnus, Phd University of Michigan, Senior Qualcomm Engineer) Finally a geometry problem for the blog. :) Thanks Dinesh! :) Problem : We have an equilateral triangle ABC of unit side length. We want to find a curve C of the smallest length that cuts this triangle into 2 halves of equal area. Obviously, the altitude of length sqrt(3)/2 will do the job but can we do better? Note that there is no other restriction on C - it need not pass through any of the triangle vertices for instance.

Source : Algo Muse, CSE, IIT Bombay Problem : An entry  a ij  in a matrix is called a  saddle point  if it is strictly greater than all the entries in the  i th row and strictly lesser than all entries in the  j th column or vice-versa. For example, the matrix shown below has two saddle points. What is the maximum number of saddle points an  n x n  matrix can have?  Update (December 14, 2011): Due to some reason I do not know of, the problem is not there on the Algo Muse website anymore. :P  Solution posted by Panna, Gold and Iron (Nikhil Pandey, CSE IITB 2009 Alumnus), Prasham Rambhia (Aero IITB Fifth Year Undergraduate Student, To be Morgan Stanley Quant) and Insomniac in comments!

Source: Asked to me by Piyush Goyal (CSE IITD Senior Undergraduate, To be Goldman Sachs Quant) Problem: Given a Rubik's Cube, find a path from centre of face to centre of cube going via each cell of cube only once. Hint: Its not possible. Try to prove it. Cheers! Update (Dec 11, 2011): Solution: Posted in comments by: Ankush Agarwal (Senior Undergraduate, CSE, IITB), Prasham (Senior Undergraduate, Aero, IITB & To be Morgan Stanley Quant), Piyush Sao (EE IITM Alumnus, Georgia Tech Grad Student), Siddhartha, Rudradev Basak (Senior Undergraduate, CSE, IITD), Yashoteja (CSE IITB Alumnus, Microsoft Research RA), Kashyap (IITM),  Gaurav Sinha (chera, IITK 1996 Graduate, Indian Revenue Service). 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!