Why are interviews so often asked about linked lists?
Translator's note: original article published in a series of tweets
Probably, you have already read a bunch of explanations why the processing of linked lists is a bad question for an interview. I first want to explain where it came from. Everyone buckle up, dive into thegame theory of HISTORY!
Although the software industry flourished in the 80s, it really took off in the 90s. In this decade, the number of workers in the US industry has tripled and exceeded a million people . With the explosive growth came the need to hire a lot of employees and evaluate them.
')
What you need to evaluate? 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 out on top, but C remained close.
C worked close to hardware without unnecessary abstractions. An empty Python dictionary consumes as much as 288 bytes, that is, 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 respect, since the standard template library appeared there, but it was officially accepted only in 1998, and it was widely used much later. I remember reading overhead arguments even in 2005).
Linked lists are a necessary data structure that allows dynamic memory allocation with less risk of buffer overflow. And it was necessary to write these linked lists manually. This means that you had to manually manipulate the pointers in the 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 yes, then 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 outdated question did not disappear, but was 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.
Probably, the situation was helped to cement the bestseller “Hacking a programming interview . ” Its author, Gail Lackman McDowell, worked in her profession in 2000–2008 and probably wrote a book based on her own experience. The book has become a desktop directory of companies that conduct interviews - and linked lists are strengthened in the list of standard questions.
Without a historical context, linked lists began to be presented as a question for “problem solving skills”. But this is completely contrary to the original goal: if you test knowledge of the language, you do not want the question to be answered (that is, “solve the problem”) by people who are not familiar with this language.
For example, the question "Determine if there is a cycle in the linked list." It is assumed that the candidate should come up with a solution like "tortoise and hare", published in a richly cited scientific article of 1967 . You ask the candidate to repeat the scientific study in 30 minutes!
Perhaps, when we went to questions like "problem solving", we calibrated the complexity, taking coherent lists as a guide. Which completely distorts the scale.
(By the way: another argument for linked lists is the “verification of the fundamental knowledge of computer science.” Well, if so, why everyone is not asked about deterministic finite automata? Rice theorem? How does the compiler work? non-representative).
Summing up, the question about the coherent list was a good test of the ability to write in C, and now it has become a bad test “Can you solve problems?”
Moral: think again about asking questions about the linked lists in the interview.
Another moral: you can learn a lot from history.
(The third moral: if you see a half-finished article and think “Eh, it’s easier to launch a project in a series of tweets,” this is a trap, don’t fall into it)
Probably, you have already read a bunch of explanations why the processing of linked lists is a bad question for an interview. I first want to explain where it came from. Everyone buckle up, dive into the
Although the software industry flourished in the 80s, it really took off in the 90s. In this decade, the number of workers in the US industry has tripled and exceeded a million people . With the explosive growth came the need to hire a lot of employees and evaluate them.
')
What you need to evaluate? 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 out on top, but C remained close.
C worked close to hardware without unnecessary abstractions. An empty Python dictionary consumes as much as 288 bytes, that is, 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 respect, since the standard template library appeared there, but it was officially accepted only in 1998, and it was widely used much later. I remember reading overhead arguments even in 2005).
Linked lists are a necessary data structure that allows dynamic memory allocation with less risk of buffer overflow. And it was necessary to write these linked lists manually. This means that you had to manually manipulate the pointers in the 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 yes, then 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 outdated question did not disappear, but was 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.
Probably, the situation was helped to cement the bestseller “Hacking a programming interview . ” Its author, Gail Lackman McDowell, worked in her profession in 2000–2008 and probably wrote a book based on her own experience. The book has become a desktop directory of companies that conduct interviews - and linked lists are strengthened in the list of standard questions.
Without a historical context, linked lists began to be presented as a question for “problem solving skills”. But this is completely contrary to the original goal: if you test knowledge of the language, you do not want the question to be answered (that is, “solve the problem”) by people who are not familiar with this language.
For example, the question "Determine if there is a cycle in the linked list." It is assumed that the candidate should come up with a solution like "tortoise and hare", published in a richly cited scientific article of 1967 . You ask the candidate to repeat the scientific study in 30 minutes!
Perhaps, when we went to questions like "problem solving", we calibrated the complexity, taking coherent lists as a guide. Which completely distorts the scale.
(By the way: another argument for linked lists is the “verification of the fundamental knowledge of computer science.” Well, if so, why everyone is not asked about deterministic finite automata? Rice theorem? How does the compiler work? non-representative).
Summing up, the question about the coherent list was a good test of the ability to write in C, and now it has become a bad test “Can you solve problems?”
Moral: think again about asking questions about the linked lists in the interview.
Another moral: you can learn a lot from history.
(The third moral: if you see a half-finished article and think “Eh, it’s easier to launch a project in a series of tweets,” this is a trap, don’t fall into it)
Source: https://habr.com/ru/post/455070/
All Articles