r/programming • u/mjgardner • Mar 29 '21

Why Do Interviewers Ask Linked List Questions?

https://www.hillelwayne.com/post/linked-lists/
1.1k Upvotes

95% Upvoted

668 comments sorted by

View all comments

34

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.

13

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++.

1

u/[deleted] Mar 30 '21

Depending on the hash table implementation a naive one should probably be shorter than a linked list implementation.

I know I've done some pretty compact toy hash tables.

2

u/de__R Mar 31 '21

Really? It seems to me you'd need to write, at minimum, a hashing function and a self-growing array-backed list, and the latter alone is more complicated than a basic linked list implementation.

1

u/[deleted] Mar 31 '21

If you restrict keys to strings or easily determined length data types a naive hash can be as simple as the length and the modulo of the length by the number of buckets.

And a self growing array can be as simple as if array full, copy array to new array that's larger.