I'd prefer someone that can infer the algorithm without knowing it before hand than someone who just memorized a bunch of them.
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/
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.
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).
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
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.
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.
The problem is that the majority of people simply don't spend time on issues like that, either in their day jobs or weekends/evenings. The closest you can get to things like that if you work in pretty boring domains, is having to pick between a Set or a Map for some data structure in the app. Or avoiding things like N+1 issues which have relatively little to do with algorithms and more in regards to how frameworks implement things.
Can someone do the latter without the former?