June 6, 2019 at 16:32Why are interviews so often asked about linked lists
- Transfer
Translator's note: the original article was published in a series of tweets
. You have probably already read a bunch of explanations why processing linked lists is a bad question for an interview. First of all, I want to explain where he came from. Clip on everyone, plunge into thegame theory HISTORY!
Although the software industry flourished in the 80s, it really took off in the 90s. In this decade, the number of industry workers in the United States tripled and exceeded one million people . With explosive growth, the need came to hire a lot of employees and evaluate them.
What needs to be evaluated? Well, first of all, knowledge of languages. According to TIOBE, in 1986–2006, C was the most popular language in the world, followed by C ++. By 2006, Java came in first, but C stayed close.
C worked close to iron without unnecessary abstractions. An empty Python dictionary consumes as much as 288 bytes, i.e. 5% of the total memory of the first generation Apple II. Abstractions are too expensive, too much overhead. If you need a complex data structure, you must build it yourself using arrays, structures, and pointers.
(C ++ turned out to be better in this regard, since a standard library of templates appeared there, but it was officially adopted only in 1998, and started to be used everywhere much later. I remember reading the arguments about overhead even in 2005).
Linked lists are a necessary data structure that allows dynamic memory allocation with less risk of buffer overflows. And you had to write these linked lists manually. This means that you had to manually manipulate pointers in linked lists.
In other words, in the 90s the question “How to expand a linked list” is not a test of algorithmic thinking or knowledge of data structures, it is a question “Did you program in C?”. If so, the answer is trivial for you. If not, it is impossible to answer (ideally).
Currently, most of us do not program in C. But the obsolete question has not disappeared, but has been modified. I suspect the reason is that a huge number of programmers continued to ask and ask it, not understanding the historical context and the reasons why this question appeared.
The situation was probably helped by cementing the bestseller “Hacking a Programming Interview” . Its author Gail Luckman MacDowell worked in the specialty in 2000–2008 and probably wrote a book based on her own experience. The book has become a desktop reference for interviewing companies - and linked lists have become established in the list of standard questions.
Without a historical context, linked lists were presented as “problem-solving skills” as a question. But this completely contradicts the original goal: if you test your knowledge of the language, you don’t want people who are not familiar with this language to answer the question (that is, “solve the problem”).
For example, the question “Determine if there is a loop in the linked list”. The candidate is supposed to come up with a solution such as “tortoise and the hare,” published in a lavishly cited scientific paper of 1967 . You ask the candidate to repeat the research in 30 minutes!
Perhaps when we moved on to issues such as “problem solving”, we calibrated complexity by taking linked lists as a guide. Which completely distorts the scale.
(By the way: one more argument for linked lists is “checking the fundamental knowledge of computer science.” Well, if so, why isn't everyone asking about deterministic finite state machines? Rice's theorem? How does the compiler work? Data structures are a very small part of computer science and often unrepresentative).
To summarize, the question of a linked list was a good test of the ability to write in C, and now it has become a poor test of “Can you solve problems?”
Moral: Think again about asking questions about linked lists in an interview.
Another moral: much can be learned from history.
(Third moral: if you see a half-completed article and think, “Oh, it’s easier to launch a project in a series of tweets”, this is a trap, do not fall into it)
. You have probably already read a bunch of explanations why processing linked lists is a bad question for an interview. First of all, I want to explain where he came from. Clip on everyone, plunge into the
Although the software industry flourished in the 80s, it really took off in the 90s. In this decade, the number of industry workers in the United States tripled and exceeded one million people . With explosive growth, the need came to hire a lot of employees and evaluate them.
What needs to be evaluated? Well, first of all, knowledge of languages. According to TIOBE, in 1986–2006, C was the most popular language in the world, followed by C ++. By 2006, Java came in first, but C stayed close.
C worked close to iron without unnecessary abstractions. An empty Python dictionary consumes as much as 288 bytes, i.e. 5% of the total memory of the first generation Apple II. Abstractions are too expensive, too much overhead. If you need a complex data structure, you must build it yourself using arrays, structures, and pointers.
(C ++ turned out to be better in this regard, since a standard library of templates appeared there, but it was officially adopted only in 1998, and started to be used everywhere much later. I remember reading the arguments about overhead even in 2005).
Linked lists are a necessary data structure that allows dynamic memory allocation with less risk of buffer overflows. And you had to write these linked lists manually. This means that you had to manually manipulate pointers in linked lists.
In other words, in the 90s the question “How to expand a linked list” is not a test of algorithmic thinking or knowledge of data structures, it is a question “Did you program in C?”. If so, the answer is trivial for you. If not, it is impossible to answer (ideally).
Currently, most of us do not program in C. But the obsolete question has not disappeared, but has been modified. I suspect the reason is that a huge number of programmers continued to ask and ask it, not understanding the historical context and the reasons why this question appeared.
The situation was probably helped by cementing the bestseller “Hacking a Programming Interview” . Its author Gail Luckman MacDowell worked in the specialty in 2000–2008 and probably wrote a book based on her own experience. The book has become a desktop reference for interviewing companies - and linked lists have become established in the list of standard questions.
Without a historical context, linked lists were presented as “problem-solving skills” as a question. But this completely contradicts the original goal: if you test your knowledge of the language, you don’t want people who are not familiar with this language to answer the question (that is, “solve the problem”).
For example, the question “Determine if there is a loop in the linked list”. The candidate is supposed to come up with a solution such as “tortoise and the hare,” published in a lavishly cited scientific paper of 1967 . You ask the candidate to repeat the research in 30 minutes!
Perhaps when we moved on to issues such as “problem solving”, we calibrated complexity by taking linked lists as a guide. Which completely distorts the scale.
(By the way: one more argument for linked lists is “checking the fundamental knowledge of computer science.” Well, if so, why isn't everyone asking about deterministic finite state machines? Rice's theorem? How does the compiler work? Data structures are a very small part of computer science and often unrepresentative).
To summarize, the question of a linked list was a good test of the ability to write in C, and now it has become a poor test of “Can you solve problems?”
Moral: Think again about asking questions about linked lists in an interview.
Another moral: much can be learned from history.
(Third moral: if you see a half-completed article and think, “Oh, it’s easier to launch a project in a series of tweets”, this is a trap, do not fall into it)