I further surmise that very few companies need these kinds of people. If your needs are people that can be managed to do basic programming tasks (my job as well), then that's what you hire. That's something like 99% of all programming work.
It's like hiring someone that understands the building of nuclear power plants, and being surprised that they don't understand basic home building codes.
The saddest part of it, for me, though, is that someone with a Ph.D. in Computer Science that is searching for a job in the non-research sector is probably having a really bad time. Research is happening, but I don't think it will jump in a very large way until there are a lot more dollars being pumped into research using public money.
One of the most unrealistic parts about a code interview is just how high-pressure it is, time sensitive in unrealistic ways, way more impact on your career than usual 5 minutes of coding, no peers to ask questions to, unclear if asking to google will be seen as a negative or not, etc. I think trying to reduce some of these unrealistic pressures, by being clear about what you're expecting (and being in this case up front that you _have_ intentionally given them something out of their domain knowledge) can probably give you a better evaluations. Some people do better under that kind of pressure than others, but if that kind of pressure is not actually representative of the actual job, it may not be what you want to be testing for.
Also set expectations for transparency and kindness (instead of bullshitting or preening) by modelling it yourself, right from the start.
IMO anyone else saying you should tell them the solutions might not have answers are dancing around needing to have that skill.
I know I will after this discussion!
I know I would also get very thrown by a question without an answer if I wasn't expecting it, in a way I don't think I would be on the job. (On the job I know too well through experience that not all problems have good solutions, but in an interview question I maybe would have assumed there was an answer they expected me to get, before this exchange).
Of course, the end goal of interviewing for an employer is maximizing their chance of filling position with good people, which involves balancing false negatives and false positives -- and in fact a "false positive" (wrong hire) is probably _worse_ than a "false negative" (turning down someone that would have been great). So... filtering out some candidate that might have been good may be a neccessary sacrifice, not a flaw in the process, so long as you're doing even better at successfully filtering out those that wouldn't work out. Whatever works!
If I felt someone was intentionally giving me a "trick question" in an interview, I might conclude they weren't someone I wanted to work for anyway, so everybody wins I guess.
I used to ask about the layers in the network stack, and how you might troubleshoot it. I start with something as simple as a firewall blocking a port, or the server not listening on the port you expect. If they do that, great. Anyone who's had to troubleshoot distributed systems should have checked that stuff plenty. Then we try a protocol they might not have used. Most developers have a rough idea of UDP vs TCP, but they might be confidently wrong about some details or try to make stuff up and say "I'm pretty sure...". We go down a layer and try some scenarios where routing is messed up. I don't expect most devs to know about that, maybe someone with more sysadmin experience, but by now it's painfully obvious if they don't know what they're talking about. It happens to be pretty handy on my team, but if at this point someone says, "you know I really don't know a lot about networking", great! I'm glad you told me. Let's skip talking about voltage fluctuations in Cat5 cables and get back to software development.
Another good one is designing a data structure where there's a lot of different access patterns you might optimize for. Gives them a chance to demonstrate some simple coding and CS skills before it gets complex, but then there's lots of room to talk about the use cases. Once you're talking about use cases, are they willing to ask about the trade-offs? Priorities of various use-cases? etc.
A good way of approaching this might be to provide problem feedback during the mock, stating that there's a given problem reported with the results or some other plausible complication and seeing how things go from there.
Also, the not knowing thing. I've hit that a few times myself, however I'll generally exhaust every reasonable option I have to look-up or reverse engineer the solution on my own first. Google / duckduckgo, stack-overflow, asking some other tech friends if they've encountered similar things before; if I worked somewhere with other technical users that I expect might have seen this they'd be just before the out of company friends on that list.
By the time I get to something I don't know, and can't find out on my own, it's actually a DIFFICULT or VERY domain specific problem. Generally then I go for adding diagnostic prints or using a debugger to trace the problem and find out where things are going wrong so I at least can narrow down causes/solutions. Even then, it's still taking a __LOT__ to get to I don't know.
Can be a problem trying to out-generalist a generalist, but if you pick something in your niche (I ask them lots of other questions relating to their background, so this question doesn't have to cover the exact job requirements) and practice the problem with dozens of interviewers, it'll be pretty hard to have someone who can genuinely out-think you in the depth of that problem. And missing out on the "I don't know" is a small price to pay to find a candidate that does that well on the problem!
There's 3 ways to answer these kinds of questions and it exposes you as either a genius (or in this case a linguist), a non-genius (real geniuses are as common as 7.5 ft tall people) or a bullshitter trying to look like a genius.*
I've never met an actual genius in an interview so let me address the other two. That third group is a nonstarter. I've known the person for 10 minutes and they're already trying to deceive me. How the hell am I going to build a product with them?
Kim Scott, some SV big wig wrote an entire book on this called Radical Candor. Essentially it's "don't bullshit people (and know where your taking the relationship when you use that rule)"
I strongly believe companies work best with the smallest bullshit quotient possible. They may sell more or be more profitable with certain flavors of bullshit, but things are easier and more stuff gets done without it.
At the end I would have rather actually made something than duped people with sham products sold on dreams
---
* I actually can't answer that question but I could probably identify the neighborhood of a real answer (...something something limitations of the von nuemann model restricting the constructions of parsing systems something something...). The point isn't to answer it, although that would be quite impressive; it's to see how far someone digs into their own BS.
What's the point of grandstanding like this? To make yourself feel smarter than they are?
My way of dealing with bullshitters (who in general are surprisingly eager to reveal themselves as such -- there's no need to lay special traps for them) is simply to say "Hmm - okay" and politely end the interview at the nearest reasonable opportunity.
When interviewing and I didn't get a job I always desperately wanted to know how to improve things next time and nobody would tell me. Instead there was this little canned BS email from HR "after much consideration blah blah blah" stop that ... tell why!
This goes one step beyond telling. Show people why. Show them what they are doing, when they are doing it, how you can see it, why it's bad, why it hurts them and help them not do it in the future.
Give them an offer to correct it after you've made it clear (this is like throwing an exception in programming versus silent failure). Reset the clock and try again if you want. Maybe they're actually great and you read them wrong (they might be a "good program" with your bad input). The interviewer isn't some flawless executioner.
Most interviewers don't act like characters out of an Ayn Rand book. At the end of the day they care about others and know they have bills to pay. Doing this shows "this is why this job can't happen". Try to be their best interview for a job they didn't get.
The candidate doesn't walk out the door with ambiguity or false pretense or the illusion of doing well. Nor do the decisions come across as arbitrary and indiscriminate. They know exactly what action they need to take for their next opportunity.
If they don't get the job on offer, the best you can do for them is help make sure they can get the next one.
> what are the strengths and weaknesses of classifying grammars via the Chomsky hierarchy?
Are there alternative classification schemes for grammars? I haven't come across any personally—not for formal languages anyway.
Or was something else meant by the question?
Type 0 is an unrestricted grammar.
Type 1 is a context sensitive grammar.
Type 2 is a context free grammar.
Type 3 is a regular grammar.
For our (CS) purposes we typically use Type 2 and 3.
The Kobayashi Maru of programming interview questions!
My first couple of hires before I did this were a brilliant computer scientist and a guy with a business degree and some coding background. I was surprised to see the guy with the business degree excel because we weren't doing many CS-hard problems, and an ability to manage time, talk about the problem, and navigate the project life cycle were far more important than classic algorithm knowledge. He needed to know how to code and debug, for sure, but like most software jobs, his soft skills were a force multiplier.
I'm pretty sure this has been done with me - I was given a problem and told to come up with something like an O(n log n) solution, and I honestly couldn't do it. I tried a few different approaches but I could think of really bad pathological cases for all of them. The interviewer gave me a few suggestions which I explored and I kept exploring them and then admitted I didn't see a way forward. I thought I was bombing and then he told me I did really well. I looked up the problem and found out he had done Ph.D. research in that area, and there was no general O(n log n) solution - only solutions that could do that in most practical cases.