This was the killer one. Interesting problem asked to me in one of the interviews.
You are given a black-box which returns a random number between 0 and 1. Give an algorithm to generate a point in the circle of radius 1.
(I was able to solve this but I must admit, its a difficult problem)
Update (December 10 2009) : To make things concrete: The black-box here returns a random number "uniformly" between 0 and 1. The question is to find a point "uniformly" in a unit circle. This would mean that the probability that a random point in the circle lies in a smaller concentric circle of radius r (r<1) is r^2. Solution by Jaadu in comments!!