397 karma · joined March 6, 2020
Much more common is there are zero or more duplicates.
Here is what I came up with:
- We need a way to record what has been already seen
- A hash-map could work, but I think we can be more efficient
- We know that all elements are less than the array length in size...
- So we can allocate a single array of flags with the same length as the input
- The flag for value `n` is at position `n` in this array
let findDuplicates xs =
let seen = Array.create (Seq.length xs) false
let mutable duplicates = []
for x in xs do
if seen[x] then
duplicates <- x :: duplicates
else
seen[x] <- true
duplicates
I'm pretty sure this is O(n)?I think it's interesting that the mathematical trick (sum of numbers 1 to n formula) does not work in the more realistic variant. This fact is probably why leet-code problems are so disconnected from the real world. It's like AI for board-games.
With the information being stored outside the resource, we know that it was deleted and the metadata about it.
- The compiler code becomes more complicated, making correctness harder
- The compiler might become slower to run
- Introducing new languages features may become harder, again due to code complexity
What would be hilarious (imo) would be if the 100th puzzle is actually unsolvable.
This misses the point. I don't care how the language implements the functionality if it meets my performance requirements and it is convenient to use.