Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

My Most Interesting Interview Problem

austinrochford.com

Post reply on HN
Print view View original

11–20 of 56 posts

Re: My Most Interesting Interview Problem

#11

Post by mturmon »

quchen wrote: post #2

For 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 have to disagree with this. It would easier conceptually and faster computationally to use rejection sampling:

  do {
    x = uniform()
    y = uniform()
    r = x*x + y*y
  } while (r > 1)
  x = x/sqrt(r)
  y = y/sqrt(r)
This does generalize to higher dimensions d, although as d gets large, you waste more samples. For spheres embedded in a handful of dimensions, it would still be fine, and it avoids all the transcendental functions associated with Normal variates. It's due to Marsaglia (1972).

Re: My Most Interesting Interview Problem

#12

Post by ColinWright »

gibybo wrote: post #9
ColinWright wrote: post #4

Earlier quoted context omitted.

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

  > For a ball, can't I just randomly generate
  > two angles (0-2pi)?
Why would that be uniformly distributed?

Re: My Most Interesting Interview Problem

#13

Post by ColinWright »

mturmon wrote: post #11
quchen wrote: post #2

For 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 have to disagree with this. It would easier conceptually and faster computationally to use rejection sampling: do { x = uniform() y = uniform() r = x*x + y*y } while (r > 1) x = x/sqrt(r) y = y/sqrt(r) This does generalize to higher dimensions d, although as d gets large, you waste more samples. For spheres embedded in a handful of dimensions, it would still be fine, and it avoids all the transcendental functions a…

It's simple, clean, clear, and works well in low dimensions. I regularly work in a few thousand dimensions, and it doesn't work at all because the volume of the sphere is too small.

These are great discussions to have with a candidate. If they already know these things then you can see if they understand why, and if they don't already know these things, you can see how they react to learning new and rather esoteric stuff that turns out to be useful.

Re: My Most Interesting Interview Problem

#14

Post by mturmon »

gibybo wrote: post #9
ColinWright wrote: post #4

Earlier quoted context omitted.

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

No, because the two angles can't easily be combined to make the resulting point uniform on the sphere.

For instance, if you call one of the angles "latitude", and one "longitude", then you will get too many samples near the poles -- think about how the lines of constant longitude start out widely spaced on the equator, but then converge at the poles. This would cause points to pile up at the poles.

Your proposal hits on the nub of why this problem is hard. It is, in general, hard to generate a bunch of non-independent random variables with a prescribed distribution. In this case, it's the angles that are not independent.

Re: My Most Interesting Interview Problem

#16

Post by [deleted] »

ColinWright wrote: post #4
pfortuny wrote: post #3

Earlier 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…

[deleted]

Re: My Most Interesting Interview Problem

#17

Post by MidsizeBlowfish »

ryanbrunner wrote: post #10

For 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 some…

Certainly. This interview was for a data-oriented position.

Re: My Most Interesting Interview Problem

#18

Post by cmsmith »

quchen wrote: post #2

For 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.)

Alternatively, just use the method in the article (scale the uniform random distribution) and if your point is more than 1u away from the origin then throw it out and try again.

You would throw out 36% of the points, but you might get that back from not using trig functions.

Re: My Most Interesting Interview Problem

#19

Post by ronaldx »

quchen wrote: post #2

For 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.)

or generate a (uniform) random direction from the centre of the circle.

Re: My Most Interesting Interview Problem

#20

Post by gibybo »

mturmon wrote: post #14
gibybo wrote: post #9

Earlier quoted context omitted.

For a ball, can't I just randomly generate two angles (0-2pi)?

No, because the two angles can't easily be combined to make the resulting point uniform on the sphere. For instance, if you call one of the angles "latitude", and one "longitude", then you will get too many samples near the poles -- think about how the lines of constant longitude start out widely spaced on the equator, but then converge at the poles. This would cause points to pile up at the poles. Your proposal hits…

Ah, of course, thanks.
Post reply on HN