A lot of real people feel this way while looking for jobs. I did for a while.
"You flubbed the algorithm question. We're looking for someone with a stronger CS background."
Done. Clean and ultimately more kind.
... Unless a large number of candidates actually are getting rejected for sexist / racist / ageist reasons masked behind culture fit concerns, and the company obviously doesn't want to admit to that?
I say this as a hiring manager, by the way, knowing full well that nothing involving the hiring process is as clean and straightforward as anyone involved wants it to be.
When Triplebyte wanted me to go through their experimental interview, part of what I was asked was to "talk about" hash tables and, later, red-black trees. That seemed vague, but, prompted for what they were looking for, I covered the following:
- Hash tables are the generalization of arrays to non-integer indices. They have the access characteristics of arrays. They store data in a backing array.
- When two keys collide, the hash table can store them in a linked list (the "buckets" approach).
- If you don't like that, you can do quadratic probing, in which you repeatedly square an offset from the true hash value for that key, until you find a space in the backing array that is not currently full.
- Quadratic probing has the disadvantage that when you delete an entry from the table, you have to leave a placeholder in the backing array saying "there used to be something here!"
- If you generate an index into the backing array which is greater than its size, you would usually deal with that by taking the index modulus the size of the backing array.
- If the backing array gets too full, you would allocate a new backing array of double the size and rehash everything into the new backing array. You double the size so that amortized insert time stays constant.
- Amortized time complexity refers to the average amount of time taken for a set of completed operations.
- Red-black trees are a type of self-balancing binary tree with the property that all paths root to leaf are within a factor of two in terms of length. I can't say much more about them and wouldn't be able to write one off the top of my head.
The feedback they gave me was that, if I wanted to continue working with them, my highest priority should be to improve my knowledge of hash tables and red-black trees.
And sure, there's plenty of room for improvement in terms of red-black trees. But I am mystified as to what else they wanted for hash tables.
How is the index into the array determined?
What are the best and worst cases for algorithmic complexity of a hash table?
Disclaimer:
I don't conduct interviews at my employer. If I did, I wouldn't ask about hash tables. I was asked to talk about hash tables in a Microsoft interview years ago and my accepted answer was much less detailed than yours.
Edited to add an adjective.
Odd question. Theoretically, that choice is unique to the individual hash table, not a property of hash tables in general. I believe languages with default hash table implementations often use the machine address of the key, although obviously that won't work for keys that are compared by value, like integers and strings. I know there has been research into how to hash strings well, and I wouldn't be surprised if such research is still happening today.
> What are the best and worst cases for algorithmic complexity of a hash table?
What's a realistic worst case? A bucket-style table using linked list buckets will perform, at worst, as a linked list, except that if you add too much the backing store will be resized and everything will be rehashed. It would be quite a challenge to provide a large number of keys that all collided with each other for multiple sizes of backing array, assuming the hash function was decent. If you limit yourself to a small number of keys, the fact that you're seeing "worst-case" performance probably doesn't really matter.
What is a hash function?
Edited to omit needless words.
Otherwise, if you go down this rabbit hole, how deep does your knowledge about the basics have to be? Do you need to know every possible hash function? Their tradeoffs? Their probability distributions? The uses for each? Implementation details?
If not, why were you even asked these questions?
The interviewer then recommended that we hire one of his friends instead.
I've seen this sort of thing happen all the time, at multiple companies.