The linked list thing happened to me very recently.
3 interview rounds and all asked linked lists questions back to back.
I was very honest in that in my 2 years on the job, (ML, DS) I had never once run into a situation where I would use a linked list. I didn't remember if Python even had a default linked list implementation and I decided to implement it from scratch. Wrong decision.
I didn't get through, but the choice of linked lists was quite bizarre, esp. for a Data Scientist position. I would have much preferred a coding question that was relevant to the job or a take home assignment.
I've been doing python for 14+ years now. Never been asked about linked-lists, but was asked about prototypical inheritance in javascript (didn't get that job -- in retrospect, very glad i didn't). Now that I'm on the other side of the interviewing table, i always start off by saying "I think coding interviews are stressful as heck, so you should know that what I'm looking for isn't the "right" answer, it's that we both learn something. You can google your way to the right result, but it takes much more skill to implement in a team." Basically I try to turn interviews into a learning experience. With that lens, I tend to have a much better appreciation about a candidate than forcing them to pick up a marker and write a loop on a whiteboard.
Went through interview rounds last year and I was asked a recursion questions for a DS interview. Been doing this for 10 years and have never come across a data problem that only recursion could solve. But I remembered it from university days, so I cobbled together a working answer.
At the end of the interview, I asked the interviewer to give me one scenario where a recursive solution would be the most efficient one. Blank stares.
That was my eye-opening moment. I would never work for a place that asks these ridiculously outdated copy-paste interview questions. Can't believe I put up with that shit for so long.
> Been doing this for 10 years and have never come across a data problem that only recursion could solve
That makes sense - there are no such problems (which is obvious if you consider the fact that Turing machines don't have recursion - nor functions, for that matter).
> I asked the interviewer to give me one scenario where a recursive solution would be the most efficient one
That also makes sense, as recursion usually isn't a technique that will bring an efficiency edge over non-recursive technique. It might often bring maintainability and understandability edge, though.
Solving the problem using recursion highlights the fact that it has, well, a recursive solution - which means that the solution can be expressed as a set of operations on top of solution to a smaller instance of the original problem. This can be an important property to notice about a problem, whether or not you're going to solve it with the function that calls itself.
Additionally, some problems have a solution that can be nicely expressed as a set of mutually recursive functions (instead of just a single recursive function). These are harder to express non-recursively. Many parsers are written like this, for example the C# parser: https://news.ycombinator.com/item?id=13915150
It would be more difficult to read and maintain any solution to many problems where you are operating on nested objects, especially if the nesting is more than a few levels deep or even arbitrarily deep, without using recursion. Also generating such objects, such as with nested parentheses, is easier as well.
>> one scenario where a recursive solution would be the most efficient one
Funnily enough, this is also what made me stop the Scala Coursera midway. They focus way too much on converting various problems into Tail-call recursion because Scala can optimize them.
That's the way to do it. Carefully dissect the ambiguous signals potential employers emit throughout their process, and form an impression around the time of an offer so you know if you'd keep negotiating.
Too often, the interviewers are just trying to emulate seeming smart out of some ego thing, haven't been trained how to interview and just emulate what they think they're supposed to do, or are too lazy to ask real-world questions.
IIRC from CS, every recursion problem can be turned into an iterative one. Even many production compilers contain handmade parsers are recursive primarily for maintainability, not for technical reasons. There are plenty of ways to make bottom-up parsers (LALR parser generators) that don't use recursion but they aren't as useful at generating diagnostics, especially explaining parse error reasons in human-readible language.
the way I see the problem is company say they want an expert in X where x might be
1- writing driver and OS internal in assembly/ ANSI C
2- writing video game physic engine in c++/CUDA
3- writing machine learning model in Python/R
but the interview is always something like
1- reverse a (linked list.tree) using your language of choice
2- write code to solve the N-queen problem ...
Basically they ask bad question to evaluate data structure knowledge and ability to solve riddle.
But they ask 0 question related to the specific expertise required for the role they are trying to fill.
exactly.. this is so stupid in my opinion and just signals another 'we only hire the best.. ya know, like google'.. implementing breadth-first-search, or a linked-list insert during a coding interview is quite possibly the most ridiculous way to determine if a potential hire will be able be productive at your company.. which, as we all know, will be writing spring boot services that return json.
now, I should also say that if your company builds libraries that actually implement these algorithms in a better, stronger, faster way, then of course by all means ask away. And, I also get that understanding what I linked list, hash map, trie, graph, etc.. is an important signal for interviewers that you've got some computer 'science' background. However, more relevant question might be why they might be used.. or the algorithmic complexity of one over the other (since in practice we're just going to use a collection library anyway). I might argue that another (equally irrelevant) signal that you've studied computer science would be ask what the integral of 1/x is.
I think it's very possible to pass all the courses and still be a pretty lousy programmer. If I read someone's code I'm often not really looking for the correctness at the beginning, but whether they get programming i.e. it's more than just characters on a screen which pass the tests
I think it would be rude to give identifiable examples, but the things that trigger my subconscious when reading good code are often the perfect balance of aesthetics, pragmatism, and mechanical sympathy for one's surroundings. Understanding even the absolute basics of how modern processors actually work is a huge plus for me because I'm biased.
The absolute basics also apply obviously - good comments, variable names that I don't have to run the program to divine the meaning of for example.
I wouldn't try to judge this based on an interview or whiteboard however, real code written for fun rather than dance monkey dance
I failed a interview for not remembering the internals of a hashmap. I learned that 20 years ago in university and have honestly never needed to consider it since then. I work with databases, servers and web apps. I was actually surprised at how many of the computer science fundamentals that I did remember after 20 years. While an understanding of how these things work is useful it's mostly unrelated to the job.
I've asked linked list questions before and here's why I sometimes use them.
I don't have a ton of extra time in an interview and I can expect a candidate to be familiar with linked lists or I can explain the data structure very quickly.
Linked list problems are relatively simple. Candidates are under a fair bit of stress during an interview so simple problems become harder than they would normally be. You also don't have time in an interview to dig into very complex problems. With a linked list I can give a problem that most candidates can work through in the time we've got and then ask follow up questions based on how they approached and solved the problem.
How many programmers actually need to implement linked lists in day to day jobs? If they are doing that, then they are likely to be over engineering other parts of the system, when there is a well tested, documented library available.
I didn't say I ask a candidate to implement a linked list. I sometimes ask them to do something using a linked list. Using basic data structures is something I would expect most people I interview to do regularly in their day to day jobs.
Why not write something more practical? For example, have them write a class that demonstrates a few design patterns like dependency injection, has a basic interface it implements (for example, a DrawPixelArray method), that kind of thing. This to me is far more informative about skills the person would be using in their day-to-day job.
It depends on the job, I think. In some positions, it is a lot more "practical" to have a command of data structures and algorithmic thinking than it is to implement fancy OO design patterns.
EDIT: A quick glance at OP's profile suggests that they are an experienced C++ programmer. I definitely think being able to handle pointers is more practical/fundamental skill than dependency injection in that context.
To be clear, I don't ask them to write a linked list class. I would typically be asking them how they would implement a function that takes a linked list and has to do something with it.
A lot depends on who I'm interviewing and what I'm looking for for that role. I don't think there's a one size fits all interview question for programming jobs. In the above example I might only want them to explain how they would solve it to see their problem solving abilities. In other cases I might want to see some whiteboard quality code and we can segue into other topics like debugging or testing the code they wrote. Your example probably wouldn't be suitable for an entry level candidate who I would expect would need more guidance for things like class or interface design but I'd expect to be able to implement functions given an API.
I disagree with the premise that the following are contradictory:
1. “It tests CS fundamentals.”
2. “It tests reasoning through a new problem.”
Both can be measured in an interview together, using well-known CS concepts to reason through a new problem based on CS fundamentals.
Especially today, as almost everyone uses standard library implementations, asking candidates how those implementations actually work, and then working through a variation of them (e.g. add an unusual requirement) is very useful in an interview context.
Everyone "knows" what a Linked List, so you don't have to spend a lot of valuable interview time explaining it. The implementation for the simple case is short enough it can be quickly written out. Then you can add a novel requirement for the candidate to extend their implementation. Now you've checked all 3 boxes:
1. Knowledge of CS fundamentals
2. Using well-known CS concepts
3. Reasoning through a new problem
If interviewers were longer, or used alternate paradigms (take-home exercises or pair-programming), then much better questions can be offered.
But ultimately, doesn't all software engineering come down to the 3 things I described? Sure, the context is different if you're a Frontend vs Backend vs Mobile vs Embedded person, I hope the interviewer is adapting for that and not asking everyone the same Linked List question.
* taken a 'real' CS class
* understand the choices that library implementations make
* have probably had to deal with large dynamic data sets and runtime optimization.
Most of the questions are predictable, but not knowing anything about them is a huge red flag.
This. What happens in a coding interview is incredibly well documented at this point. If you can't be bothered to prepare, study, and brush up coding skills for interviews, I do not want to hire you. I tend to ask medium difficulty questions because I am looking for 1) ability to reason through a problem and 2) professionalism and motivation for a career.
The point of an interview is to evaluate a candidate's fit for a particular role. This reads to me like the evaluation criteria is whether the candidate prepared for interviews or not. I don't understand this worldview at all, and I've been a hiring manager at both startups and FAANG. What's also well documented is that studying Leetcode is about keeping a warm cache of solutions to common problems at interview time, and much less to do with reasoning through problems.
> I tend to ask medium difficulty questions because I am looking for 1) ability to reason through a problem and 2) professionalism and motivation for a career.
Congrats! You are selecting for people who 1) rote problems for interviews and 2) motivation to clear your interview.
"What happens in a coding interview is incredibly well documented at this point."
Indeed. And so much so that a whole industry has sprung up to teach people how to play the game. Pretend you've never heard the problem before despite having learned to solve it via Hackerrank or Leetcode. Ask lots of "clarifying questions" to the interviewer to show them how "you" think. Then in a feigned stroke of intuition produce the optimal solution on the whiteboard.
>"If you can't be bothered to prepare, study, and brush up coding skills for interviews, I do not want to hire you."
"coding skills for interviews"? As opposed to coding skills required for the actual role your company needs to fill? It never occurs to you that good candidates might be too busy making deadlines to spend their nights and weekends working through LeetCode problems? This is why hiring is broken.
An ex-collegue was into hacker rank style things. I saw him doing one and pointed out that it's the sort of stuff he will never use on the job. A lot of the stuff he builds is overengineered and he is more interested in producing clever code than maintainable code.
So the author's theories certainly resonate. I started my professional career in the mid-80s and yes, having facility with C and pointers in particular was critical. I can remember asking potential candidates around that time to explain the practical differences between doubly dimensioned arrays and pointers to pointers.
Without a doubt, a SIGSEGV was always a prelude to a painful session with adb trying to track down where your arithmetic had gone wrong.
Please everyone keep asking for cs fundamentals questions for interviews. I get to keep picking up great devs that get annoyed at all the weird questions.
I ask about how applicants have implemented things and bang around the edges with questions to gauge the depth of their understanding.
I myself flat out told recruiters I don't do whiteboard coding. If the interview requires that, don't bother putting me up. I'm more than happy to answer architecture questions, deep dive on what I've done, look at my github. However, I refuse to stand there and whiteboard algorithms for employers. I'm not good at coding when people stare at me, so I'm not going to.
In turn, I don't do that to candidates. Having a technical dialog is great. You can easily sort of the pretenders and get a real good sense if they are a good team player, which ranks almost as highly as technical chops.
This is really interesting. If it's not prying too personally, mind sharing where you're at or some example companies?
I've interviewed at maybe 15-20 companies over the years and never not had to whiteboard or live code in some way. The thought of not having to seems so foreign to me.
I feel like whiteboarding has only gotten popular in the last 10 years, maybe less. I've been at six companies in that span, interviewing at probably 12-14 total.
Out of the six, four have been tech startups including the one I am in now. The industries have been cybersecurity (x2), online retail, and online marketing.
The two non-startups have been in education and healthcare.
2016 was the last time I didn't have the luxury of looking while jobless, but I was still pretty picky. I already knew I didn't like white boarding, so I started to warn recruiters that I wasn't good at it. Two early interviews, I told recruiters this, and they both urged me to go to their interviews anyway. I went ahead thinking it would be good practice.
Not surprisingly, I wasn't offered because I just wasn't that interested, and it showed in the interviews. I remember getting a bit curt in one interview because the last person that I interviewed with (going on 4 hours), asked me the same coding question as the first person.
After that experience, I became more inflexible on my no-coding interview requirements. It probably was just dumb luck, but this wasn't a problem, I was told. Two more companies after that were at companies that did architecture interviews centered around data platforms, and I eventually took one offer.
Whiteboard has actually become less common in the last ten years in my opinion (20 years in the industry). It's moved towards take home exercises, which are a more realistic gauge of what you are doing, but are just such a time sink. They take a minimum of half a day, and then you are pushing out fairly rushed code, so not the best.
Everyone wants a miniature throwaway app, including project setup and test usually. Then you get a problem when one library you wanted to use doesn't install easily, or you have some random problem that takes an hour to debug.
Last time I got failed on a number of things many of which weren't asked for. Linting failed on two whitespaces, as I didn't have pylint set up on my home machine. I should have returned json, rather than html, despite the task asking for a 'page, no need for styling'. And I didn't provide a setup.py, despite it not being asked for. I provided the most difficult integration test to implement, but they complained I didn't add more unit tests, even though they has said to describe what tests you would have implemented if you were short on time, which I did.
Have you made any bad hires that way? I used to think that I could gauge someone's depth of understanding by asking pointed questions about past projects, but after doing that several times and following it up with a simple coding problem that they totally flailed around on, or having a colleague tell me that they failed a simple coding problem in their interview, I realized that some people are just very good at faking understanding at that level (talking about code but not actually coding). Especially if it's on their "own" project that they're familiar with and have practiced responses to.
So far its been pretty solid. My key approach is to ask about the last task they were working on. Then keep asking further questions on it to gauge their depth of understanding.
For someone I want to hire there is almost always a "Beautiful Mind" moment. They stop trying to distill information and start just start talking about all the little details they needed to iron out to get it working right. That when I know they actually did the work and are not just a taking credit for being on a project.
Why did you choose that over other approaches?
Did you use an ORM or raw queries?
What was the O(n) on that operation?
What kind of database did you access?
How did you add that to the CI/CD pipeline?
Just flex the questions for whatever and the people that did not do the work fall apart. Then you have solid devs that show up every day and do the work. You also get the bonus of the dev knowing their new boss knows their shit.
On the other hand, there are some common data structures that are essential in day to day software development.
Hash maps are one of them. If you're not aware of their performance benefits, it will probably impact the quality of your work.
I think it would be fair to test for that with a scenario where a hash map is required, and see what they do. No coding involved, just "what would you do here".
The majority of work these days are web apps, and the bottlenecks are usually database query and IO issues. Many can be solved with an appropriate index. If you have a slow Django app, I would guess than 9 out of 10 times it is someone who is letting the ORM produce far too many queries in loops. Hashmaps are never something I have needed to look into personally, but I guess it depends on exactly what you are coding.
Rereading your comment, do you mean just using a hashmap / dictionary, or do you mean writing your own hashing functions? The first is invaluable, but I have never had the need for the second (pretty sure you could define your own hashing functions in Perl, but I never found the need).
This is, and has been forever, my playbook in an interview. It reveals so much about coding ability, and about communication skills.
We don't ask people to spell things out if they claim they speak English on their resume, so why bother with the basics? I'll trust that the schools are doing their job.
Doing a linked list is my primary question for coding interviews. It is something I think everyone has seen or done in school so should be pretty easy. It is also small enough that it can be explained during an interview if they don't know. A linked list can be programmed in any modern language that has references. It lets me get some insight into how the person thinks and works through problems.
Primary insights I am looking at:
How does the candidate approach the problem as stated?
Do they ask any clarifying questions?
Can they explain the code they have written?
Did they listen to what I asked for? Some people who have been studying will just start typing what they have memorized.
Are they doing anything interesting with the language they have chosen? Are they able to answer questions about their choices?
Most of the time people will get through some kind of add method, and a delete method. Usually by that time I have enough information to move past that question. Doing puzzles like reverse the list don't really add any more information and I have stopped asking that even if there is time.
> It is something I think everyone has seen or done in school so should be pretty easy
Only if they studied CS! A lot of good devs didn't. However, as you're willing to explain the concept during the interview, I think your usage is reasonable.
> It is something I think everyone has seen or done in school so should be pretty easy.
Here are some things everyone has seen or done in school : proofs on in theorems on geometry, integral of an obscure function. I am pretty sure it should be "easy" to answer them in an interview.
One of the items under discussion is appropriate to the group under discussion (programmers), the other is not. For the most part we don't care if programmers can integrate functions or prove theorems, we do care if they can program.
Whether linked list questions are appropriate or not is another matter, but at least they're in the correct domain.
> Whether linked list questions are appropriate or not is another matter, but at least they're in the correct domain.
It is not just "another" matter, it is THE matter. The correct domain is a vast space. The OP wants the interviewee to go through something they know instead of knowing more about the interviewee. It's lazy interviewing - it makes no attempt to understand the person's "appropriate" skills. If you care if they can program, you won't ask a LinkedList question. For the most part, neither the interviewer nor the interview would ever program a LinkedList apart from a few courses in university.
> For the most part, neither the interviewer nor the interview would ever program a LinkedList apart from a few courses in university.
And many non-professional athletes going out for a tryout will be put into artificial situations as well instead of being placed on the team and taken to an actual competition for their trial, it doesn't mean that tryouts are fundamentally flawed.
Linked list questions (or other data structure/algorithm questions) are synthetic questions used to gauge competence of individuals because we usually don't get the option to hire someone for a month and try them out in a real world scenario. If they're the sum of the interview, then they're moronic; if they're a portion of the interview, then they're (arguably) reasonable. Certainly more reasonable than the non-programming domain topics you listed.
> And many non-professional athletes going out for a tryout will be put into artificial situations as well instead of being placed on the team and taken to an actual competition for their trial, it doesn't mean that tryouts are fundamentally flawed.
Athletes play games that are universally timed, programmers don't. Besides sportsmen and athletes are regularly tried out in "lower" games before they graduate to a "higher" level.
Linked List questions select for university education and memorising problems, not programming. You are making a false binary of "whiteboard or hire for 1 month" which once gain shows laziness as an interviewer. If you are so proficient in your field, you should be able to gauge a competence of an individual from their past work. It shows more about the interviewr that they resort to some cookie-cutter university course questions to decide competence.
It's kind of funny that linked lists are almost never an appropriate choice on modern systems because of their poor locality and cache performance. Linked lists were a much better fit for 1970s and early 1980s microprocessors that almost never had caches (memory access time in the 1970s was similar to clock speed).
That means linked lists are increasingly relegated to toy problems and unusual domains. They're no longer really a practical tool to organize data - it would be better in many cases to use an array and copy the entire contents on insert.
On my work we do use linked lists, they are simple and convenient to collect a few items of data together when the item count is not known in advance. The trick is to allocate linked list structures from the arena allocator (which keeps these structures close in memory). The programs in my work may run for days and may use terabytes of RAM (EDA chip design verification).
I agree that linked lists could be optimized, but usually they are not the worst offender. The biggest gains in performance usually happen when an accidental O(n^2) slowdown is replaced with a correct n*log(n) version.
There are a couple of large red flags here, but why not just use an array instead of an arena allocator and a linked list (of pointers I'm guessing).
If you need a linked list, use an array with indices and you can cut the size in half if you don't need 64 bit integers. If it has to be enormous, make a linked list of arrays for better locality.
Our arena allocator does not reuse memory for simplicity (it allocates only forward, like a stack). A lot of the libc malloc complexity comes from the need to manage deallocated pieces of memory.
Which means that using array over this arena would waste more memory (due to array resizing) than linked list. When array is resized, the unused memory from the old array will stay unused until the whole arena is deallocated.
> Which means that using array over this arena would waste more memory (due to array resizing) than linked list
I think you are way off track. The point here is that whatever you are doing is unnecessary. You don't need an arena and probably don't need a linked list. You are using an arena allocator as an array already if you are never freeing anything. Just make fewer large allocations.
> does not reuse memory for simplicity (it allocates only forward, like a stack)
First, stacks can shrink when items are popped off. Second, if you are using an 'arena allocator' and a linked list on top of it when you could actually just allocate memory into an array are you really gaining simplicity? You are purposely not reusing memory and have a program using terabytes of memory and running for multiple days. Is that really simplicity?
Pretty much everything you have said so far is an enormous red flag, but the good news is that there are probably ways where you can use orders of magnitude less time and memory while making the program more straight forward.
The problem solved by arena allocators here is to avoid many calls to malloc. System allocator is slow, especially in multithreaded environment. Instead of calling malloc 1000 times to allocate 1000 small pieces (like 16 bytes sized each), malloc is called once and then all the small pieces are carved from the big memory block.
The arena allocators are also popular in game development. Memory is allocated from the arena allocator during frame processing (16 ms), and all this allocated memory is deallocated at once at the end of the frame.
Again, I don't understand why you wouldn't just allocate large arrays, especially knowing that excessive memory allocation is slow and going to lock on top of that (you could use jemalloc, but that is orthogonal here).
> Instead of calling malloc 1000 times to allocate 1000 small pieces (like 16 bytes sized each), malloc is called once and then all the small pieces are carved from the big memory block.
No one who has any idea about performance is saying lots of memory allocations are ok. It sounds like what you are doing though is allocating arrays but then using them for 'arena allocators' when you could just use them directly and use indices for ordering if you need that.
> The arena allocators are also popular in game development. Memory is allocated from the arena allocator during frame processing (16 ms), and all this allocated memory is deallocated at once at the end of the frame.
I would ask why the memory needs to be deallocated at the end of each frame. A C++ vector can be cleared without releasing its capacity. What you really want is to have all the memory that you need allocated once so it can be reused over and over easily. There is no reason to involve an allocator on a frame to frame basis of a video game unless you go over what you already thought you would need.
If you have 'millions' of 'memory managers', why not just use a few big arrays? It really seems like an over complication of a problem that doesn't need to be difficult. I'm surprised no one would take the time to clean that out if there are terabytes of memory used and multiple days for single program runs.
I think these are the types of questions that should be asked long before run times end up being measured in days and memory usage is measured in terabytes.
Linked lists are good for when you need inserts and deletes in the middle of a list and traditional linked lists made from memory allocations and pointers are obsolete.
Even if you don't know how many items you will have in advance, allocating large arrays still works. You can always chain large arrays together. The strange thing is that you are saying you use linked lists, but you are allocating them out of arrays that are already allocated.
Yes, it works fine. I will only add that we do reuse memory. The program deallocates memory managers when they are no longer needed (there could be millions of them at any single time).
I one time took a class that introduced every linked data structure (lists, trees, stacks, queues, etc) with statically allocated arrays. Only later did they show the dynamic memory implementations. I thought it was a bit weird at the time, but now I guess it was to get students to focus on the data structure, instead of worry about pointers.
I like reading about software history and this is a new angle to approach it from. When did people start testing one another on this particular thing, and why not this other thing?
I learned how to write linked lists in some first year comp sci course in the mid-90s and used them extensively in my first job after graduating, which was writing database software in C. I'm sure I was asked about them in various interviews afterwards, most of which involved no C whatsoever, and I'm equally sure I thought this was a completely normal thing to ask. In retrospect, it does seem strange.
An interesting dive into the cargo cult of tech interviews. Maybe I misunderstand the author's methodology. Here's the chain of reasoning he seems to be advancing:
1. Linked list questions are often about pointer manipulation.
2. C and Pascal make frequent use of pointer manipulation.
3. If Usenet posts that mention C and Pascal mention pointer manipulation more than Prolog, Lisp, and Smalltalk posts mention it, linked list questions must have been designed to test for experience with C and Pascal.
The last inference seems either extremely circumstantial or trivially true. Prolog doesn't expose pointers to the user, as far as I know. Smalltalk just seems to have object references. If pointers are only available in C and Pascal, then it stands to reason that only C and Pascal posts will mention pointers. There's nothing about linked lists in this argument.
So, sure, a category of interview questions that crucially rely on pointer manipulation does test a candidate's understanding of pointer manipulation. But looking at Usenet posts does not offer any additional support for this explanation.
I can also imagine that those questions were posed in C or Pascal, which itself obviously filters for people who have used C or Pascal.
(3) is backwards: it's a prediction, not a deduction. I had the theory "LL questions were meant to test C/Pascal knowledge", based on studying `net.jobs`. I then came up with a test for the theory: if it was true, then the C and Pascal newsgroups would spend a lot more time talking about pointers and memory manipulation than other language newsgroups. That turned out to be true. If it turned out to be false, then other programmers are likely spending as much time thinking about memory manipulation as C/Pascal programmers, meaning LL questions wouldn't be a good shibboleth.
That doesn't mean the theory is true, but the fact it withstood my prediction gives me more confidence in it, the same way I'd be more confident in a scientific. Another prediction would be that C/Pascal manuals spend more time on LL algorithms than manuals for other languages. That one I haven't (yet) checked.
I understood that you were testing a hypothesis. My point is that the test is only improving our confidence about LL questions marginally or not at all.
Specifically, you already have the premises that LL is about pointers, and that some languages are far more "about pointers" than others. Validating the fact that people talk about pointers in posts on languages that support pointers and that they don't talk about pointers in posts on languages that don't support them is a forgone conclusion.
Like, I'm buying the argument overall and I think it's a useful dive through history, I'm just not buying the test.
It's a simple question with radically different answers.
I had people not knowing what it is, some says they find an existing library and few excitedly explain on a whiteboard how they work, single vs double-linked etc.
These days I would not reject an interviewee if they didn't know about linked lists, but depending on their answer it may be what makes their resume end up in the "2nd interview" pile instead of "maybe".
An anecdote:
I prepared a little bit with Hackerrank for my Google interview (in Oct 2018) and never once encountered a problem where a linked list would be remotely useful. I also watched the YT video about why LL are useless in practice in most cases (cache locality etc) and I therefore eliminated them +- completely from my "toolset" (despite being actually pretty comfortable with them (spent a lot of time implementing sort algorithms on single & double linked lists).
Then, one of the interviews had some problem about a scenario that wasn't actually that far away from something one could encounter in real life and the optimal solution (by far) was with a simple linked list.
I completely blew it. I devised some convoluted MinHeap solution with Log(n) that was confusing as hell and my interviewer was wondering why he's wasting his time (he didn't tell but it was my impression). In the last few seconds he said something like "do you know a data structure with cheap inserts at the end and start" and everything was clear (but to late).
No hard feelings, wouldn't have hired myself after that performance as well.
My personal relationship with linked lists has had its highs and lows. When I was teaching myself C as a teenager, the linked list was the first pointer-based data structure I implemented myself, and the cause of so very many segfaults. I was so delighted to understand how it worked. But time passed, I eventually discovered languages that implement lists for you, and my relief was infinite. I'm glad I understand how linked lists work and I hope I rarely need that knowledge.
Unfortunately McDowell's Interview Book seems unstoppable and I expect to be answering list questions forever.
I used to ask about linked list (and connection pools) as a stage two fizzbuzz just to give a straightforward requirement to see how people think through something that has a little bit of a hard bit and might make the interviewee think to make sure requirements are met.
It also helps a little with culture to weed out the “I’d use a library” or “I’d Google it” as the purpose is to just walk through how to code something.
I never asked anyone to write a linked list, but it is sort of straightforward to write in a short period of time.
What's wrong with "I'd use a library" or "I'd Google it"?
I think that's the most honest answer, and someone in the field for 10+ years I _prefer_ those answers. I don't want someone reinventing a library if a good one exists, and I hope people Google answers (or use Stack Overflow) to find solutions that are a bit more vetted. I was at a company where they pushed for all their own coding and it was a _mess_. The amount of proprietary technology we had to maintain was ridiculous, and in most cases there was 3rd party libraries that would have handled the problem as well or nearly as well.
I agree that "I'd use a library" doesn't tell you how good of a coder someone is, but I'd much prefer a "lazy programmer" to an overly-clever, always-do-it-yourself programmer. If the point of the interview is to see how someone codes, have them code something in the realm of what they would actually be doing.
Also, to be clear, if you are incredibly clever _and_ know how to do it yourself, but seek to find the balance of when to use libraries vs when not t,o I find that the most valuable.
Background: Current FAANG employee, previously CTO of small startup
> What's wrong with "I'd use a library" or "I'd Google it"?
Saying "I'd use a library" isn't a reliable signal. If you hire based on it, everyone will just parrot it. On the other hand, being able to solve programming/math problems is a reliable signal. Linus and Jeff Dean are very good at such problems and it's not a coincidence.
> Saying "I'd use a library" isn't a reliable signal.
True. That's why you shouldn't be asking a question where that's a good answer in the first place.
> Linus and Jeff Dean are very good at such problems and it's not a coincidence.
Sure. But being good at these problems also isn't what makes Jeff Dean or Linus good programmers. Being good at solving novel problems is. The problem with the linked list question is that half of your interviewees will have seen it before and half of them wont, thus giving you quite a biased view on them.
> half of your interviewees will have seen it before and half of them wont
That's just not true at all. There's a huge supply of algorithmic problems and it's easy to invent new ones, so a typical problem given in an interview will be novel to pretty much all interviewees.
> That's why you shouldn't be asking a question where that's a good answer in the first place.
I’d like a better question, but time is limited and spending lots of time on explaining the context behind a real example is harder. Although it’s not like I’m married to these questions and would gladly replace them with some generic question that tries to address threading, resource management, and whatever linked lists are supposed to test.
Disagree. The guy who built the system I am now maintaining reinvented the wheel many times. So now we have a lot of undocumented buggy code. Most people aren't programming the linux kernel, they are writing a variation on web based CRUD.
> What's wrong with "I'd use a library" or "I'd Google it"?
I meant if that’s their only answer and they aren’t able to design something like a linked list from scratch.
Usually the answer went like “I’d of course use the built in class Foo, but for purposes of this answer, yadda yadda yadda”
Sometimes I would get someone who would argue over wherever it’s a dumb question or try to explain how they don’t know how to make getters and setters because they would just Google the answer. So that’s a bad sign for culture, teamwork.
IRL you don’t want people making their own linkedlists, just like no one should actually write FizzBuzz.
But it’s helpful to filter out the number of non-programmers who apply for programmer jobs.
They asked no Linked-List questions (I was prepared for them, the only time I have ever used linked-lists was in interview prep).
I also think the FAANG interview was pretty bad overall (took 6 months to go through), the last question was great. It required no algorithms, but a difficult problem to solve that required me to think on my feet rather than apply a known algorithm.
I can also tell you that my current team leads have both emphasized the importance of being able to find information, less importance being able to do it off the cuff (which I agree with).
They have pretty strict words around not sharing problems unfortunately, and while it's unlikely it would be traced back to me the potential isn't worth my job.
Exactly. If I have a new problem to solve, I may have an idea how to solve it, but I might as well see how others have solved it as there may be a better solution.
Right I expect anyone that just graduated 1 or 2 years ago to be able to write it in 15 minutes.
But someone who is an expert in machine learning or SQL ... and have not used data-structure for the past 20 year would need to study for it.
Do you want to hire the programmer that have 0 deep knowledge of the specific thing you are working on but can quickly tell you the content of CS 101 books or do you want someone that have skill set, experience and knowledge that complement your current team?
Not everyone who is a programmer starts with undergrad CS. Why not ask them to build a basic web app in their preferred framework, or read and process a basic text file, or any number of things that are more practical than implementing a low-level data structure?
That's fine for assessing graduates, but good developers with a lot of experience won't be as familiar with writing algorithms from scratch. They'll have to do a lot of revision for technical tests just to memorise reels of information they'd google in 10 seconds in real life.
> Any serious intro to CS course will have them as part of the curriculum (at least for linked list).
Your implied assertion is that a CS degree is required for programming. That's a good way to select for people like you, which is one of the strongest biases in hiring. One should also take survivor's bias into account, increasing the likelihood that if you're a programmer and did a CS degree, you think a CS degree is required.
Whether a "serious intro" to CS should include recursion and linked lists depends on whether you think:
a. a CS degree should prepare for a programming job
b. it should only prepare for a programming job
c. a CS degree actually prepares for a programming job
d. data structure knowledge is fundamental to programming in general
My personal answers are it should prepare for a programming job, but not exclusively, and that it doesn't usually (adequately) prepare for a programming job. In that context, it should include data structures, general computer architecture and similar historic/foundational topics. I wouldn't go so far as to call them fundamental, because that implies they're must haves. I also wouldn't go so far as to say any CS course that doesn't offer them isn't serious. Maybe that school has a greater focus on preparing for the job, or maybe someone's major is more akin to IT project management than technical.
In the end, a degree is:
* a proxy for general intelligence
* a basis for your social network
* a status symbol (school pedigree)
* an introduction to the topics covered
* an authority argument
* an indication of how well that person does at tests in an academic setting
That's it. If you're lucky, someone with a degree remembers most of what they covered in classes. At best, a CS degree is correlated to someone being able do fill a programming role.
What programming may require is:
* General intelligence
* Systems thinking (e.g. abstraction, information flows, decision trees)
* Programming language skills
* Patterns (architecture, design, OO/FP)
* Knowledge of data structures
* General IT knowledge (DevOps)
* Domain knowledge
* Framework familiarity
* Math skills
* Solving novel problems
* Absorbing new knowledge
* Communication skills (requirements gathering, expectation management, reporting, etc)
One could arrive at these skills through passion and dedication to the hobby, learning on the job, vocational training, a bootcamp, a CS degree, a PhD and more. Of these skills, the ones least likely to be required for the vast majority of positions are math skills and data structures - beyond the absolute basics.
I think it's important not to get our Ps and Qs reversed, don't you?
Sure, a bootcamp grad might have the required skills, if I'm lucky. But most won't and interviewing over and over has a non-negligible cost (I'm wasting everyone's time)
A serious CS degree provides a better signal to noise ratio. And should cover most of the points you listed as potentially required to program anyways.
> interviewing over and over has a non-negligible cost
I would say, specifically in the US where this type of question is asked, it is negligible compared to a dev's yearly salary. What one should consider is the time spent interviewing all candidates versus the cost of making a bad hire and doing it all over again. The only thing you're limiting when interviewing fewer people is the short-term cost of "hours spent doing interviews". That's a myopic metric.
Another thing I didn't mention in my list is churn or employee retention. Another aspect is if your domain/application might be more appealing to someone who doesn't have a degree and might stay interested and on board longer.
> A serious CS degree provides a better signal to noise ratio.
For one, noise is subjective. And in filtering out the noise, you're filtering out outliers - both good and bad. Even assuming you're right, that would only mainly apply to juniors.
> And should cover most of the points you listed as potentially required to program anyways.
The question is if you're selecting for the right criteria, since some of my points can only be arrived at through experience and general maturity.
The simple fact is: an education is only one aspect of someone's CV, a start and a depreciating asset over time. There is no sense in ignoring the candidate's job experience, general life path, public repos, etc.
> I would say, specifically in the US where this type of question is asked, it is negligible compared to a dev's yearly salary. What one should consider is the time spent interviewing all candidates versus the cost of making a bad hire and doing it all over again. The only thing you're limiting when interviewing fewer people is the short-term cost of "hours spent doing interviews". That's a myopic metric.
You are right, most of the cost is in the bad hire.
> For one, noise is subjective. And in filtering out the noise, you're filtering out outliers - both good and bad. Even assuming you're right, that would only mainly apply to juniors.
I tend to start off with a "calm-the-nerves" question, something like "write me a function to print out all the numbers from INT_MAX down to 0", which has a (small) gotcha in the termination condition, but is relatively simple.
Then I'll ask something like "write a function to find the nth-to-last entry in a singly-linked list", which is possibly difficult if you haven't come across multiple-runners before.
But the meat of the interview is something like "design me an algorithm to manage the entry-gate for a car-park that can cope with bikes (1/2 space), cars (1 space) and busses (4 spaces)".
There's so much you can do with that last one. The most impressive answers I get are those that recognize it as malloc() with zones, and cope with the corner-cases (can't park a bus around the corner of a car-park, 4 spaces have to be in a straight line...)
I mean, I have a variety of questions like each of the above, and I tailor the interview to suit what other members of the team are asking too, but the quick-functions at the start are really to calm nerves and get them into the swing of the interview. The main point is the design/thought-process one, which takes the majority of the time.
Does it seem reasonable to you to assume that a task on your job interview will be answered with "I'll take someone elses library" and they'll just be "ah, ok, you're hired!"?
Yes, because that's the correct answer in a real-world situation. If you want to play some game with the applicant, be sure to tell them you're playing fantasy and not reality.
Yes and I usually say that. It’s not meant as a trick question. Sometimes I’ll prefix it with “While you would never do this is real life, please walk me through how you would design and implement a database connection pool...”
I got asked a python question that involved a couple of list comprehensions. I did it and got asked how to do it without an intermediate variable. It involved nesting the list comprehensions, and I nearly didn't get it, not because I didn't understand how to do it, just that I have a personal rule never to do that, as it makes code quite difficult to read.
The question shouldn't be about linked lists. That's very specific and, as mentioned, has simple rules that can be learned and regurgitated. It should be about linked structures in general. It's a great way to separate really good programmers from "coders" and "devs" imo.
I really hope that companies continue asking these questions and rejecting great candidates who choose to keep real world knowledge in their figurative L1 cache. After all, it makes it much easier for my company to find people that code real world solutions instead of grinding on leetcode.
Wild speculation: because Noetherian induction is kind of tricky? And linked lists are a way to sort of allude to that trick ones without calling it out by name?
I used to ask a linked list question. It was “write a function that takes a linked list where values are integers and return a new linked list, grouping the odd numbers first and the even numbers last.” I was very specific about what I was looking for: not just to solve it in the “simplest”/most performant/most concise way, but to see if they could create good abstractions to make it easy for a very junior dev to read and reason about.
So, hopefully that meant building some sort of linked list class, with methods for “add”, “concat,” and maybe “filter”, and not just manipulating nodes directly.
I wouldn’t tell people directly that they should write those classes/methods, only hinted towards them. I don’t think anyone came up with the idea of writing “filter” on their own, and people often struggled with the implementation. The interviews were and hour long and I gave lots of hints. Not a lot of successful candidates from it, and I was quite lenient.
I would expect that if you don't tell people what you want they will fail to produce it.
I recall a mind reading interview I received once. He described a problem he faced, asked me how he solved it. ?! I explained how I would solve it, and while it's possible my answer missed something or was non-performant, I'm pretty sure it was a correct implementation. Nope. It wasn't what he did. I got a job offer, but turned it down, because holy crap.
I mean if you feel that all the people you interviewed are worse programmer than all the people you went to school with then it's likely the problem was not the candidate but the way the question was asked.
I don’t have a CS degree and not everyone we interview has one. But judging candidates against who you went to school with seems like an odd strategy. I don’t understand your thinking there.
I assumed you had a CS degree sorry.
My point is at the university I graduated from "far from one of the top university", second year student all had to write a clone of "Mario Bros" from scratch in 6502 assembly. And wrote most part of an operating system "basic filesystem, task scheduler, virtual memory system ..".
Which mean even the student that had the worst grade did all that and could do it again without help.
So if I had to interview someone that went to the same university that I did, I don't see the point in asking them to write code to invert a linked list or to solve the n-queen problem because I already know they can do this and I am more interested to know if they have real world experience.
By real world experience I mean know the downside of using a database like Apache Cassandra and to not use it for storing money related data despite all the hype about nosql ...
But do you ask this question, because it‘s part of the job to write linked lists or because it‘s something they should know if they had proper education?
I don’t care if they know what a linked list is. I’d happily show them that part. Everyone I’ve interviewed knew what one was though. The thing I was looking for was how they were organizing their code and breaking down the problem. That’s critical for the job.
The problem is CS degrees. What do you learn in a CS degree? First you learn data structures, then you learn algorithms, then maybe if there's time they burst your bubble and tell you about caches and how CPUs actually work.
What's the first data structure you learn? The linked-list, of course. So to many interviewers, focusing on linked lists is the equivalent of fizzbuzz. No one could be a computer programmer without it!
> The problem is CS degrees. What do you learn in a CS degree? First you learn data structures, then you learn algorithms, then maybe if there's time they burst your bubble and tell you about caches and how CPUs actually work.
There's 4 years in a standard CS degree program, there's time unless your curriculum or choice of focus is more strictly on the theoretical side, which is not typical outside of a few universities (as the only or primary option). Every second tier university graduate I've mentored has understood these topics. Except for the past 5 years where they are, more consistently, only capable of programming in Python or similar high level language and their program of study has divorced itself of talking about the real-world behavior on real hardware (from the same schools that, previously, seemed to understand or at least be aware of these topics).
Fair enough, but my understanding of European universities is that those 3 years tend to be more focused (on a specific area of study) than US university programs. That is, this is a reasonable description of many US 4-year degree programs for CS (using semesters):
Freshman:
Semester 1: English 101, Math 101 (maybe calc), Physics 101, CS 101, History 101
Semester 2: English 102, Math 102 (calc by now), Physics 102, CS 102, History 102
Sophomore:
Semester 1: Math 201 (calc), Chem 101, CS 201, Language 101
Semester 2: Math 202 (last calc, maybe stats), CS 202 & 203, Language 102
Junior - Senior: Mostly CS, with math or engineering support courses
My understanding of European universities is that the non-degree courses are typically not present unless someone specifically elects to take them (perhaps for a dual degree or minor). Which still goes with my point. Algorithms and data structures take no more than 1 year to study (EDIT: the basics), whether in a European or US university you have 2-3 additional years to cover the rest including getting into the technical details like why you want one of these loops and not the other:
for i from 1 to n
for j from 1 to m
a[i][j] = ...
// versus
for j from 1 to m
for i from 1 to n
a[i][j] = ...
It’s probably one of the more fair (or easiest fair data structure) you can ask someone about. If you don’t practice bfs or dfs recently you can forget traversal. With a linked list you can reason through it on the spot.
The answer should be obvious - because linked list questions require you to understand the concept of a reference, and because large numbers of candidates can't solve them.
I don't believe large numbers of candidates can't solve them.
I believe large number of candidate can't solve it on whiteboard in less than 10 minutes.
If you honestly think that University give diploma to people that can't write a linked list then we have a bigger problem as an industry!
> I don't believe large numbers of candidates can't solve them. I believe large number of candidate can't solve it on whiteboard in less than 10 minutes.
Which is why I give them the choice between a whiteboard and a laptop, and give them closer to 45 minutes to do so, and give generous credit for close-enough solutions.
A large number of them can't solve these questions under those constraints, either.
Linked list Q's are great if you're interviewing embedded sys engineers writing low-level kernel code in C and need to keep track of resources. In that case, I would see if they could also implement a 2D infinite sparse matrix.
Test for what the job requires, hopefully real-world problems using sequences of open-ended questions. Everything else academic or immaterial to the job might just be a mental shortcut or Lemminging everyone else.
Perhaps run through how to talk to and provide customer service to non-technical stakeholders if those exist.
Author here. Why wouldn't interviewing DMs on Twitter be research? I'm getting "oral histories" from a bunch of different people and comparing them for common patterns. It wasn't the only thread of research I did, but it was really helpful to orient myself at the start.
Yes. You also may have missed the part where the author describes trawling through forum posts from decades past in an attempt to gather data on past hiring practices in addition to today's.
It's also possible (likely, even) for the time that a topic starts showing up in textbooks to be different from when it starts showing up in job interviews.
Just to head off any speculation about the reasons I didn't study CS books, it's 100% because I Just Forgot
> While reviewing this post, my friend Alex Koppel suggested another idea: comparing how much the corresponding language manuals talk about memory manipulation. In retrospect, that’s a much better idea than trawling Usenet posts. I just didn’t think of it at the time, probably because I was already trawling Usenet to understand the job market. That’s a good research lesson: don’t over fixate on one primary source.
Yep! Probably not immediately (this post was a writeup of research I did in 2019), but it'll happen. I also want to dive Byte Magazine archives to see if they have anything interesting to say, too.
I did. He root-causes it to Joel Spolsky's interview style which the author claims was heavily influenced by what was useful to know at Microsoft during his tenure.
My response is to highlight why it's still relevant to ask them today.
I'm going by memory of Spolsky's article, from when I read it many years ago. One of his main points was that in asking a person to reverse a linked list, he watched to see if the person first sketched out a diagram, or simply started writing code -- because, as he believed, no one could do this without first sketching out a diagram, and going right to code was a red flag, indicating someone who (my memory is foggier, here) lacked the right temperament for a developer.
Couldn't they just... mentally imagine the diagram? I personally am bad at picturing things in my head but a simple linked list is pretty easy to do, and it isn't as if reversing one is an especially complex operation.
To be clear I'm not trying to suggest you think a candidate couldn't do that, I'm just surprised that this apparently didn't occur to Spolsky
I don't see anything in this about diagramming. In fact, from an earlier comment in that article this would be an "easy" or "medium" problem, and how quickly someone can solve these is something he considers. Does it take you 20 minutes to reverse a linked list, even with his Google-search like hints, or does it take you < 5 minutes because it comes to you quickly and any delay is talking or trying to keep a consistent pseudo code format on the white board?
3 interview rounds and all asked linked lists questions back to back.
I was very honest in that in my 2 years on the job, (ML, DS) I had never once run into a situation where I would use a linked list. I didn't remember if Python even had a default linked list implementation and I decided to implement it from scratch. Wrong decision.
I didn't get through, but the choice of linked lists was quite bizarre, esp. for a Data Scientist position. I would have much preferred a coding question that was relevant to the job or a take home assignment.
Well, I guess it was a good signal nevertheless.