3 ms·

The moral of this story is: Amazon asks candidates some poor questions. Very difficult sort of a problem to solve on your feet, especially since "random" and "s

by aston 18y ago

The moral of this story is: Amazon asks candidates some poor questions. Very difficult sort of a problem to solve on your feet, especially since "random" and "stochastic" are so related in people's minds.

Tichy 18y ago
I had to come up with such an algorithm a while ago and don't remember it being very difficult. Later I learned "my" algorithm is officially acknowledged, there was a HN post about it a while ago (some other guys stole my idea and slapped their name on the algorithm, damn it). Of course my Java-Dev-friend only answered "just use the shuffle method of the Array collection". Besides, I'd rather work for a company that asks too difficult questions than too easy ones.
- aston 18y ago
  If you get it right the first time, you're probably just lucky. When was the last time you had to formulate an inductive proof at a career fair? And why should you be expected to? If you already know about the Knuth shuffle and you get it right, the question wasn't worth asking in the first place.
  - Tichy 18y ago
    No I wasn't lucky. I briefly considered various alternatives and settled for the correct one. What made me select it was the thought "wait a minute, there already is a random function in my programming language, why not use it". I actually find it hard to think of a suitable alternative for that algorithm. Also, I don't think the question was for an inductive proof. To me the question seems exactly right, not too easy and not too hard.
    - aston 18y ago
      Maybe I'm not being clear. The difference between the right algorithm and the wrong one here is whether or not items that have already been randomly swapped can be swapped again. Simply performing n random selections on the list is wrong, and the easiest way to see why it doesn't work is harder math than you probably want to ask people for. Meanwhile, proving the other answer correct does require an inductive argument (pretty similar to the one that a selection sort works). If your intuition led you to the right answer, that's cool, but for those who guess wrong, it sucks for them. The question doesn't do a good job of distinguishing between people who are smart and people who aren't because both the right and wrong answers seem pretty right because they're both stochastic. Unfortunately, only one is truly random.
      - Tichy 18y ago
        To be fair, I don't think I went through as elaborate mathematical considerations as the writer of the article. But even he mentions that he immediately had a bad feeling about the wrong solution, simply because it is doing too much work. The step for me was to move away from the stochastic problem and say "wait a minute, there is a random generator built into my computer already, how can I use it directly". Assuming a horde of mathematicians has already showed that the inbuilt random numbers generator is as good as possible, that way I avoid all the maths issues. And that is a step that seems reasonable to expect from a good programmer. Edit: just read the Knuth Shuffle entry at wikipedia. Happy that I even reinvented the Knuth optimization myself ;-)
jwilliams 18y ago
True, especially if they use the word "shuffle"... To me that brings to mind shuffling a deck of cards first - which is somewhat analogous the "swap elements" array shuffling technique.

by aston 18y ago

Tichy 18y ago

I had to come up with such an algorithm a while ago and don't remember it being very difficult. Later I learned "my" algorithm is officially acknowledged, there was a HN post about it a while ago (some other guys stole my idea and slapped their name on the algorithm, damn it). Of course my Java-Dev-friend only answered "just use the shuffle method of the Array collection". Besides, I'd rather work for a company that asks too difficult questions than too easy ones.

aston 18y ago
If you get it right the first time, you're probably just lucky. When was the last time you had to formulate an inductive proof at a career fair? And why should you be expected to? If you already know about the Knuth shuffle and you get it right, the question wasn't worth asking in the first place.
- Tichy 18y ago
  No I wasn't lucky. I briefly considered various alternatives and settled for the correct one. What made me select it was the thought "wait a minute, there already is a random function in my programming language, why not use it". I actually find it hard to think of a suitable alternative for that algorithm. Also, I don't think the question was for an inductive proof. To me the question seems exactly right, not too easy and not too hard.
  - aston 18y ago
    Maybe I'm not being clear. The difference between the right algorithm and the wrong one here is whether or not items that have already been randomly swapped can be swapped again. Simply performing n random selections on the list is wrong, and the easiest way to see why it doesn't work is harder math than you probably want to ask people for. Meanwhile, proving the other answer correct does require an inductive argument (pretty similar to the one that a selection sort works). If your intuition led you to the right answer, that's cool, but for those who guess wrong, it sucks for them. The question doesn't do a good job of distinguishing between people who are smart and people who aren't because both the right and wrong answers seem pretty right because they're both stochastic. Unfortunately, only one is truly random.
    - Tichy 18y ago
      To be fair, I don't think I went through as elaborate mathematical considerations as the writer of the article. But even he mentions that he immediately had a bad feeling about the wrong solution, simply because it is doing too much work. The step for me was to move away from the stochastic problem and say "wait a minute, there is a random generator built into my computer already, how can I use it directly". Assuming a horde of mathematicians has already showed that the inbuilt random numbers generator is as good as possible, that way I avoid all the maths issues. And that is a step that seems reasonable to expect from a good programmer. Edit: just read the Knuth Shuffle entry at wikipedia. Happy that I even reinvented the Knuth optimization myself ;-)

jwilliams 18y ago

True, especially if they use the word "shuffle"... To me that brings to mind shuffling a deck of cards first - which is somewhat analogous the "swap elements" array shuffling technique.