[sago]

> These "solved problems" are the result of countless hours of research by computer science experts with masters and Ph.D degrees.

We're talking about reversing a linked list, right?

This is the second time I've had this kind of surreal conversation on HN (the first was summing a list of integers), and I confess I am completely baffled. We are talking about reversing a linked list.

I absolutely expect somebody with a even minimal programming competence to be able to perform simple manipulations on interconnected data. And I can't imagine a much simpler manipulation, taking into account the connections, than that.

Knowing the difference between a problem that you can solve intuitively, And one that requires hours of PhD research, is also a good skill to have.

[kstenerud]

Yes, it's only a linked list, and reversing it is trivial. The problem comes with the inevitable "OK, now how would you make it more space/time efficient?" question. I've had it countless times, and it's always infuriating because the answer is out there, on google, written by some PHD ages ago. The interviewer himself has read it, which is why he knows, and yet now he expects me to come up with something comparable in a "clean room" situation, usually involving a white board.

Really, those kinds of questions such as algorithm optimization only test your ability to come up with creative solutions in a stressful and time constrained situation. And even then you're not testing that because even the best of us will experience temporary brain paralysis in stressful situations, so you're actually just testing for luck.

And if that's what the working environment is like, fine so long as the candidate knows it's always like that and accepts those conditions (I wouldn't). But if that's NOT what the working environment is like, why are you even testing for it?

[sago]

Really? Reversing a linked list? It really doesn't take a PhD to do that in O(N) time and O(1) space. I don't remember 'reading' an algorithm, isn't it just obvious that you walk through the list flipping the direction of the links?

Now of course, I'm making a specific point about a specific question. I'm not making a point about all 'algorithm whiteboard' interviews. Maybe you misunderstood the point, and thought I was. But I agree, many of them are utterly bonkers. Nobody is going to intuitively derive Floyd Warshall's algorithm with a whiteboard in 10 minutes. And coding trivia interviews are always pointless. If you can learn the right answers to 'pass' my interview, I'm not doing a very good job, imho.

But for very simple things like basic manipulation of the the simplest possible data structure involving a reference, I absolutely think a minimally competent programmer should be able to demonstrate their ability. Can you reverse it? Can you rotate it? Can you split it into buckets? Can you twizzle pairs? Can you insert in the middle? If you can't do those things with a cons-cell, in O(N), I can't imagine how you would cope with basic manipulations on more complex data.

[spc476]

Where I work, I deal with call processing (the stuff that happens when a call is made between two phones). If I were doing an interview, I might ask "We now have to deal with SIP, which means dealing with SIP messages, which are text based. We use C and C++ in this department, but we're open to other languages depending upon ease of integration. Which languages and libraries would you use to parse SIP messages, and why?"

It's a problem we face (or rather, faced and solved [1]) unlike reversing a linked list (or implementing a Red/Black or AVL tree or sorting data).

[1] Lua (very easy to integrate with C and C++) and LPeg (for parsing text).

[virgilp]

TBH, that depends HIGHLY on the context. If I'm not familiar with Lua, do you not hire me? I'd answer "flex and bison" because they're (for me) extremely easy to work with, rest on solid theoretical foundations, have great tools for checking & understanding you grammars, and produce blazingly fast parsers - probably orders of magnitude faster than whatever you do in Lua.

Oh, and the parser code is C, so it integrates perfectly.

[spc476]

I would accept that (maybe with a follow up question if the code generated by flex and bison is re-entrant; I know that the older lex and yacc aren't). I also would accept "I would first look for an existing library that can parse SIP messages in C or C++." I might seriously question you if you answered "I would write code to parse SIP messages in C or C++".

And for the record, flex and bison might be faster than Lua and LPeg, but so far, it hasn't been an issue.

[virgilp]

> if the code generated by flex and bison is re-entrant

This has been fixed long ago, you can definitely get reentrant parsers if you need to. Also, I don't know the SIP grammar, but fwiw, I'm able to write an extremely clean recursive descent parser in C++ (1); for simple grammars, it's often an overkill to go the flex/bison route. Also by "writing code to parse messages in C++" someone familiar with boost might be thinking about using boost::spirit. That's not necessarily a bad choice.

(1) Just looked - it's in fact too complex for that; but the point is, the right tools are dependent on the skillset of the person who answers, which may be different from your own/ your team's. Just because you find writing parser by hand daunting, doesn't mean that I do (I taught compiler design at the university, worked on a commercial C++ compiler, wrote many parsers).

Your interview question is good - but the key to it is the "why" part, not the answer of "how would you do it". And it's simply a different sort of question - your question tests the mindset + domain knowledge; The "reverse a linked list" question aims at filtering-out the developers that are not worth loosing time with. A developer that can't reverse a linked list is completely useless in a C++ project (in fact, his contribution is likely to be negative - doing more damage than adding value).

[joshjje]

Yeah, dont worry about him. I fully agree with everything you are saying.