[erganemic]

Coming up with algorithms on the spot isn't a viable strategy for technical interviews any more, even if you're a super-genius. Here's a question that the page author claims took Donald Knuth 24 hours to solve [1], which is classified on Leetcode as a Medium(!) difficulty question [2]. Leetcode Medium questions are typically the cut-off point for most FAANG-tier interview questions--and while this is a hard medium, I know someone who got a variation of it at a Meta interview, and was expected to solve it in 30 minutes. So unless you're 48 times faster at inferring algorithms than one of the best algorists in the world, memorizing tricks is the game you have to play if you want a FAANG-adjacent job!

Of course, then the natural reaction is "if your hiring process would pass on Donald Knuth, your hiring process is broken," which is absolutely true, already known, and (apparently) deemed acceptable.

[1] https://keithschwarz.com/interesting/code/?dir=find-duplicat...

[2] https://leetcode.com/problems/find-the-duplicate-number/

[vitiral]

That problem is a terrible interview question, mainly because it's completely trivial with O(n) memory (just use a Set), but requires a different branch of comp sci at O(1).

Personally I also feel that any question that needs an O(1) memory when you _start with an array_ is disingenuous. O(1) memory was used for things like tape storage, where N was some huge external storage. If you already have an array, then the chance you don't have double that memory are dibcus.

[sanedigital]

Not sure I agree. It's very simple if you look at what's "wrong" with the input: it has a duplicated number, which means there's a "right" version of it without. That right version is just the count from 1->n. Once you see that, you can see that all you have to do is sum each list and calculate the difference.

[kd5bjo]

This algorithm fails in the case that the duplicated number appears more than twice in the list, which is explicitly allowed by the problem statement.

[sanedigital]

It’s not, on Leetcode. I submitted it as an answer and it worked. In the case where the number is repeated more than once (m times), you have an array of n+m elements. Divide the sum by m, subtract, problem solved.

[kd5bjo]

In that case, their test suite doesn’t cover all relevant cases. Consider nums = [1,1,1,1,4]: There are 5 elements, so n=4, and all elements are within the range [1,4]; only the 1 is duplicated. This fulfills all of the listed requirements.

The actual sum is 8, and the 4th triangular number is 10, so the duplicated number according to your algorithm must be -2 (or some fraction thereof, depending on how you calculate m).

[kd5bjo]

The LeetCode version doesn't require linear time, and caps the number of elements to 10^5, so the brute-force O(n^2) time solution seems perfectly acceptable.

[dullcrisp]

Tried it with a simple loop, got time limit exceeded unfortunately.

[bena]

I recently did the Foobar with Google challenge and yeah, I feel this.

Question 4b was a Max Flow problem. And question 5 was Polya's enumeration theorem.

With both of those, I was not aware of the algorithms beforehand. I understood what 4b was asking, "Ok, I need to find out the bottlenecks and figure out how many bunnies I can feed through the maze at once." And 5 was more incremental. "This is a matrix.", "Ok, I know if I know the number of distinct row mixes and column mixes, I could also maybe figure out how many distinct matrix configurations I could make", etc, which led me to Burnside's lemma, which led me to Polya's enumeration theorem.

It took me a long while to make all those increments however. Given 30 - 50 minutes, I doubt I'd be able to even implement Polya in the blind.

[zepolen]

FAANGs would pass on Donald Knuth, their entire process is made to find devoted soldiers who will memorize every algorithm and sit through 10 interviews and are too naive to think for themselves. Corps want to say "Do this, fast, using what you know" and the candidate says "Right away!". Knuth on the other hand would say "Hold up, there might be a better way, screw the deadline, I'll find it". Corps don't want that.

[robbie-c]

I just looked at this for 30 seconds, do you just XOR everything together? Then you could XOR it with all the numbers 1 to n again to get just the duplicate number, as every number would appear in the XOR twice except the duplicate number which would appear once.

Edit: I misread the problem :D I initially read it as every number appears once and one number appears twice, but alas it's not so simple :D

[sanedigital]

Sum the input list, sum the list of [1...n], subtract and voila!

[robbie-c]

Yeah, sadly you're not guaranteed some of the things that are needed for this to work. I defo believe the story that it took Knuth a day to figure this out, although when you see the answer it's pretty easy to understand.

[sanedigital]

What things? I submitted it as an answer on Leetcode and it was accepted.

[dullcrisp]

With only one repeated number, you can sum the array and subtract 1+…+n to get the answer. Still an annoying trick you wouldn’t expect in an algorithm problem. Though the leetcode version also doesn’t require linear time, so I guess you could just iterate and compare in quadratic time to solve it?

[lmz]

But the leetcode one is a different question in that it guarantees only one duplicate element.

[cdelsolar]

How is this tough? Use a dict?

Edit: or even easier, because I didn't read the question properly the first time, sum all the numbers from 1 to n (use Euler's trick for extra points) and sum your array and take the difference.

[Faark]

The original challenge didn't include the "only one" repeated number part, btw