Ease Software Engineer Interview Experience — A "Debugging" Round That Was Really a Key-Value Store Without a Dictionary

Implement a key value store without a dictionary or set.

I was told that this round was going to be a debugging session. The interviewer gave the question above.

Mistakes that I made:

1. I did not start with a class definition. The interviewer pointed it out, so I eventually started with a class definition.
2. The interviewer kept asking me about cache collision. I raised an exception for the cache collision. Having the callers handle cache collision is a bad implementation. But for the key errors, it was okay.
3. I was not able to implement the cache collision handling. I proposed chaining, but he said that that would not be O(1). I should have clarified average and worst case time complexity in detail.
4. Linear probing might have been the answer. I was not able to come up with the solution within 45 minutes.