On a great interview question (opens in new tab)

Instead of doing stuff like this, you can just give candidates realistic programming challenges and have them write code. You don't even need to be in the room with them; after all, you won't be when they're actually doing the work.

This question could be improved as follows:

* present the naive solution. Explain that this is a PR that was submitted in 20 minutes by our new intern from Waterloo. Ask them to help improve it.

* suggest to them the intern’s argument why the lookup is O(1) and explain that it’s actually O(n). Ask them to write a PR comment to break the news to the intern.

* explain the optimal solution with tries. Ask what happens if the vocabulary is big enough—and the prod environment is resource constrained—so that the trie is rarely in memory when the function is called. How would the trie solution compare to a binary search through a length normalized list of words?

This kind of question is barely useful to interview new hires—when you still may have basic questions about how much undergrad material “stuck”. Within a few years when they hit full-performance level you should care much less about this kind of question and much more about “higher order” thinking about engineering.

How do you communicate bad news? How do you identify, communicate, and mitigate risk? How do you plan large tasks at at appropriate level without over engineering the solution? What questions should you ask at different project stages to capture the right requirements, anticipate issues, and successfully execute over time?

But whatever, I’m sure you get lots of signal out of repeating “a hash table lookup is O(1)” “nuh uh” on loop for 10 years. :eyeroll:

That is who you're optimizing for.

Key point: I've never met anyone in the industry whose job it is to implement algorithms without reference materials all day long. It's more like... you might find yourself needing 1-2 clever bits a year, and the rest of the time you're tweaking model classes and hunting down UI bugs.

Algorithms are both easy to Google and these days, CoPilot will do the hard 4/5ths for you if you actually need them. It's also common that the really intense stuff is written by the PhD braintrust cofounder, not the people being hired after the fact.

What I want to know when I'm interviewing is simple: how do you approach solving problems; do you have an interesting personality that I'd like to interact with every day; are you the sort of person who has a strong instinct about what the next thing to do is, and will default to working on that thing without prompting?

Do you think learning new things is exciting? Are you able to admit you don't know something and do you feel comfortable asking for help when you're stuck?

Do you seem reliable? Are you a starter, a finisher or both?

Do you have a sense of humour? What do you do on the weekend?

Ultimately, I care what you know... but I am far more interested in your capacity to quickly master new things.

Responses are awesome because it gives you an idea of what this person's background is and what breadth of knowledge they have and what they think is cool or exciting. Maybe they start with a contact closing and signals being denounced, or an interrupt being triggered, or the OS and window manager, or the browser and DOM events, or HTTP or TLS or TCP or Ethernet or WiFi or LTE or routing and the tiers of network infrastructure or DNS or load balancing or proxies or web servers and tiers of API services or databases... It's can lead to some really fun technical conversation, follow up about how they learned the things they know and experiences they've had, and most of the time the interviewer learns something too.

That might be something you are looking for in a member of your team, but it's not a great indicator that they'll bring much additional shareholder value.

This kind of 'let's watch people struggle with my favourite LC puzzle, which I think I know inside-out' just seems very inconsistent, not very predictive, and just quite flaky to me.

On the job, my very first response to any kind of problem that looks algorithmic is to google the hell out of it, even if I think I know the answer already. In future, it will be to get gpt to write it.

I think the actual challenges in real-world software are not algorithmic, but architectural and beyond, and then only after thoroughly understanding the problem in the first place.

Isn't that in itself is a flag that this is in fact not a great interview question, unless it's being used for hiring candidates fresh out of college, say during campus interviews.

> I continued to use [the interview question] because I got good signal from the candidates.

Working at Google, this is something I hear a lot: that some question, or other interview thing, is good for getting "signal" from candidates. But how do you actually know?

Like, I feel to definitely know a question is good you would actually need to track candidates after they start working and see if their performance on the question correlates with their job performance. (Unfortunately, it seems impossible to track candidates who don't get an offer.)

“Tell me about a software project you played a significant role in. What did it do, how did it work, who made the tech choices, what was your role in it, what went right, what went wrong, if you were to rebuild it what would you do differently, what did you learn?”

I know it’s really a lot of questions but it’s still just one in a way “talk to me, in a free form back and forth way about software development”.

The reverse trie is genius, but with dynamic programming do you still need it? I would say that if in the general setting you can afford O(n^2) preparatory steps, and therefore you can just remember which (start, end) pairs correspond to a valid word with regular trie lookups. That is O(n) steps for each start position, giving a total of O(n^2).

For part 1 using a hashtable to look up the dictionary words, the complexity is not O(n^2) where n is the length of the input string. It should be O(w^2) where w is the length of the longest word in the dictionary.

The hash key material of the dictionary words has at most w characters. When computing the hash key for the input string, it can be truncated at w, as any longer input won't lead to a hash key making a match in the hashtable.

For part 1 using a trie, the complexity is O(w) rather than O(n). This is actually more obvious since walking down a trie tree will stop at the last character of a dictionary word.

Again for part2, the complexity is O(w 2^n) using bruteforce with hashtable, O(w^2 n) using DP with hashtable, and O(w n) using DP with trie.

Edit: Also for short strings like dictionary words, O(w) is kind of meanless since with SIMD or SWAR the short word can be folded into one or two DWORD. You can effectively treat it as O(1).

Unless you're an insecure, narcissistic engineer who feels "smarter" than everyone else or a cargo cult follower of some business fad, there are no magic questions to instantly separate "good" candidates from "bad."

You discover good engineers by whiteboarding and working on challenging problems together than can possibly turn into real commits. Ego and solving manhole cover problems doesn't delver good commits.

I then push them on this until they realize that any implementation of the dictionary lookup function of a string would be o(n) at best, and as such the total runtime of the solution is O(n²).

Surely it's

String -> Hash -> Is hash in hashmap

All of those operations are O(1) so the total operation is O(1)

The only reason I can think that the optimal solution was immediately obvious to me is perhaps because in a previous life I did a lot of work building convoluted application specific indexing schemes for data in a distributed KV store that had basically zero useful built-in secondary indexing schemes where piles of parallel GETs were about as "free" as just doing one, but chaining strings of requests back & forth to the client iteratively made for sad times. This meant that it was essential to be clever about what could be coded into key names and precomputed from application/use-case context to know what keys to fetch "all at once" to gather as much relevant data as possible with as few serially dependent requests as possible. One such use case depended on a modified C-trie as part of the solution, so I got very familiar with what kinds of problems they're for and what their limitations are.

Given that, I can't tell what that says about the question, about me, or about Google. What I can say for sure is that because I can't tell the above, the technical interview at my company is signing an NDA and sitting down for a couple hours and just actively pairing on real work & real problems with real teammates.

With the nature of software development work being what it is, I really don't understand why we as an industry run interviews like they're game shows or try to manufacture workplace simulators with terrible model conformance.

That said, from the article this article links to, I find this puzzling:

> The candidate’s performance on the problem isn’t binary. The worst candidates don’t even manage to implement the fizzbuzz solution in 45 minutes. The best implement a memoized solution in 10 minutes, allowing you to make the problem even more interesting, e.g., asking how they would handle a dictionary too large to fit in main memory. Most candidates perform somewhere in the middle.

Two things I worry about: if the interview isn't "binary", how do you decide whether the candidate passed? Is doing just the simpler version fine as long as you ask for low pay? Or are you still failed? Or does it depend on whether other candidates did better, which is another way of saying you failed? It seems to me it's still binary.

And the other thing is: if the candidate did great in 10', please don't ask additional questions. The candidate is a "hire". Don't make it "interesting", an interview is not the place to shake things up to make it "interesting". Understand that for most people, interviewing is a stressful situation. For "interesting" times they have their friends and Netflix.

You’ve already lost me, dude. If the question can’t meaningfully differentiate between a junior and a high level senior, it’s a trash question.

How can a word be the combination of two words if the first word isn’t a word?

So, for example, if the first letter isn’t A or I, we can stop doing lookups for any combination of just a single letter and the remainder of the word.

Etc.

Is that true?

I am actually siding towards the candidates on this one

presumably it would be O(n_words_in_dictionary) for the dictionary check, which as the number of words in the dictionary is constant, would make the overall algorithm O(n) ...

Fun write-up though. The comment saying this optimizes for clever freshmen is spot on in my book.

The maximum number of iterations is the length of the longest word in the dictionary.

This means that part 1 of the problem can be solved in O(1)+O(1).

That doesn’t mean you will be happy with it. Not all O(1)s are equal.

I found one sentence very interesting:

> Moreover, the problem as I present it, has enough range to sift out bad candidates from good ones even if the candidates have seen the problem before, which is why I successfully used it even though it was banned at Google.

How do you measure the question's success? Is there some kind of feedback you get about how the person you made a decision about went on to perform? What about the people that ended up not being hired?

Is n the length of the word or the length of the dictionary? And if it's the length of the word (<< the length of the dictionary), why does it matter if it's linear or quadratic?

The problem as described:

“Write a function that given a string, determines if it’s a concatenation of two dictionary words.”

given that description I think you can't have left over fragments. But the code seems to allow fragments (don't know Python). Also it just returns a boolean? So we just need to know if there is two words contained within our word within the dictionary.

If that's the case, and the "dictionary" is an actual dictionary used by humans (they mean like a Dictionary like The Oxford American Dictionary right?), then, because the letters of a word are considered nouns (that is to say the letter b is a noun - Merriam-Webster https://www.merriam-webster.com/dictionary/b) then any word with more than one letter is a concatenation of two words. Which is anyway stupid because no one cares about concatenations of words, people care about compound words and this is not how you would find compound words.

I bet that's not what they want to hear though. I generally do really bad on questions.

   Some come up with a greedy algorithm which finds the first prefix that is in the dictionary, and then returns whether the rest of the string is in the dictionary

>The fastest I had a candidate solve the entirety of the problem with all bells and whistles was in 20 minutes, by a freshman from the University of Waterloo, the type who did high-school competitions.

>The most depressing failure I saw was a PhD graduate from University of Toronto who could not produce working code for the first section of the problem in 45 minutes.

>I once had a candidate with 15-years work experience give me lots of attitude for asking them such a simple question, while at the same time struggling at it.

All of this data points to the fact that this question may not be good. A phd graduate and a person with 15 years of experience rejected for someone who practices programming for competitions? What gets me is that the data is painting an obvious picture here. A very obvious picture. An obvious picture that we aren't sure what's a good interview and a bad interview question.

But the problem is that most people when looking at this completely miss it. It's not obvious to the interviewer and it's not obvious to alot of people who like google style questions. We literally have not much data and not much science backing any of this up.

It's an illustration of how biased humans are and illustration of how extra biased interviewing for software positions is. If there's anything more unknowingly biased and then the replication crisis in science it's technical interviews for companies. There needs to be real feedback loops that correlate interview question passing with Actual performance.

Google is in a good position to grab this data but I'm not sure they are doing so given how they just okayed this guys gut decision to go against the grain and use this question. I'm not against this question, but certainly to call this great in the face of controversial data that he himself gathered and listed on his post is just a complete blueprint of the extent of human blindness.

The reality of what's going on here is the person here in the interview is just getting off on dominating other people with a hard question. It's not on purpose but he's doing it without realizing it. The blog post in itself is a bit showy. It's like "I can answer this question but a phd graduate can't".

Actually the best questions I ask, and the ones that give me the best candidate "signal" are what I call the "clean code" style questions (as in code that is simple, easy to extend, not necessarily Uncle Bob Clean Code).

I'd rather not post examples here because I still use these questions, but the theme is as follows:

* These questions ask to implement functionality that you could see in a (super simple) real world application.

* They start super simple, and include several follow ups that increase in complexity.

* No data structures and algos beyond the basics. Loops, lists, hash maps and little else. What most programmers would use on the job on a daily basis.

I found in practice these work really well, specially with experienced programmers who can flex their low level design skills. People who ace leetcode style questions tend to do worse here, but no wonder, since they've been trained in a complete different style of interview.

Good questions allow multiple possible solutions[1], allowing a candidate to arrive at a successful solution via many different paths while still evaluating whether they are going to be able to perform well at the job. I don’t think this question comes close to meeting that standard.

[1] By which I mean fundamentally different approaches rather than syntactic variants on the same basic thing

Bad news: You have to walk this stable genius through 50 years of Suffix Tree and constant time LCA algorithms in 20 minutes.

abbbbbcdddddde => aB5cD6e

The number of developers who struggled or utterly failed with this was depressing.

Is any of this better then randomly selecting? Do we even know if there is a skill set that is optimal, or if multiple complementary skill sets work best? Do we know what they look like, how to select for them? Or are we all just filtering for whatever collective definition of cleverness people involved in a given set of interviewing and hiring tasks prefer?

I suspect on average it's better to filter out good candidates than filter in bad ones so as long as a selection process skews towards eliminating most candidates probabilities will have most teams covered on that front. Of course this only works when salaries in programming are rising faster then the rest of the labor market, attracting a growing cohort each fiscal cycle.

What is the runtime complexity of an algorithm? Set it up with varying amounts of data fed to it (or whatever N is) and then time the real thing (or a suitable minimal but complete example).

Then you can instrument or profile the algorithm in any number of different ways to ask what is being called so often.

If you do it right you can really measure what it is doing, and you're getting closer at least to "production" code where you're not just working with pencil and paper but you've got real algorithms running hardware with finite sized caches.

Ultimately it doesn't matter what anyone writes down on pencil and paper if the hardware doesn't agree with you. Usually I measure it first and then work backwards knowing the answer already.

I've never worked at that company and I don’t know if as an interviewer you pick a question from a catalog. If that’s the case, and if you’re so inclined in asking this type of nonsense, I’d suggest a small tweak: a third party selects the question with some sort of guarantee/constraint that this would be the first time the interviewer asks that question, and so is now in more or less level ground with the interviewee. No other option but to have a discussion among potential colleagues.

For starters, it's staggering how many people can't do it.

But also, it's a great question because it's simple enough that you don't have to be clever but you can get a feeling for all sorts of things. Do they ask questions? Any questions? What possible inputs might cause problems? What do they name their method? What tests do they write? (Project is set up already with an example test class ready to go.) Etc etc

The customer wants to increase their sales. They want something that auto-generate sales responses to incoming emails. Discuss.

The problem with technology workers is that they believe technology is important. The above question allows you, the interviewer, to see if they have actual critical thinking skills.

Annnnnnnnd I’m out.

Good taste — writing cohesive, loosely coupled code with a sensible bank of unit tests an a strong dose of product sensibility — is largely orthogonal to being good at solving algorithmic or ds questions. One of the best developers I know, who makes seven figures a year a year (trading software), would likely bomb the second part of this question. Contrawise, a young researcher I know who has won multiple scholastic programming competitions and crushes leet code, would destroy this problem in seconds … and yet, I pity his coworkers who have to live with his atrocious code.

More accurately, he would first look at the interviewer like he was a dolt, and then bomb the question :)

If they only know simple data structures, going from a hash to a hash of hashes is one of those "eureka" moments that can really shows how a candidate is willing to collaborate on a problem and react to new ideas.

Heaps are an interesting data structure to use for interviewing, but I do find they can be a little less intuitive, and their use cases translate less directly to business logic and are more of an optimization task. It depends on what talents you're looking for on your team!

https://iq.opengenus.org/time-complexity-of-hash-table/#:~:t....

The trie/reversed-trie solution is a little too clever to arise naturally from conversation (and probably not optimal because hardware implementation).

This seems pretty nitpicky, especially considering we're assuming substring creation is O(1). And isn't a hash table lookup of a string O(n) at worst, not at best? And since this seems like a fixed dictionary, we're only doing queries not insertions, couldn't you just choose a different hashtable algorithm like dynamic perfect hashing to guarantee O(1) lookups?

I also don't like how it starts off with the dictionary being a blackbox style function, and a later part of the question requires you to change the internals of this dictionary query function. My very first thought would be about the structure of the dictionary query. And then when told to ignore that, I would assume that's still the case when asking to later optimize the algorithm.

Not surprising. This sort of interview is selecting for people who have exactly this kind of academic knowledge.

Well, that removes most of the fun of it.

I think that’s actually a good example of why this is not a good question. It’s disconnected from any realities.

if i was (am retired) i would typically ask questions about the languages we were using. in my case this would typically be c++ and sql. so i would normally ask things like:

"tell me something about the copy constructor"

or:

"when would you want to do a union?"

amazing how many people were dumbfounded by these. and notice, no leetcode crap needed.

However, software engineering is so much more than writing code to solve a well specified problem.

- oftentimes, the problem is not well specified. The engineer needs to find out what the problem specification really is.

- In a lot of cases, a solution already exists publicly. The engineer needs to find documentation or code that solves the lecified problem or a similar problem. Usually somebody has already thought about optimization of this type of problem and has documented it.

- Often, a feature needs to be added to an existing codebase. Often a similar feature already exists in the codebase and the new feature can be implemented in a similar way. The engineer needs to find the similar feature and has to figure out how to generalize or adapt it into the new feature.

- A lot of times technical debt needs decreasing. This involves understanding feature implementations or models/paradigms in an existing codebase, understand how they are inefficient or needlessly complex. Creativity is the trait mostly needed in this case to address it.

- often new APIs need to be made, needing modeling and documentation. Also often existing APIs or newly imported libraries need to bevused to tackle problems.

- Above points address the purely technical skills. Non-technical skills are just as important. Communication, teamwork, prioritization, time and stress management, customer relations,...

Tldr - this great interview question targets just one aspect of the job.

With performance like that, I'd call it a "trash interview question".

When you use wildly inaccurate processes, you build bad teams and good people know you'd be wasting their time so they don't even go in the door.

Seems like the practical application of this is to quickly disallow strong memorable passwords of the form "correct horse battery staple". https://xkcd.com/936/ If so, deeply misguided.

- part 1: got it in like 20 seconds of thought

- part 2: got a variant with a trie in maybe 5 minutes thinking, wasn't exactly the same as the given one but close enough

- part 3: thought about it for an hour (got nerd sniped). got a trie + recursive dynamic programming solution that's O(N^2) in the size of the input string. the actual solution took me 15 minutes, the rest was trying to prove the the big-O

Let's say the string is wxyz. As we iterate, we'll split into the possible prefixes and suffixes:

    w xyz
    wx yz
    wxy z
    wxyz (suffix is empty string, we have to special-case this I think)

Looking up a string in the trie is O(N). But for the prefixes, we can "remember our place" in the trie, so that the cost of an incremental character is constant. So membership checking wxy only incurs the cost of y, given that we've already just looked up wx.

The prefix is either a word in the dictionary, or it isn't. If the prefix is not in the trie, we advance to the next character and repeat, with the next prefix grown by one character and the next suffix shrunk by one character. If the prefix is a word in the trie, we call our function recursively on the suffix, and memoize the result. If the recursive call comes back true, we're done, and we return true. If it's false, we advance to the next possible prefix and repeat. If we reach the end, the prefix now comprises the whole string, so we just return whether it's a full word in the trie or not.

In the base case of the recursion, the suffix is a single character, which is a constant-time lookup in the trie. So every recursive call after that can just look up that memoized result. Same for the 2-character suffix, 3-character suffix, and so on:

    - 1 character: z:    z: 1 operation
    - 2 character: yz:   y, z suffix memoized, yz: 3 operations
    - 3 character: xyz:  x, yz suffix is memoized, xy, z suffix is memoized, xyz: 5 operations
    - 4 character: wxyz: w, xyz(memo), wx, yz(memo), wxy, z(memo), wxyz: 7 operations
    - N characters:      prefix 1, (N-1)(memo), prefix 2, (N-2)(memo), prefix 3, (N-3)(memo) ...: 2N operations

So summing the cost of all those recursive steps, it is O(N^2) in the length of the string.

The word "cantonal" works as a good test case because it has lots of sub-words: can, cant, canto, canton, a, an, ant, anton, ton, tonal, on. The memoization doesn't show up for it though, so I'll append "q" to make "cantonalq", which should return False:

    c -> no
    ca -> no
    can -> yes
        t -> no
        to -> yes
            n -> no
            na -> no
            nal -> no
            nalq -> no
        ton -> yes
            a -> yes
                l -> no
                lq -> no
            al -> no
            alq -> no
        tona -> no
        tonal -> yes
            q -> no
        tonalq -> no
    cant -> yes
        o -> no
        on -> yes
            (-alq suffix is memoized) -> no
        ona -> no
        onal -> no
        onalq -> no
    canto -> yes
        (-nalq suffix is memoized) -> no
    canton -> yes
        (-alq suffix is memoized) -> no
    cantona -> no
    cantonal -> yes
        (-q suffix is memoized) -> no
    -> return False

Generally I don't mind "pure" DS/algo interview questions, so long as they're plausibly related to something one might actually do. I have actually used tries before on a real problem. Dynamic programming with memoization tricks? Never. Has anyone ever had something remotely similar come up in real work? I mean I know there are caches everywhere but that's not the same thing. It just seems like a sick hazing ritual that nerds inflict on one another.

Conclusion: bad interview question.

Maybe it is understandable since the article does not clarify any of this, but folks should notice that:

- This type of interview is part of a process, composed of multiple interviews. Not the only one, and not the deciding factor. Questions on behaviors, team dynamics, etc, are also part of the process and covered in other interviews (usually done by managers). You could fail a systems interview and still pass the interview process. The specific interview mentioned in the article seems not too complex, though, so I wouldn't be surprised if it is a screening interview that rejects candidates when not passed.

- People mentioning that the interviewer is wrong on time or space complexity are also missing the point. It doesn't matter. If someone in the interview mentions O(n) instead of O(n2) and can reason that, that's already a good signal. It is not so much about being right or wrong. It is about thinking about those things when coding, keeping them in mind, been able to express that and run someone else through your thought process, etc. Someone plainly saying something is O(n) without any further explanation can give a bad signal, but someone explaining why she thinks so can be a good signal, even if ultimately the solution is not O(n).

- IMO, folks saying that this favors junior engineers and people fresh out of college are wrong. This favors people who ultimately understand the foundations of programming. People fresh out of college had a refresher on that not so long ago, so they've been practicing it more. The thing is, some people in our industry get further away from that as they add seniority to their career, but there's also lots of senior people that are very well versed on this kind of thing. Specifically, the question in this article is extremely simple, so TBH I don't understand why someone senior would fail to know the answer to that question just because that person is senior. Maybe these companies are just not looking for that kind of senior engineer for this specific positions. That's all. There's also a lot of different seniority levels, too. I could see this interview having less weight on a decision as seniority increases, but still important.

- "this does not represent a realistic scenario". That's a given. As a company, you have maybe 8 hours total with the candidate (multiple rounds of interviews plus the on-site). Onboarding into the company and a team, until you're productive, will take weeks/months. There's no way of testing a realistic scenario on an interview. We get the best signal we can with the time we're given.

- Not passing the interview process is very demoralizing, but it does not mean the company thinks you're a bad engineer or that you're not good enough. The process is designed to minimize false positives, so they tend to prefer to reject candidates if there's any question or mixed signal in the interviews.

- I'm not saying the process is perfect, by the way. For example, there's also luck involved, too. It shouldn't, but there is. To give one example: interviewers are people too. They need to be trained in the process of interviewing, what signals to look for, etc. There are good and bad interviewers. Interviewers can have a bad day and judge some answer as unsatisfying when some other day it would be fine, etc.

sure, some will trip over themselves.

20m was the best?

poor screener?