Today’s problem is actually one I’ve seen before in a technical interview. I tried it then using nested loops that was O(n^2) complex and took longer than I expected trying to keep track of when an item was found and how to handle more than one duplicate entry. My interviewer suggested using a hash which I had never considered; that’s experience for you.
Since the loops are O(n^2) and I got lost in the truth tables the first time, I’m going to take my interviewers advice and use hashes instead. The plan is that as each value is added to the hash-table a collision will occur when a second number is added and throwing a duplicate entry. To do this I’m going to make my own simple hash object that will support:
- adding values to the table
- automatically increasing the table size if it gets >80% allocated
- reporting a duplicate value
- reporting the current hash allocation percent
Should be fun.
Hopefully while filling out your taxes you didn’t run in to any issues with duplicate numbers. However, if you did now is your chance to make up for it. For today’s problem you’ll be passed in an array of integers and asked to identify all the duplicate numbers.
For a bonus solve it in under O(n^2) without making use of a set/hash (unless you want to implement your own).