3 ms·

Wait till this appears on LeetCode and gets included in the FAANG whiteboard interviews to be solved in 15 minutes.

robinhouston 8y ago
I know you’re joking, but apparently it was given as a programming problem in a contest on at least one occasion. See here: http://www.njohnston.ca/2014/08/obvious-does-not-imply-true-the-minimal-superpermutation-conjecture-is-false/ http://www.njohnston.ca/2014/08/obvious-does-not-imply-true-...
- robinhouston 8y ago
  Here’s another more recent case where it appeared in a coding contest: https://discuss.codechef.com/questions/133115/wrong-problem-in-the-contest-coding-hours https://discuss.codechef.com/questions/133115/wrong-problem-...
- bootsz 8y ago
  It's not a joke: https://leetcode.com/problems/cracking-the-safe/ https://leetcode.com/problems/cracking-the-safe/ It has been asked in real interviews
  - robinhouston 8y ago
    That’s a different (rather easier) problem: note that the safe combination can contain the same digit more than once. The solution to this problem is given by de Bruijn sequences: https://en.wikipedia.org/wiki/De_Bruijn_sequence https://en.wikipedia.org/wiki/De_Bruijn_sequence
    - bootsz 8y ago
      Ah, I see. Thanks
bootsz 8y ago
Yeah, I was thinking the same thing. Seems very similar to this problem: https://leetcode.com/problems/cracking-the-safe/ https://leetcode.com/problems/cracking-the-safe/ And can confirm that at least one FAANG company has asked this in a real interview.
- quenstionsasked 8y ago
  Haven't taken the time to read through this properly so forgive the question - but is this any different from the above problem? And if so - if someone solves this programming task on leetcode have they not then also solved the permutation problem from OP?
  - deleted 8y ago
    [deleted]
  - robinhouston 8y ago
    It is different because a safe combination may contain the same digit more than once, so the intended solution is a de Bruijn sequence: https://en.wikipedia.org/wiki/De_Bruijn_sequence https://en.wikipedia.org/wiki/De_Bruijn_sequence

I know you’re joking, but apparently it was given as a programming problem in a contest on at least one occasion. See here: http://www.njohnston.ca/2014/08/obvious-does-not-imply-true-the-minimal-superpermutation-conjecture-is-false/ http://www.njohnston.ca/2014/08/obvious-does-not-imply-true-...

robinhouston 8y ago
Here’s another more recent case where it appeared in a coding contest: https://discuss.codechef.com/questions/133115/wrong-problem-in-the-contest-coding-hours https://discuss.codechef.com/questions/133115/wrong-problem-...
bootsz 8y ago
It's not a joke: https://leetcode.com/problems/cracking-the-safe/ https://leetcode.com/problems/cracking-the-safe/ It has been asked in real interviews
- robinhouston 8y ago
  That’s a different (rather easier) problem: note that the safe combination can contain the same digit more than once. The solution to this problem is given by de Bruijn sequences: https://en.wikipedia.org/wiki/De_Bruijn_sequence https://en.wikipedia.org/wiki/De_Bruijn_sequence
  - bootsz 8y ago
    Ah, I see. Thanks

bootsz 8y ago

Yeah, I was thinking the same thing. Seems very similar to this problem: https://leetcode.com/problems/cracking-the-safe/ https://leetcode.com/problems/cracking-the-safe/ And can confirm that at least one FAANG company has asked this in a real interview.

quenstionsasked 8y ago
Haven't taken the time to read through this properly so forgive the question - but is this any different from the above problem? And if so - if someone solves this programming task on leetcode have they not then also solved the permutation problem from OP?
- deleted 8y ago
  [deleted]
- robinhouston 8y ago
  It is different because a safe combination may contain the same digit more than once, so the intended solution is a de Bruijn sequence: https://en.wikipedia.org/wiki/De_Bruijn_sequence https://en.wikipedia.org/wiki/De_Bruijn_sequence