Hacker News Reader

Comment by ethbro | Hacker News Reader

Generally because employers, either through lack of effort or deliberate attempt to shield feelings, are never clear with people about why they weren't hired after an interview.

"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?

View on HN

Having been involved a bit with screening candidates, I'm not even convinced that interviewers or hiring managers are routinely clear with themselves about why they do or don't hire somebody. It seems more like a feeling that is rationalized afterward.

I strongly agree that this is true in a lot of cases, and the ahead-of-time rationalization of limiting liability helps to perpetuate the lack of necessity of a clear, defensible reason for rejection.

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.

> You flubbed the algorithm question. We're looking for someone with a stronger CS background.

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.

Here are a few questions that are not explicitly answered in your post.

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.

> How is the index into the array determined?

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.

I'll try being explicit with my first question.

What is a hash function?

Edited to omit needless words.

Isn't that a bit of strange question to ask if you wanted someone to explain hash tables? If I brought in a candidate to interview for hash tables, I would probably expect them to already have a base covering hash functions.

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?

Yes because we all use red-black trees everyday. SMH.

Were you interviewing for a position in which you'd regularly have to implement hash tables or red black trees (possibly with some novel twists) or other algorithms?

If not, why were you even asked these questions?

Triplebyte doesn't interview for positions, they just interview.

The main reason that candidates don't get honest feedback is to limit liability-- companies don't want hiring managers to say something horrible or misphrase something and then have them be liable for violating hiring discrimination laws.

And nothing but fodder for a lawsuit. There's zero to gain for the employer and plenty to lose by giving any details to a rejected candidate.

It's easier to have a relatively objective interviewing process for technical roles. OTOH management/sales roles are usually decided on subjective criteria and on how much confidence the interviewee projects.

Except that the process which exists for technical roles has been shown time and again to be pretty bad, too.

I've seen someone (who was highly skilled and highly qualified for the job) not get hired, simply because one of the interviewers on the board interpreted the candidate's well-founded confidence as arrogance. They deemed the candidate as a "bad culture fit" as a result.

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.

And it isn't usually that hard to do: https://insights.hpe.com/articles/what-to-tell-that-it-job-a... .

Reply on news.ycombinator.com