5 ms·

That’s why I include a LL question in my code interviews. But, my question is about the simplest possible LL algo: Assume I have the simplest possible linked l

That’s why I include a LL question in my code interviews. But, my question is about the simplest possible LL algo: Assume I have the simplest possible linked list of integers in basic C. Just struct Node { int data; Node *next; }; Assume I also have a plain old C array of ints. I can trivially iterate through both of these data structures and sum up the ints they contain. Either way it’s a linear, O(n) operation. However, everyone knows linked lists are slower than arrays. The question is: How much slower? The most common answer I get is “2x”. This is always after working carefully through the steps to iterate a list and ignoring steps to iterate an array. I like the question because it tests 2 things: 1) Are you aware of the existence of cache? Many people I’ve interviewed have only heard of it vaguely. 2) If you don’t know the answer, are you at least curious enough to ask what the answer is and have a conversation about it?

skrebbel 7y ago
> 2) If you don’t know the answer, are you at least curious enough to ask what the answer is and have a conversation about it? This is a bad test. People might be too nervous to ask, especially if they just feel like they've failed a test. You're testing for "is this person comfortable in an interview setting", not for "is this person curious enough".
- corysama 7y ago
  True. Managing the nervousness of awkward engineers during interviews is a whole topic in itself.
  - skrebbel 7y ago
    In fact, I'd wager that one of an interviewer's primary goals should to find a way to fully disregard someone's interviewing skill. Search hard for questions that a sweaty super-nervous introvert would be able to do just as well as a confident natural talker. Find wording that lets you give hints / explain the question better without the interviewee going "oh no, a hint, that means i failed this step!". I personally think this is very hard to get right, but it has to be a top prio. It's much harder (and much more valuable) than cooking up a sufficiently difficult whiteboard coding question.
kccqzy 7y ago
I would have hated this problem. There are so many things unclearly specified. What allocator is used to allocate this linked list? Did you use a small-object pooled allocator that essentially places the nodes of a linked list sequentially in memory? Did you permute the order of the nodes afterwards? Is each node even located in separate pages, using up the TLB as you dereference? Could there be page faults when you deref the next field? Without knowing how the nodes are laid out in memory, it is impossible to answer. Unless of course, you merely use this question as a ruse to elicit a discussion about low-level systems programming.
- DarkWiiPlayer 7y ago
  > Unless of course, you merely use this question as a ruse to elicit a discussion about low-level systems programming. Didn't OP already imply that the point of the question was not as much to get a specific answer, but to probe whether or not the interviewee knows about all the factors that need to be considered?
  - kthejoker2 7y ago
    So why not ask exactly that? "What are some of the factors and tradeoffs to consider when implementing X / deciding between X and Y, etc.?"
- corysama 7y ago
  You would have done great with this question :) Asking "Do you know the magic answer I happen to know?" questions is the great sin of technical interviews. Instead the goal is to keep the candidate comfortable and semi-confident while digging out their mindset about relevant technical issues.
314 7y ago
The steps to iterate the array should impose no overhead on a superscalar processor. It’s a different situation on a simple embedded processor, but the range of possible answers for memory:ALU ratios, cache line size, cache latency, allocation patterns, MMU behavior and some other factors make this an ill-posed question. Pedantic nitpick: that is not the simplest LL algorithm. It is more complex than empty().
- corysama 7y ago
  The question is intentionally ill-posed. The goal is to find out how you model the problem, not that you guess some magic number.
  - 314 7y ago
    Asking broken questions seems like a strange way to find out what somebody knows.
tracker1 7y ago
Personally, I tend to get the impression I might not actually enjoy the work at a company that concentrates on low-level questions like that. I happen to like JS and node a lot, for very pragmatic reasons. I've also dabbled in Go and Rust for equally pragmatic reasons. It does help to understand some of the things under the covers when you need them. That said, for a LOT of jobs, code that works and is business rule correct is more important than if it takes a blink of an eye or three. I tend to prefer a first pass in node/js, and then break things off or optimize as needed in practice. Scale !== raw performance and is often more important.
- corysama 7y ago
  The candidates were applying for positions in game development at a company that made high-end 3D mobile games. Raw performance translated directly to retention and therefore revenue there.

skrebbel 7y ago

> 2) If you don’t know the answer, are you at least curious enough to ask what the answer is and have a conversation about it? This is a bad test. People might be too nervous to ask, especially if they just feel like they've failed a test. You're testing for "is this person comfortable in an interview setting", not for "is this person curious enough".

corysama 7y ago
True. Managing the nervousness of awkward engineers during interviews is a whole topic in itself.
- skrebbel 7y ago
  In fact, I'd wager that one of an interviewer's primary goals should to find a way to fully disregard someone's interviewing skill. Search hard for questions that a sweaty super-nervous introvert would be able to do just as well as a confident natural talker. Find wording that lets you give hints / explain the question better without the interviewee going "oh no, a hint, that means i failed this step!". I personally think this is very hard to get right, but it has to be a top prio. It's much harder (and much more valuable) than cooking up a sufficiently difficult whiteboard coding question.

kccqzy 7y ago

I would have hated this problem. There are so many things unclearly specified. What allocator is used to allocate this linked list? Did you use a small-object pooled allocator that essentially places the nodes of a linked list sequentially in memory? Did you permute the order of the nodes afterwards? Is each node even located in separate pages, using up the TLB as you dereference? Could there be page faults when you deref the next field? Without knowing how the nodes are laid out in memory, it is impossible to answer. Unless of course, you merely use this question as a ruse to elicit a discussion about low-level systems programming.

DarkWiiPlayer 7y ago
> Unless of course, you merely use this question as a ruse to elicit a discussion about low-level systems programming. Didn't OP already imply that the point of the question was not as much to get a specific answer, but to probe whether or not the interviewee knows about all the factors that need to be considered?
- kthejoker2 7y ago
  So why not ask exactly that? "What are some of the factors and tradeoffs to consider when implementing X / deciding between X and Y, etc.?"
corysama 7y ago
You would have done great with this question :) Asking "Do you know the magic answer I happen to know?" questions is the great sin of technical interviews. Instead the goal is to keep the candidate comfortable and semi-confident while digging out their mindset about relevant technical issues.

314 7y ago

The steps to iterate the array should impose no overhead on a superscalar processor. It’s a different situation on a simple embedded processor, but the range of possible answers for memory:ALU ratios, cache line size, cache latency, allocation patterns, MMU behavior and some other factors make this an ill-posed question. Pedantic nitpick: that is not the simplest LL algorithm. It is more complex than empty().

corysama 7y ago
The question is intentionally ill-posed. The goal is to find out how you model the problem, not that you guess some magic number.
- 314 7y ago
  Asking broken questions seems like a strange way to find out what somebody knows.

tracker1 7y ago

Personally, I tend to get the impression I might not actually enjoy the work at a company that concentrates on low-level questions like that. I happen to like JS and node a lot, for very pragmatic reasons. I've also dabbled in Go and Rust for equally pragmatic reasons. It does help to understand some of the things under the covers when you need them. That said, for a LOT of jobs, code that works and is business rule correct is more important than if it takes a blink of an eye or three. I tend to prefer a first pass in node/js, and then break things off or optimize as needed in practice. Scale !== raw performance and is often more important.

corysama 7y ago
The candidates were applying for positions in game development at a company that made high-end 3D mobile games. Raw performance translated directly to retention and therefore revenue there.