CSE Blog - quant, math, computer science puzzles

Source: Very standard problem in Quant interviews (Taken from quantnet, xkcd forums) Problem: A bowl of spaghetti contains n strands. Thor picks two ends at random and joins them together. He does this until no ends remain. What is the a) expected number of spaghetti loops in the bowl? b) expected average length of the loops? (in strands) c) expected number of k -hoops? ( a k -hoop is a loop made from k strands) Solution: Highlight the part between the * symbols for the answer. * a) Expected number of loops = 1 + 1/3 + 1/5 + ... + 1/(2n-1) (the sum of the first n odd reciprocals, about (ln n)/2 + ln 2 + gamma/2). When m strands (2m ends) remain, pick any end: the other end you join it to is uniformly one of the 2m - 1 remaining ends, and exactly one of those closes a loop. So a loop is created with probability 1/(2m-1) at that step, and summing the indicators over m = n, n-1, ..., 1 gives the answer (NG's recurrence; Rudradev Basak's generating funct...

Source: Asked to me by Chinmay Chouhan, Junior Undergraduate, CSE IITB Problem: Given the set of numbers from 1 to n : { 1, 2, 3 .. n } We draw n numbers randomly (with uniform distribution) from this set (with replacement). What is the expected number of distinct values that we would draw? Update (Oct 30, 2011): Solution posted by Yashoteja Prabhu (RA at Microsoft Research, IITB CSE 2011 Alumnus), Garvit Juniwal (IITB CSE Senior Undergraduate), Dinesh Krithivasan (IITM Alumnus, Phd University of Michigan, Senior Qualcomm Engineer), Nikhil Garg (IITD CSE Senior Undergraduate) and Avinash in comments!

Source: A linear algebra problem book Problem: Find the function f   ( member of span {1, sin x, cos x} ) that minimizes norm of ( sin 2x − f(x) ), where the norm comes from the inner product < f , g > = integral over x from -pi to pi [ f(x)g(x) ] Update (Oct 30, 2011): Solution posted by Harsh Pareek (Graduate Student at UT Austin, CSE IITB 2011 Alumnus) in comments.

Source: http://stackoverflow.com/ Problem: Consider these two function definitions void foo (){ ... } void foo ( void ){ ..... } What is the difference between these two functions? Hint: The answer depends whether this is C code or C++ code. Solution: Highlight the part between the * symbols for the answer. * In C++ there is no difference: both declare a function taking no arguments. In C they differ. void foo(void) declares a function taking no arguments - calling foo(42) is a compile error. void foo() declares a function with an unspecified (unprototyped) parameter list: the compiler accepts calls with any arguments, e.g. foo(66) compiles fine and the argument is simply ignored. So in C, foo() means "parameters not specified", not "no parameters". (Note: in a *definition*, void foo(){...} defines a no-argument function, but calls to it are still unchecked without a prototype; writing (void) is the correct habit in C.) Solution by DETERMINANT from th...

Source: http://www.gowrikumar.com Problem: The following C program segfaults of IA-64, but works fine on IA-32. int main () { int * p ; p = ( int * ) malloc ( sizeof ( int )); * p = 10 ; return 0 ; }   Update (Oct 30, 2011): Wrong problem. Sorry for the trouble.

Source: http://www.gowrikumar.com Problem: What is the output of the following C++ code? #include <stdio.h> #define f ( a , b ) a ## b #define g ( a ) # a #define h ( a ) g ( a ) int main () { printf ( " %s \n " , h ( f ( 1 , 2 ))); printf ( " %s \n " , g ( f ( 1 , 2 ))); return 0 ; } Update (14 Sept 2011): Solution posted in comments by Prathmesh Prabhu (CSE IITB 2010 Alumnus and Wisonsin Madison II-year Graduate Student)

Source: Asked to me by Amol Sahasrabudhe (IITB 2004 Alumnus, Worked at Morgan Stanley Quant Division, Deutsche Bank) Problem: You are given 2n numbers ( 1 to n and 1 to n ). You have to arrange these numbers in a sequence such that between any two i `s , there exists exactly i-1 numbers. Is it possible for all n ? If no, what are the values of n for which this is possible? Disclaimer: I have not been able to solve it. Sudhanshu Tungare (IITB 2008 EE Alumnus, Morgan Stanley) claims to have a solution. Cheers! Update (November 1, 2011): Part solution posted by Nishant Totla (CSE IITB Senior Undergraduate), Richie and Sarat in comments! Complete solution posted by Siddhant Agarwal (EE IITB Alumnus, CMI Grad student) in comments! Thanks a ton.