My Most Interesting Interview Problem
austinrochford.com
My Most Interesting Interview Problem
1–10 of 56 posts
Re: My Most Interesting Interview Problem
#2For the interested, the easieat way of generating random points on a circle is drawing (x,y) component-wise from a normal distribution and then normalizing the vector. (And two independent Gaussian variables can be easily sampled using the Box-Muller transformation.)
Re: My Most Interesting Interview Problem
#3For the interested, the easieat way of generating random points on a circle is drawing (x,y) component-wise from a normal distribution and then normalizing the vector. (And two independent Gaussian variables can be easily sampled using the Box-Muller transformation.)
I'd rather take a random uniform distribution from 0 to pi and take it as the arc-length.
Why is your construction 'uniform' on the circle?
Re: My Most Interesting Interview Problem
#4For the interested, the easieat way of generating random points on a circle is drawing (x,y) component-wise from a normal distribution and then normalizing the vector. (And two independent Gaussian variables can be easily sampled using the Box-Muller transformation.)
I'd rather take a random uniform distribution from 0 to pi and take it as the arc-length. Why is your construction 'uniform' on the circle?
> Why is your construction 'uniform' on the circle?
> I'd rather take a random uniform distribution
> from 0 to pi and take it as the arc-length.
How would you generate points distributed uniformly on the surface of a three dimensional ball?
Re: My Most Interesting Interview Problem
#5For the interested, the easieat way of generating random points on a circle is drawing (x,y) component-wise from a normal distribution and then normalizing the vector. (And two independent Gaussian variables can be easily sampled using the Box-Muller transformation.)
I'd rather take a random uniform distribution from 0 to pi and take it as the arc-length. Why is your construction 'uniform' on the circle?
Maybe I was too fast saying "easiest", arc-length works as well. My approach generalizes to arbitrary dimension though.
As for why it's uniform, recall that when X and Y are independent, then P(X and Y) = P(x)P(Y) ~ e^{-x^2-y^2} = e^{-r^2}, which is independent of the angle.
Re: My Most Interesting Interview Problem
#6For the interested, the easieat way of generating random points on a circle is drawing (x,y) component-wise from a normal distribution and then normalizing the vector. (And two independent Gaussian variables can be easily sampled using the Box-Muller transformation.)
How do you prove than the component-wise normal distributions, once normalized, become uniform on the circle?
UPDATE - OK, got it in some comments that were posted while I was posting this one!
Re: My Most Interesting Interview Problem
#7Earlier quoted context omitted.
I'd rather take a random uniform distribution from 0 to pi and take it as the arc-length. Why is your construction 'uniform' on the circle?
> Why is your construction 'uniform' on the circle? That's a very good question, and the sort of thing that would need to be in a comment somewhere. The answer is that the bi-normal distribution is rotationally symmetrical, a fact that is not immediately obvious. > I'd rather take a random uniform distribution > from 0 to pi and take it as the arc-length. That's a good solution for the simple one-dimensional circle i…
Poster here, I actually had considered adding both of these methods to the end of the post, but decided to keep it focused on the problem itself.
edit
Maybe I'll write about them in a follow-up post.
Re: My Most Interesting Interview Problem
#8Earlier quoted context omitted.
I'd rather take a random uniform distribution from 0 to pi and take it as the arc-length. Why is your construction 'uniform' on the circle?
> Why is your construction 'uniform' on the circle? That's a very good question, and the sort of thing that would need to be in a comment somewhere. The answer is that the bi-normal distribution is rotationally symmetrical, a fact that is not immediately obvious. > I'd rather take a random uniform distribution > from 0 to pi and take it as the arc-length. That's a good solution for the simple one-dimensional circle i…
Yes, I see and understand. Thanks for the info.
It is obvious if you think of it (exp(x1^2+...+xn^2) is symmetric on all the variables). Yep, understood.
Re: My Most Interesting Interview Problem
#9Earlier quoted context omitted.
I'd rather take a random uniform distribution from 0 to pi and take it as the arc-length. Why is your construction 'uniform' on the circle?
> Why is your construction 'uniform' on the circle? That's a very good question, and the sort of thing that would need to be in a comment somewhere. The answer is that the bi-normal distribution is rotationally symmetrical, a fact that is not immediately obvious. > I'd rather take a random uniform distribution > from 0 to pi and take it as the arc-length. That's a good solution for the simple one-dimensional circle i…
For a ball, can't I just randomly generate two angles (0-2pi)?
Re: My Most Interesting Interview Problem
#10For a general-purpose developer interview question, I think this relies a little too heavily on domain-specific knowledge to be generally useful.
Personally, while I was quite decent at algebra and geometry in university, my skills have atrophied significantly, to the extent that I really didn't know where to start with this problem. I don't think it represents what most programmers do on a day-to-day basis, and someone with a strong math background would probably be far more capable of answering this, despite not necessarily being a better developer.
If this sort of thing represents what developers at your company would likely be doing on a daily basis, I think it could be a relevant question. Otherwise, I think a question like this is very likely to inadvertently screen out good developers.