Posts

Showing posts from October, 2011

Sphagetti Breakfast

Image
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)

Distinct numbers in a sample draw

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!



Function Inner Product

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.