Why do interviewers ask linked list questions?
hillelwayne.com
hillelwayne.com
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.
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
{a=>1, b=>2, c=>2} Have them swap keys and values.
See if they can cope with duplicates.
On large hiring spree (20+ hires, hundreds of interviews) I would walk in, give them that in any language they wanted.
Moment I saw they understood, I would let them know they passed and walk out. Let others handle the social aspects of interviews.
90% failed test or took ages to get to solution.
Remaining would finish it under a minute and be confused as to why we gave them such a trivial test.
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.
But to be fair at Wallstreet you are likely to work with quants and have to do integral :)
Aside: Linked lists in python have a built-in deque: https://docs.python.org/3.7/library/collections.html#collect...
(I still had to google that one)
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.
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
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.
Also: https://knowyourmeme.com/memes/im-getting-too-old-for-this-s...
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.
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.
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.
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.
1. “It tests CS fundamentals.”
2. “It tests reasoning through a new problem.”
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
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.
Congrats! You are selecting for people who 1) rote problems for interviews and 2) motivation to clear your interview.
If you can't be bothered to hire people, earn a profit, and not turn traitor on everyone, I do not want to bail you or your failing bank out.
Next market crash, burn m*f*er burn.
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.
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.
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.
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.
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.
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.
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.
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".
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.
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.
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.
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.
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.
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.
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.
Sports interviews are way more atuned to the actual job than software interviews.
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.
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.
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.
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.
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 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.
> 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.
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.
It's easy to write a linked list in FORTRAN-77, using an array as the underlying storage - I've done it several times.
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.
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.
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.
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.
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".
That made me grin -- 'the programming scene'. What a club!
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.
It's one step above the fizz-buzz.
Right. But this is a critique overused questions the candidates may have already seen rather than linked list questions.
In my experience, linked list questions come up because they're a simple data-structure that gets at ordering vs look-up tradeoffs.
Unfortunately McDowell's Interview Book seems unstoppable and I expect to be answering list questions forever.
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.
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
The point of the question is to solve a problem in ~15 minutes. Algorithms and Data Structures are used for these because everyone knows them.
Even when not teaching about memory, it's used to teach recursion.
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?
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.
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.
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.
True and true. A bad hire is extremely costly.
Call me crazy, I think an interview question should test for one's ability to program well, not test their memorization knowledge.
My argument is precisely that linked-list questions are a poor proxy for programming well. It's testing the wrong thing(s).
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).
What was the question?
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.
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.
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.
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.
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.
I keep hearing about these people, but I have never met one in 20 years.
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.
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.
Or you just wanted to not hire someone if it took him more than 10 minute to do it on a whiteboard?
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 ...
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.
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!
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).
Depends on the nation, in Europe 3 years is the standard.
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
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] = ...After Bologna, Portuguese universities made the 5 year into a degre + masters, and push for everyone to keep doing the 5 years just as before Bologna.
Which most do, otherwise they would be undervalued versus everyone that took the degree before Bologna.
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!
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.
* Not unfamiliar to many
* NULL
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.
Whats wrong with looking at CS textbooks and see when the topic became common?
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.
> 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.
So you start any interview with something that should known by the candidate and can then move on to harder questions that will need to be explained.
My response is to highlight why it's still relevant to ask them today.
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?
“We can safely assume everyone can speak.”
“It tests reasoning through new information.”
Cue popular article built upon the back of this strawman. Makes one wonder about the camel that broke the strawman's back.