The reality is that generating good questions for a structured interview is difficult. You can't just pose a programming problem. As you've noted, most programming problems have multiple good answers. Differentiating between multiple good answers from different candidates re-introduces subjectivity. Your brain would rather convince you that one valid answer is less good than another, even when it's not, that to admit to you that it can't differentiate or generate a narrative for you. The part of your brain that generates narratives is incredibly powerful and does not care about how accurate your hiring process ends up being.
What we tried to do was create questions that generated lists of facts. "Spot all the errors in this code" would be an example of this approach (but none of the three we used). We went into the process wanting to embrace epistemological uncertainty, generating a historical trail of data that we could retrofit to candidate performance.
In the end, work sample testing was so much more powerful a predictor for ourselves that we never fully got around to analyzing the data. Sometimes we'd get candidates that clearly generated inferior "lists of facts"; I think there may have been 1-2 instances where that outcome actually overruled work-sample testing delivered prior (out of a few tens of engineering hires and probably ~100 interviews).
I wouldn't breach such a contract nor should you hire someone that would be willing to do so. The sole exception being in the cases where it would be the best for the public interest, i.e. whistle-blowing.
Is anyone though?
For most questions, there's no "right" answer, but there are a set of points that the interviewer wants to see you touch on. For example, they might first want to see that you can code up a naive brute-force variant of the algorithm, checking whether you know the programming language claimed and can think through the problem, and ask you the algorithmic complexity. Then they'll want to see if you can get a divide-and-conquer or dynamic programming variant with lower time complexity. Then they might ask "What if it has to be an online algorithm, where new input arrives before the computation finishes?" Then they'll ask "How would you distribute this over 1000 machines, and what are the failure modes?"
At each stage, they're watching how you answer, and where you get stuck. If you ask clarifying questions or spend time to think before diving into coding, that's a plus. If you have never heard of the problem before (this is frequent - many questions are not in textbooks), they want to see how you would reason through it, and break it down into subproblems that are similar to textbook problems. If you miss language trivia, most people don't care; when I did interviews I'd usually volunteer the answer if they missed some API call, and when I interviewed my interviewers did the same. If you don't know how to solve the problem and can't make any effort to move forward through a solution, that's a big negative. Similarly if you don't know what the concept of big-O is or why it's important.
But the real magic comes when they run out. What do they do then? Good people say that they don't know. Often, they will take guesses at a few more based on general principles. E.g., "I'm sure there are arguments for sorting, but I only use top for that." Or, "There must be more ways to filter, but I only do it by user or command." They'll usually look a bit uncomfortable, because they are the sort of person who likes knowing things. But what they won't do is bluff or make things up.
And honestly, that's my biggest tip for hiring: find people who like understanding things and know a good amount for their level, but are willing to say when they don't know. People who can't do that are dangerous.
I don't score it by how many option-letters people know. I score it by how well they demonstrate familiarity with a basic ops activity, which is finding out what's running.
Even if somebody said they never used ps, or like below, only use one incantation, that isn't a problem, because my follow-up there would be to ask how you'd find out what's using all the RAM or what's using a lot of CPU.
Maybe they're just used to using different tools, in which case I can ask for details for those tools. (And then check manually later to make sure I'm not getting snowed.) But if they've done a bunch of ops stuff, they'll demonstrate the sort of know-from-doing level of familiarity with something.
In theory I could just ask the broader question to start. But some people are good talkers, and I'm looking for evidence that people are good doers. All that said, I've shifted mainly to more experiential interview processes, as actually doing is the best way to see if somebody's a doer.
To me any question where the obvious answer is "I can trivially look all that up in the man pages" is a gigantic red flag that I don't want to work at that place.
If I'm feeling curious that day, I might begin a conversation about what you think you are testing for with that question, as I've spent a fair bit of my career studying hiring pipelines. But if I hadn't had my coffee yet or were irritated or something I'd probably just ask to talk to someone else.
That said, as I've explained elsewhere in the thread, the point isn't to see how many they know. It's to see that a) they know some portion of it that people doing the work would know, and b) have reactions to the rest that indicate useful work habits and attitudes.
A perfectly find first answer to is "I only use ps -aux. I'd just look in the man page if I needed anything else." Because then we could have a good discussion of how they use that output to figure out things, what sort of things they'd expect to see in the man page, and what other tools they use to see what's going on.
I know you're not asking people recite "ps" flags from memory. The problem is, you're looking for a subjective "X-factor" in how someone answers a trivia question.
I used to really like this approach too. I'd think of things that you'd only know if you'd actually done the kind of work I'd done. I had some favorite interview questions: "what are some of the functions you carry around with you from project to project in your 'libyou.a' library", and "where would you start looking if you had to debug a program that segfaulted in malloc"? I think the logic I was using is the same as the logic you're using here.
Ultimately, I think it's a bad approach. Equivalently strong candidates look at their work through different lenses, and find different things memorable. Far more important to me, though, is that some people really suck at interviewing --- and, what motivates me more, having succumbed to this repeatedly as a hiring manager and also being myself I think an example of the phenomenon --- some people just interview way better than they should.
The other problem with this question is that, by its phrasing, it implies that there is a right answer. If I can name more ps flags than an other person, I'm a better candidate. Which when put that way, I think points out its faults. Maybe you don't intend for that to be true, but you'd have to fight your own cognitive biases pretty hard to not at least bias towards the person that can name 17 flags off the top of their head, or the one that teaches you a new flag combo you didn't know. Even though those things are likely not that good of predictors of a good candidate.
You've said what you really want to get to, is can they admit when they don't know something. If that is important to your hiring process (and I'd encourage you to validate that with data), ask them a question no one could know the answer to. Ask the same question to every candidate, and grade it purely pass fail. Did they say "I don't know" or not.
>> admit when they don't know something... encourage you to validate that with data
My experience is that people that won't admit they don't know something are not necessarily bad employees. Often they are capable employees, although this is a trait I rarely see in the best employees. However, I find they are toxic to a good work environment, since they won't listen to people who do know something.
They do seem to get promoted to management had a much higher rate :)
So the process is, in fact, designed to make people feel uncomfortable, for a little bit (or at least you're definitely aware that this is a frequently occurring side effect).
Does that not suggest to you that there may be a negative tradeoff at play here? (To wit: yes you do manage do efficiently extract a few bits of information from them... but at cost of having them feel like they're being, well... interrogated. And are already "losing points" by that point in the conversation with you).
I had a PM friend who would try to push the bounds of a candidate's knowledge until they gave up and said "I don't know". The actual knowledge wasn't the point of the question: it was that they could say "I don't know", because PMs who can't tend to make life miserable for the engineers & other teammates who work with them.
And I agree with your PM friend; I think willingness to admit ignorance is even more valuable there.
But no, I don't think they walk away feeling interrogated. My style is pretty conversational, and when people don't have all the answers, I definitely work to make them feel comfortable with that. E.g., for this question I'd close with something like, "Of course nobody knows all the arguments to ls. I sure don't. So you did fine."
Try it next time you're mingling with ops people. Say in a bar at a conference. Don't look at what they answer. Look at how they answer. Some people are comfortable not knowing. Some people are excited to discover the ones they forgot they knew. some people get curious and eager to fill the hole they've just noticed in their knowledge. And some people get defensive and peevish.
Again, this is one of those, "Here's what I've got cached, and here's where I'd look up what I don't know offhand" questions.
From the ps manpage:
Note that "ps -aux" is distinct from "ps aux". The POSIX and UNIX standards require that "ps -aux" print all processes owned by a user named "x", as well as printing all processes that would be selected by the -a option. If the user named "x" does not exist, this ps may interpret the command as "ps aux" instead and print a warning. This behavior is intended to aid in transitioning old scripts and habits. It is fragile, subject to change, and thus should not be relied upon.
/actually I'd probably hit up the man page first...
Since the 'ps -o' flags are only useful in that one command, I just look them up in the (rare) situation where they seem the best alternative. Having been at this for decades, I try to reserve my limited memory capacity for factoids that will pay off, and being able to process columnar data generically at an instant seems more useful than knowing a special way to do it with that one command.
Not sure how well this works in practice though.
They were. I was asked a ton of this kind of Linux/Unix trivia in one session. As well as just random stuff. For example:
https://twitter.com/ubernostrum/status/659182356171874304
As a result of having read this story, I can now always instantly remember what 2^24 is too :-).
So 1000 * 1000 * 16 = 16 million would be an easy estimate to make.
If you are designing a system and want to have an idea of how much space or memory an approach will take, being good at this kind of math can be really helpful.
(I mean, I get it, this kind of general estimation and/or ball-parking can be incredibly valuable, but this doesn't sound relevant in any way.)
To be fair to Google (in regard to this one filter question only), they actually are up front about expecting a significantly higher baseline of general mathematical awareness (even for non-mathy roles) than most other shops. At any rate, this kind of estimation comes up in capacity planning (both in architecture planning, and for algorithms on a single box) all the time. Which after all is what Google does, at nearly every level of their stack, (nearly) all the time.
So, no, still not useful questions.
My opinion is that big-O often ends up being used as a premature optimization effort hindering "just get the right answer first". Maybe that brute force method will work in a reasonable clock-time cost, despite having egregious algorithmic cost. You won't know if you're busy overengineering and optimizing before you even have a working solution.
The reason is because when your dataset is in the petabytes, any algorithm bigger than O(N log N) is not going to terminate. You're not going to get any answer at all; your MapReduce is going to sit there burning CPU time for a day, and then you'll kill it, and you won't have any idea what went wrong. (This is learned from experience, if you couldn't tell.)
In a startup context, I'd certainly agree with you - that's exactly the approach I'm taking with my startup, where I'm doing a lot of the debugging and code-wrangling on my local laptop after verifying that the data I want exists and calculating its size with a couple cloud-computing passes. It can sometimes be useful to prototype & iterate with a small subset of the data until you've got the algorithms down.
But many of the algorithms Google cares about don't give any useful results on small data sets. I remember running a few collaborative-filtering algorithms and finding that they gave zero answers because within my small sample of 0.01% of the total data, nobody liked anything else that anybody else did.
[1] Well, it's really the amazing amount of throughput that modern architectures can achieve. Latency hasn't improved quite as much given the inescapable limitation of the speed of light.
Perhaps it has changed as well; when I left (2014) they had just started encouraging engineers to focus on one particular task, with the architecture already defined, while when I started (2009) there were still a number of problems of the form "here's a feature we want to add; here's the data we have available; how can we build it?"
What if you're having a conversation with someone about local politics and you're convinced the local zoning rules don't encourage growth in the way they think they do. Do you force the subject of conversation so you can make sure they know just how wrong they are? Not if you want them to walk away having a good impression of you.
Instead if the talk turns to zoning you put out feelers to see if they'll want to talk about the larger issue, and only engage in the conversation if it seems like the time for it.
The analogy isn't perfect, but if the interviewer wants to talk about the larger issue, you're probably well matched and will have a great interview. If not, and you know enough about runtime complexity to discuss the tradeoffs, then you know enough to just answer the textbook big-O question and move on.
Then there are situations where the code you write must play nicely within a massive, already-complex system, wherein it will work with potentially huge inputs. Like at Google.
So, saying in a Google interview that you don't think Big Oh is super important, and that you prefer shipping whatever correct solution you come up with first and then worrying about efficiency if it ends up being slow, would likely not get you very far.
Let's say you created your own company and you're interviewing engineers.
Would you be comfortable hiring someone who doesn't know the difference between O(n^2) and O(2^n)?
Or someone who doesn't even know what these concepts represent?
There's also the thing I picked up from playing around with graphics demo coding; get the algorithm working first, even if it takes 10 seconds per frame. Then look for the slow parts, concentrating first on the inner loops. Whatever you do, don't try to prematurely optimize the code as you write it, as tempting as it may be. Because almost certainly you'll make things worse than if you waited until after you have a working first pass.
This applies to way more than just fast graphics code, of course.
Any sort of technical solution given at a Google interview would generally have the following questions:
1) What big O time does this algorithm run in? Why? What big O space requirements does it take.
2) If space were more/less expensive, or time more/less important, how would you change the solution and why?
Understanding those tradeoffs and being able to analyze code at that level is a big part of most software engineering jobs.
The interviewee is more than welcome to study data structures and interview questions about data structures. A poor student will just memorize questions and answers by rote without really understanding the data structure in question. The good student will actually learn and understand data structures in the context of the solution.
One would hope that interviewers are able to ask follow-up questions about the solution which distinguish between the two.
EDIT: During the best tech interview I have done, I had no idea how to solve the question asked (that is, I had not studied its solution despite this being a relatively common question). I was able to ask articulate questions and invoked understanding of data structures as I went along. Memorizing solutions is a game of luck, and not recommendable.
There's a limit to how far you can get just Googling stuff ("how do I reverse a string") for recipe-book solutions to things. I think practically everything in Computer Science could be Googled ("how does merge sort work", "what is an inclusive vs exclusive cache") at some level but this doesn't mean one shouldn't know a great deal of it. At least, if you want one of these jobs...
I think one of the most helpful methods of determining a good interviewer vs. a good future employee is taking a structured, situational interview question, i.e. "How would you go about selling a new product to a customer?" and turning it into an actionable work sample that is tailored to your company. "We make this piece of software that does this. Spend the next 10 minutes writing a cold email to a prospect that outlines our offering." As the interviewer, grade the work sample on structured criteria that is important.
You do want to try out the question and criteria before depending on it too much, but it's easy enough to try it out on a colleague.
I take it you're working from a different theory, where you try to put the expertise in a machinery of questions and answers, relying less (or not at all) on the interviewers themselves. I think that's also a valid approach, one with different limitations.
Personally, as I mentioned elsewhere, I'm not a big fan of interview questions anymore period. If I want to know if somebody can do the work, now I try to create situations where they just do the work. But if one is trapped in the dominant tech interview paradigm, I personally favor investing in interviewers more than the questions themselves.
I'd probably start here to lighten up the mood due to how cliche the question has become:
If there are consistently used questions and specific criteria for assessing responses, can a candidate just learn the likely questions and what constitutes the "right" answer?