My Most Interesting Interview Problem | Hacker News Reader

My Most Interesting Interview Problem

austinrochford.com

in clear probability related context, the guy uses "uniformly distributed" and "normally distributed" interchangeably. I usually fail interview with such guys.

The most recent spectacular failure happened when interviewer asked about sets, i described Java Set interface as an example (they are Java shop so i thought the choice was right), looking dissatisfied he asked to talk about "sets" in general, and got, lets say, really confused, when i tried to elicit whether he means naive set theory - seeing that i didn't hit what he wanted, i offered along the lines of Russel's theory of types, ... the guy got almost angry and said "just sets in general", and i kind of supposed that we settled on naive, though it sounded like he didn't like "naive"... he asked what we can do with a set, like for example iterate over its elements, i noted that that of course depends on the set's cardinality ... by look on his face at that moment it was really clear that the interview is finished.

It's not a good idea in an interview to antagonize your victims like this. The goal is to find out what they know, not be a forum for you to show off what you know. This is a very common mistake by interviewers.

I was saying it as the one being interviewed. I conduct interviews differently, in particular never give small problems, and mostly i just drill down various items on their resume (sometimes in the areas lesser known to me, so i'd learn something from the interview :) in the direction what they did, how, what alternatives were considered and why that specific design/approach was chosen over the alternatives, etc...

Sounds like the parent comment was the interviewee, not interviewer.

Ooops, that was a typo, thanks for catching it!

This was almost painful to read, mostly because I've been through the same kind of interview many times. It is also amusing that another comment here is assuming that you were the interviewer in this example, when you were actually the interviewee.

The depressing thing is that this interviewer probably went back to HR (if the company even had an HR department) and told them that you didn't know anything about basic sets (whatever that means).

The interviewer's line of questioning amounted to guess what number I'm thinking of that is between 1 and 100.

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

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

Completely agree. While I feel I could probably figure it out given time, in an interview setting I would test badly at this question. Does that mean I'm a terrible developer? I don't think so.

Interviews are tricky to get right. It's my opinion that interviews should aim to prove that the candidate knows enough to do the day-to-day work, plus test for good personality fit etc. After that, there should be a short probation period to learn more about each other.

Honestly, my perfect interview (as a candidate) would be a quick chat about my previous work experience, some one-on-one work with another developer to solve a common problem the company faces and then a few drinks with the team to get to know everyone.

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'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 in two dimensional space, but does not generalize to higher dimensions. The technique of drawing points from a normal distribution and normalizing works for any dimension. That's the usual follow up question when the candidate gives your (very good for the given question) solution.

How would you generate points distributed uniformly on the surface of a three dimensional ball?

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.

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.

That's not quite what "rotational symmetry" means in this context. A collection of random variables independently distributed according to identical "doubly-rectified" exponential distributions would also be symmetric under variable interchange.

However, this represents invariance only under sequences of axis-aligned rotations that are multiples of pi/2. The joint distribution of a collection of independently and identically normally-distributed random variables is invariant under arbitrary rotations, which is a much stronger form of invariance.

E.g., if you drew [x1...xn] from a distribution like exp(-|x1|-|x2|-...-|xn|), which is invariant with respect to variable interchange, and normalized to unit length, the resulting distribution would be markedly non-uniform over the surface of the n-dimensional unit hyper-sphere.

In fact, the differences in the symmetries of these distributions are crucial to the relative behaviors of L1 and L2 regularizers in machine learning. These differences have significant practical, and not merely theoretical consequences.

Right, symmetry! rotational symmetry, which is the one required for this problem. Thanks.

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?

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.

Ah, of course, thanks.

you can use longitude and z (height "up the axis") (it's uniform because a ring of thickness dz at height z is of area 2pi * z * cos(lat) * dz/cos(lat) (so the latitude cancels nicely - it's a trick used for equal area map projections).

Use a space-filling curve?

this a a cute idea, but i don't know of one (on the surface of a sphere). do you? also, are all space-filling curves uniformly dense in the limit? (presumably it depends on how you transform from a plane to a sphere, and if you get that right, you can just use it directly)

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.

I think you meant 2*pi? Wouldn't that only fill the top half of the circle?

Yes I obviously did mean 2*pi but I always get confused with these two numbers...

Not that it matters much, being a lecturer in Mathematics...

"Not that it matters much, being a lecturer in Mathematics..."

Trigonometry was always my favorite Math. But my second calculus class in college was taught by a brilliant (I later found out) native-Hindi speaker. His English was good enough but it took me three weeks to correctly write down the fractions he was quoting as "three under two".

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!

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

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.

Intriguing, what do you use something like this random multi dimensional sphere for?

Choosing a random direction uniformly for various varieties of hill-climbing optimization algorithms. The uniformity is necessary for the analysis of termination conditions.

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.

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

Good point, but if you wanted to work with an arbitrary distribution in the plane as a generalisation of this I think you'd need to look for an equal-area map from R2 to S2? (eg http://en.m.wikipedia.org/wiki/Lambert_azimuthal_equal-area_...)

Edit: I mean R2 to S2 (although this is bijective)

This would generalize properly beyond two dimensions, right?

Q for the math guys:

Is this the closed form pdf of the angle distribution of one quarter of the circle?

http://www.wolframalpha.com/input/?i=1%2Fcos%28min%28x%2Cpi%...

1/cos(min(x,pi/2-x))

plus the normalization term to make \int(..) == 1:

http://www.wolframalpha.com/input/?i=int+1%2Fcos(min(x%2Cpi%...

Constructed by arguing that the probability is directly proportional to the length of the hypotenuse.

It looks alright to me, but you'll have to normalise it for it to be a pdf

Yes, that's what the second link is for to normalize it. Maybe I should've made that clearer.

Bertrand's Paradox addresses a separate issue but illustrates how subtle issues like this can be http://en.wikipedia.org/wiki/Bertrand_paradox_(probability) . The geometric interpretation that the OP offered in which he noted that the map had to be area preserving is a nice way of visualizing why the given implementation doesn't hold but that's just the start. As for the implementation this is also a great example of when something is hard to do in one coordinate system but trivial in another. Polar coordinates are the way to go.

To me, the answer to the actual question is so obviously "no", that I was almost confused. It's as though someone asked me, "which direction is the floor?" Anything that easy must have a trick.

So I though maybe it was related to "points" meaning actual rasterized pixels on the screen. The you get the slightly counter-intuitive result that the diagonal line actual has the same number of pixels as the vertical line, and thus will produce the same density of points on the circumference. However, this line of reasoning would require that we know the lines are far enough apart that they don't overlap pixels.

What kind of job was this for? After stumbling through questions involving trees, arrays and other data structures, I have come to the conclusion that I'm a mathematician dressed up as a mediocre programmer.

This interview was for a data scientist position. I am also a mathematician masquerading as a programmer.

What are the practical applications to something like this?

Interviewing new applicants to your company.

Random search. You evaluate a function (say, a loss function for a statistical model given certain parameters) at a random point, and then randomly displace it by a constant amount in a random direction.

Random search is quite useful for hyperparameter optimization, and it can be a useful building block for something like simulated annealing or parallel tempering.

Video game controllers.

DirectInput joystick data outputs a square range (0,0)->(65535,65535) which is usually uniformly remapped to a circle to be used by the game. Then you have to add in a dead zone to eliminate the noise from the controller around the neutral position.

http://ars.userfriendly.org/cartoons/?id=20070105

Should not be described as points on a circumference?

Doing it about points in a circle made me think of a different problem (which is also interesting)

(Just to clarify, the circumference is the line that contains a circle. I assume that won't be misnamed in a geometry problem of this kind)

Canonically, a circle is the set of points equidistant from a given point (the center of the circle). The set of points inside the circle is known as a disc. Generalizing slightly, a circle is a 1-sphere and a disc is a ball in 2 dimensions.

So no, the post has it correct. In fact, circumference is the scalar value corresponding to the length of the circle. This relies on significantly more structure (i.e. having a metric) than the terms circle and disc.

If you're doing stuff with point sets, "unit circle" typically refers to the point set satisfying x^2 + y^2 =1, the "unit disc" or "unit ball" would be used to refer to the point set satisfying x^2 + y^2 < 1 (open unit ball) x^2 + y^2 <= 1 (closed unit ball).

Reply on news.ycombinator.com