These "solved problems" are the result of countless hours of research by computer science experts with masters and Ph.D degrees. For those of you who studied computer science in college, you likely had lectures where the teacher or TA walked you through the process of resolving each of these algorithms.
Unless you are hiring for companies like Netflix, Cloudflare, Google, etc. where you basically need to invent new fields of research in computer science, expecting a programmer to "come up" with the same solution in 10 minutes a team of CS experts solved after many hours of research might be a little unrealistic.
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.
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?
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.
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).
Oh, and the parser code is C, so it integrates perfectly.
And for the record, flex and bison might be faster than Lua and LPeg, but so far, it hasn't been an issue.
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).
Hmm. Scratch Cloudflare from that list. We are not 'inventing new fields of research'. We are looking for smart people of all sorts of backgrounds to come work on our stack.
It perplexes me. What do you gain by not doing that?
A simple task on a linked list takes two minutes to explain and five minutes to solve. The kind of task someone might do for me day-to-day have a whole bunch of context, and require knowledge or explanation of architecture and data configuration. I don't want to spend more than a couple of minutes explaining the problem, just to test whether they can program their way out of a paper bag.
>The kind of task someone might do for me day-to-day have a whole bunch of context, and require knowledge or explanation of architecture and data configuration.
Did you think I wouldn't have to face this problem too?
If you can't decouple one relevant chunk of code from your software sufficiently to be able to give it with a minimum of context to an interviewee then I'd have serious questions about the level of coupling in your codebase and, by extension, your programming ability.
Yes you would. You would not faced that problem on the first day of job and you would be expected to take time to learn during first days/weeks of the job (depending on complexity).
Also, once you will have that context and understand architecture and data configuration, the task will boil down to "reverse the damm list" or "write one epic sql query" or alternatively "read this epic sql query and refactor it away for christ sake".
It's okay, we're very unlikely to work together. Feel free to keep doing it your way, and I'm not going to worry about a random HNer impugning my coding ability based on a comment about interviewing style.
Also, if you're only giving real-world work tasks, do you screen at all for basic competence first? I ask because I suspect we're talking about different things.
Also 2 (edit), does your work only involve one kind of task? How do you assess the breadth of their basic understanding without using simple problems? Are your programmers doing very repetitive stuff?
I've done both with and without. I honestly found it hard to make judgments about what effect what I was doing was having on the hiring funnel though.
If you're talking about that rather than later stage hiring then yes, I agree it's a different kettle of fish.
Then use it in the test! If you're judging people on how well they pick up proprietary software, give to them and make them do something with it.
My tests usually involve giving the candidate exposure to some software/module or other which they were not previously familiar and I judge them on how well they can work with it, applying general programming knowledge they will actually use day to do in the process.
(or in other words, total time taken to do n tasks is mn + b, where m is the efficiency when using your stack, and b is the time taken to originally learn your stack. b is relatively large, so with n=1, that's a very different thing than with n=100.)
It tests how long it takes somebody to learn a small part of it, certainly.
Would that not be relevant for a job where you intend for them to learn your stack?
"not how well they can solve problems once they're using your stack."
A properly structured test could (and, clearly, both of our cases, should) accommodate both - to begin with, the ability to find their bearings in code with which they are not familiar and subsequently to solve problems within that context.
I usually do tests like this that last 45 minutes.
>or in other words, total time taken to do n tasks is mn + b, where m is the efficiency when using your stack, and b is the time taken to originally learn your stack. b is relatively large, so with n=1, that's a very different thing than with n=100.
For clarity, I work at google and I'd argue that for all but the most trivial problems, it would take even a good candidate more than 45 minutes to get their bearings. Most new hires do multiple days worth of codelabs before sitting in their desks.
Sure, you can limit scope, to things with 1-2 files where everything is handled for you and no data transfer between systems, building, or commiting required, but then we're getting into a class of problems where your limited to relatively simple, logical issues with very well defined APIs, a class of problems that data structures fit very, very well.
It's an easy problem for sure, and I yet I could imagine many a competent programmer to lock up for reasons that have nothing to do with the problem and everything to do with the situation and sense of pressure they might experience during it.
I think that misses the point. A linked list is a simple data structure that needs little explanation, and yet uses indirection in a way that can get you into trouble. As such, it is a great toy problem to asses a person's ability to work with linked data. Reversing a list, is similarly, very simple to explain, and a quite rudimentary operation.
So if I'm trying to asses basic ability to manipulate data in code, it seems much simpler than trying to give them a real-world linked data structure and have them do a real-world manipulation on it.
The real problem is the assumption that this is a 'solved problem', i.e. that a) there is an one-true-way algorithm out there, and b) that is what the interviewer wants you to know (i.e. know in the sense of knowing a fact). That is true of too many interviewers, and that is the problem.
I can imagine setting that as a question in an interview. And I wouldn't be interested in 'the algorithm', I'd want to see that someone could figure it out easily. If someone came in and clearly had just learnt it, it would tell me nothing. I would immediately ask them something else to take them out of their rote prep. But if someone came in and couldn't figure it out, why would I think they'd be any better on 'unsolved problems'? In terms of being able to manipulate data, it isn't much beyond Fizzbuzz.
The 'it's a solved problem' attitude smacks of leftpad thinking to me.