I've had 4 technical interviews in my life and passed all of them. I didn't practice for them, I just have strong foundations in CS. The most criticism of interviews comes from people who can't get past them.
I once had a candidate who completely bombed the interview, one of the worst interviews I've ever done, but he had a great portfolio. I took the risk and hired him on instinct and he turned out to be an amazing frontend developer who just doesn't do well when he's on the spot standing in front of someone. Years later I recommended him to someone else who was hiring, with the caveat that "he's going to bomb the interview," which he did. The guy called me back and said, "I can't hire someone who did that badly on the interview" and I told him, "do it, you won't regret it, I promise you." He did make the hire, and it predictably went great.
Interviews work well for salespeople because interview skills and sales skills overlap a lot. Interviews don't work as well for engineers because interview skills and engineering skills overlap very little. It's just a large injection of noise into the hiring process.
The point I want to get to is: I have a buddy who I have dragged along with me (many times staking my reputation on his abilities), to every engagement I go on and this guy could not pass a how to use Microsoft Word interview. He has Aspergers and locks up and fails miserably in the interviewing process, but the honest, reality is, he is 10 times the developer I am, the guy sees patterns instantly and has a knack for code organization. He can master a new technology in a week and is hands down the best developer I have ever met.
That being said, over the years watching him has lead me to the conclusion that it is indeed the ones they hold faith in the technical interview are actually the ones that are the most stove piped and only see the world thru their limited experiences. It should be classified as a form of confirmation bias.
On the other side of things, I can say that most of the criticism of interviews I hear are from people who passed the interviews, possibly a long time ago, and are complaining that the technical interview process is inappropriate for hiring people onto their team, but they have to do it anyway. It's a common sentiment that the correlation between technical interview performance and job performance is weak.
But there are way more jobs and positions than there are candidates like you. And you can't have every company be full of superstars.
The argument is for the rest of us, having a hiring process that optimizes for superstars doesn't select the best of the rest - it selects a random subset of the rest.
I work with a lot of teams as a contractor/consultant/whatever you want to call it. I often have to bite my tongue when team members that work for my clients forget what I believe are really simple things. For example, doing lookups in a hash vs an array. That was literally the entire solution to a performance problem I solved for a client: loop through an array once and make a hash, and then do lookups from the hash. Dropped the calculation from 4 minutes to 4 seconds.
The point is, this stuff comes naturally to me. When I think about going to town and shopping at 4 stores, I curse google maps for not implementing a heuristic TSP solver. When I started playing with hashicorp consul and vault, I went and read the Raft paper just to understand what was going on.
There's a lot of people in the industry that don't think about this stuff. I probably wouldn't if it didn't just come. I've got this deeply ingrained curiosity, and some kind of innate talent to remember it all and keep drinking from the fountain.
It's hard to remember that not everyone is like me. I'm not trying to say any of this as some form of humble brag or anything. It's just really important to remember that how I think and act isn't the same as most people. That, I suspect, is why the GP called you a superstar. You likely think about things in a much deeper and more frequent way than others.
Like I mentioned in the sibling thread, I've been programming C for twenty years, and learned BASIC on a Vic-20 four yearsish earlier than that (at age 8). I learned all of that from library books.
Mostly, my algorithm for learning almost anything is "look at something that is somewhat magical, and figure out how it works inside". I've been doing that for years and years. Questions like "who programs BASIC? And how?" lead to learning about assembly. "How does BASIC store my program in memory?" "How does it translate what I type into output on the screen?" Etc.
Not to ramble on... unfortunately, I don't know of such a resource, and I don't really know what material it'd cover if I wrote it.
So one of my problems is that I don't actually know what I'm missing out on.
I haven't needed to implement my own hashing table or methods on a real world project, as far as I can remember, but yes, I've absolutely written code that would have performed miserably if I hadn't known to use a hash rather than an array. I just didn't custom roll the hash, I used the hashing methods available to me in that language.
I'm aware of what a hash is, and what a hashing function is, and how collisions are resolved, and strategies to handle them. But I'm also almost certain I've been screened out of jobs because I couldn't implement a hash with a good hashing function in 45 minutes at the whiteboard. I just don't walk around ready to do this.
Assuming you're looking for a 32-bit hash value, my lazy whiteboard hash function would probably be something like:
- for strings, xor the bytes a word at a time.
- for ints, just use the 32-bit value
- for objects, let them provide their own, and if none is provided just use their memory address (this assumes that the objects don't have equality operators... that gets more complicated. If an object implements an equality operator, it also needs to implement a hash operator.)
These rules are by no means optimal, but they'd probably do as good enough for something that's not super high performance.
It also bears keeping in mind, I learned C twenty years ago, at the tender age of 12. Self-taught from the book that came with the compiler floppy[1]. We wouldn't have Internet at home for another 2 years, so I would occasionally persuade my parents to take me to a local Internet cafe for an hour to slurp up as much as I could at 28.8kbps and scribble it down. Bit manipulation operators are pretty deep in my soul at this point.
---
So going back to the original discussion... that came pretty natural to me. "How would I implement a hash function?" The brain whirrs a little bit and says "hey, here's some things to think about". I am 100% aware that this isn't typical, and do not expect others to have the same experience.
In fact, if I were hiring someone, I would be totally satisfied with an answer of "I'm not sure how to implement a hash function off the top of my head. It takes the object/value that we're going to insert into the hash table and turns it into a number that we can use to index into the appropriate bucket. Can we look one up?"
Hell, I'd probably be satisfied with "Here's when I'd use a hash table, and here's when I'd use an array. I've never implemented a hash table but I'd love to know how it works under the hood."
For me when hiring, the two biggest things I'm looking for are the ability to decompose problems into manageable parts, and a curiosity about how everything works. Those two things together tend to make any other knowledge gaps totally manageable; I'm not omniscient, but my desire to learn as much as I can about anything I don't understand can sometimes give off that illusion :P.
Overall, yeah, interviewers want to see that hash map largely written, often at a white board. Minor errors and bits of pseudocode are ok, but it should pretty much work.
YMMV, of course, but it isn't just me.
http://steve-yegge.blogspot.com/2008/03/get-that-job-at-goog...
"Hashtables: hashtables are arguably the single most important data structure known to mankind. You absolutely have to know how they work. Again, it's like one chapter in one data structures book, so just go read about them. You should be able to implement one using only arrays in your favorite language, in about the space of one interview."
Of course, Steve Yegge isn't the final word on prepping for google interviews, and I only had one experience there myself, but yeah, I'd say he's pretty spot on here (in fact, the google recruiter who arranged my interviews forwarded me the Yegge blog post, though I'd already read it earlier).
I assume that this should be value modulo m, where m is actual size of the backing array.
for strings, xor the bytes a word at a time.
Well, for strings the same, that is, final output modulo m.
Perhaps my take on things is different since my degrees are in math, so I don't have a bunch of 'canned' algorithms stored in my head, and so in a whiteboard would come up with my own technique, even for possibly basic things like trees / sorting.
It's the same for CS; basic knowledge of algorithms and data structures, and how these can be composed, is what a technical interview tests.
But I did have to spend a few hours looking up and refreshing my knowledge of tree traversal. If I'd taken a technical interview exam on tree traversal prior to that four hours or refreshing my memory, I almost certainly would have failed. And yet I within the day I was able to write the code.
They aren't testing whether you can look it up and do it, they're testing whether you have it all loaded into short term memory, on the spot.
Like a lot of people, I'm tired of having to reload it all and essentially retake my data structures exam. A lot of us just don't want to interview anymore. I know that if I need to, I can write a BFS or find all permutations of a set. If the opportunity is good enough, sure, I'll study up and get ready to do this at a whiteboard, but it's boring and unpleasant at this point, and I might not get or want the job, so at this point, I rarely bother.
Tech interviews are a big part of why tech companies are experiencing a "shortage" of applicants. They're hardly the only reason, but I'm pretty convinced they are a reason.
I'm still in university, but have managed to intern at a few a places so far and found the critical parts of each interview to be nearly identical. Microsoft and Google asked questions that boiled down to basic data structure problems, and Dropbox asked a simple backtracking problem. The problems weren't ones I had specifically prepared for, but were ones that I could break down because of my foundations in CS.
The only interview I've failed was my first one. The interviewer asked me to implement a Gaussian blur on a small whiteboard; between not knowing the algorithm and not having enough room, I flopped pretty hard. There wasn't a realistic way to prepare for this question, it was just one of those things you had to know at the time.
Given that there is a certain amount of randomness in interviews, of course it's possible to have a streak of successes. I don't look at a die that I just rolled 4 times and never got a 6 and determine it's loaded.