15 ms·
Why do interviewers ask linked list questions?
- sorokod 6y agoInterviewing DMs on twitter is research? Whats wrong with looking at CS textbooks and see when the topic became common?
- mandelbrotwurst 6y agoYes. You also may have missed the part where the author describes trawling through forum posts from decades past in an attempt to gather data on past hiring practices in addition to today's. It's also possible (likely, even) for the time that a topic starts showing up in textbooks to be different from when it starts showing up in job interviews.
- sorokod 6y agoSure it will, about the time it takes students to get into interviewing roles.
- hwayne 6y agoJust to head off any speculation about the reasons I didn't study CS books, it's 100% because I Just Forgot > While reviewing this post, my friend Alex Koppel suggested another idea: comparing how much the corresponding language manuals talk about memory manipulation. In retrospect, that’s a much better idea than trawling Usenet posts. I just didn’t think of it at the time, probably because I was already trawling Usenet to understand the job market. That’s a good research lesson: don’t over fixate on one primary source.
- hwayne 6y agoAuthor here. Why wouldn't interviewing DMs on Twitter be research? I'm getting "oral histories" from a bunch of different people and comparing them for common patterns. It wasn't the only thread of research I did, but it was really helpful to orient myself at the start.
- beeforpork 6y ago> There’s a good chance you’re totally disconnected from the programming scene. That made me grin -- 'the programming scene'. What a club!
- zabzonk 6y ago> FORTRAN-77: You don’t have any dynamic memory or data structures, so this is impossible in the first place. It's easy to write a linked list in FORTRAN-77, using an array as the underlying storage - I've done it several times.
- jonathankoren 6y agoI one time took a class that introduced every linked data structure (lists, trees, stacks, queues, etc) with statically allocated arrays. Only later did they show the dynamic memory implementations. I thought it was a bit weird at the time, but now I guess it was to get students to focus on the data structure, instead of worry about pointers.
- karmakaze 6y agoSimilarly for recursive algorithms in COBOL, before the newfangled RECURSIVE program type.
- zabzonk 6y agoNay! This ungodly nonsense be flying in the face of nature! Some things Man was not meant to meddle with.
- njacobs5074 6y agoSo the author's theories certainly resonate. I started my professional career in the mid-80s and yes, having facility with C and pointers in particular was critical. I can remember asking potential candidates around that time to explain the practical differences between doubly dimensioned arrays and pointers to pointers. Without a doubt, a SIGSEGV was always a prelude to a painful session with adb trying to track down where your arithmetic had gone wrong.
- screye 6y agoThe linked list thing happened to me very recently. 3 interview rounds and all asked linked lists questions back to back. I was very honest in that in my 2 years on the job, (ML, DS) I had never once run into a situation where I would use a linked list. I didn't remember if Python even had a default linked list implementation and I decided to implement it from scratch. Wrong decision. I didn't get through, but the choice of linked lists was quite bizarre, esp. for a Data Scientist position. I would have much preferred a coding question that was relevant to the job or a take home assignment. Well, I guess it was a good signal nevertheless.
- mhh__ 6y agoI think it's very possible to pass all the courses and still be a pretty lousy programmer. If I read someone's code I'm often not really looking for the correctness at the beginning, but whether they get programming i.e. it's more than just characters on a screen which pass the tests
- devoutsalsa 6y agoHow can you tell if someone gets programming? Could you share a couple examples of getting (or not getting) programming?
- mhh__ 6y agoI think it would be rude to give identifiable examples, but the things that trigger my subconscious when reading good code are often the perfect balance of aesthetics, pragmatism, and mechanical sympathy for one's surroundings. Understanding even the absolute basics of how modern processors actually work is a huge plus for me because I'm biased. The absolute basics also apply obviously - good comments, variable names that I don't have to run the program to divine the meaning of for example. I wouldn't try to judge this based on an interview or whiteboard however, real code written for fun rather than dance monkey dance
- nullserver 6y agoHand them a small hash/dictionary {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.
- prepend 6y agoI used to ask about linked list (and connection pools) as a stage two fizzbuzz just to give a straightforward requirement to see how people think through something that has a little bit of a hard bit and might make the interviewee think to make sure requirements are met. It also helps a little with culture to weed out the “I’d use a library” or “I’d Google it” as the purpose is to just walk through how to code something. I never asked anyone to write a linked list, but it is sort of straightforward to write in a short period of time.
- benmller313 6y agoDo the people you weed out that suggest using a library know that the purpose of the question is to walk through how to code something?
- izacus 6y agoDoes it seem reasonable to you to assume that a task on your job interview will be answered with "I'll take someone elses library" and they'll just be "ah, ok, you're hired!"?
- jhayward 6y agoYes, because that's the correct answer in a real-world situation. If you want to play some game with the applicant, be sure to tell them you're playing fantasy and not reality.
- prepend 6y agoYes and I usually say that. It’s not meant as a trick question. Sometimes I’ll prefix it with “While you would never do this is real life, please walk me through how you would design and implement a database connection pool...”
- collyw 6y agoI got asked a python question that involved a couple of list comprehensions. I did it and got asked how to do it without an intermediate variable. It involved nesting the list comprehensions, and I nearly didn't get it, not because I didn't understand how to do it, just that I have a personal rule never to do that, as it makes code quite difficult to read.
- cgh 6y agoI like reading about software history and this is a new angle to approach it from. When did people start testing one another on this particular thing, and why not this other thing? I learned how to write linked lists in some first year comp sci course in the mid-90s and used them extensively in my first job after graduating, which was writing database software in C. I'm sure I was asked about them in various interviews afterwards, most of which involved no C whatsoever, and I'm equally sure I thought this was a completely normal thing to ask. In retrospect, it does seem strange.
- grillvogel 6y agobecause someone was assigned "data structures" question on the interview loop and needed to come up with a problem
- 908B64B197 6y agoWhy? Because every serious CS program will expose students to array vs linked-list and basic memory management during the first year. 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.
- topaz0 6y agoYou clearly didn't read the post
- 908B64B197 6y agoI did. He root-causes it to Joel Spolsky's interview style which the author claims was heavily influenced by what was useful to know at Microsoft during his tenure. My response is to highlight why it's still relevant to ask them today.
- mariodiana 6y agoI'm going by memory of Spolsky's article, from when I read it many years ago. One of his main points was that in asking a person to reverse a linked list, he watched to see if the person first sketched out a diagram, or simply started writing code -- because, as he believed, no one could do this without first sketching out a diagram, and going right to code was a red flag, indicating someone who (my memory is foggier, here) lacked the right temperament for a developer.
- dragonsngoblins 6y agoCouldn't they just... mentally imagine the diagram? I personally am bad at picturing things in my head but a simple linked list is pretty easy to do, and it isn't as if reversing one is an especially complex operation. To be clear I'm not trying to suggest you think a candidate couldn't do that, I'm just surprised that this apparently didn't occur to Spolsky
- 6y ago
- vkou 6y agoThe answer should be obvious - because linked list questions require you to understand the concept of a reference, and because large numbers of candidates can't solve them.
- skyde 6y agoI don't believe large numbers of candidates can't solve them. I believe large number of candidate can't solve it on whiteboard in less than 10 minutes. If you honestly think that University give diploma to people that can't write a linked list then we have a bigger problem as an industry!
- vkou 6y ago> I don't believe large numbers of candidates can't solve them. I believe large number of candidate can't solve it on whiteboard in less than 10 minutes. Which is why I give them the choice between a whiteboard and a laptop, and give them closer to 45 minutes to do so, and give generous credit for close-enough solutions. A large number of them can't solve these questions under those constraints, either.
- skyde 6y agodo you believe those people where not able to solve these kind of question the year they graduated ?
- globular-toast 6y agoThe question shouldn't be about linked lists. That's very specific and, as mentioned, has simple rules that can be learned and regurgitated. It should be about linked structures in general. It's a great way to separate really good programmers from "coders" and "devs" imo.
- TheChaplain 6y agoIt's a simple question with radically different answers. I had people not knowing what it is, some says they find an existing library and few excitedly explain on a whiteboard how they work, single vs double-linked etc. These days I would not reject an interviewee if they didn't know about linked lists, but depending on their answer it may be what makes their resume end up in the "2nd interview" pile instead of "maybe".
- baron816 6y agoI used to ask a linked list question. It was “write a function that takes a linked list where values are integers and return a new linked list, grouping the odd numbers first and the even numbers last.” I was very specific about what I was looking for: not just to solve it in the “simplest”/most performant/most concise way, but to see if they could create good abstractions to make it easy for a very junior dev to read and reason about. So, hopefully that meant building some sort of linked list class, with methods for “add”, “concat,” and maybe “filter”, and not just manipulating nodes directly.
- skyde 6y agodid you really expect someone that have a bachelor or master degree in computer science to not know how to do this. Or you just wanted to not hire someone if it took him more than 10 minute to do it on a whiteboard?
- deleted 6y ago[deleted]
- baron816 6y agoI wouldn’t tell people directly that they should write those classes/methods, only hinted towards them. I don’t think anyone came up with the idea of writing “filter” on their own, and people often struggled with the implementation. The interviews were and hour long and I gave lots of hints. Not a lot of successful candidates from it, and I was quite lenient.
- skyde 6y agoI mean if you feel that all the people you interviewed are worse programmer than all the people you went to school with then it's likely the problem was not the candidate but the way the question was asked.
- baron816 6y agoI don’t have a CS degree and not everyone we interview has one. But judging candidates against who you went to school with seems like an odd strategy. I don’t understand your thinking there.
- fredophile 6y agoI've asked linked list questions before and here's why I sometimes use them. I don't have a ton of extra time in an interview and I can expect a candidate to be familiar with linked lists or I can explain the data structure very quickly. Linked list problems are relatively simple. Candidates are under a fair bit of stress during an interview so simple problems become harder than they would normally be. You also don't have time in an interview to dig into very complex problems. With a linked list I can give a problem that most candidates can work through in the time we've got and then ask follow up questions based on how they approached and solved the problem.
- Salgat 6y agoWhy not write something more practical? For example, have them write a class that demonstrates a few design patterns like dependency injection, has a basic interface it implements (for example, a DrawPixelArray method), that kind of thing. This to me is far more informative about skills the person would be using in their day-to-day job.
- dahfizz 6y agoIt depends on the job, I think. In some positions, it is a lot more "practical" to have a command of data structures and algorithmic thinking than it is to implement fancy OO design patterns. EDIT: A quick glance at OP's profile suggests that they are an experienced C++ programmer. I definitely think being able to handle pointers is more practical/fundamental skill than dependency injection in that context.
- fredophile 6y agoTo be clear, I don't ask them to write a linked list class. I would typically be asking them how they would implement a function that takes a linked list and has to do something with it. A lot depends on who I'm interviewing and what I'm looking for for that role. I don't think there's a one size fits all interview question for programming jobs. In the above example I might only want them to explain how they would solve it to see their problem solving abilities. In other cases I might want to see some whiteboard quality code and we can segue into other topics like debugging or testing the code they wrote. Your example probably wouldn't be suitable for an entry level candidate who I would expect would need more guidance for things like class or interface design but I'd expect to be able to implement functions given an API.
- darrylb42 6y agoDoing a linked list is my primary question for coding interviews. It is something I think everyone has seen or done in school so should be pretty easy. It is also small enough that it can be explained during an interview if they don't know. A linked list can be programmed in any modern language that has references. It lets me get some insight into how the person thinks and works through problems. Primary insights I am looking at: How does the candidate approach the problem as stated? Do they ask any clarifying questions? Can they explain the code they have written? Did they listen to what I asked for? Some people who have been studying will just start typing what they have memorized. Are they doing anything interesting with the language they have chosen? Are they able to answer questions about their choices? Most of the time people will get through some kind of add method, and a delete method. Usually by that time I have enough information to move past that question. Doing puzzles like reverse the list don't really add any more information and I have stopped asking that even if there is time.
- nicoburns 6y ago> It is something I think everyone has seen or done in school so should be pretty easy Only if they studied CS! A lot of good devs didn't. However, as you're willing to explain the concept during the interview, I think your usage is reasonable.
- tchalla 6y ago> It is something I think everyone has seen or done in school so should be pretty easy. Here are some things everyone has seen or done in school : proofs on in theorems on geometry, integral of an obscure function. I am pretty sure it should be "easy" to answer them in an interview.
- Jtsummers 6y agoOne of the items under discussion is appropriate to the group under discussion (programmers), the other is not. For the most part we don't care if programmers can integrate functions or prove theorems, we do care if they can program. Whether linked list questions are appropriate or not is another matter, but at least they're in the correct domain.
- buescher 6y agoThere are linked list questions in the interview tips chapter of Deep C Secrets if I remember correctly. That's definitely 1990s and definitely C.
- jlizzle30 6y ago> 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 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.
- gbronner 6y agoIt filters for people who have * 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.
- sbilstein 6y agoThis. What happens in a coding interview is incredibly well documented at this point. If you can't be bothered to prepare, study, and brush up coding skills for interviews, I do not want to hire you. I tend to ask medium difficulty questions because I am looking for 1) ability to reason through a problem and 2) professionalism and motivation for a career.
- romanhn 6y agoThe point of an interview is to evaluate a candidate's fit for a particular role. This reads to me like the evaluation criteria is whether the candidate prepared for interviews or not. I don't understand this worldview at all, and I've been a hiring manager at both startups and FAANG. What's also well documented is that studying Leetcode is about keeping a warm cache of solutions to common problems at interview time, and much less to do with reasoning through problems.
- tchalla 6y ago> I tend to ask medium difficulty questions because I am looking for 1) ability to reason through a problem and 2) professionalism and motivation for a career. Congrats! You are selecting for people who 1) rote problems for interviews and 2) motivation to clear your interview.
- steve76 6y ago> If you can't be bothered to prepare, study, and brush up coding skills for interviews, I do not want to hire you. 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.
- 6y ago
- postalrat 6y agoThe same reason they will also ask dynamic programing questions: to let people who memorized all the tricks sound smarter than they are.
- davidw 6y ago* Relatively simple * Not unfamiliar to many * NULL
- jasonpeacock 6y agoI disagree with the premise that the following are contradictory: 1. “It tests CS fundamentals.” 2. “It tests reasoning through a new problem.” Both can be measured in an interview together, using well-known CS concepts to reason through a new problem based on CS fundamentals. Especially today, as almost everyone uses standard library implementations, asking candidates how those implementations actually work, and then working through a variation of them (e.g. add an unusual requirement) is very useful in an interview context. Everyone "knows" what a Linked List, so you don't have to spend a lot of valuable interview time explaining it. The implementation for the simple case is short enough it can be quickly written out. Then you can add a novel requirement for the candidate to extend their implementation. Now you've checked all 3 boxes: 1. Knowledge of CS fundamentals 2. Using well-known CS concepts 3. Reasoning through a new problem If interviewers were longer, or used alternate paradigms (take-home exercises or pair-programming), then much better questions can be offered. But ultimately, doesn't all software engineering come down to the 3 things I described? Sure, the context is different if you're a Frontend vs Backend vs Mobile vs Embedded person, I hope the interviewer is adapting for that and not asking everyone the same Linked List question.
- phendrenad2 6y agoThe problem is CS degrees. What do you learn in a CS degree? First you learn data structures, then you learn algorithms, then maybe if there's time they burst your bubble and tell you about caches and how CPUs actually work. What's the first data structure you learn? The linked-list, of course. So to many interviewers, focusing on linked lists is the equivalent of fizzbuzz. No one could be a computer programmer without it!
- Jtsummers 6y ago> The problem is CS degrees. What do you learn in a CS degree? First you learn data structures, then you learn algorithms, then maybe if there's time they burst your bubble and tell you about caches and how CPUs actually work. There's 4 years in a standard CS degree program, there's time unless your curriculum or choice of focus is more strictly on the theoretical side, which is not typical outside of a few universities (as the only or primary option). Every second tier university graduate I've mentored has understood these topics. Except for the past 5 years where they are, more consistently, only capable of programming in Python or similar high level language and their program of study has divorced itself of talking about the real-world behavior on real hardware (from the same schools that, previously, seemed to understand or at least be aware of these topics).
- tester89 6y ago> There's 4 years in a standard CS degree program, Depends on the nation, in Europe 3 years is the standard.
- Jtsummers 6y agoFair enough, but my understanding of European universities is that those 3 years tend to be more focused (on a specific area of study) than US university programs. That is, this is a reasonable description of many US 4-year degree programs for CS (using semesters): Freshman: Semester 1: English 101, Math 101 (maybe calc), Physics 101, CS 101, History 101 Semester 2: English 102, Math 102 (calc by now), Physics 102, CS 102, History 102 Sophomore: Semester 1: Math 201 (calc), Chem 101, CS 201, Language 101 Semester 2: Math 202 (last calc, maybe stats), CS 202 & 203, Language 102 Junior - Senior: Mostly CS, with math or engineering support courses My understanding of European universities is that the non-degree courses are typically not present unless someone specifically elects to take them (perhaps for a dual degree or minor). Which still goes with my point. Algorithms and data structures take no more than 1 year to study (EDIT: the basics), whether in a European or US university you have 2-3 additional years to cover the rest including getting into the technical details like why you want one of these loops and not the other: for i from 1 to n for j from 1 to m a[i][j] = ... // versus for j from 1 to m for i from 1 to n a[i][j] = ...
- throwaway284534 6y agoI really hope that companies continue asking these questions and rejecting great candidates who choose to keep real world knowledge in their figurative L1 cache. After all, it makes it much easier for my company to find people that code real world solutions instead of grinding on leetcode.
- runawaybottle 6y agoIt’s probably one of the more fair (or easiest fair data structure) you can ask someone about. If you don’t practice bfs or dfs recently you can forget traversal. With a linked list you can reason through it on the spot.
- kaiju0 6y agoPlease everyone keep asking for cs fundamentals questions for interviews. I get to keep picking up great devs that get annoyed at all the weird questions. I ask about how applicants have implemented things and bang around the edges with questions to gauge the depth of their understanding.
- snapetom 6y agoThis. 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.
- kjeetgill 6y agoThis is really interesting. If it's not prying too personally, mind sharing where you're at or some example companies? I've interviewed at maybe 15-20 companies over the years and never not had to whiteboard or live code in some way. The thought of not having to seems so foreign to me.
- snapetom 6y agoI feel like whiteboarding has only gotten popular in the last 10 years, maybe less. I've been at six companies in that span, interviewing at probably 12-14 total. Out of the six, four have been tech startups including the one I am in now. The industries have been cybersecurity (x2), online retail, and online marketing. The two non-startups have been in education and healthcare. 2016 was the last time I didn't have the luxury of looking while jobless, but I was still pretty picky. I already knew I didn't like white boarding, so I started to warn recruiters that I wasn't good at it. Two early interviews, I told recruiters this, and they both urged me to go to their interviews anyway. I went ahead thinking it would be good practice. Not surprisingly, I wasn't offered because I just wasn't that interested, and it showed in the interviews. I remember getting a bit curt in one interview because the last person that I interviewed with (going on 4 hours), asked me the same coding question as the first person. After that experience, I became more inflexible on my no-coding interview requirements. It probably was just dumb luck, but this wasn't a problem, I was told. Two more companies after that were at companies that did architecture interviews centered around data platforms, and I eventually took one offer.
- sombremesa 6y agoSo why do people like to conduct verbal interviews? If you ask people, you usually get one of two answers: “We can safely assume everyone can speak.” “It tests reasoning through new information.” These answers are contradictory. Cue popular article built upon the back of this strawman. Makes one wonder about the camel that broke the strawman's back.
- legerdemain 6y agoAn interesting dive into the cargo cult of tech interviews. Maybe I misunderstand the author's methodology. Here's the chain of reasoning he seems to be advancing: 1. Linked list questions are often about pointer manipulation. 2. C and Pascal make frequent use of pointer manipulation. 3. If Usenet posts that mention C and Pascal mention pointer manipulation more than Prolog, Lisp, and Smalltalk posts mention it, linked list questions must have been designed to test for experience with C and Pascal. The last inference seems either extremely circumstantial or trivially true. Prolog doesn't expose pointers to the user, as far as I know. Smalltalk just seems to have object references. If pointers are only available in C and Pascal, then it stands to reason that only C and Pascal posts will mention pointers. There's nothing about linked lists in this argument. So, sure, a category of interview questions that crucially rely on pointer manipulation does test a candidate's understanding of pointer manipulation. But looking at Usenet posts does not offer any additional support for this explanation. I can also imagine that those questions were posed in C or Pascal, which itself obviously filters for people who have used C or Pascal.
- hwayne 6y ago(3) is backwards: it's a prediction, not a deduction. I had the theory "LL questions were meant to test C/Pascal knowledge", based on studying `net.jobs`. I then came up with a test for the theory: if it was true, then the C and Pascal newsgroups would spend a lot more time talking about pointers and memory manipulation than other language newsgroups. That turned out to be true. If it turned out to be false, then other programmers are likely spending as much time thinking about memory manipulation as C/Pascal programmers, meaning LL questions wouldn't be a good shibboleth. That doesn't mean the theory is true, but the fact it withstood my prediction gives me more confidence in it, the same way I'd be more confident in a scientific. Another prediction would be that C/Pascal manuals spend more time on LL algorithms than manuals for other languages. That one I haven't (yet) checked.
- legerdemain 6y agoI understood that you were testing a hypothesis. My point is that the test is only improving our confidence about LL questions marginally or not at all. Specifically, you already have the premises that LL is about pointers, and that some languages are far more "about pointers" than others. Validating the fact that people talk about pointers in posts on languages that support pointers and that they don't talk about pointers in posts on languages that don't support them is a forgone conclusion. Like, I'm buying the argument overall and I think it's a useful dive through history, I'm just not buying the test.
- DenisM 6y agoThe goal of such questions is not to find very competent engineers, but to remove most of the very incompetent. It's one step above the fizz-buzz.
- deleted 6y ago[deleted]
- failwhaleshark 6y agoCS interviewing theater. 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.
- tdeck 6y agoIt's kind of funny that linked lists are almost never an appropriate choice on modern systems because of their poor locality and cache performance. Linked lists were a much better fit for 1970s and early 1980s microprocessors that almost never had caches (memory access time in the 1970s was similar to clock speed). That means linked lists are increasingly relegated to toy problems and unusual domains. They're no longer really a practical tool to organize data - it would be better in many cases to use an array and copy the entire contents on insert.
- Jenya_ 6y agoOn my work we do use linked lists, they are simple and convenient to collect a few items of data together when the item count is not known in advance. The trick is to allocate linked list structures from the arena allocator (which keeps these structures close in memory). The programs in my work may run for days and may use terabytes of RAM (EDA chip design verification). I agree that linked lists could be optimized, but usually they are not the worst offender. The biggest gains in performance usually happen when an accidental O(n^2) slowdown is replaced with a correct n*log(n) version.
- CyberDildonics 6y agoThere are a couple of large red flags here, but why not just use an array instead of an arena allocator and a linked list (of pointers I'm guessing). If you need a linked list, use an array with indices and you can cut the size in half if you don't need 64 bit integers. If it has to be enormous, make a linked list of arrays for better locality.
- Jenya_ 6y agoOur arena allocator does not reuse memory for simplicity (it allocates only forward, like a stack). A lot of the libc malloc complexity comes from the need to manage deallocated pieces of memory. Which means that using array over this arena would waste more memory (due to array resizing) than linked list. When array is resized, the unused memory from the old array will stay unused until the whole arena is deallocated.
- oerpli 6y agoAn anecdote: I prepared a little bit with Hackerrank for my Google interview (in Oct 2018) and never once encountered a problem where a linked list would be remotely useful. I also watched the YT video about why LL are useless in practice in most cases (cache locality etc) and I therefore eliminated them +- completely from my "toolset" (despite being actually pretty comfortable with them (spent a lot of time implementing sort algorithms on single & double linked lists). Then, one of the interviews had some problem about a scenario that wasn't actually that far away from something one could encounter in real life and the optimal solution (by far) was with a simple linked list. I completely blew it. I devised some convoluted MinHeap solution with Log(n) that was confusing as hell and my interviewer was wondering why he's wasting his time (he didn't tell but it was my impression). In the last few seconds he said something like "do you know a data structure with cheap inserts at the end and start" and everything was clear (but to late). No hard feelings, wouldn't have hired myself after that performance as well.
- mvh 6y agoWild speculation: because Noetherian induction is kind of tricky? And linked lists are a way to sort of allude to that trick ones without calling it out by name?
- sevensor 6y agoMy personal relationship with linked lists has had its highs and lows. When I was teaching myself C as a teenager, the linked list was the first pointer-based data structure I implemented myself, and the cause of so very many segfaults. I was so delighted to understand how it worked. But time passed, I eventually discovered languages that implement lists for you, and my relief was infinite. I'm glad I understand how linked lists work and I hope I rarely need that knowledge. Unfortunately McDowell's Interview Book seems unstoppable and I expect to be answering list questions forever.