CSE Blog - quant, math, computer science puzzles

Source: Quant interview at Religare Technova Problem: Write a C program to compare two integers without using relational operators (== != < <= > >=)   Solution: Highlight the part between the * symbols for the answer. * Idea: subtract and inspect the sign without any relational operator. Equality: a == b iff (a ^ b) == 0, i.e. use if (!(a ^ b)). Greater/less: with 64-bit ints, d = a - b; the sign bit of d tells the answer: ((uint64_t)(a - b)) >> 63 is 1 iff a < b (Sanjoy's version). Equivalently, without shifts: if (d - abs(d)) is nonzero, d was negative so b > a; otherwise a > b (NG's version). A branch-free max uses the same sign trick: max = a - ((a - b) & ((a - b) >> 63)) for 64-bit ints. (Caveats from the thread: watch out for integer overflow in a - b, and abs() itself is usually implemented with a comparison - the sign-bit version avoids that.) Solution by Sanjoy and NG from the 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:  Mailed to me by Sudeep Kamath  (EECS PhD Student, UC Berkeley, EE IITB 2008 Alumnus), Taken from Anand Sarwate (Postdoc at UC San Diego, PhD from UC Berkeley) Problem: Given a permutation p of length n , let c(p)  be the number of cycles in p . Suppose p is drawn uniformly from the set of all permutations. Show that Expectation of 2 raised to the power of number of cycles is n+1 , i.e E[ 2^c(p) ]= (n+1) Hint: 1) There is no high funda group theory/number theory involved. I could solve this in 15 minutes \m/ \m/ 2) After you are done, you might want to read this  (*Spoiler Alert*) Solution: Hint posted by Nikhil Garg (CSE, IIT Delhi third year undergraduate student) in comments! Solution posted by Kalyan in comments! Kalyan's comment explained in detail by me in comments! A simpler solution posted by Gaurav Sinha (chera) (CSE IITK 1996 Alumnus, Indian Revenue Service) in comments!

Source: CMU Puzzle Toad Problem: Farmer Brown is standing in the middle of his perfectly circular field feeling very content. It is midnight and there is no moon and unknown to the farmer, Martian zoologists are landing randomly at points on the circumference of his field. They land at one minute intervals, starting at midnight. As soon as there are martians at points A,B,C such that triangle ABC contains the center of the field, Farmer Brown will be teleported to the waiting space-ship and transported to spend the rest of his life as an exhibit in a Martian zoo. What is the expected time until he is abducted? Related Problem: http://pratikpoddarcse.blogspot.com/2009/10/semi-circle-covering-n-points-puzzle.html Solution: Posted on CMU Puzzle Toad ( http://www.cs.cmu.edu/puzzle/solution33.pdf ). Check my name in the acknowledgments \m/ \m/

Source: www.quantstudy.com Problem: Let A and B be two cities, with two different roads connecting them. Suppose that two cars can travel from A to B on different roads, keeping a distance that does not exceed 1 mile between them.  Is it possible for two cars to travel one from A to B, the other from B to A such that the distance between them is always greater than one mile? Update: (23 January 2011) Solution: Posted by Gaurav Sinha (chera) (CSE IITK 1996 Graduate, Now working at Indian Revenue Service) in comments! A more general solution with clear explanation posted by Ameya Ranade (Microsoft Software Engineer, CSE IITB 2009 Graduate)

Source: Asked to me by Piyush (Third year Undergraduate Student, CSE, IITD) Problem: There is a big line of people waiting outside a theater for buying tickets. The theater owner comes out and announces that the first person to have a birthday same as someone standing before him in the line gets a free ticket. Where will you stand to maximize your chance. Solution: Solution posted by me in comments!

Source: http://deltaepsilons.wordpress.com/ Problem: Consider a set of n objects from which m are drawn randomly at a time, with replacement.  What is E(n,m), the expected number of draws I have to make to have drawn all of the objects? Note that we solved a similar problem and got the value of E(n,1) some time back in this problem . Solution: Highlight the part between the * symbols for the answer. * E(n,m) = sum_{j=1}^{n} (-1)^(j+1) . C(n,j) / (1 - C(n-j,m)/C(n,m)), where C(n-j,m) = 0 when n-j Derivation (inclusion-exclusion). Let T be the number of draws needed. For a fixed set J of j objects, the chance that none of them appears in t independent draws is r_j^t with r_j = C(n-j,m)/C(n,m). So by inclusion-exclusion P(all n seen within t draws) = sum_{j=0}^{n} (-1)^j C(n,j) r_j^t, hence P(T > t) = sum_{j=1}^{n} (-1)^(j+1) C(n,j) r_j^t. Now E[T] = sum_{t=0}^{inf} P(T > t), and summing each geometric series gives the formula. Sanity checks. For m = 1, r_j = (n-j)/n and E = n...