8 ms·

Can you elaborate on what made the question obscure? I'm asking because I used the question "print out the first 52 numbers in random order"in interviews before

Can you elaborate on what made the question obscure? I'm asking because I used the question "print out the first 52 numbers in random order"in interviews before, and the answers seemed to give a good hint about understanding of basic CS concepts.

anothernewdude 4y ago
np.random.choice(52, 52, False) + 1
- CoastalCoder 4y ago
  I'd start with, "What do you mean by 'random'?"
  - eastbound 4y ago
    Obligatory response, Dilbert’s “9… 9… 9…” number generator, “the problem with randomness, is that you can never be sure…” https://www.dilbert.com/strip/2001-10-25 https://www.dilbert.com/strip/2001-10-25
    - mjochim 4y ago
      If we are talking obligatory responses, don't forget this one: https://xkcd.com/221/ https://xkcd.com/221/
  - bornfreddy 4y ago
    Yup. Seemingly trivial questions can reveal a lot about the candidate.
    - znpy 4y ago
      Indeed. I have been routinely questioned about what happens from when you type www.somesite.com and when the webpage is displayed when interviewing over the years and realised that nowadays I could fill 2 whole hours talking about all the stuff that actually happens (and many times I would have to say “but about this specific thing I’m not very knowledgeable about)… whereas at the start of my career i would have probably spoken for like 15 seconds and felt smart about answering “such an easy question”.
  - deleted 4y ago
    [deleted]
  - klyrs 4y ago
    Mine would be "what do you mean by 'first number'." If they answer with one-indexing, walk out of the interview.
  - buzzdenver 4y ago
    What is the catch here? In multi dimensional and infinite cases it can be a little tricky, but in this one is there more to it than "all permutations should have the same probability"?
    - CoastalCoder 4y ago
      I'm not an expert, but here are a few of the things that come to mind for me: - One conception of random is subjective: the pattern must not be predictable by a particular person/entity. E.g., the Fibonacci sequence may seem random to a person with IQ 3, but not IQ 1000. - I think related to that is the concept of cryptographically random: [0] - Random numbers can have different statistical distributions. You referred to uniform randomness, but depending on the application, that's not necessarily what you want. E.g., [1] Especially for statistical / Monte Carlo modeling. - Depending on just how random you need something to be and to whom, you may or may not need specialized computing hardware. [2] - Sometimes people kinda want random, but they also want reproducibility if necessary. Think randomly generated unit test input, or randomly generated game levels. For those applications, it's helpful to know that most software uses pseudo- -random number generators (PRNG's). If you can remember the specific number used to seed the PRNG stream, you may be able to deterministically re-execute the code at will. Alternatively, if you want to (nearly) guarantee that subsequent runs of the program aren't the same, you'll want to somehow ensure that a different seed number is used for the different program runs. So if anything about the job opening depends on this kind of stuff, IMHO it's a great interview question. [0] https://crypto.stackexchange.com/questions/39186/what-does-it-mean-for-a-random-number-generator-to-be-cryptographically-secure https://crypto.stackexchange.com/questions/39186/what-does-i... [1] https://stackoverflow.com/questions/37828955/what-is-the-difference-between-uniform-and-gaussian-random-timer https://stackoverflow.com/questions/37828955/what-is-the-dif... [2] https://en.wikipedia.org/wiki/Entropy_(computing) https://en.wikipedia.org/wiki/Entropy_(computing)
tzs 4y ago
It might be the difficulty of actually getting it right (if by "right" we mean that all 52! permutations are equally likely. Or perhaps it is more accurate to say the ease of not getting it right. Something like this: 10 pick a number from 1 to 52 20 if not already printed it 30 print it 40 if we have printed 52 numbers 50 halt 60 goto 10 works, but could take arbitrarily long time. Most people prefer bounded run time. Most people seem to come up with something like this: array = [1, 2, ..., 52] for i = 0 to 51 j = random(0,51) swap(array[i], array[j]) print(array) That has bounded time (constant time assuming random and swap are constant time). Unfortunately not all permutations are equally likely. We can see that all permutations are equally likely by noting that there are 52 iterations of the loop, and each iteration has 52 possible outcomes. That gives us a total of 52^52 possible outcomes. 52! does not divide 52^52, so it is not possible for each of the 52! possible outcomes to be equally represented in the 52^52 outcomes. To fix this, you can use the same basic idea of going through all 52 places in your array [1, 2, ..., 52] and swapping each with a random location, but instead of swapping the Nth location with a random location in the whole array, swap with a random location that is not earlier in the array. Then you still have 52 iterations, but now the number of outcomes varies by iteration. The first iteration has 52 outcomes. The second has 51 outcomes. The third 50 outcomes and so on down to that last having only 1 outcome. That gives 52! possible outcomes, all equally likely. We just then have to show that every one of the 52! permutations is among those outcomes which is easy to do, and then we have shown that this is a correct shuffle.
- Kim_Bruning 4y ago
  So what happens in your code if you just change the line j = random(0,51) to j = random(i,51) ?
  - tzs 4y ago
    That is indeed the simplest fix. It is called the Fisher-Yates shuffle [1]. [1] https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_modern_algorithm https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#T...
Kim_Bruning 4y ago
Interesting, what CS concepts were you looking for?
- buzzdenver 4y ago
  Stuff like whether the algorithm will always stop, or whether it runs O(N) vs O(N square). The main point to me was more to be able to have a conversation about the solution rather than it being absolutely right. I remember quite a few people using randomness, the most odd (and totally wrong) one using a random sort function over an array of (1..52).
  - treis 4y ago
    Why is the random sort wrong?
    - buzzdenver 4y ago
      Random sort meaning that sometimes a>b, other times a<b for the same values. Whatever algorithm a language's built in sort implements probably assumes that comparisons are consistent. I remember checking a few versions of perl and some created a core dump iirc.
      - treis 4y ago
        Ah okay. Thought you meant using something like shuffle in Ruby. I do wonder what the result of doing a randomized sort like that would be. Probably not really random. Feel like numbers near the median would be overrepresented in the middle of the array.
dimatura 4y ago
This question came up in a weekly "random topic" talk that we had at an MIT lab I was visiting at the time, many years ago. One of the lab members - who was a very impressive coder and researcher - had been asked this question at a google interview. I remember being pretty surprised that he wasn't familiar with the fisher-yates shuffle (and that this would be considered a good question to ask at google). His first answer to the problem was actually one of the "obvious" (and incorrect) answers one might give. But then he also walked us through the process he went through with the interviewer on deriving a correct algorithm, along with a mathematical justification of its correctness. I think regardless of whether one is familiar with the typical algorithms, being able to explain and justify them does show skills. (And fwiw, he did end up getting an offer and working at google).
klyrs 4y ago
Hilarious. Python's random module has a built-in shuffle.
lrvick 4y ago
The questions I got were very specific to playing card patterns. The one I remember best was "How many times does it take to perfectly cut and shuffle a deck of cards before it is back in original order". Spoiler: A "perfect" shuffle is called a Faro shuffle and the holy grail of false shuffles to master as a magician. When a deck is cut evenly at 26 cards (doable with practice or a slightly bent or irregular marker card) and Faro shuffled correctly eight times, the deck will return to its original order. If I really liked the company I might indulge your question, but it would annoy me unless you were a game development company and this was a real problem someone faced recently. I general I don't like live coding questions because they don't reveal anywhere near the quality of work I produce if left alone to think for a bit. If the questions pertain to a real world problem I will noamally indulge them though. As an interviewer I don't make people do them. I often do live code -review- to see if people can understand code and spot security flaws or bugs as I find that a more useful skill than coding anyway, and code review -is- something actually often done together with peers in the real world. I sometimes ask for people do take-home tests if they have no open source projects I can reference, because seeing how people code on their own is how I find out if they can do the job. If they use search engines to help, I don't care. That is how real life works. That said, I only do this if I know the employer is willing to pay them for the time. Work simulation goes both ways. If I am going to make it like real work, I need to pay for it like real work.

anothernewdude 4y ago

np.random.choice(52, 52, False) + 1

CoastalCoder 4y ago
I'd start with, "What do you mean by 'random'?"
- eastbound 4y ago
  Obligatory response, Dilbert’s “9… 9… 9…” number generator, “the problem with randomness, is that you can never be sure…” https://www.dilbert.com/strip/2001-10-25 https://www.dilbert.com/strip/2001-10-25
  - mjochim 4y ago
    If we are talking obligatory responses, don't forget this one: https://xkcd.com/221/ https://xkcd.com/221/
- bornfreddy 4y ago
  Yup. Seemingly trivial questions can reveal a lot about the candidate.
  - znpy 4y ago
    Indeed. I have been routinely questioned about what happens from when you type www.somesite.com and when the webpage is displayed when interviewing over the years and realised that nowadays I could fill 2 whole hours talking about all the stuff that actually happens (and many times I would have to say “but about this specific thing I’m not very knowledgeable about)… whereas at the start of my career i would have probably spoken for like 15 seconds and felt smart about answering “such an easy question”.
- deleted 4y ago
  [deleted]
- klyrs 4y ago
  Mine would be "what do you mean by 'first number'." If they answer with one-indexing, walk out of the interview.
- buzzdenver 4y ago
  What is the catch here? In multi dimensional and infinite cases it can be a little tricky, but in this one is there more to it than "all permutations should have the same probability"?
  - CoastalCoder 4y ago
    I'm not an expert, but here are a few of the things that come to mind for me: - One conception of random is subjective: the pattern must not be predictable by a particular person/entity. E.g., the Fibonacci sequence may seem random to a person with IQ 3, but not IQ 1000. - I think related to that is the concept of cryptographically random: [0] - Random numbers can have different statistical distributions. You referred to uniform randomness, but depending on the application, that's not necessarily what you want. E.g., [1] Especially for statistical / Monte Carlo modeling. - Depending on just how random you need something to be and to whom, you may or may not need specialized computing hardware. [2] - Sometimes people kinda want random, but they also want reproducibility if necessary. Think randomly generated unit test input, or randomly generated game levels. For those applications, it's helpful to know that most software uses pseudo- -random number generators (PRNG's). If you can remember the specific number used to seed the PRNG stream, you may be able to deterministically re-execute the code at will. Alternatively, if you want to (nearly) guarantee that subsequent runs of the program aren't the same, you'll want to somehow ensure that a different seed number is used for the different program runs. So if anything about the job opening depends on this kind of stuff, IMHO it's a great interview question. [0] https://crypto.stackexchange.com/questions/39186/what-does-it-mean-for-a-random-number-generator-to-be-cryptographically-secure https://crypto.stackexchange.com/questions/39186/what-does-i... [1] https://stackoverflow.com/questions/37828955/what-is-the-difference-between-uniform-and-gaussian-random-timer https://stackoverflow.com/questions/37828955/what-is-the-dif... [2] https://en.wikipedia.org/wiki/Entropy_(computing) https://en.wikipedia.org/wiki/Entropy_(computing)

tzs 4y ago

It might be the difficulty of actually getting it right (if by "right" we mean that all 52! permutations are equally likely. Or perhaps it is more accurate to say the ease of not getting it right. Something like this: 10 pick a number from 1 to 52 20 if not already printed it 30 print it 40 if we have printed 52 numbers 50 halt 60 goto 10 works, but could take arbitrarily long time. Most people prefer bounded run time. Most people seem to come up with something like this: array = [1, 2, ..., 52] for i = 0 to 51 j = random(0,51) swap(array[i], array[j]) print(array) That has bounded time (constant time assuming random and swap are constant time). Unfortunately not all permutations are equally likely. We can see that all permutations are equally likely by noting that there are 52 iterations of the loop, and each iteration has 52 possible outcomes. That gives us a total of 52^52 possible outcomes. 52! does not divide 52^52, so it is not possible for each of the 52! possible outcomes to be equally represented in the 52^52 outcomes. To fix this, you can use the same basic idea of going through all 52 places in your array [1, 2, ..., 52] and swapping each with a random location, but instead of swapping the Nth location with a random location in the whole array, swap with a random location that is not earlier in the array. Then you still have 52 iterations, but now the number of outcomes varies by iteration. The first iteration has 52 outcomes. The second has 51 outcomes. The third 50 outcomes and so on down to that last having only 1 outcome. That gives 52! possible outcomes, all equally likely. We just then have to show that every one of the 52! permutations is among those outcomes which is easy to do, and then we have shown that this is a correct shuffle.

Kim_Bruning 4y ago
So what happens in your code if you just change the line j = random(0,51) to j = random(i,51) ?
- tzs 4y ago
  That is indeed the simplest fix. It is called the Fisher-Yates shuffle [1]. [1] https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_modern_algorithm https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#T...

Kim_Bruning 4y ago

Interesting, what CS concepts were you looking for?

buzzdenver 4y ago
Stuff like whether the algorithm will always stop, or whether it runs O(N) vs O(N square). The main point to me was more to be able to have a conversation about the solution rather than it being absolutely right. I remember quite a few people using randomness, the most odd (and totally wrong) one using a random sort function over an array of (1..52).
- treis 4y ago
  Why is the random sort wrong?
  - buzzdenver 4y ago
    Random sort meaning that sometimes a>b, other times a<b for the same values. Whatever algorithm a language's built in sort implements probably assumes that comparisons are consistent. I remember checking a few versions of perl and some created a core dump iirc.
    - treis 4y ago
      Ah okay. Thought you meant using something like shuffle in Ruby. I do wonder what the result of doing a randomized sort like that would be. Probably not really random. Feel like numbers near the median would be overrepresented in the middle of the array.

dimatura 4y ago

This question came up in a weekly "random topic" talk that we had at an MIT lab I was visiting at the time, many years ago. One of the lab members - who was a very impressive coder and researcher - had been asked this question at a google interview. I remember being pretty surprised that he wasn't familiar with the fisher-yates shuffle (and that this would be considered a good question to ask at google). His first answer to the problem was actually one of the "obvious" (and incorrect) answers one might give. But then he also walked us through the process he went through with the interviewer on deriving a correct algorithm, along with a mathematical justification of its correctness. I think regardless of whether one is familiar with the typical algorithms, being able to explain and justify them does show skills. (And fwiw, he did end up getting an offer and working at google).

klyrs 4y ago

Hilarious. Python's random module has a built-in shuffle.

lrvick 4y ago

The questions I got were very specific to playing card patterns. The one I remember best was "How many times does it take to perfectly cut and shuffle a deck of cards before it is back in original order". Spoiler: A "perfect" shuffle is called a Faro shuffle and the holy grail of false shuffles to master as a magician. When a deck is cut evenly at 26 cards (doable with practice or a slightly bent or irregular marker card) and Faro shuffled correctly eight times, the deck will return to its original order. If I really liked the company I might indulge your question, but it would annoy me unless you were a game development company and this was a real problem someone faced recently. I general I don't like live coding questions because they don't reveal anywhere near the quality of work I produce if left alone to think for a bit. If the questions pertain to a real world problem I will noamally indulge them though. As an interviewer I don't make people do them. I often do live code -review- to see if people can understand code and spot security flaws or bugs as I find that a more useful skill than coding anyway, and code review -is- something actually often done together with peers in the real world. I sometimes ask for people do take-home tests if they have no open source projects I can reference, because seeing how people code on their own is how I find out if they can do the job. If they use search engines to help, I don't care. That is how real life works. That said, I only do this if I know the employer is willing to pay them for the time. Work simulation goes both ways. If I am going to make it like real work, I need to pay for it like real work.