5 ms·

I have mixed feelings about this. I had an interview at Palantir with a self-described "front-end" guy, who asked me to write an algorithm to find a number betw

by Jd 14y ago

I have mixed feelings about this. I had an interview at Palantir with a self-described "front-end" guy, who asked me to write an algorithm to find a number between zero and infinity, where you could pick a number and you would get a response that would tell you whether or not the number was lower or higher than the secret number. The dude had a particular form of approaching the problem that was not at all the fastest form, in fact, he insisted on starting at zero and using an algorithm that was "2x," which he insisted was "fast enough." I thought that a system which started at zero and went up by multiples of two was obscenely slow, and I hinted at this, but he insisted on having things his way. In the end I'm sure he wrote me a bad review and I wasn't offered the job (I didn't really want it anyways, given my impression that the team I was interviewing for wasn't that focused). In any case, I didn't go right now and say this is dumb, but I hinted at a better way, and even this hinting lead to some conflict. In the end I didn't get the job. I'm conflicted if this was the best approach. I could have pretended to be dumber than I actually am and gotten the job offer at least, which at this present moment I could probably use for leverage in the search for contracts or a job, but I couldn't bring myself to accept his not particularly good algorithm (full disclosure: the process was also affected by the fact that my flight was delayed from the east coast, that I got 4 hours of sleep, the fact that I insisted in wearing a tweed coat to the interview, which may have impacted ever important perception of "fit," and that the interview in question was a "surprise" interview after several other interviews).

mratzloff 14y ago
It's a binary search in infinite space. His solution expands the problem area until the number is in the space and then shrinks the problem area until it finds the number. A better solution is to pick an arbitrarily large number and only expand if you have to--otherwise you're shrinking from the very beginning. That's how I would have answered the question, anyway. But yes, I've dealt with interviewers like this--typically it's because they don't understand the subject matter well enough to evaluate or accept an answer they didn't prepare for.
- teraflop 14y ago
  I disagree that that solution is unequivocally better. It depends on the distribution of the input data; if the expected value of the number is small, then you're better off starting at zero than dramatically overestimating. Of course, either way the algorithm runs in O(log n) time.
  - Jd 14y ago
    Within the context of the interview question, the solution is specifically stated to be between 0 and infinity, and you can't surmise that the number is necessarily closer to 0. This is the error that my interviewer made. He was trained to deal with things within the context of situations closer to real life rather than the theoretical box he had established for the interviewing situation. As for my case, I did attempt to start at an arbitrarily large number (but he wouldn't let me), and then went up exponentially (i.e. x = x * x), bi-secting the space once the upper-bound was found and solving from there. My interviewer was sadly not that bright and didn't understand my solution, forcing me to re-write it -- incidentally, lecturing me on how wonderful O(log n) is along the way.
    - teraflop 14y ago
      > the solution is specifically stated to be between 0 and infinity, and you can't surmise that the number is necessarily closer to 0. Closer to 0 than what? Infinity? By any reasonable definition, every integer is closer to 0 than infinity. I think the problem as stated is underspecified; I disagree that increasing "exponentially" (the solution your interviewer described would increase exponentially; your version is doubly exponential, I think) is always faster. Both versions have the same worst-case running time, and if you want to talk about expected running time you need to make assumptions about the data distribution. As a counterexample, if you start with an initial guess of 2 and keep squaring, but the true number is 2^1025, then you end up doing much more work than if you had doubled instead of squaring. I can certainly agree with you that lecturing in an interview is unproductive. Not only is it understandably off-putting, but it doesn't give the interviewer any additional input to the hiring decision and therefore is a waste of everyone's time. (Unless one of the job requirements is coping well with being lectured to, I guess.)

by Jd 14y ago

mratzloff 14y ago

It's a binary search in infinite space. His solution expands the problem area until the number is in the space and then shrinks the problem area until it finds the number. A better solution is to pick an arbitrarily large number and only expand if you have to--otherwise you're shrinking from the very beginning. That's how I would have answered the question, anyway. But yes, I've dealt with interviewers like this--typically it's because they don't understand the subject matter well enough to evaluate or accept an answer they didn't prepare for.

teraflop 14y ago
I disagree that that solution is unequivocally better. It depends on the distribution of the input data; if the expected value of the number is small, then you're better off starting at zero than dramatically overestimating. Of course, either way the algorithm runs in O(log n) time.
- Jd 14y ago
  Within the context of the interview question, the solution is specifically stated to be between 0 and infinity, and you can't surmise that the number is necessarily closer to 0. This is the error that my interviewer made. He was trained to deal with things within the context of situations closer to real life rather than the theoretical box he had established for the interviewing situation. As for my case, I did attempt to start at an arbitrarily large number (but he wouldn't let me), and then went up exponentially (i.e. x = x * x), bi-secting the space once the upper-bound was found and solving from there. My interviewer was sadly not that bright and didn't understand my solution, forcing me to re-write it -- incidentally, lecturing me on how wonderful O(log n) is along the way.
  - teraflop 14y ago
    > the solution is specifically stated to be between 0 and infinity, and you can't surmise that the number is necessarily closer to 0. Closer to 0 than what? Infinity? By any reasonable definition, every integer is closer to 0 than infinity. I think the problem as stated is underspecified; I disagree that increasing "exponentially" (the solution your interviewer described would increase exponentially; your version is doubly exponential, I think) is always faster. Both versions have the same worst-case running time, and if you want to talk about expected running time you need to make assumptions about the data distribution. As a counterexample, if you start with an initial guess of 2 and keep squaring, but the true number is 2^1025, then you end up doing much more work than if you had doubled instead of squaring. I can certainly agree with you that lecturing in an interview is unproductive. Not only is it understandably off-putting, but it doesn't give the interviewer any additional input to the hiring decision and therefore is a waste of everyone's time. (Unless one of the job requirements is coping well with being lectured to, I guess.)