Why a linked list always come between me and a great job offer | Hacker News Reader

Why a linked list always come between me and a great job offer

13 pointshelpless50 comments

Recently I interviewed at a big company in bay area and everything went well except I can't FINISH (but explain the approach and half coding done) coding a version of reverse a linked list in 20 minutes. I am coding in java for last 4+ years. Why all of my great work experience and coding and design skills + good performance in other 4.5 interviews are escaped by a single linked list question?? Is this the trend in all over bay area technology companies????

View on HN

While I strongly dislike "puzzle questions" and questions which don't directly apply to the job (e.g. Reverse Linked List for a Java job?), I will say that this comment:

> I checked the guy who asked me the question, he never went to any competitive school or never has done anything special except mugging up those linked list question.

Makes you look bad. Disagreeing with the questions or interview process is completely fine. Making it personal by looking up the interviewer and then suggesting that such questions are unreasonable because the interviewer isn't worthy of them is unprofessional and immature.

Also maybe this is a company YOU don't wish to work at? If they were giving you inappropriate interview questions maybe that is an indicator of the company's internal culture (e.g. unreasonable demands, etc).

The problem is that irrelevant whiteboarding questions are far more the norm than relevant whiteboarding questions. Most companies interview this way, so if you avoid those companies you avoid nearly everyone.

I'm a full stack developer who specializes in front-end. Knowing how to structure a front-end app, knowing/following JavaScript best practices, and understanding the arcane idiosyncrasies of JavaScript are in my opinion three of the biggest values a front-end developer can add. However, the companies that assess this stuff in interview are an extremely small minority. I usually get questions about binary trees.

It's partly because it's more difficult to assess those ways of thinking in interview, and it's partly because linked list kinds of questions are just the way interviewing has always been done, so people keep doing it.

A linked list is a fundamental data structure. Being expected to reason about fundamental data structures is not unreasonable.

Unless you specifically know that taking 20m to reverse a linked list was the reason for not being hired (I'm skeptical), you're just guessing.

While I don't generally ask questions like this, I'd also be wary of someone that can't reverse a linked list in 20 minutes, although it depends on what type of position you're actually applying for.

I also didn't go to a competitive school; I don't know what arbitrary criteria you'd use to decide if I've "done anything special".

I expect coders to be able to code, or at least reason about code, more or less on demand. I'm pretty forgiving about poor whiteboard coding performance since I also suck at it. But even a terrible whiteboard performance can be accompanied by the thought process behind it, and from that, you can discern whether or not the coder knows anything and just sucks at being put on the spot, or if they truly don't know.

It's not about the knowledge, it's more about being on the spot.

More experience and credentials you have, the higher expectation is desired, which leads to higher pressure to solve that problem in the best case possible.

I've been coding since 14 years old, got a degree in Computer Science, haven't been back to school in 5 years, and most of my work just comes to me as second nature. If I have just small doubts of my abilities, I just cannot perform. Which happens during interviews.

I can reverse a linked list even in my dreams. But I was not able to finish the coding under the pressure and time constraint. I explain all the pointer manipulation etc and interviewer was satisfied (unless he was lying :) ).

These two sentences:

> "I can reverse a linked list even in my dreams."

> "I was not able to finish the coding"

are to my mind incompatible. Are you absolutely sure the issue is not that you haven't practiced enough? Bear in mind that it is a fairly trivial data structure.

I'm having a hard time reconciling the first two sentences.

If it's intuitive then where was the pressure from? And if you had 20 minutes there wasn't much of a time constraint.

The last sentence is counter to your original post, which was that because of this part of the interview you didn't get the job (which is possible, but I'm still skeptical).

I'd spend some time practicing "mini presentations" where you take a problem like this, and pretending like you're in that situation. Code on a whiteboard (or some paper on the wall). Think out loud so the interviewer knows where you're at. Practice how to write code for someone else to read, and so you have an idea of what patterns or anti-patterns you exhibit.

No need for pointer manipulation. When I had to implement reversing a linked list (for which already an implementation is there) I'd first ask whether it's single or double linked. In the former case (Pseudocode)

    LinkedList toInvert;
    LinkedList out;

Either iterate through toInvert and call out.push_front(...) on each element or (if the operation may be destructive) do

    while (!toInvert.empty)
      out.push_front(toInvert.pop_front())

All this should not take more than 5-6 lines - should be doable in 20 minutes. Also: these two lines surely could also be written under pressure.

If the linked list is double linked, I'd ask whether the reversing has to be called often in the code. If yes, you could add a direction flag to the linked list, which tells in which direction the iterator will iterate. This makes the iterator implementation a little bit more complicated, but makes the reversing O(1).

This is a solved problem.

   Collections.reverse(myLinkedList);

Absent a demonstrated performance issue, there's no reason to even consider writing and tuning a new version. There's a debugged performant library. The first engineering tool is to apply is Google, not a whiteboard.

I'm unconvinced knowing how to manipulate data structures is useless knowledge.

It's not useless knowledge, but it's less useful than sound judgement regarding which problems require the preparation of a new design and which can be solved with off the shelf components.

Twenty-five years ago It might have been faster to write such a routine than to find it in a library. I found `Collections.reverse()` in under five minutes on StackOverflow and I suck.

I think you've missed my point.

Your "sound judgement" argument is orthogonal to my "being able to reason about fundamental data structures". I doubt most people will need to manually re-write list operations. Most people will need to reason about fundamental data structures.

Ultimately I guess I just find it impossible to believe that basic coding skills are no longer relevant to a large number of commenters here, and that using a "but I can find it on teh Googs" is a reasonable response to "please write a few lines of trivial code that operate on a trivial, but fundamental, data structure".

Questions warrant answers commensurate with the effort invested in their construction. "How do you reverse a linked list?" is, on it's face, a waste if time. Beyond being a solved problem:

~ Single or doubly linked?

~ How is the data structure implemented (e.g. is there a header structure and to what does it point)?

~ What does "reverse" mean? mutate in place? create a new list? and if I am to mutate it in place, why?

~ Reversing a linked list is O(n). One implementation us pretty much as good as another. It doesn't really differentiate on insight into the problem.

~ Winding up in a situation where reversing a list is critical smells like bad design...a stack/queue would have been a better choice upstream than a queue/stack.

But though all that may make for interesting conversation, "with a library call" is the only professional answer to "How would you write a function to reverse a list?"

> "with a library call" is the only professional answer to "How would you write a function to reverse a list?"

Most interviewers - in my experience - would then mark you down as a smartarse and the interview will be all downhill from there.

I can in fact be a smartass in the presence of bullshit.[1]

I come from a field where there is an ethos of professionalism, and the answer to "How would you reinforce a strip footing?" is "With rebar."

~ Uncle Bob has a point.

~ Half of all interviewers are below average.

[1] "Bullshit" in the technical sense - when a person knowingly states something misleading or false and openly doesn't care if the person hearing those statements believes them.

I'm wholly in agreement with you. I suspect questions like this are used in lieu of a sane programming test. Although I guess they might have relevance if you have no library (embedded?) or there are weird constraints (can't think of any).

If the company is writing embedded systems, then purchasing a library will probably make more sense than rolling up a complete linked list implementation. If there are weird constraints to the point where reversing the linked list justifies writing special code, then any assumption that the linked list is the right data structure is worthy of doubt.

The truth is that in a few hours, looking at some of the code base and discussing it is going to give both parties a better feel for the fit of person and job than anything else. The interviewer gets a feel for how the candidate will deal with the mess that is someone else's code and build process and the candidate gets a better feel for the mess they will be dealing with.

How about if you are implementing a library for a new programming language?

Don't PL developers need to implement things like List.reverse() in their new languages all the time?

Rhetorical question, because I know the answer is yes.

Here's an example for Julia: https://github.com/JuliaLang/DataStructures.jl/blob/master/s...

    function reverse{T}(l::LinkedList{T})
        l2 = nil(T)
        for h in l
            l2 = cons(h, l2)
        end
        l2
    end

(Note that this algorithm is not an in-place reversal, so it wouldn't have worked for the OP's interview.)

Can you imagine someone hiring for such a position using such poor pre-interview screening that reversing a list made sense as an interview?

The premise of your remark indicates the absurdity of the claim of relevance. An interview for a position responsible for writing a new language in a language sufficiently low level to require a new `list.reverse` would invariably require implementation of a list type as well...what language includes <List> without a reverse?

Do I think that it makes sense? No. I agree with you there. Can I imagine it? Absolutely. It's just how the industry does hiring.

It's pretty well known that Google's hiring process for SDEs is designed to select for skilled computer scientists--the type of people who could do something like implement a stdlib for a new PL if needed. Then, since they can afford to hire only great all-around CS people, they can just allocate people to projects after the hiring decision is made. Of course not every SDE job at Google requires that level of CS skill, and it's massively wasteful to put most people on projects below their skill level, but they can afford to hire that way just because they're Google.

As a side effect, other companies hiring developers are likely to just cargo-cult whatever Google is doing.

> Most people will need to reason about fundamental data structures.

I've had to use linked lists precisely twice in the last 10 years and both times were because I'd been forced down to C for API reasons. Even then I just used the BSD macros and didn't give it a second thought. When on earth would I ever need to reason about them?

But they want to find out about both kinds of knowledge, your sound judgement on problems and your ability to prepare designs by reasoning about data structures and such. If they only asked questions where the correct answer in production is to come up with a new design, they'd have to ask pretty difficult interview questions. Instead, they ask questions that are simpler and common enough to be implemented by libraries to test your design skills, and your ability to determine when to use off the shelf components should be tested somewhere else. It's quite common to ask more general questions about problem solving and evaluation to get at those sorts of things.

It seems to me that data-structures are the wrong level of abstraction for software engineering positions that aren't using C or an equivalent portable assembly language.

In most situations what matters is datatypes, not data structures. That is, queues and stacks, are the important abstractions...and reversing a linked list in non-trivial cases means that:

~ Either a queue was used instead of a stack

~ or vice versa

~ or perhaps a dequeue should have been used.

Does it matter if an ordered bag is layed out in memory sequentially or with links until profiling justifies refactoring? And when you're in Java, refactoring largely going to be a matter of swapping out one set of library calls for another congruent set...and hopefully, all this happens behind an interface.

Using off the shelf components when it makes engineering sense is a hallmark of professionalism. Reinventing linked list functions is, in most situations, a indicator that a person needs close supervision.

I think this misses the point.

The real problem is: Show me you understand this basic data-structure well enough to perform a simple task.

"Collections.reverse(myLinkedList);" is the correct answer to "How would you reverse a linked list if it came up in your job?", but is not a relevant answer to the interview question.

When I was asked this they specified doing it in-place - I figured that was the only reason it'd be interesting.

If the interviewer was satisfied, are you sure the linked list question was the issue?

An alternative view on this, which may seem cynical but which I find empowering:

In their best form, these types of questions are a litmus test for whether you have a certain type of background. When they fail it's because they test for skills not required by the job. It's fashionable to complain about this, but it seems to me to be more practical and useful to just get better at answering these sorts of questions. Leveling up from "terrible" to "adequate" at this will take less time than you think, and due to the craigslist penis effect[1] will put you way ahead of the game.

Easy resource to get started: https://www.interviewcake.com/

This book is pretty well regarded: http://www.amazon.com/Cracking-Coding-Interview-Programming-...

Btw, anyone with better starting places for this, please jump in.

[1] http://www.iwillteachyoutoberich.com/blog/the-craigslist-pen...

EDIT: formatting

My personal view is cracking the coding interview is not a good quality book. I would prefer to read jon bentely book instead. or formally eva tardos or cormen algorithm book.

These companies has made computer science students simply dev ops who never use algorithm (except during interviews). So many computer science students don't go beyond cracking the coding interview. This is really sad.

Fair enough, but I feel I should clarify my comment.

I'm suggesting that if you feel the interview process is flawed even from the company's standpoint (i.e. not screening for the appropriate skills) your best approach might be to reverse engineer the interview (i.e. get better at answering the questions, instead of actually developing the [perhaps irrelevant] skills being screened for).

The Tardos book that I think you're referring to is a $100+, 850 page CS textbook with the goal of making you an expert on algorithm design. The book I suggested costs $30 at is focused on a specific goal of getting through the interview.

I'll grant, however, that there may be better resources for this (and I'd be very curious to hear what others think those are).

I agree that these interview questions are going to be around for the foreseeable future, so people need to just learn them. But it's still a waste of time -- you have a limited amount of time to devote to learning new technology. You can either spend your time building a cool side project with interesting languages, frameworks, or technologies that are highly relevant to your work or you can use it to study algorithms you will never implement outside of an interview.

When faced with this dilemma in the past I have picked the interview prep because it's necessary, but I'd rather have been building cool stuff that actually helps me do my job better.

I'm sorry to hear your interview didn't go well. I know it's a crushing blow to have weeks of build-up undone by a temporary brain fart.

Here is how employers rationalize this: resumes are not reliable. Resumes can include exaggerations, or even outright lies. When looking at your work experience, however great, it's hard for the prospective employer to know if you made any real contribution, or if you were just nominally attached to the project. Your past employers certainly won't say.

So they need to put you on the spot, to make sure you're the real deal. It would admittedly be nice if the questions were targeted towards your experience, but frankly, reversing a linked list is not an unreasonable problem. You should be able to do it.

If you performed well in the other interviews, the linked list may not have sunk you. Finding good engineers is hard, and if you demonstrated mastery exceeding basic CS problems, they may be able to explain away your mistakes as nervousness, tiredness, or just getting befuddled.

You can reference check or see code in github. If nothing is reliable then just invite candidate and play Russian roulette :)

I realize I'm going against the grain a little bit here, and I realize that reversing a linked list is a pretty contrived problem. But...

One of the things I look for is people who have a decent understanding of how the implementations underlying abstractions might be implemented. I've found that that can dramatically reduce the amount of unnecessary complexity and work (either by leaning on the properties of the implementation, or by using a different abstraction that is more appropriate).

A prime example from my work history was with Google App Engine and the data store (this was in 2008ish, before they had a solid SQL abstraction). I read the documentation for the API and kind of "got it", but it wasn't until I read the BigTable paper that I really understood how it worked and how to design for it. Each query has two parts: an index look up, and a bulk read from disk. If you're trying to do something that doesn't fit into that model, it's going to be SLOOWWWW. Once you understand that, you can be more creative in designing your indices and structuring your data to fit into that underlying model. Way better than having your "simple query" explode into 1000 subqueries.

You have no idea why they didn't hire you. It's probably a completely different reason, even if they said it was the linked list question.

If the interviewer likes a candidate, every minor error is forgiven. If the interviewer doesn't like the candidate, any minor mistake is a reason for "no hire".

Just move on. There are plenty of opportunities.

Another equally plausible hypothesis is that the other 4 interviewers gave only lukewarm feedback ("This person seems to know his/her stuff, but I'm somewhat reserved because...") and the decision ultimately against you.

Yet another hypothesis (not pleasant to consider, but it happens) is that it's got nothing to do with linked list and everything to do with another interviewer who gave you a "warm-up question", saw you spend 30 minutes on it, decided it's a lost cause and just made sure you feel good about the result (because that's the professional thing to do, and you never know if the candidate might pull off something spectacular with the next interviewer).

In general, what a candidate feels about an interview has very little correlation with how the interviewer scores the candidate. (Even for a single fixed candidate.)

other interview was finished 15 minutes early with 2 problem solved.

Are complete morons and uninformed flunkies an influential part of the recruiting process? Yes.

Do companies overlook and miss brilliant talent? It happens everyday.

Move on. Focus your search efforts on interesting organizations, dialoging with senior executives/managers who you know how to help.

You might be creating the impression of not being sharp enough. It's probably true that you will never need to reverse a linked list in real life but it is not particularly difficult either.

It is just a fancier fizz buzz test.

I completely agree. I feel like these type of interviews are biased towards developers who have just graduated and still have data structures fresh on their minds and have the free time to actually study for interviews. I also think that this is an incredibly inefficient way to hire developers for both sides of the process. I mean, having 4-5 developers spend a one hour meeting for each interviewee who has a high chance of not making it is such a waste of time. And on the interviewee side, having them take a day off just to interview? That's a lot to ask especially if they are interviewing for several companies. Again, this is a bias towards younger grads who do have the time to take a day off.

Personally, if these algorithm interviews are nothing more than a fancy FizzBuzz test, why not just provide a take home coding problem? And if the interviewee doesn't pass them, then at least they just didn't waste a vacation day to interview with the company. And if they do pass, then subsequent interviews should be more open ended (like how to design/code an elevator) and more knowledge base (deep down questions about systems that they have worked on) to prove that they try to understand the entire problem space and not just do superficial fixes.

Also IMO, asking questions where there is an obvious right or wrong answers adds unnecessary pressure to the interviewee since a 90% correct solution is still wrong. And expecting an interviewee to code during a whole day interview is crazy. How many of us can think straight after having a whole day high pressured meeting?

In all honesty, the place where I worked with the best developers was with this one company who only had an average level of difficulty on their interview process but was very proactive in letting people go if they don't measure up within 6 months. I'm not saying that is the correct approach (as it had an adverse effect on the company culture and welcoming new employees), but I think for me, I would gladly do that rather than go through the Bay Area interviews.

In my (limited) experience bay area startup attach way too much value to bullshit interview tests like these. I'm a proficient developer, I know a lot of practical stuff about programming (setting up a solid architecture, design patterns, scalability, etc.), I have proven many times that I can build, launch and market products from A to Z, but I forgot most of the theoretical stuff I learned back at school, simply because I never have to use it. For example, I failed misserably at writing a recursive function, simply because I never need it and it's usually considered bad practice.

It's nice if you know all the theory, but you really don't need that for 95% of the programming jobs.

I felt really crushed after I failed the test and forgot all that basic knowledge, but in the end it doesn't even matter.

I would argue that recursion is very important. Could you elaborate on what makes it bad practice? Sure, in languages without tail-call optimization, using it instead of a loop will incur more overhead, but certain problems (like traversing directories in a filesystem, nodes in an XML document, or any tree structure) are impossible to implement otherwise. Do you have a specific scenario in mind where recursion was a poor solution to your problem?

Having been on both sides of a technical interview many times I see these kinds of things as a sort of pissing contest. You would think that devs would approach a technical interview in a more pragmatic way, but instead it turns into a secret handshake to figure out if your interviewee has read the same books you have. I've actually walked into multiple interviews where I was effectively quizzed on the book "Programming Pearls" -- which is/was required reading at Google. There seems to be a belief among devs that if you don't know A or B then you don't know anything. I've gone from positions where I did extensive ML and signal processing to interviews where I walked out thinking I was a complete fraud. I don't know why we do this to each other....

A linked list is a pretty trivial data structure that all CS students should learn in their first course. 20 minutes is a long time, and if you couldn't figure out how to reverse it, at least in pseudo-code, during that time, I would question your grasp of CS fundamentals.

I guess that some interviews are more about showing off their (interviewer's) skills instead of mutually exchanging views. Cliched puzzles around linked lists are one game they are good at and gives them a confidence to beat you at their own game.

I honestly doubt any interviewer is looking to catch someone out by asking them to invert a linked list. Also 5 interviews must be pretty expensive, why would you try to 'beat' the candidate away at that point?

It caught me out once... At the time I thought it was useless with no real practical application. But I was only fooling myself. Reasoning about linked lists is a basic fundamental and easy to solve. After I failed, I went away and studied it, and implemented it in code. Many many people can reason about it and describe the pointer manipulation at a high level, but then only 10% can actually put pen to whiteboard so to speak. It is a remarkable question. After you master that (take half a day), move onto trees and then maybe graphs. Practice modeling some problems with those data structures and after you do that any development job is yours for the taking.

A similar thing happened to me a while back - except it was for a UX-focused front-end development position. When I turned it around and asked the interviewer why it would be a waste of time in nearly every use case to implement linked lists in Javascript, I got nothing, he just moved on to quizzing me about binary trees. This was the point at which I decided that, despite it being an interesting company tackling a great challenge, I just wouldn't be able to come in to work with people like this every day. Catch ya later, second-tier application performance monitoring startup!

:) your experience was worse than me :)

Depends on the company. I was applying for a jr/student linux admin job at a university. They asked me to code a linked/doubly/inverse linked list in C++. The school did everything in java... Beyond that no other job has asked me about linked lists.

Reply on news.ycombinator.com