Re:Mystery Math Whiz and Novelist Advance Permutation Problem
by option_greek on Tuesday November 06, 2018 @04:04AM
(#18389417)
Wait till this appears on LeetCode and gets included in the FAANG whiteboard interviews to be solved in 15 minutes.
[ Parent
| on HN ]
Re:Mystery Math Whiz and Novelist Advance Permutation Problem
by robinhouston on Tuesday November 06, 2018 @04:34AM
(#18389540)
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-...
Re:Mystery Math Whiz and Novelist Advance Permutation Problem
by robinhouston on Tuesday November 06, 2018 @09:35AM
(#18391317)
Here’s another more recent case where it appeared in a coding contest: https://discuss.codechef.com/questions/133115/wrong-problem-...
Re:Mystery Math Whiz and Novelist Advance Permutation Problem
by bootsz on Tuesday November 06, 2018 @10:32AM
(#18391862)
It's not a joke: https://leetcode.com/problems/cracking-the-safe/
It has been asked in real interviews
Re:Mystery Math Whiz and Novelist Advance Permutation Problem
by robinhouston on Tuesday November 06, 2018 @11:22AM
(#18392344)
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
Re:Mystery Math Whiz and Novelist Advance Permutation Problem
by bootsz on Tuesday November 06, 2018 @11:40AM
(#18392550)
Ah, I see. Thanks
Re:Mystery Math Whiz and Novelist Advance Permutation Problem
by bootsz on Tuesday November 06, 2018 @10:31AM
(#18391854)
Yeah, I was thinking the same thing. Seems very similar to this problem: https://leetcode.com/problems/cracking-the-safe/
And can confirm that at least one FAANG company has asked this in a real interview.
Re:Mystery Math Whiz and Novelist Advance Permutation Problem
by quenstionsasked on Tuesday November 06, 2018 @10:59AM
(#18392114)
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?
Re:Mystery Math Whiz and Novelist Advance Permutation Problem
by robinhouston on Tuesday November 06, 2018 @11:25AM
(#18392393)
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