6 ms·
My Most Interesting Interview Problem
- fatman 13y agoWhat 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.
- MidsizeBlowfish 13y agoThis interview was for a data scientist position. I am also a mathematician masquerading as a programmer.
- quchen 13y agoFor 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.)
- ronaldx 13y agoor generate a (uniform) random direction from the centre of the circle.
- pfortuny 13y agoI'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?
- ColinWright 13y ago> 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?
- MidsizeBlowfish 13y agoPoster 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.
- pfortuny 13y agoYes, 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.
- psb217 13y agoThat'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.
- pfortuny 13y agoRight, symmetry! rotational symmetry, which is the one required for this problem. Thanks.
- gibybo 13y agoFor a ball, can't I just randomly generate two angles (0-2pi)?
- quchen 13y agoMaybe 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.
- smoyer 13y agoI think you meant 2*pi? Wouldn't that only fill the top half of the circle?
- pfortuny 13y agoYes 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...
- smoyer 13y ago"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".
- alxbrun 13y agoHow 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!
- mturmon 13y agoI 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).
- ColinWright 13y agoIt'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.
- RyanZAG 13y agoIntriguing, what do you use something like this random multi dimensional sphere for?
- ColinWright 13y agoChoosing a random direction uniformly for various varieties of hill-climbing optimization algorithms. The uniformity is necessary for the analysis of termination conditions.
- cmsmith 13y agoAlternatively, 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.
- deleted 13y ago[deleted]
- noAlchemy 13y agoGood 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_projection http://en.m.wikipedia.org/wiki/Lambert_azimuthal_equal-area_...) Edit: I mean R2 to S2 (although this is bijective)
- sopooneo 13y agoThis would generalize properly beyond two dimensions, right?
- ryanbrunner 13y agoFor 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.
- MidsizeBlowfish 13y agoCertainly. This interview was for a data-oriented position.
- peacemaker 13y agoCompletely 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.
- deleted 13y ago[deleted]
- sologoub 13y agoWhat are the practical applications to something like this?
- lifeformed 13y agoInterviewing new applicants to your company.
- fiatmoney 13y agoRandom 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.
- visualphoenix 13y agoVideo 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.
- jackmaney 13y agohttp://ars.userfriendly.org/cartoons/?id=20070105 http://ars.userfriendly.org/cartoons/?id=20070105
- VladRussian2 13y agoin 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.
- deleted 13y ago[deleted]
- hnriot 13y agoIt'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.
- VladRussian2 13y agoI 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...
- jurassic 13y agoSounds like the parent comment was the interviewee, not interviewer.
- 13y ago
- lpage 13y agoBertrand's Paradox addresses a separate issue but illustrates how subtle issues like this can be http://en.wikipedia.org/wiki/Bertrand_paradox_(probability) 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.
- jaimebuelta 13y agoShould 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)
- gsteinb88 13y agoCanonically, 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.
- JackFr 13y agoIf 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).
- susi22 13y agoQ 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%2F2-x%29%29+%28x+from+0+to+pi%2F2%29 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%2F2-x))+from+0+to+pi%2F2 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.
- thomasahle 13y agoIt looks alright to me, but you'll have to normalise it for it to be a pdf
- susi22 13y agoYes, that's what the second link is for to normalize it. Maybe I should've made that clearer.
- sopooneo 13y agoTo 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.