We recently tried to identify such a question, with a scope such that the candidate should take about an hour and a half to complete - where complete also implies documentation, tests, etc. We couldn't find an appropriate question which would be something that would be highly indicative of the specific work they'd be doing that a) Didn't require a ton of domain knowledge (we don't expect people to have that domain knowledge coming in) or b) Would be too specific to particular technologies such as which ORM type library one is using, which type of DB, what libraries, etc.

Typically when I've seen examples of these questions where they are fully relevant they're in a space that's tightly defined - you're using say RoR, MySql, etc and candidates are expected to be proficient in those. That's not us.

I asked someone that today, and it didn't go very well. I gave him the hint to start with writing code to print out all of the children of a node, then when that stack overflowed, he was able to make progress.

Do you think there are senior generalists engineers who would be great who could struggle with that question? Its hard for me to put myself in those shoes but I believe it could be possible.

The goal of that question from my perspective is to watch them solve a problem that requires recursion. I've always found that people who do well on that stuff tend to get stuck less designing software in general.

I do worry that it cuts out people who would actually be good.

I'm very interested to hear thoughts on this from others.

It's never happened to me yet with this type of problem, but i'd be really impressed if I did run into someone who has the optimal algorithm for this memorized and can code it on demand in an interview. I'd certainly want to check that they haven't spent all of their time just memorizing algorithms and they can still do other things of course.

If this did happen i'd want to validate that they really understand the solution and aren't just spamming it out by rote, but if they've really got a few algorithms in the bank like this i'll just consider this box checked and move onto other considerations.

all I really want to know is if the candidate has the "horsepower" to deal with these sorts of problems, many people don't. someone who can code optimal solutions to these things on demand obviously does.

That said, obviously this is much easier for someone who's dealt with trees and graphs and such a lot before, so it's not ideal. I'd certainly be interested in a better way.

Iterate through the list adding its nodes to a set. If a node is already present when we go to add it, then stop, since we've found a cycle. Otherwise if we reach the end there is no cycle. With a hash set which has O(1) insert and membership check, the algorithm takes O(n) time and space since.

Note that I mean we're adding the nodes themselves to the set, not the element stored by / pointed to by the nodes. This may mean storing a pointer to the node in the set, or some other kind of object identifier.

I think this solution is fair to expect from anyone, including the caveat about node identity. Plus a candidate who already knows tortoise and hare should be able to come up with this when asked to solve the problem another way ("what's the simplest, most naive solution you can think of?"). I am not sure that I would expect anyone to come up with solutions beyond this one and the O(n^2) solution during an interview. I think those solutions correspond to knowledge that everyone should have in their working set. "Have I seen this thing before" is a pretty simple application of data structures. The O(n^2) solution trades off storage to track whether a node has been seen with determining it on demand in duplicate each time by traversing the list from the beginning repeatedly.

(If solutions are fair game that involve modifying the list, such as reversing it, or assuming that list nodes can be marked as seen, then make sure the boundary of what's allowed is clearly communicated. Make sure that the candidate does not neglect to consider a category of solutions by mistaking it as out of bounds. Candidates who are asked to design an algorithm to process a data structure cannot usually modify that structure to make the problem easier, so if this is something that you want to encourage, then you might tip the candidate in that direction by asking them to write the definition of their list node, and encouraging them to implement the node however they want as long as it meets your definition of being a linked list. Conversely if this is out of bounds, it might be best to provide the definition of a list node.)

Anyway, it seems like a fair simple interview question along the lines of a medium difficulty FizzBuzz, if the answers above give full credit. I don't think effective software engineers would be tripped up by this. One area of concern might be people looking for overly fancy solutions without trying "er... can I just track what nodes I've seen in a set?", but finding simple solutions is part of being a good engineer. I think there are better questions than this one: (1) it's too easy to memorize all the answers (2) it's already well known by this point (3) I have not heard of a good way to build on the question to make it challenging and interesting for high performing candidates. This might be an OK intro question before moving onto a harder one. I've never asked this in an interview - just going by instinct.

I agree with you that there are probably better questions. As you say, I'm looking for a medium difficulty fizzbuzz. I also agree with you that this is not going to be challenging and interesting for high performing candidates.

Incidentally, if someone has managed to memorize the solution to this and other algorithm problems I would consider that a pass. just the ability to do that is enough. there's enough code involved that they have to understand the problem pretty well to memorize it, and its the ability to understand that i'm interested in. (Barring some extreme outlier with super memory but bad other skills, but I'll have to detect that with other questions).

"The goal of that question from my perspective is to watch them solve a problem that requires recursion"

I wouldn't use recursion for my solution. It takes up stack space for no reason. If I'm going to be allowed to use more space, I'd just loop through the list, add them to a set, and check if I've already seen it. No recursion, but extra space. Is it more space than another stack frame? Depends on the type of set I'm using. But at least I know I won't blow up the stack (maybe the heap :-)

Since you are asking for opinions from others, I'm going to assume you wouldn't be upset with me solving it this way. So am I less of an engineer because I didn't immediately go for recursion?

With that said, everyone has a baseline - answers they expect to see. But everyone has to keep an open mind.

My company is trying to come up with a corpus of questions and answers to those questions at the junior, normal, and senior level. I've voiced my opinion that it is a slippery slope. If you get someone who isn't a skilled interviewer, and the interviewee doesn't use one of the prescribed 3 answers, what happens to that candidate? Granted it is one data point in the loop, and not the only data point. But as I stated, it becomes easier to be "lazy" during the interview.

No, not at all. a stack is a stack, whether it's the call stack or one you maintain in code.

Its not the recursion that's important to me, it's holding a problem of moderate complexity in your head in order to be able to come up with a solution. Problems that lend themselves to recursion seem to present a bar that some engineers struggle with, and others find easier, in my anecdotal experience.

I know I said recursion is important all over the place, clearly my thinking is sloppy on this and needs to improve.

I have this idea that there is a class of problem, that lends itself to recursion, that separates the wheat from the chaff in some ways. maybe that's nonsense.

What I really want to test for is the ability to juggle abstractions while working through code problems. there's probably a better way to do it.

Thinking about this corpus of questions and answers, I guess the common idea of fixing broken code might have a bit more merit because it removes the risk of an interview focusing too much on judging the approach and turning it into a trivia contest (have you seen this before and do you remember how to do it).

I'm going to assume your answer is "on the job performance". If not, this is going to be a difficult conversation, and I'd ask why you are trying to measure for something you aren't going to be paying for.

The best predictor of on the job performance is ... on the job performance. Everyone but the most junior person has experience. Look at that.

All of these exam type questions usually rely on knowing a trick, or being recently well versed. I TA'd a graduate course in Algorithms. That's rather relevant, I would think, since you aren't offered that if you don't have ability. Yet you know the last time I've done, say, dynamic programming? It's been awhile. I know about it, I know when to decide whether to pull it out, but ask me to do it, in a high pressure interview (all interviews are high pressure), and well, I'll probably fail. I'm working on other things like Bayesian inference. Bet you'd fail doing that stuff, even though it is just simple multiplications and such, when you get down to the implementation. Unless, of course, you are working on that sort of stuff right now.

I find the situation in SV somewhat ridiculous. To go out and interview means a lot of prep. Google recommends spending a month reviewing algorithms before applying. You know, I have an actual job, and I have open source side projects, and I have a family, and hobbies, and an old dog I want to spend all my time with. It is trivial to find out my skills by looking at what I have done and asking me questions about it. Have me give you a 1-2 hour tech talk, for example (I like public speaking, most don't so that is not a universal solution). Have me write some code with you, if you must. I work at a very high level, but I am not necessarily 'clever' at seeing the right trick in 10 seconds under pressure in an interview.

Also, how important is that sort of thing, really? For some jobs it is, undoubtedly. If you want me to write a load balancer for your cloud infrastructure, there are some algorithms I need to understand. Even then, not knowing something now is not evidence I can't do the job. I can learn - it's how I've done everything up to now. I can learn your thing too. More importantly (to my mind) - am I a hard worker? Can I mentor others? Can I lead a team? Can I put a schedule together, and recognize when that is appropriate and not appropriate? Can I make a budget? Can I talk to clients? Do I meet my deadlines? Do I solve problems - not implement the cards in this sprint - but see friction of some sort at work and engineer a solution? Do my peers like working with me? Do I get shit done? Is my code maintainable, readable, modular, commented? Can I write? Can I teach? Can I work with the CEO?

I've been to so many interviews where they don't even try to learn any of that latter stuff, where they show no interest in what I have done, where they don't try to figure out if I can do the actual job they are doing, but are deeply interested in if I can program a smart pointer, from scratch, to some arbitrary set of requirements. It is all just deeply puzzling to me.

All I'm really going for is to ask someone to write some code live, on their laptop with their tools, so I can watch how they debug, how they think through things, etc. I want the problem to be hard enough that the person has to model execution in their head and that it's challenging to do so.

I have found that there are people who can code decently well but get badly stuck when the complexity hits a certain level. I'm trying to not hire them in senior positions.

For example, I had a recent project where we were analyzing user data and producing a bunch of edges representing potential connections detected between users, as a way of sniffing out fraud rings.

One feature associated with this was a banning UI, allowing loss prevention types to navigate through the graph, select groups of users according to certain criteria, and generally look for patterns that are evidence of fraud rings manually, to supplement the automatically generated analysis.

There are a lot of front end people who will go into brainlock on this kind of thing. I need to make sure I have some people around who don't.

When making senior hires, I want people who can write code for this sort of thing without making a huge mess or just getting stuck for weeks.

Presenting a real sample from a problem like this needs way too much context though.

I'm going to keep thinking about how to precisely define the type of task that i'm really talking about here. My fuzzy definition about ability to model execution of X complexity in one's head is obviously weak and probably flat out wrong.

So when it comes to "junior, normal, senior" they dont have to be different questions, in my opinion. Opened ended questions give flexibility for the candidates inclination and complexity in answering. Depending on how the candidates doing add increasing complexity, discuss improvements, or try again with a simpler setup. Something like Word Count can go many different ways; If they like C talk about char and buffers and syscalls. If they like javascript, well then you can make fun of their tail call recursion.

It seems to me to still be very poorly understood in general that the purpose of a question in an interview is not to see if the candidate gets the right answer, but to see how they function. (In those interested enough to read the discussion this deeply it's probably somewhat better understood.)

I always stipulate that they can use whatever brute force approach they want, and that i'm not judging on the algorithm. (Though we'll then discuss the big O complexity of what they've done and i'll ask them to brainstorm some avenues for optimization).

The main drawback of this particular problem is that it's biased toward people with more formal CS experience who have probably seen more tree and graph stuff, when i'm not really trying to measure for that experience directly.

I'd be interested in a problem that doesn't have that aspect but still takes up a fair bit of brain space when thinking through. What I mean by that is that when you're trying to build and debug something recursive, you have to hold in your mind some representation of what the stack will be at various points, and not everyone has a great aptitude for that.

I don't know anyone who does trick questions (most people I know find them anathema, and even Google -- famous for them -- acknowledges they're useless). I definitely do know some people ask the 'cycle in a linked list' question (or others like it); honestly, I don't see a problem with that set of questions.

When I interviewed at Google (four years ago now I think) there were no trick questions. Hard questions? Yes. But none that had "gotcha" answers that you'd either have to know already or be some kind of genius to come up with on the spot in an interview.

Netflix does like to hire senior staff, who often have previous public accomplishments they can refer to, and discuss in interviews.