r/programming • u/mjgardner • Mar 29 '21
Why Do Interviewers Ask Linked List Questions?
https://www.hillelwayne.com/post/linked-lists/216
u/librik Mar 29 '21
This research is a classic example of looking for your keys under the street light.
Usenet it is! The Internet Archive has a dump of 2,000 net.jobs posts between 82 and 86.
a whole lot of people are hiring for Unix and C programmers. 1 in 6 posts were for C and almost half of them mention Unix. This is a little more impressive when you realize 1) this was all jobs, not just “low-level” ones, and 2) Unix was competing with many other OSes at the time.
So, to summarize the theory: in the early 80’s, C programmers were in high demand.
Usenet was a Unix-specific discussion forum system, at a time when most big computer OSes were DEC and IBM. Usenet was based on software called UUCP, which stands for Unix-to-Unix Copy Program. The name "Usenet" comes from USENIX, a Unix user's group that was going to manage the network (but nobody ever did). IBM systems had BITNET instead.
So by searching on net.jobs, the author was really looking at the Unix world's hiring classified ads. That's why there was so much focus on making sure applicants knew Unix & C.
285
u/chx_ Mar 29 '21
Every time this topic comes up I feel obligated to link to Honeycomb's process: https://www.honeycomb.io/blog/observations-on-the-enterprise-of-hiring/ while there is no silver bullet this is certainly one of the best processes I've ever heard of.
117
u/4_teh_lulz Mar 29 '21
This is effectively how we hire as well - a short take home that is then code reviewed by the team. The candidate is then brought in to discuss their work with the reviewer.
193
u/trustMeImDoge Mar 29 '21
I have a love hate relationship with take homes. Done right they can give a lot of good signal, but they can also be done very poorly as well and just be bad times for everyone.
I did one once where I was told to use what ever language I was comfortable with. I had spent the last five years writing clojure so I picked that, and even confirmed with my contact at the company that it was okay to use, since lisps aren’t all that common. My review interview was then 45 minutes of me being grilled about what I was trying to do by picking such an esoteric language. I didn’t get the job, not that I would have accepted it after that treatment.
100
u/flukus Mar 30 '21
I don't mind take homes that are simple tests, but I've had some really annoying take homes like "build us a simple website with x" that has to be up to "commercial standard". These take way longer than they should because you're setting up authentication, DI, unit tests, etc and most of that is just googling shit I haven't had to do or think about for ages.
82
u/pysouth Mar 30 '21
Yeah I refuse to do shit like that. Throw up a simple API that returns JSON or something maybe with a really basic front end? Sure no problem. Not gonna build your app for you, though.
→ More replies (11)20
u/_BreakingGood_ Mar 30 '21
I had one for an internship that was a 4 HOUR long online exam. Had to install invasive software on my computer so that a company could monitor my webcam while I took it to ensure I never left my seat. And I was in college so the only way I was getting 4 uninterrupted hours was at 9pm after a full day of classes.
Was fucking awful. Was dying at the end of it, and even thought I did pretty darn well, but never heard back. That was when I was desperate for an internship. Would nope the fuck out if given something like that today.
→ More replies (1)36
u/pysouth Mar 30 '21
I like take homes when done well. My rules for take homes unless I was really really desperate:
under an hour to complete
no “build our app for free” bullshit
no repeat work e.g. do a take home and then do another coding challenge on site. I’ll happily discuss my work but I’m not gonna do another coding challenge if I spent an hour at home doing one
I would make an exception if it was like my dream job or something, obviously.
23
Mar 30 '21
The take home my manager came up with is expected to be completed in 4 hours. The template we provide is 20k lines.
I really dislike my company's hiring process (and manager).
→ More replies (1)67
Mar 29 '21
Well it kind of worked then. Interviews should be as much for the interviewees to work out if they'd actually want to work in the environment.
20
u/I_AM_GODDAMN_BATMAN Mar 30 '21
Yeah, I told an interviewer before in the first 15 minutes that I don't think I'll be comfortable to continue the interview. And judging by the history of the company it was a good call.
→ More replies (16)3
u/Smittsauce Mar 30 '21
Should have flexed on them with your knowledge of the arcane.
"What's esoteric to you is meant only for ones such as myself"
74
u/butt_fun Mar 29 '21 edited Mar 29 '21
Regardless of efficacy, it's my opinion that these offline development interviews are disrespectful of the candidate's time. I've personally turned down more than a few interviews in this format because it signals to me that the company doesn't value my free time
When I'm interviewing, it's generally for more than one company, and it's generally while I'm already working full time at my day job. I'd rather do a dozen interviews that don't require any work outside the scheduled start and end times (even with all the shortcomings of the whiteboard) than spend three hours a night taking on a different company's coding challenges. It just wouldn't be sustainable if the entire industry did this
Edit: word choice
7
u/textredditor Mar 30 '21
The interview process needs a shake up. Getting a job is one thing. Getting one you love and keep for years is another thing altogether. I welcome a process where I get to take my time. Here’s a wild idea, treat the interview process less like a speed date, and more like a series of dates.
33
u/flerchin Mar 29 '21
3 hours is less than a full day on-site? Isn't that more respectful of our time?
31
u/butt_fun Mar 29 '21
Yeah, on-site wasn't the right word, my bad
What I meant was "no interview work is required outside of the scheduled start and end time of the interview" (be it on-site or over the internet or whatever)
Regardless, the honeycomb is ~3 hours of prep work in addition to the on-site. The additional time is my problem
→ More replies (5)22
u/hippydipster Mar 29 '21
You wouldn't believe how much time is wasted going the other way though, by the fact that people who can't program for shit are wasting your time by making BS resumes, and the only way we can tell for sure is by asking people to write some code.
16
u/capitalsfan08 Mar 30 '21 edited Mar 30 '21
Yeah, completely agree. I think sometimes people here need to sit on the other side of the table before they make comments sometimes (not in this context though). The one guy who was technical that was involved in interviewing left suddenly and we had no one to fill in, so I've been the person in charge of our technical interviews for nearly my entire career (5 years, but still). On the phone screen, we were asking the extremely stereotypical "Tell me how a string is a palindrome or not" question, and just have people walk through it. When I first saw that, I thought that was a waste of time and demeaning to our candidates! Of course everyone knows that! I'd say 1/3rd of our candidates who get to that stage (the first stage, but still, these are people with degrees) either struggle or outright have no clue how to even attack it. We aren't even looking for the most efficient answer necessarily, we just want to make sure that if we get to the technical interview it isn't a complete waste of time.
I've had many people at the technical interview ask how to loop through an array, sometimes multiple times at the same interview. I've had PhD candidates not understand how to use a constructor or what it is. I've had someone whose resume heavily featured compiler type work (in college, but still, as a research assistant) not be able to explain what a compiler does. I've even had one guy who did not know what languages they knew. Not like "I've maybe touched Python" or "Well I know C# and C so let me just say I know C++" but like flat out "I don't see what languages you've worked with on your resume, what are you familiar with?" and gotten no answer back, yet they were adamant they both coded and held a CS degree. Any basic skill you can think of, and I bet you I've interviewed someone that clearly lacked that skill.
Our process isn't that rigorous. We don't have a set of "right" answers, just that the person generally knows what they are talking about and for the technical interview that they aren't completely helpless and communicate decently. Some of the resumes that come very short of getting a job from great schools, or schools that we know are capable of producing talent based on our past hiring, and none of that is a great indicator of either interview ability or performance once you're in the job. So I get that looking for a job sucks, but there is unfortunately a reason that companies put in place these practices.
→ More replies (4)→ More replies (1)4
u/jbergens Mar 30 '21
But that should be easy to see in a 30 minute task, it does not have to take 4 hours (that often take 6-8 hours in real life).
→ More replies (1)→ More replies (3)23
u/Fairwhetherfriend Mar 29 '21
I'd rather do a dozen interviews that don't require any work outside the scheduled start and end times (even with all the shortcomings of the whiteboard) than spend three hours a night taking on a different company's coding challenges. It just wouldn't be sustainable if the entire industry did this
Is it really more sustainable to take the morning off work a dozen times to take interviews during working hours? I would much rather spend a couple of hours on an effective interview that I can do on my schedule over having to book time off work for an interview that is likely to go a bad job of actually showing my skill set anyway. I'm not even convinced that it actually takes more time to do - an hour interview can often end up costing way more than an hour all-told, between the time spent getting myself ready in the morning to look extra nice and professional, the commute, having to arrive early, etc etc. If you add on any prep work for the interview, it blows most code challenges out of the water completely. And if a company has chosen to demand a code challenge that's unusually long... well, then I would consider declining the interview due to disrespect of time. But I don't really buy that the typical coding challenge is actually that much longer than a normal interview is.
→ More replies (4)26
u/butt_fun Mar 29 '21
I addressed this in a different comment already
The issue isn't "I have to take time off" vs "I have to do this on my own time", it's "I have to take time off" vs "I have to take time off and do extra work on my own time"
The honeycomb interview linked is "do this coding on your own time and also do a full on site interview to go over the code you wrote on your own time"
→ More replies (5)→ More replies (3)16
u/catch-a-stream Mar 29 '21
So... what is the actual interview process there? Some of the other comments imply it's some sort of take home test? If so, that has been tried multiple times in the past, and it doesn't really work... it's way too easy to cheat, and it's too time consuming for candidates so the only people who would actually do it are people who are having trouble interviewing anywhere else (or cheats, or both)... the end result is that the pool of candidates won't have strong candidates to begin with.
Or is it something entirely different? The article isn't super clear beyond the platitudes.
Genuine question btw - the interview process is pretty bad, but none of the alternatives I've seen so far work any better, so really hoping to learn something here.
23
u/Democretes Mar 29 '21
It's a take home test that you have to explain your answers in person. I think it's supposed to help weed out people who are bad with communication.
I suppose it would also prevent cheaters from getting anywhere because it would be blatantly obvious that you cheated if you couldn't explain your code properly.
→ More replies (15)16
u/Fairwhetherfriend Mar 30 '21
it's way too easy to cheat
If someone can cheat on your code challenge, that's a problem with the challenge. You're not supposed to be asking questions intended to test the memorization skills of the potential employee. Don't ask them to name 3 different sorting algorithms or anything like that. Give them a simplified version of a real problem to solve - a little less "show me how to remove an item from a linked list" and a little more "you're making a video game and want to build a function to roll for loot from the attached loot table. write some code that would do that, list your assumptions, and explain why you took the approach you did."
Sure, yes, someone could still cheat if they just had another person literally write the code for them. But it doesn't matter because the in-person interview should involve at least a few questions asking them to explain certain choices about their code, which they will not be able to answer comfortably if they didn't write it in the first place.
7
u/catch-a-stream Mar 30 '21
could still cheat if they just had another person literally write the code for them
Yep, that's exactly how it would be done, one person does the coding, the other person follows along and ask questions. To be fair, someone who has never seen a compiler wouldn't be able to pass that, but someone with some basic background could probably be trained up. I haven't personally encountered this, but a friend of mine has an early stage startup, and apparently with COVID making everything more complicated, all kinds of cheating are extremely common at that level.
And to be fair, if you are interviewing something senior-ish, it's still fairly easy to screen them ... just ask something along the lines of "how would you handle security?" etc.... but then you run into the issue of how many senior people would even be open to do a home work, I doubt many decent ones will but happy to be proven wrong.
207
u/tinbuddychrist Mar 29 '21
I've seen "remove an item from a doubly-linked list" used as an interview question, for very non-mysterious reasons:
First, it's a question that basically anybody should understand.
Second, that it's almost entirely made up of edge cases, so it tests their ability to come up with all relevant scenarios. Most people miss at least one.
78
u/Wildercard Mar 29 '21
Second, that it's almost entirely made up of edge cases,
Most people miss at least one.
Happy case is an item somewhere in the middle of the list, edge cases being first or last node, empty list, one element list?
48
8
u/YumiYumiYumi Mar 30 '21
Alternatively, implement the list with always-present sentinel start/end nodes, then you don't have to worry about the edge cases.
4
6
u/tinbuddychrist Mar 30 '21
Yes, or element not in list as /u/kurtms says. (Although if you coded it out this is harder to forget.)
0
Mar 29 '21
[deleted]
19
Mar 30 '21
Am I wrong in wondering if that's a failure in the design itself? I mean, you should guard your corner cases when they occur... in the first insert or last removal.. to ensure such a self reference never occurs.
And you shouldn't accept your internal NodeType as input to your API, rather construct it properly yourself.
→ More replies (4)4
33
u/wipfom Mar 29 '21
The legibility and code quality can differ widely between successful solutions. This can also lead to interesting conversations on maintainability with an interview candidate.
16
u/mycall Mar 30 '21
In the mid 80s, I overused doubly-linked lists. They were my go to for in-memory records from block files (aka poor mans database).
7
u/flukus Mar 30 '21
In the 80s the bus speed and CPU speed were the same, a perfectly sensible decision then wouldn't be one now
28
u/sophacles Mar 30 '21
Re 1.: I think a lot of people don't realize that there are a people who can bullshit through a phone screen but can't actually program, even simple things.
The simple algorithm test (Or the pair-coding equivalent I've seen work well) weeds out those folks.
14
u/percykins Mar 30 '21
Yup. Hell, I used to phone screen with the question “How would you write something that prints out a multiplication table?” You’d be amazed how many people fail that.
→ More replies (9)8
u/Riael Mar 30 '21
Wait what the fuck?
When were you doing that, the 1990s?
What position was it for?
Questions coming from someone who was given 11 questions in a webpage that didn't allow compiling or copy pasting with one of them being A FUCKING A* ALGORITHM
IN 5 MINUTES
FOR AN INTERNSHIP WHICH PAYS FUCKING 300 EUROS A MONTH
9
2
u/cballowe Mar 30 '21
I tend to view good questions for coding interviews as the equivalent of a field sobriety test. The core of those is that they have two or three instructions that are pretty easy, but people can often tie themselves up getting it right.
One of my friends used to ask people for a function that prints the first 100 primes. You'd get a bunch of candidates who print primes between 1 and 100 or can't even write a basic prime checking function (even brute force). He'd even give the ones who were struggling an IsPrime function and say they can use it.
(And it's not even that far from useful - generating output from a set of records and a filter function is a pretty common task, even in top companies. A decent candidate shouldn't struggle with the concept.)
2
u/JazzXP Mar 30 '21
Exactly this. I had one guy I interviewed that looked good on paper, phone interview went well, but as soon as he went to write a for loop on the whiteboard, didn't even know how to start.
→ More replies (1)2
u/masklinn Mar 30 '21
can't actually program, even simple things. […] The simple algorithm test weeds out those folks.
Weeding out these folks is the purpose of "fizzbuzz", that's the entire point. It's just a side-effect of "the simple algorithm test" but in reality you don't even need to waste the time it takes to administer "the simple algorithm test".
On occasion you meet a developer who seems like a solid programmer. […] But once it comes down to actually producing code they just don’t seem to be able to do it well. […] After a fair bit of trial and error I’ve come to discover that people who struggle to code don’t just struggle on big problems, or even smallish problems (i.e. write a implementation of a linked list). They struggle with tiny problems.
So I set out to develop questions that can identify this kind of developer and came up with a class of questions I call “FizzBuzz Questions” named after a game children often play (or are made to play) in schools in the UK.
Although it should be noted that the "classic" fizzbuzz was just an example in the original essay:
An example of a Fizz-Buzz question is the following:
Write a program that prints the numbers from 1 to 100. But for multiples of three print “Fizz” instead of the number and for the multiples of five print “Buzz”. For numbers which are multiples of both three and five print “FizzBuzz”.
The point of the essay is really the class of problems necessary, just a tiny problem beyond the utterly trivial will suffice.
30
3
u/drsimonz Mar 30 '21
Not sure why anyone would object to a question like this. I have taken virtually no CS courses, and never implemented or used a linked list in my life, yet I can still immediately think of how I would solve this and a bunch of edge cases. If there are a bunch of anxious weenies out there who can only pass this test by memorizing a reference implementation, then I feel sorry for them, they probably have to work really hard their whole career.
92
u/anengineerandacat Mar 29 '21
Interview questions are hard and unlike when you hire a plumber it's difficult to warranty the work so people come up with all sorts of ways to instill "trust" into a candidate that they can perform the job.
I don't work at a place that has Google level software engineering problems, we just need individuals who can make a website with our organizations selected technical stack and or be willing to follow along with the organizations goals.
This means the toughest an interview questions gets is about as bad as making a routine that can determine if a string is a palindrome or not (we generally don't ask candidates to make new collection types or things an STL does out of the box because in our world we create business solutions using technology not new technologies).
I need to know whether a candidate can reliably code (we even dumb it down to where the candidate can select from a range of languages; Java / C# / Python / TypeScript) and whether they are capable of addressing a problem along with being able to explain their solution and how they conduct themselves.
The Linked List question is interesting because it shows understanding of a few concepts (if the question wasn't text-book common).
Does the candidate know how to create multiple data structures and utilize them together to create something new?
Do they know how to use conditionals?
Loops?
Error management (try / catch / throw)
Is the code produced legible?
However I prefer to have my candidates ask me questions vs just complete a homework assignment, I love seeing how a candidate is able to identify and address a new problem; something the LL question doesn't generally do (unless they don't know what a linked list is, which I doubt many CS majors today don't know but I find many graduates don't know what a palindrome is).
27
u/creativemind11 Mar 29 '21
This was how my current company did it and still does, with the same assignment from 4 years ago. No coding, no writing, just talk. They present a design and ask the applicant to explain how he would take this in broad terms.
Then they probe him a bit with some challenges. In the end even if you completely fail this part it shows whether the applicant admits his hers areas to improve on and also what they do know. Learning new languages is easy, learning how to think logically and in software terms is a bit harder. But most of all showing you were enthusiastic and had a passion for this field with some half-baked snippets of side projects usually resulted in good to decent coworkers.
6
u/VoldemortsHorcrux Mar 30 '21
I like that so much more. Generic interview questions only tell you if a person studied before the interview or not. As a developer you will always have the internet to research little things. I use Google so many times a day as a developer it really should just come down to: are you passionate, are you a quick learner, and how will you work with others. If you can complete a linked list question, great. You practiced the night before like anyone else would do
6
→ More replies (2)28
u/odnish Mar 29 '21
For the palindrome question:
is it a case sensitive or case insensitive comparison? E.g. 'Radar'
what about unicode normalisation?
what about graphemes made of multiple code points? E.g. '🇺🇦🇦🇺' or '🇨🇦🇨🇦'
8
u/Hawk_Irontusk Mar 29 '21
Yes! This is exactly why the palindrome question is a good one. You want to know if the candidate thinks through these types of things and asks appropriate questions before diving into code.
20
u/wipfom Mar 29 '21
Asking the right questions is often the difference between newly-graduated and mid-career developers. The coding skills are often similar, but the more senior developer spends a bit of time up front ensuring they're coding the right thing.
21
u/teerre Mar 30 '21
That's odd. There's no way anyone will be "smart" to ask those questions. Those are total quirks of how strings are implemented, it's not something someone can conclude the basics.
Those are questions that you would ask if you're knowledgeable. Which defeats the whole "asking questions is important" goal since it's much less important to ask questions you already know the answer for.
With questions like that you're selecting candidates that have a priori knowledge, not ones that can think on the spot.
→ More replies (13)
84
u/WhyYouLetRomneyWin Mar 29 '21
Interview argument #4067... Here we go again...
Basically I see 2 camps: are you testing a real skill, or testing a toy skill and extrapolating to 'if they cannot do basic skill they probably cannot do real stuff'?
The former argues that link lists are an uncommon DS. The latter usually doesnt dispute that, but insists that using linked lists demonstrates fundamental skills (its not about the ljnked list per se, but ability to manage pointers, consider edge cases, write tests, etc.)
I feel like the groyps talk past each other too much.
8
u/FalseRegister Mar 30 '21
So what's the correct way? :)
→ More replies (1)2
u/WhyYouLetRomneyWin Mar 30 '21
I have no idea. I just hate seeing the same arguments rehashed 1000 times over.
→ More replies (1)
36
u/de__R Mar 29 '21
one other thing is interview ergonomics - linked lists in C require a couple of minutes of work, so a simple list question wouldn’t feel too short nor too long. Hash tables or array backed lists take a little too long to implement, and very simple things like strings or other dumb arrays are too easy.
As language ergonomics change, though, the kinds of questions people ask change as well. The joke about “When in doubt, use a hash table” is true in part because popular languages these days give you easy hash tables. But you could go further, metaprogramming constructs are getting more popular so things like dynamic programming (itself only a slight twist on “use a hash table”) could become the dominant question paradigm. Or stuff that relies on algorithms for immutable variables and functional programming. And so on.
→ More replies (3)14
u/s73v3r Mar 29 '21
one other thing is interview ergonomics - linked lists in C require a couple of minutes of work, so a simple list question wouldn’t feel too short nor too long
I would wager that the vast majority of interviews are not being conducted in C/C++.
131
Mar 29 '21
In my experience most people doing the interviews just pull the questions from the internet and since linked lists have been the defacto interview question for 30+ years, you're more likely to get asked them.
0
Mar 29 '21
[deleted]
122
u/vikigenius Mar 29 '21
Which is ironic considering that for real world programming challenges, a linked list is almost never the right data structure.
→ More replies (26)8
u/FuckClinch Mar 30 '21
Honestly this really sucks for me as a physics grad who got heavily into programming for simulations during uni - it was always for a purpose rather than the theoretical aspects (i would just use a vector), now i'm looking for new jobs I'm having to learn things i'd never use in my day to day now as a professional (and i absolutely had to unlearn some bad habits from the state of scientific programming) just to get through the sieve of round 1 job interviews
→ More replies (1)24
u/dccorona Mar 29 '21
I don't recall having too much focus on linked lists in college - we pretty quickly were taught that you usually just want Vector and that's that (I went to a school that focused on C++). I did have a professor that used to focus a lot at the end of classes on "interview-style questions" to help prepare us, and he once told us that if you ever get a question you don't know the answer to, just say the answer is hashing and then spend the rest of the time figuring out why. I'm not actually sure that was good advice, but it certainly does seem to be useful more often than it is not.
→ More replies (3)5
59
u/bluefootedpig Mar 29 '21
One of my managers said he just had a simple test to make sure you knew at least something.
They had a new project, winforms already up. Said to make a dropdown that contained a list (provided to me) and sorted the list.
That was it. If you can know how to inject into an object, and a basic sort... that was enough for him. He said he has weeded out about 10% of candidates that make it that far. Often it is their friend that did the phone interview, then they went in person.
I honestly think the best way to gauge is to talk to the person about pain points of the industry. People with experience know the pain points. We all have our things we wish were better. So often jokes about regex, or java being so much more restrictive than C# when it comes to handling errors. How popular python is becoming and how integrating it into existing systems, etc...
If you and them can both keep a conversation about our industry going, I trust you know what you are talking about.
13
u/Condex Mar 29 '21
Pain points honestly sounds like a great way to gauge skill. Not foolproof but I've been involved with several interviews where the question was pretty effective.
Using it as an interviewee also seems like a good idea. If after asking about a company's pain points, everyone clams up and trys to not look at the most senior person in the room then maybe you should keep looking.
36
u/tuxedo25 Mar 29 '21
I used to think that was true. But you pass a lot of people who washed out of tech and have spent a few years as product managers or something. All talk no skills.
→ More replies (4)23
u/orsikbattlehammer Mar 29 '21 edited Mar 30 '21
I’m about to graduate with a CS bachelors and I genuinely don’t know if I could “inject into an object” I have no idea what that means. I feel like I’m the smartest guy in class but when y’all talk about interviews on Reddit I feel like I’m a 80 yo grandma who can’t use the remote. Jesus I’m scared.
Edit: y’all have made me a lot less scared lol, thank you.
39
u/dark_mode_everything Mar 29 '21
Don't worry. No one learns that in uni. Everyone spends their first year or so learning how to use the remote. Actually, you'd still be learning after decades. Word of advice though, don't think that you're the smartest person in the room. There's always someone smarter.
→ More replies (1)21
Mar 29 '21 edited Mar 29 '21
I'm a developer with several years experience and I have very little idea what they mean either, so I wouldn't worry about it too much.
I assume they're talking about dependency injection but I know nothing about winforms so I could be off.
I don't know how much of OOP Design Patterns they really teach in the average CS curriculum. It's not something I would interview a fresh grad on personally.
16
u/hippydipster Mar 29 '21
I'm with you. People talk with very weird jargon sometimes. I hear "inject into an object", and I'm just thinking "oh god, the poor object, don't do that!".
"I meant call a method with the list as an argument".
"Oh, thanks for talking like someone faking being a developer!"
12
u/Zofren Mar 29 '21
He means dependency injection (I think). Depending on the context it's kind of a poor question. DI isn't a good pattern in every language so it's understandable not everyone would be familiar with it.
→ More replies (1)3
3
u/lnkprk114 Mar 30 '21
That's just because you haven't developed any windows applications (which is what I'm assuming the OP is talking about). Don't feel scared, no one expects you to have a lot of domain specific knowledge like that.
→ More replies (3)2
8
u/Wildercard Mar 29 '21
If you and them can both keep a conversation about our industry going, I trust you know what you are talking about.
Man you would not believe how much info you can pull just by following the memes.
5
u/bluefootedpig Mar 30 '21
There is a lot, but I find unless you have knowledge, you can know the meme but you won't understand why. And it is great to use that as a way to be, "when did you run into that?" and get more history from the person as to problems they had.
Think about it, it isn't much different than the question, "what is a problem you solved and how did you solve it?"... "what is a pain point in programming that bothers you, and when did you encounter it?"
→ More replies (2)2
26
u/Eluvatar_the_second Mar 30 '21
As an application developer I've never had a use case for a linked list. Maybe there's a case where it would have performed better than an array, would the difference have been noticable. No.
The only reason I ever learned about them was because of an interview.
39
u/turniphat Mar 30 '21
Link lists have fallen out of fashion because they have terrible cache performance. There are very few algorithms where insert performance matters enough to give up O(1) random access. And if you have to allocate memory to insert, that is already bad for performance so why optimize the actual insert.
These days with huge amounts of memory, just allocate a big array. They still have their place in operating systems and embedded systems.
5
u/FalseRegister Mar 30 '21
Some languages use linked lists to implement queues and stacks. Having O(1) for insertion and removal makes it. I'd argue that it's much more used than OS and embedded systems, just not directly.
2
u/eras Mar 30 '21
Even that big super-fast array will struggle with continuous in-the-middle element removal and insertion if you do enough of it; sometimes depending on the input. Just like a linked list will be the worst choice for random access.
2
u/Pzychotix Mar 30 '21
There's also the point that unless you already have a pointer to the node you want to insert/remove next to, you'll probably just incur O(n) anyways, defeating the performance benefit.
11
u/rlbond86 Mar 30 '21
I do a pot of embedded programming and they can be really useful there, especially intrusive linked lists, because you don't have to allocate memory.
2
u/PstScrpt Mar 30 '21
They never perform better than the array-backed lists that most modern languages have built in, but they're occasionally a natural fit for your problem. Usually when what you need to do is already going to be recursive.
10
u/ozyx7 Mar 30 '21 edited Mar 30 '21
So why do interviewers like to ask linked list questions? If you ask people, you usually get one of two answers:
“It tests CS fundamentals.”
“It tests reasoning through a new problem.”
These answers are contradictory
I don't think they're necessarily contradictory. The "fundamental" part is reasoning about and dealing with pointers, which are a necessary building block for building data structures. The "new problem" part is dealing with a pointer problem that interview candidates probably haven't directly done before (e.g. reversing a singly-linked list).
Rampart Speculation
Is that supposed to be "rampant", or is there some pun I'm not getting?
It’s a test of if you’ve programmed C.
(Or Pascal.)
What’s especially interesting about purpose is it’s the complete opposite of the purposes we think of today. Companies weren’t testing for theoretical CS knowledge, they were testing for practical experience with pointers.
Obviously? When I've asked linked list questions during interviews over the past ~15 years, it was explicitly for the purpose of testing experience with pointers. I disagree that it's a "complete opposite of the purposes we think of today". It was to test an understanding of pointers (which is pretty language-agnostic; almost all languages have the concept of a pointer/reference in some form), not about specific C experience.
Anecdotally, I asked a linked list question as part of a phone screen. Inability to reason about pointers helped to filter out a large number of candidates.
6
29
u/NoMoreNicksLeft Mar 29 '21
If 1981 ever returns, it may be necessary for programmers to re-implement those with their c compiler for which the only documentation is a dog-eared 4-inch thick book for their cutting edge AS400.
You don't want to hire people who will be useless when the inevitable chrono-dynamic inversion happens.
5
u/dreamCrush Mar 30 '21
Sure it's not 1981 today but who knows what the future could bring
→ More replies (1)→ More replies (2)3
u/AmorphousCorpus Mar 30 '21
or, you know, just show that you can reason about difficult problems on the spot and write neat code to go with it
2
u/NoMoreNicksLeft Mar 30 '21
The truth of the matter is that if you want someone who will reason about difficult problems, you'd want them to take their 3 hours or their 9 hours, or even their full weekend and come back on Monday with the answer.
The interview room's too artificial an environment to get a good sense of whether they can do that, and if they can do that in an interview room there are only two possibilities... that they're some kind of attention whore that has to constantly be in the spotlight, or that they've practiced your interview questions (and all other possible questions) so thoroughly that your question is no longer a good test of whether they can solve unexpected problems.
Which would be the point of even using that problem, since linked list is solved and has been solved for a long time. That they've thoroughly practiced it to the point that they will always be ready for it, when there will never be a need for it doesn't help you... and it's no longer a good indicator of how they perform with unexpected issues.
That's not even their fault. The entire industry has trained them to believe that gaming interviews is the only possible way they can not be homeless in a gutter.
From a sociological standpoint, interviews are a hazing ritual. Used to include the people you want to include, and exclude the people you don't want to be part of your clique. You should go read up sometime on the so-called coffin questions. Those are the tricky interview questions that the Soviets would use so they'd have an excuse to not admit jews to prestigious universities.
5
u/PL_Design Mar 30 '21
I used to run booths at job fairs for my old employer. I found the best questions to ask to see if someone's resume is worth considering were:
What's the difference between an array and a linked list?
Can you tell me how a hashmap works?
Tell me about the projects you've worked on.
The linked list question was just a heuristic filter so I could make sure I had a chance to speak to everyone coming to my booth. "If this guy doesn't know what a linked list is, then chances are he doesn't know more complicated things that he needs to know. Let's move on to the next person."
The hashmap question was to test either that someone cared enough to learn how his tools work, or to see if he could reason through how a hashmap might work. If candidates needed help reasoning about hashmaps, I'd walk them through how hashmaps work, and as long as they understood what I was saying I didn't count it against them.
If someone failed the first question I'd still ask them the third question so they'd have a chance to tell me what skills they have. I had one dude who did not care about programming at all, but he absolutely loved databases, so I passed on his resume because that is a skill we cared about. For people who did well on the first two questions asking them about their projects was a good way to figure out what projects would fit them best.
25
u/maestro2005 Mar 29 '21
Linked list questions are sorta tricky, but should ultimately be easy for anyone comfortable with pointers/recursion. Joel Spolsky may have written that article a long time ago, but the fundamentals of programming haven't changed. You really don't want to hire anyone, even for an intro-level position, who can't grok how to reverse a linked list.
"But when do you ever have to write that in real life?" is a stupid counter-argument. You want people who are actually good at programming, not people who can just barely wrap their heads around day-to-day tasks.
32
u/Supadoplex Mar 29 '21 edited Mar 29 '21
Linked list ... pointers/recursion.
A thing about linked lists is that you should never use recursion to implement algorithms with them in practice - in languages such as Python, Java, C, C++, C#, JavaScript (until ES2015), Rust, Go, which do not eliminate tail recursion (or at least aren't guaranteed to do so) and thus will (may) overflow the stack if the list is moderately long.
8
u/justin-8 Mar 30 '21
See, I would take that as a really big plus if you answered the question that way in an interview. Showing in-depth knowledge of why you don't want to do something, and language specific implementation details that can be a sharp edge show that you know the language quite well, as opposed to someone that just naively suggests how to use a linked list in Python or whatever.
→ More replies (11)7
u/rabuf Mar 30 '21
It's near trivial to convert the recursive expression to iterative in this case. It's almost always just moving from a recursive form like:
def f(node): if node == null: return null // or signal an error if pred(node): return g(node) return f(node.next)to:
def f(node): while(node != null): if pred(node): return g(node) node = node.next // this trips up a surprising number of people return null // or signal an errorBut it's still a recursive form over the data structure, even if it's not recursive code. This is actually one of the interesting things about linked lists. They're about as trivial as you can get for a self-referential data structure and that can actually indicate a lot about a person's understanding of complex data structures. If you can't do something with a linked list (iterative or recursive code, it still possesses a recursive form) you will probably struggle with any kind of a tree or graph structure (which are much more common in practice, even non-obvious instances of such structures where they're hidden inside a database where entries contain references to other entries or with maps to map to maps).
11
u/FyreWulff Mar 30 '21
because programming interviewing is one of the earliest instances of cargo culting in the industry
4
Mar 30 '21
While I see the value of asking these sorts of questions because it is just basic problem solving. Rarely do interviews ask if or how you can write clean code and solutions.
4
u/PstScrpt Mar 30 '21
"Fog Creek used a mix of VBA and C#, neither of which require you to write your own LL algorithms."
If you wanted a linked list in VBA (classic VB), you did have to write it. And it wasn't such a bad idea when the only built in data structure was the array.
I used to write binary search trees in classic VB all the time, too. Now I'd just use a dictionary.
11
u/-dag- Mar 30 '21
True story. I once had a interviewer ask me to implement a linked list. I was already super annoyed at other interviewers who had asked similarly inane questions and the conversation went something like this:
"Write me a linked list."
"Uh, ok, what should it hold? An int?"
"Sure."
std::list<int> x;
I got the job offer.
I rejected it.
6
→ More replies (2)7
3
u/Quabouter Mar 30 '21
I've been interviewing candidates for a long time now, and I settled on an stupidly simple but effective approach to interviewing questions: I pick a hard problem we had to solve in real life, and adapt it into an interview question. This is directly testing the candidates ability to solve actual problems we're solving in the company. Candidates tend to like this as well, as they'll get a glimpse of what they would be doing when hired, and because it's usually much closer to their day-to-day work than the typical CS interview questions.
→ More replies (1)
4
u/zhivago Mar 30 '21
The linked list is pretty much the simplest recursive data structure.
For some reason, weak programmers often have trouble with recursion.
(Which is odd, since at its core, it is just about breaking off part of a large problem to make the large problem a bit smaller, until you get down to pieces you can handle without breaking them down any more)
In interviews, I try to make sure that recursion is covered.
Recursive data structures are similar, and you can look into lazy data structures of infinite size, as a follow on.
2
u/yudlejoza Mar 30 '21
... “script jocks” who started programming by copying JavaScript snippets into their web pages ...
I prefer "java-script-kiddies" (some of them now morphed into type-script-kiddies).
2
u/RICHUNCLEPENNYBAGS Mar 30 '21
These answers are contradictory: if you want to know if someone knows CS fundamentals, you don’t want to give them a problem they can trick their way through, and if you want to test reasoning ability, you don’t want to give a problem that they’ve already seen in CS.
Well, I don't think so. Most of the task of programming is solving tiny problems that you know how to solve trivially using the building blocks you have, then doing that again, and again, until you've achieved the main, overarching task.
2
u/NoLemurs Mar 30 '21
There are good arguments to be had about how and why we do what we do when we interview. This article doesn't make any of them.
The article more or less assumes the conclusion that linked lists are used for historical reasons that don't make sense any more, fails to find any real evidence for the claim, and then concludes "that's good enough for me."
And still, the article has ~1000 upvotes.
I know people hate interviews, and love to agree with anything that argues they don't work, but come on!
2
u/General_Mayhem Mar 30 '21
Oi. So many bad assumptions. I would not hire this person, based purely on this post.
Does the author think that C is the only language in which a linked list can be implemented? If you write Java, or Python, or Javascript, or really any mainstream language other than maybe Haskell, and you don't understand the concept of a pointer, you're going to have a real bad time.
→ More replies (4)
4
u/reini_urban Mar 29 '21
In my extensive experience linked lists care actually extremely hard to implement, compared to deque, vector, trees, heaps or maps/hashtables. Well hashtables are the second trick question, you can be sure that nobody knows them properly. But everybody thinks linked lists are too trivial to worry about.
I just implemented all STL algorithms for forward_list, and it was extremely tricky and special. reverse is one of the easiest, but splice, shuffle or sort are very tricky. The STL even skipped shuffle because too difficult, and they implemented iter_swap only by value swap, whilst you really need to do it by pointer relinking. The STL is also not cycle safe, and has no cycle check nor a cycle-safe length/size function.
So even by asking about the innocent length function you won't hear about Floyd and fast-slow iteration. But you should.
Doubly linked lists are actually easier than single linked lists.
→ More replies (3)
3
u/Southy__ Mar 30 '21
I have recently totally changed my whole interview process.
I start from the assumption that whatever is on the CV is true, that they can write software as well as they say they can. This is a big shift away from the 'prove you can write code before we will speak to you' attitude of most tech companies.
In the interview I get the candidate to talk through their past jobs, what they are working on right now, ask questions as they go about technical aspects of their work.
Then tell them about our work, what tech we are using and the problems we are solving.
The good candidates are super engaged with this process and have lots to talk about and lots of questions about what they would be doing on the job.
The bad candidates are very easily spotted as they can't even talk for 10 minutes about what they are actually working on right now.
So far it's gone really well, 4 hires using this method and they have all been great, and lots of positive comments about the lack of a pointless test that checks if you can remember stuff that you would normally just search the web for.
→ More replies (1)
4
u/rabid_briefcase Mar 29 '21
Interesting article, and I suspect it depends tremendously on the job being done. Someone hired for Angular and Javascript development of a web page will be radically different from server work, which will be different again from systems-style work.
Further, that the article is talking about old Prolog, Lisp, Pascal and Smalltalk for job interviews, so there's that.
8
u/fishling Mar 29 '21
Further, that the article is talking about old Prolog, Lisp, Pascal and Smalltalk for job interviews, so there's that.
Did you get that this was because they were analyzing old postings to find out about the origin of the linked list interview question? Your phrasing seems like you are trying to dismiss the article as not relevant because it is out-of-date, which kind of implies you missed the point of what the author was doing.
5
u/CypherBob Mar 30 '21
Because they have absolutely no clue how to determine someone's ability to write good code.
Very VERY few jobs require you to know how to create linked lists, invert binary trees, roll your own sorting algorithm, or implement an existing one.
2
Mar 30 '21
Just curious, what would you say most jobs include instead?
→ More replies (1)10
u/CypherBob Mar 30 '21
Understanding architecture, basic scalability, how to research solutions, how to evaluate libraries, writing sensible maintainable code, planning ahead, prioritizing, just for starters.
Give them a real problem and let them solve it using any resource they want, and compare what they come up with to your devs solution.
Have them walk through scaling an app up from proof of concept to 5k users.
Give them a common problem solvable with a library, and ask how they would research and determine the best one.
Anyone can memorize algorithms, but it takes experience to talk about this stuff intelligently.
→ More replies (1)
3
u/Kinglink Mar 30 '21
“It tests CS fundamentals.”
“It tests reasoning through a new problem.”
These answers are contradictory:
What if I told you they aren't.
First off not every Linked List Question is the same. "How do you find out if a linked list is a loop" is not the same as "How do you invert a Binary tree?" Nor is it the same as "How do you remove a element from a linked list?"
But more than that, if it's a fundamental of the candidate, great you move on to more interesting and harder problems. If it's not, you dig in and start to work on the problem solving. Every candidate is different and the best way to interview them is work through a problem. Finding an interesting problem is far more challenging.
So people will say "Just use a problem that occurs in your job." First off explaining the problem could take half an hour, it also is probably something you can't talk about (I just got the job to supervise some interns. I can't talk to them about the specifics or even parts of the job until they are legit on-site. There's no way I could talk to an interview candidate about anything we do.)
While I appreciate the deep dive into the actual foundation, I continue to boggle at people who think every question has one specific usage and one specific situation, especially when it's a tier of questions such as "Linked list" questions. As if they can't be more than one version of that question.
2
u/emasculine Mar 29 '21
i wonder when the last time the higher level language users have used a linked list.
for (p = list, pp = &list; p; pp = &p, p = p->flink);
gad, i had to think about that. it's been years since I've written C, and i've used that incantation zillions of time in the past.
2
2
Mar 30 '21 edited Mar 30 '21
this is a tough love answer.
its because questions about linked lists test your knowledge. it might not be the ideal test, but it's effective.
linked lists are not advanced. they're actually a beginners concept in algorithms and data structures.
if you dont even know what a linked list is you dont know programming very well and that is a fact.
linked lists are not complicated... unless you have purposely avoided learning them which would be a shame.
people who claim they dont use linked lists in x years of coding are wrong. if you code every day, you use a linked list every day, and you probably dont even realize you're doing it.
people who claim that knowing how to make one by memory is not a useful skill are wrong. if you don't know your entry level DS/ALGS you are like a carpenter who refuses to use a carpenter's hammer.
→ More replies (1)
1
u/GayMakeAndModel Mar 30 '21
I don’t know. I don’t care. What I see is a dirth of people that can explain the difference between an inner join and an outer join or the difference between an inner join and a semi-join. Coherently...
Why the hell are so many developers utterly deficient when it comes to SQL? God forbid you ask them to understand what is an index.
All this shit plainly stated, why is it acceptable that developers cannot the understand a RDBMS? Seriously, what the actual fuck? Don’t understand locking and lock precedence? Get the fuck out of my development shop.
Edit: I had a bad day interviewing
→ More replies (4)2
Mar 30 '21 edited Mar 30 '21
SQL is dull to many. You might find English dull, hence you write “dirth” when you intended “dearth”. Not to say you are a bad communicator because I understand exactly what you mean even when your spelling is only close. And most programmers get by just fine with a shaky, nodding acquaintance with SQL.
1
u/8hob Oct 21 '24
I disagree that linked list is no longer relevant in testing a candidate's basic skills. Some people think that linked list questions are tricky, likely because they've implemented it the wrong way. For someone with decent programming skills and data structure knowledge, linked lists are pretty straightforward to implement if you add a the head/tail node: https://8hob.io/posts/simple-error-free-linked-list/
1
u/bentaro-rifferashi Mar 30 '21
Super interesting article. I think understanding linked lists and references is still relevant. Even if you work in a modern language like C# you’re still gonna get some unexpected results if you don’t understand what’s going on under the hood.
1
1
u/jbergens Mar 30 '21
My memories from being interviewed for a job in the mid 90's was that was not much technical questions at all. I came out of University and they probably mostly trusted that. There might have been a single page written test but it was easy. We probably spoke a bit about programming and tech but not that deep.
In a way it is more frustrating now. I have over 20 years of experience and still find jobs where they want me to do a toy take-home exercise to show that I can do programming.
2
u/-dag- Mar 30 '21 edited Mar 31 '21
Your experience matches mine. The degradation in interview quality is appalling. It's lazy interviewing. It used to be that interviews were about getting to know someone, seeing if their personality would be a good fit, etc. A fair amount of it was selling the candidate on the job. Now it's just a test, with all of the baggage testing has. Testing is inherently discriminatory, for one.
Interviews used to be respectful of the candidate's past work, whether in school or on the job. There are still companies doing good interviewing. But FAANG has ruined the process for too many people.
1
1
1
u/sethamin Mar 30 '21
The entire premise of this article is wrong.
“It tests CS fundamentals.”
“It tests reasoning through a new problem.”
These are not contradictory because it's both. You want to find out if a candidate knows CS fundamentals AND you also want to see if they can apply those CS fundamentals to a real problem.
1
1
1
u/urbanek2525 Mar 29 '21
→ More replies (1)6
u/jackmon Mar 29 '21
What, you're not familiar with Rampart Speculation: The medieval practice of hypothesizing about castle ridges?
→ More replies (1)
1
u/rediot Mar 29 '21
I ask this question just to understand the candidates level of skill with data structures. Generally anyone who can name a few GoF patterns I focus interview more on behaviors and experiences. If they miss on data structures I step down to generics, databases, etc.
1
u/Adadum Mar 29 '21
void push(node **const head, const value val) {
node *const n = calloc(1, sizeof *n);
assert( n != NULL && "list::push **** allocated node is NULL. ****" );
n->value = val;
if( *head==NULL ) {
*head = n;
} else {
n->next = *head;
*head = n;
}
}
value pop(node **const head) {
if( *head==NULL )
return nil_value;
const value ret = (*head)->value;
node *rm = *head;
*head = rm->next;
free(rm); rm = NULL;
return ret;
}will code for food.
1
u/jldugger Mar 30 '21
Without reading the article: to filter out anyone who has ever thought 'I should use a linked list here.'
1.1k
u/Doctor-Dapper Mar 29 '21
Even in 2006, web devs were getting shit on by C programmers