Twitter | Search | |
Hillel Wayne
You've probably seen a bunch of rants on why "do thing with linked list" is a terrible interview question. I'd like to explain why "do thing with linked list" is an interview question in the first place. Buckle up everyone, it's time for some g̶a̶m̶e̶ ̶t̶h̶e̶o̶r̶y̶ HISTORY!
Reply Retweet Like More
Hillel Wayne 10 Feb 18
Replying to @hillelogram
While the software industry was thriving in the 80's, it really took off in the 90's. Between 90 and 00 the number of software employees tripled to over a million people. With the explosion in demand comes the need to recruit and evaluate at scale.
Reply Retweet Like
Hillel Wayne 10 Feb 18
Replying to @hillelogram
What do you need to evaluate? Well, language competence for one. And according to the TIOBE, between 1986-2006 the most popular language in the world was C, followed by C++. By 2006 Java was more popular, but C was still close behind.
Reply Retweet Like
Hillel Wayne 10 Feb 18
Replying to @hillelogram
C is bare metal. An empty python dict is 288 bytes, or 5% of a 1st gen Apple 2's RAM. Abstractions are too expensive to provide, too much overhead. If you want a complex data structure, you have to build it yourself with arrays, structs, and pointers.
Reply Retweet Like
Hillel Wayne 10 Feb 18
Replying to @hillelogram
((C++ was a little better in this regard because it had the standard template library, but this was only formally adopted in 1998 and entered common use much later than that. I remember reading arguments about the overhead as late as 2005.))
Reply Retweet Like
Hillel Wayne 10 Feb 18
Replying to @hillelogram
Linked lists are a necessary data structure, since they give you dynamic memory allocation with less danger of buffer overruns. Which means you had to write linked lists by hand. Which means you had to manipulate the pointers in linked lists by hand.
Reply Retweet Like
Hillel Wayne 10 Feb 18
Replying to @hillelogram
In other words, back in the 90's "how do you reverse a linked list" isn't about "algorithmic thinking" or "data structures", it's _have you coded in C_. If you have, the question is trivial. If you haven't, the question was (ideally) impossible.
Reply Retweet Like
Hillel Wayne 10 Feb 18
Replying to @hillelogram
Nowadays, most of us don't code in C. Rather than get rid of the question, it seems to have morphed. I suspect this is because a large block of programmers were asked it and continued to ask it, unaware of how deeply tied to the historical context the question actually was.
Reply Retweet Like
Hillel Wayne 10 Feb 18
Replying to @hillelogram
I think "Cracking the Coding Interview" also helped cement it. Laackmann McDowell did most of her engineering work 2000-2008 and likely wrote it based on her own experiences. CCI became the playbook companies used for interviewing and linked lists stuck.
Reply Retweet Like
Hillel Wayne 10 Feb 18
Replying to @hillelogram
Removed from the historical context, linked lists got rebranded as "problem solving skills". But this seems the opposite of what you'd expect from the original questions: if you're testing language familiarity, you DON'T want people to be able to fake it!
Reply Retweet Like
Hillel Wayne 10 Feb 18
Replying to @hillelogram
Take "determine if a linked list has a cycle in it." The solution people are supposed to come up with, "Tortoise and Hare", was AFAICT published in a heavily-cited 1967 research paper. You're asking a candidate to reinvent CS research in 30 minutes!
Reply Retweet Like
Hillel Wayne 10 Feb 18
Replying to @hillelogram
I'm randomly guessing that, as we moved more to "problem solving" questions, we calibrated difficulty based on linked lists as a reference point. Which throws the entire scale out of whack.
Reply Retweet Like
Hillel Wayne 10 Feb 18
Replying to @hillelogram
(tangent: another argument for linked lists is they "test fundamental CS skills". If so, why aren't we also tested on DFAs? Rice's Theorem? How a compiler works? Data structures are a very small part of CS and often nonrepresentative.)
Reply Retweet Like
Hillel Wayne 10 Feb 18
Replying to @hillelogram
To summarize, linked list questions used to be a good test of "can you write C" and are now a bad test of "can you solve problems". Moral: Reconsider using linked lists questions in interviews. Other Moral: There's a hell of a lot we can learn from history.
Reply Retweet Like
Hillel Wayne 10 Feb 18
Replying to @hillelogram
(moral three next time I see a half-finished draft of an essay and think "eh it'll be less effort to just tweetstorm the draft" it's a trap DON'T FALL FOR IT)
Reply Retweet Like