Between 2010 and 2019 I interviewed dozens of Software Engineer candidates at Google. Almost always I asked the same interview question. Moreover, this question happened to be on the banned list at Google, because it was publicly available on Glassdoor and other interview websites, but I continued to use it because I got good signal from the candidates.
I stuck to the same question for nearly a decade too, even if it was barely more difficult than fizzbuzz. The ability to compare against the past candidates was very useful, which would not be possible when changing questions too often.
The sad reality was that it was waaaay too effective as a fizzbuzz eliminator (> 80%) which I don't know what it tells me about the candidates in general or just about our recruiting :-)
> The sad reality was that it was waaaay too effective as a fizzbuzz eliminator (> 80%) which I don't know what it tells me about the candidates in general or just about our recruiting :-)
I suspect there are a lot more people who frequently choke on easy coding questions, under the very specific conditions of interview-stress (which is very different from, "the client is unhappy and is also onsite and you'll be in a meeting with them later" stress, and from "production broke" stress, so no, I don't think it's a good proxy for general "grace under fire", as it were, either) than there are actual full-on bullshitters who manage to land software jobs while being truly incapable of doing even the basics of the job.
For one thing, I think such top-tier, extremely-convincing bullshitters would have an easier and less-stressful time applying that skill directly to some other role, since there are some well-paid roles where that kind of thing is exactly what companies want, so it doesn't pass the smell test for me that so very many would be trying to land software jobs—not just ones who exaggerate skill or try to get into the industry while woefully unprepared, but who also are able to fool interviewers at a reasonably-high rate in conversational interviews, yet fail simple coding tests.
That is, I suspect a large majority of "ha! I caught a faker!" anecdotes or anec-data are actually a false-negative on the test from people choking under interview conditions, and that most real fakers would also have been caught in any half-competent conversational interview anyway.
The remainder should be probably be hired regardless, then re-homed to sales when you realize what's going on, since they're evidently top-percentile bullshitters and social chameleons. Joking, of course... kinda. Maybe.
There's certainly part of that, but there's also likely selection/sample bias. The better the programmer, the less time they probably spend in interviews. And the "reward" on passing a programming interview if you're marginal is quite high, depending on your alternative choices of employment.
(Top tier Ivy League university acceptance rate is 3-10%, so if you're looking for someone of at least that caliber among the general population (or even among developers), an 80% rejection rate might not be crazy. FAANG (or its ilk) are the "Ivy League" of Software Development jobs)
The tens of thousands being laid off from that ivy league and ones who jumped the, 6 step, multi-tiered interview hurdles to get a job offer, later rescinded, might disagree with that value proposition.
What percentage of candidates would you believe freeze up so badly that they can't program at all?
Over the years, I have seen significant numbers of applicants who couldn't write FizzBuzz, and even one who couldn't sum up the numbers in an array (ignoring overflow). Some of these people had reasonable resumes, and many of them could talk about software development in the abstract.
This was usually a sign of poor phone screening, but it always blew my mind.
Interviews make me realize I don't know how to code on the spot while 4 people (responsible for judging me and determining my worth) watch me. I second guess everything and freeze up. My mental capacity to solve a problem is being taken up by a fight/flight response (wanting to push through the question or quit). The environment I'm in is foreign, outside of my typical coding setup. My brain has no time to adjust. You could look at my github and see someone who's an excellent coder, but put me in an interview scenario like the one OP wrote and it's like 10 years of education just disappear.
Out of curiosity, how do you think you might do in a 1-on-1 coding interview doing something incredibly basic, like:
- Sum an array.
- Write FizzBuzz.
- Count the words in a string.
- Compute the length of a linked list.
Assume you get to use the language of your choice and a familiar text editor. You aren't being graded on semicolons or gotchas. And the interviewer isn't hovering too closely.
Because that's the situation that always mystified me. How many people freeze up under reasonably favorable interview conditions to the point that they can't write even basic code? (And would those people be able to pair on a tricky bug when production is down?)
I absolutely do read a candidate's online code, if they mention it in their resume. That only seems respectful. And I think it might be reasonable to waive in-person coding tests if someone is obviously competent.
(Of course, now that Copilot is getting smarter, it's going to be harder to evaluate people's GitHub repositories or to include trivial problems in pre-interview screens.)
> Out of curiosity, how do you think you might do in a 1-on-1 coding interview doing something incredibly basic, like:
In my 20ish-year career, I've had... oh, ballpark 30 interviews, and I am certain I convinced at least two of those that I had absolutely no idea what I was doing, one on something about as hard as what you list, another on something only barely harder. One was around the middle of that span, another, four or so years ago. The number would be higher, but most of my interviews have not featured coding questions. I have an incredibly high offer rate from interviews that haven't done those (70%? Maybe higher), and near-zero from ones that did.
I can, in fact, code. I've taken complex projects from zero to production, solo, with companies that couldn't have afforded to keep me on for years if I couldn't pull my weight. I've developed a reputation at multiple places as the one to go to with tricky or low-level problems, or the one to hand odd-ball problems with tech no-one's familiar with. I collaborate well, I do the solo thing well, I'm good in a meeting with stakeholders, I can take a support call like a champ. I figure things out, I deliver, I ship. I am not bad at this whole thing. But interview coding? LOL.
> (And would those people be able to pair on a tricky bug when production is down?)
I'm cool enough under pressure that it's been remarked upon throughout my career, over and over. Interviews still get me—specifically, the performing part of coding questions, the rest is no problem.
I think it's because they're kinda hostile (yes, yes, "we're both just deciding if we're right for one another" and "you're interviewing them too", but c'mon, see exactly all the chatter about interviewers trying to find liars and expecting there to be lots of them—you're under a microscope). Production-down is collaborative. Angry-client is collaborative (from your co-workers, anyway). Not just that you're working together, but supporting one another, everyone's got everyone else's back. Most stressful work situations are fundamentally safe in a way that interviews are entirely not. There's nothing to prove, only a problem to solve.
I'm also shit at public speaking—not talking to people, not meetings, but speaking before an audience, and I mean shit—and playing music in front of strangers is basically my nightmare (and yeah, I've done it). I suspect both those are true for most people. The stress of coding in front of someone while they judge me is identical to those situations, for me.
I am guilty as charged of saying impulsively that the first solution is O(n)!
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).
One is the length of the word. The other is the number of dictionary elements.
If your language is constrained to 1,000 words, then the dictionary will be pretty small and the hash table can be constructed with no chains. That should have constant-time lookup no matter how long the query concatenation is.
I don't see why O(n^2) should be optimal. The question is only to determine if a match exists, and that can be expressed as a regular expression. In the following I omit all 1-letter words since my dictionary includes all the letters.
>>> words = [line.strip() for line in open("/usr/share/dict/words") if len(line.strip()) > 1]
>>> words.sort(key=len, reverse=True) # because Python uses left-to-right match, not longest
>>> pattern = "(" + "|".join(words) + ")+$"
>>> import re
>>> matcher = re.compile(pattern) # takes a few seconds
>>> matcher.match("ducksoup")
<re.Match object; span=(0, 8), match='ducksoup'>
>>> matcher.match("ducksquom")
>>> matcher.match("theremanywordsinthisone")
<re.Match object; span=(0, 23), match='theremanywordsinthisone'>
>>> matcher.match("theremanywordsqinthisone") is None
True
Python uses backtracking, so this probably isn't O(n), especially with the ability to choose the dictionary.
But with there are non-backtracking matchers which would make this O(n). Here's re2 from https://github.com/google/re2 :
>>> import re2
>>> opts = re2.Options()
>>> opts.max_mem = 200000000
>>> matcher = re2.compile(pattern, opts)
>>> match = matcher.match("ducksoup")
re2/re2.cc:821: DFA out of memory: pattern length 2493008, program size
1323834, list count 1089251, bytemap range 54
>>> match.start(), match.end()
(0, 8)
>>> match = matcher.match("ducksquom")
re2/re2.cc:821: DFA out of memory: pattern length 2493008, program size
1323834, list count 1089251, bytemap range 54
>>> match is None
True
This is first time I've used re2. There's probably a way to prevent that warning message - I believe this is falling back to an NFA, which might not be O(n)?
Anyway, here it is processing the concatenation of 100,000 words selected at random (I've omitted the warning message):
>>> s="".join(random.sample(words, 100000))
>>> len(s)
956249
>>> import time
>>> t1 = time.time(); print(f"is concatenation? {matcher.match(s) is not None} " + f"time: {time.time()-t1:.1f} seconds")
is concatenation? True time: 12.3 seconds
>>> t1 = time.time(); print(f"is concatenation? {matcher.match(s+'Q') is not None} " + f"time: {time.time()-t1:.1f} seconds")
is concatenation? False time: 12.3 seconds
Cut the size by 10 and it's about 10x faster:
>>> s="".join(random.sample(words, 10000))
>>> len(s)
95457
>>> t1 = time.time(); print(f"is concatenation? {matcher.match(s) is not None} " + f"time: {time.time()-t1:.1f} seconds")
is concatenation? True time: 1.3 seconds
For this test it appears to be linear in the query size.
Edit: if I increase max_mem to 2_000_000_000 then I don't get the warning message. But then the DFA-based search takes 141.5 seconds. That should be O(n) time in the query length, but an order of magnitude slower than the NFA-based search.
That's why O(n) analysis isn't enough to really figure out "a faster solution."
It does, but the article actually doesn't define n and it's confusing.
In the common case, where s is short and the dictionary is big, the size of the dictionary probably matters most to the running time. s is likely a cache line and a handful of instructions to compare — whereas the dictionary probably doesn't fit in L1 or L2, maybe not L3. Obsessing about algorithmic analysis based on the string size instead of the size of the dictionary gives good signal for whether the candidate is a pedant, and poor signal about engineering.
> 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²).
I think the point is in the initial algorithm given there are (n-1) lookups of two substrings whose combined length is n, requiring the hash function to process (n-1)n characters, because the hash algorithm is O(n) in the query string length.
That said, the dictionary words have a finite size. The largest word in my /usr/share/dict/words is 24 characters - formaldehydesulphoxylate. That means for an input of size n only 24n bytes need to be processed to identify if it's composed of two dictionary words. And if it's 49 bytes long, or longer, it's a simple calculation - "not".
Try running the search many times. The lazy DFA should get faster.
The lazy DFA is technically O(m*n) just like the NFA. The "lazy" part of the "lazy DFA" is why. Because it builds itself during the search. A real DFA would be truly O(n) because it would be fully built before starting a search.
I get 141.5 seconds for the first time, (laptop in suspend mode during the second), 84.8 seconds for the third, 67.9 seconds for the fourth, and
re2/re2.cc:821: DFA out of memory: pattern length 2493008, program size 1323834, list count 1089251, bytemap range 54
is concatenation? True time: 102.0 seconds
for the fifth. It would appear to not be caching, or at least not in a way that makes this timing faster than the NFA.
In any case, my point is that we know this problem can be solved in O(n) time.
The dictionary words have a fixed, known upper bound to their length. It's a fixed size dictionary. The dictionary lookup can be considered O(1) on this basis alone.
But then, that means that my candidate string can only be a maximum of twice the length of the longest dictionary word, so the entire process is O(1).
For realistic English words, we're talking about a typical candidate string of length, what, 20 maybe? I need to do somewhere between 19-38 dictionary lookups of 1-19-letter strings to test every splitting of such a word. Why are we even doing big-O analysis here?
Only when you start looking at arbitrarily long strings to see if they are word sequences does this analysis even make sense.
The reverse trie — i.e., suffix tree (and related suffix array) — is genius. But a good hash table is almost certainly the way to go. Maybe a wicked good engineer can write this algorithm using a suffix array that actually performs faster than a good hash table with a string compare... but most will miss cache and branch mispredict all over the place.
Also can we discuss why we would want someone to write a trie or any of these solutions rather than using something like a dict? If I saw some convoluted solution like this in a PR there better be a really good reason for it.
This is a fun puzzle, but it's not clear to me how this selects for people with the aptitude to perform well in any particular software development job, as the number of times I've been asked to determine is a string is/contains the concatenation of two dictionary words is I think zero.
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.
Unfortunately, I just checked and ChatGPT gives the correct (slow) answer to your question:
def is_concatenation_of_two_dict_words(word, dict_words):
"""
Returns True if the input word is a concatenation of two words in the input list of dictionary words,
and False otherwise.
Args:
- word (str): The input string to check.
- dict_words (list[str]): A list of dictionary words to check against.
Returns:
- (bool): True if the input word is a concatenation of two words in the input list of dictionary words,
and False otherwise.
"""
for i in range(1, len(word)):
prefix = word[:i]
suffix = word[i:]
if prefix in dict_words and suffix in dict_words:
return True
return False
In general, I don't think that LeetCode questions have any particular advantage over work sample tests when LLMs are involved. Your questions will end up on LeetCode, where LLMs will index them and will be able to recite the answers.
> I don't think that LeetCode questions have any particular advantage over work sample tests when LLMs are involved.
I agree. We do work sample tests, and in addition to the code and docs the candidates hand in, what really matters is the walkthroughs we do with them. Why did they do it that way? What alternatives did they consider? What are the pros and cons? What past projects did they draw on? How did they research this?
Candidates usually enjoy this - most programmers enjoy talking about a just-finished project, especially when they feel good about the result - and you get to learn a lot about them.
If someone turned in an LLM-assisted work and lied about it, I doubt they'd fare well. And if they did use LLM assist - could be an interesting conversation all the same. What did you reject? What did you correct? Why?
You're writing "work sample tests," and I'm hearing "take home assignments." Is that right?
If so, how do you solve the problem of the assignment just taking way too much time compared to a more typical process, where you do a phone screen and 3-5 hours of technical interviews with a behavioral or 2 thrown in there? I know that if you send me a take home that's any like most of the ones I've gotten in the past, and your competitor says I can do a recruiter chat and technical phone screen to qualify for a 4-5 hour onsite, I'm going with them just on the sheer amount of time and effort needed from me for each process.
How do you get around the fact that if you give such a test to enough people, some of them will eventually put it up on Github for the world to see and crib from? Even for those willing to accept the time commitment, how do you account for the bias involved in giving the same assignment to working candidates and people just out of school? There's a good bit of implicit age discrimination going on there, since folks who have been working a while are far more likely to have families than those just out of school. And then there's the old "fraudulent candidate hires someone else who's actually good to do the assignment." Granted, that person won't succeed at the job, but it'll take at least some weeks before most companies will give up on someone they hired, even if they're completely hopeless at the actual job.
I could go on and on, but I think you get the idea.
A) you have developers you already have hired take the tests regularly and make sure they are properly calibrated for time
B) you replace time in interviews with the test you don’t just add it on as another thing.
C) you change the test regularly and implement basic plagiarism filters on the tests you do have.
As a person who has been in the industry a fair bit I think the flexibility of take home work samples gives me a leg up over day long in person interviews (and the last time I interviewed it was multi day not 4 or 5 hours).
I don’t have to take time off of work or not pick up my kid from school or anything. Just do it in my free time.
Yeahhh, I'm gonna need you to fuck right off with all this reasonable attitude you've got about this... lol, (kidding of course.)
Seriously though, you've basically outlined the only reasonable way to go about it. The problem is really that that's a lot of fucking work you're opting into with 3 little sentences, and after all that, you actually end up with a non-repeatable process, which is not really ideal. I'm still highly skeptical that it's not biased toward people without families, either.
But my real issue here is that at least 75-80% of companies that do this crap obviously don't implement any of that stuff, and most of the rest don't do all 3. You really need all 3 in order to maintain any integrity to the process, and that's, unfortunately, one of the strengths of whiteboard hazing from the employer side. I know I'm never doing another 2+ hour take-home again, and the fact that employers generally don't do any of that stuff are more or less my reasons.
I agree that most companies don’t do work sample hiring well. But most companies don’t do any technical filters well. They’ll waste your time with dumb whiteboarding, or leet code or god forbid personality tests.
To me it’s a strong signal if a company has a work sample test because it shows they have at least one part of their process that has a chance to be a good filter. It’s an even stronger signal if they’ve replaced the majority of their pipeline with it.
I won’t say I won’t accept a job that didn’t do a work sample component but it would definitely jade my thinking against the firm. And I’ve certainly told companies I wouldn’t continue with their hiring process after hearing what it entails.
def is_concatenation_of_dictionary_words(s, words):
if not s or not words:
return False
n = len(s)
dp = [False] * (n + 1)
dp[0] = True
for i in range(1, n + 1):
for j in range(i):
if dp[j] and s[j:i] in words:
dp[i] = True
break
return dp[n]
It doesn't find the trie (or regex) solutions to parts 1 and 2, though. It also finds the right complexity for its solution for part 1, but when asked for an O(n) solution, it first repeats an equivalent algorithm, and suddenly claims it is O(n) because the hash is O(1).
That said, I believe an engineer with the answers it gave, would easily figure out from its output what the right complexity is. (Figuring out the trie, may not be so easy.)
That said, meanwhile, ChatGPT is not yet at a point where it can write out a full working repository solving a nontrivial problem. It can help, but it is not autonomous; and realistically, if someone can get that help to reach a good solution for a test, they can do so for a salary.
When I asked, it first gave the for loop answer. I asked it the complexity, it answered, then I asked it if it could find an algorithm with lower complexity and it came up with an answer using a trie, although not the reversed words trie trick.
Better than the candidates I interview would do, and probably better than I would do, I would probably need a hint to use a trie and I haven't analyzed algorithmic complexity in a quarter of a century.
At least in my experience dynamic programming only comes up when I'm studying for interviews. Of all algorithms common in interview questions, I think DP has the highest ratio for occurrence on whiteboards vs occurrence in most software development jobs. I understand it's fun when you spot the solution but I think it only really proves your candidate did their homework
- While DP might be rare, memoize is quite common alternative. Sticking a @functools.cache in Python for example. They are functionally equivalent in many cases,
- I believe knowing their data-structures and algorithms is the difference between an okay programmer and a good one,
- When interviewing entry-level software-engineers, there's not much else you can ask them except for what they learned in class, which is these kinds of questions.
> I believe knowing their data-structures and algorithms is the difference between an okay programmer and a good one
For me, the difference between and okay programmer and a good one is: how much Linux/Unix they know (processes, core system calls, networking, sockets, awk/sed/bash). Whether you are writing apis for ecommerce platforms or writing custom k8s providers, Linux knowledge is a must. Knowing how to implement a trie? I bet most of us have never been in that situation.
That depends on what kind of system you are developing. For example if you're writing APIs for e-commerce platforms you may need to know how to tune a container's CPU and memory limits but not the difference between cgroups v1 and v2.
Likewise, there are jobs where being able to reason on complexity and data structures is important.
We have developers writing APIs for e-commerce platforms that don't know a lick of Linux, thus proving it's possible to write code without knowing how to deploy it.
Those are fair points and you also said you didn’t expect them to implement DP. I’m curious what your minimum expectations are for the candidate to solve. When I ask these questions it’s usually about the journey more than the destination (which I believe you mentioned in the beginning) but I’m guessing you’d at least expect the candidate to come up with the brute force solution.
I think the difference between a good front end developer and an ok one is how they understand about what goes on under the hood of React.
Your broad strokes don’t account for the domain knowledge of a job. If all you’re doing is interviewing college grads, then I guess you have no choice, but this interview question sucks in just about any other context.
> While DP might be rare, memoize is quite common alternative. Sticking a @functools.cache in Python for example. They are functionally equivalent in many cases
They're not just functionally equivalent. They are the same thing. There are two things you need for a dynamic programming solution:
1. You remember the answer every time your function is called. ("Memoization".)
2. You structure your function calls so that they will ask for a lot of answers that have already been computed.
What you don't want is: say you're computing the sums of contiguous subsections of an array. You've already figured out that indices [2:5] sum to 3 and indices [5:8] sum to 8. When you need the sum of indices [2:8], you need to make sure you get it by asking for sum(2,5)+sum(5,8), and not by asking for sum(2,6)+sum(6,8).
> They're not just functionally equivalent. They are the same thing. There are two things you need for a dynamic programming solution
At a high level they are the same, but it makes sense to distinguish between the techniques based on whether you need random access to the already-computed data.
For example, if you are computing the nth fibonacci number f(n), a DP solution needs only the state f(n-1) and f(n), but a typical memoized solution keeps around all the state f(1) through f(n-1). For tougher problems, you can't always convert between them trivially while keeping performance the same.
> if you are computing the nth fibonacci number f(n), a DP solution needs only the state f(n-1) and f(n), but a typical memoized solution keeps around all the state f(1) through f(n-1)
That's all true, but is it comparing like with like?
The "generic DP" solution to the problem is to allocate an array of n elements and fill it in from f(1) to f(n). That's the same amount of storage the "typical" memoized solution uses; cutting it down to an array of 2 elements plus an (implicit) offset between the part of the array that's in use and the full array seems to be an optimization on top of the DP solution.
You could apply the same optimization to a memoized form of the solution. I certainly agree that you most likely wouldn't do that, but you could.
What do we learn by comparing a tightly optimized DP solution against a "typical" memoized solution? Why do we give the DP solution credit for not using what it "doesn't need" while penalizing the memoized solution for what the programmer probably added unnecessarily?
I came to the field from a slightly different direction; I never studied DP in classes (I was a bio major) but used them extensively in my undergraduate research and later when implementing a few toy bioinformatics algorithms (it's a real joy when it works for the first time!). Even though I've written them a number of times, I really doubt I'd ever be able to spot a DP problem and solve it with that, without some hinting. I do not think it provides useful signal unless you're looking for people who will be writing algorithms.
I suspect it's less useful as a "this person will excel" test and more useful as a "this person won't fail miserably" test. Which for most hiring decisions is the more important factor. I would under no circumstances hire someone who couldn't at least get the brute-force level solutions and talk intelligently about performance concerns.
IMO, the disdain from LeetCode from developers vs. its continued use disconnect stems from the fact that we developers tend to assume that the goal of the hiring process is to find the very best possible candidate, whereas the goal in reality is to find somebody "good enough" as efficiently as possible.
The disdain is fueled by companies' behavior. Your approach makes sense, but if that were the case, then a DSA whiteboard interview should be a fail/pass -- a company shouldn't prefer a candidate that managed to cook up an O(n log n) solution over a candidate that only got a solution in O(n2). In my experience, no company doing whiteboard interviews works like that. As OP themselves said in another comment, "it's not a binary yes/no, but gives a range to score the candidate"
At the end of the day, you can't test for negatives and just pick a random person that doesn't fail anything. You need to have a defined set of values to look for in a candidate, and to design an interview that tests for those values. That's why I hate DSAs -- for most (all?) companies, they're treated as dogma rather than a pragmatic solution to a difficult problem.
I ask multiple related questions, and if a candidate struggles with one of them, I probe for strengths in other areas.
No one answer to a question in that interview is a pass or fail. But the interview, holistically, is a pass or fail, or a conditional[1] pass.
[1] I was impresssed by some aspects of the candidate, but there are notable, significant weaknesses. Please determine if other interviewers have detected similar weaknesses, or if the candidate just got unlucky with my particular question.
I suspect it's less useful as a "this person will excel" test and more useful as a "this person won't fail miserably" test.
Unfortunately the OP seems to be using it in the former sense (when applied to the tries solution that he things will separate the "good" candidates from the plodding lunkheads).
> ...[companies and interviewers] that the goal of the hiring process is to find the very best possible candidate, whereas the goal in reality is to find somebody "good enough" as efficiently as possible.
I suppose that's why mathematicians came up with the idea of "optimal stopping." There are literally tons of scenarios out there where the goal isn't to get "the very best possible candidate," but to get someone "good enough," or maybe even the best person you can get after putting a reasonable amount of time and effort into searching.
Huh, well. That's no good. People upvoted me, so I'm assuming it's fixed now. Since you're the only one who's mentioned it, I'm guessing you made it happen, so, thanks. :)
"it's less useful as a "this person will excel" test and more useful as a "this person won't fail miserably" test."
This is also an unproven statement with dubious validity.
I come from the trading world where the leetcode equivalent is a brain teaser. After much deliberation, the only thing we could think of for why a brain teaser was useful was that it often proved someone wanted the job so badly that they memorized all the brain teasers. And that type of dedication and drive is what we really wanted.
To me, I don't understand why someone who develops with advanced IDEs, using complex tools and libraries, is in the least bit judged by putting them in front of what is essentially a text editor, and asking them to solve a problem that's of no relevance to their job, using no tools that they're comfortable with
You can use all the IDEs and tools and libraries you want, at the end of the day you still need to know how to read and write code. If you can't pound out a FizzBuzz-level without help, no amount of tooling, IDEs, or libraries is going to make you capable of developing software.
Period. If someone tells me they can develop software in a language, and they can't write ~10 lines of code, that tells me they lied. It's like when getting lifeguard certified they require you to dive down to the bottom and grab a brick. Nothing at all in the day-to-day job of lifeguard requires retrieving submerged bricks, but the set of people who possess the swimming skills to be a lifeguard is fully included within the set of people who dive to the bottom to grab a brick.
At least for Red Cross certification, the training is a mix of teaching and test. The basic swimming skills are basically a test, as it's incredibly unlikely that someone would develop those in the 2-3 days that the course runs.
When I was a young lad you had to pass basic, intermediate, and advanced swimming classes before signing up for the guard class. Each class took about two weeks of daily lessons at the local pond.
This qualified me to sit next to a pool in a condo complex where no one ever swam for eight hours a day. Best job I ever had.
It's just as easy to analogize it as picking up a brick is to lifeguard training as it is to say it's swimming in melted chocolate is relevant to lifeguard training.
Your question has no scientific justification. It just is a problem you can do, and you like yourself and think you're awesome. So you think it finds people like you. But even that isn't scientifically supported.
If you think trying to use machismo like declaring your opinion as fact with a "Period" emphasis is somehow a substitute for evidence, then you're talking to the wrong person.
I'll take someone whose Github repo shows talent, dedication and passion, but who misspelled an include header in their brain teaser over the inverse any day of the week. But you do you. Neither you nor I have a lot of evidence to support our preferences either way.
You are either deliberately misinterpreting what I'm saying, or are unaware of just how muddy the hiring pool is for software jobs. If you post a software role, you will get a significant number of applicants who will struggle to write FizzBuzz. Not on grounds of misspellings or missing semicolons: they genuinely have no idea how to code. If you have them code for you, it's really not hard to spot.
Digging through a couple GitHub repos is a good way to find good developers versus poor ones. The goal of a leetcode question is to separate the developers from the non-developers. And you can do that pretty adequately with 2 questions: "Tell me about something you've worked on" and "Hack together a solution to this trivial question".
Anyone who hasn’t sat in the interviewer’s chair would be shocked at how many “Senior Software Engineers At BigCo” can’t even write a program that “displays a countdown of all even numbers from 100 to 2, each on a different line.” There is literally no baseline level of knowledge that is a given, like there is for, say, a doctor.
Sure but then why do people do leetcode hards coding brain teasers? This is like asking a journalist to write a sentence that is reversible when you just want to know he speaks English.
It strikes me as counter productive to select for memorization for a job based on research and collaboration. It's easy, but then the whole "software development is costly and error prone" problem looks self inflicted.
This is a decade old story, but I was asked FizzBuzz for the first time without knowing what it was, and got it fundamentally wrong. This was three years into a career in which I alone had written a full equity arbitrage trading system in C++ that was making millions per year. I had written PDE solvers running in production for 50 traders doing $1bn worth of trades a day. I was not a liar.
The question did not "weed out someone who couldn't code." It weeded out someone who couldn't use a totally unfamilliar dev environment while being stared at and asked to "walk me through your thoughts" instead of letting me think. It left me distracted, thinking both "this is easy, what's the catch" and "wtf is the point of this?"
"Tell me about something you've worked on" is a totally fine question. I'm not arguing with that. But anything leetcode is not, IME. This becomes increasingly true as people's careers develop. If you've spent your last two years writing hyper low latency deserialization engines and packet processing, then you'd know that's what the job is about. In the macro, trading engines and game engines are one medium leetcode problem from an algorithms point of view, but they require teams of people and years of optimization and customization to make truly effective. I don't want to test for the person who can make a really basic solution in 30 minutes. I want to test for the person who can optimize a tiny fraction of it in 2 days.
That’s a disingenuous argument enabling somebody with a massive ego problem.
1) most people here, I believe, don’t have a problem testing a developer’s code writing acumen.
2) People weigh something. Bricks weigh something. It’s the same exercise. The analogy in software would be the difference between asking someone to write _an_ function that can do x vs write _the_ function your company uses to do x.
3) the lions share of counterarguments here propose using real world exercises vs toy problems
I think you're missing the point of the comment about tools.
Programmers skew anxious. In theory there's no difference between writing basic code on a whiteboard and writing it in an IDE. But in practice, an interview is a novel, high-stakes environment with a bunch of judgy strangers. So if you then have people do the interview using tools that are unfamiliar, a notable percentage of them will be thrown off.
Once I switched to encouraging people to bring their own tools (own laptop, own editor, preferred language), I saw a marked decrease in people bombing interviews. Some of the people you might have put in the "they lied" bucket were, at least for me, just ones who got really nervous and so were unable to grab the brick.
To me, that's a bad interview, because the job isn't going to be high-stakes whiteboard coding. It's going to be sitting quietly in a comfortable and safe place and gradually improving things. The more an interview can be like that, the better.
Isn't the brick test pretty close to a work-sample test?
I've always assumed the brick was meant to simulate a drowning swimmer, whose rescue is pretty clearly part of the lifeguard's job. I guess a mannequin would be more realistic, but it still seems pretty close.
I prefer solving puzzles -as- my work. If I’m not doing work that gives me the opportunity to take a Problem Solved Victory Lap every once in a while, I don’t want the job.
I can tell you the reason for the continued use of leetcode (or similar) at my company. We started giving junior candidates a leetcode-ish test with a low bar for passing to screen out really weak programmers. Everyone who passed went on to on-site interviews. Interviewers complained about having too many interviews to do. So the recruitment team just cranked up the score required to pass. Bingo, less work for interviewers.
Sadly everyone who makes it to an on-site is now a competitive programming enthusiast who is probably a really poor fit to actually working in software development.
Many people are vaguely aware of this problem, but nobody has a strong incentive to put in the work to come up with anything better.
I agree that leetcode questions are great for quickly eliminating bad candidates, but this question has the classic problem of being way too hard. Like 50% of leetcode questions are difficult dynamic programming problems (why the obsession with dynamic programming?). Even in the most algorithm heavy job I've had which actually did involve coming up with novel algorithms there was 0 dynamic programming.
And most programming jobs involve no complex algorithms at all. At most you have to be a little careful to avoid N^2 occasionally.
Leetcode is great for filtering out bad candidates but if your solution involves dynamic programming it is too hard for an interview.
I actually have had to solve a version of this problem on the job. There was a database of tagged photos; for some reason all the tag strings had had their spaces stripped. So you had to efficiently find a probable chunking into words. (Of course the original text wasn't always all dictionary words.)
OTOH re the concern for O(n^2) time when n is bounded by word lengths, and when the inner loop was in already-optimized string comparisons in your language's hashtable library -- I think that part is very artificial.
> OTOH re the concern for O(n^2) time when n is bounded by word lengths, and when the inner loop was in already-optimized string comparisons in your language's hashtable library -- I think that part is very artificial.
Yes! The candidate already optimized for the important thing (which the author forgot about and added in a footnote), which is that the list of words could be very long, and that the words in an English dictionary are relatively short.
Optimising for the important factors based on an assessment of the problem domain is actually a more important skill than regurgitating the best algorithm from the book. If the author wanted to suggest a solution suitable for very long needles, he should have used a different domain like, say, gene sequencing.
But even if the job actually requires solving puzzles like that one, what's the point of asking the candidate to solve it in 45 min? Without googling? That's what it's actually totally unrealistic.
Give me any problem related to algorithms+ds to be solved in 45mins without internet access and someone looking over my shoulder and I will give you a poor solution. But give me a day and internet connection and I will solve the problem in the most efficient/readable/maintainable way possible.
It's especially ironic that this puzzle structure selects away from candidates whose ordinary method would be to look up available algorithms, rather than just going with the best answer they came up with off the top of their head.
To be honest the first solution is literally one line of code. The data structures are those included in Python, there's nothing to look up. It's an important skill to take some code written by others and understand precisely it's performance characteristics.
The interview question is not just about knowing data structures and is not about Behdad showing off either. It's the starting point for a Socratic discussion.
I don’t think it’s super relevant for the challenge to be similar to the day job challenges. Maybe it’s even unclear what those are at the point of interviewing.
What is important is that the candidate’s skills generalize well to both the challenge in the interview as well as the day job. A question like this might be a good indicator or not depending on the job.
If people completely fail at this question it can reveal a lot of relevant information.
I've given this same advice for _years_ for designing technical interviews. Take a problem that you or your team has actually faced in the last n months. Distill it down to remove tribal knowledge and get it to something you or a capable colleague can hammer out in m minutes. Give the candidate 3m minutes to solve it. Typically this means it should take you 15 minutes to solve and give them 45 minutes.
Our biggest hit for a question that followed this for an SRE type role: we had a cron job that was legacy and buggy and caused a couple of issues over 6 months. We went back and created a very similar script with very similar bugs, added some similar data and re-seeding scripts, and told the candidates "customers say that feature $x is not working, and that is ran by this script. Here is how to run it, here is the user's id that can be found in the data seed." We added some other data validation problems. After they fixed it, we asked them what they would do to make this more production safe and dig in on what they have and have not done for improving existing systems. We expected discussions on structured logging, metrics, alerting, testing, code layout, etc.
Over time, the roles that you are looking to fill and the weaknesses on the existing team that you want to shore up will change and you will need different interview questions. Maybe more towards distributed systems or more towards testing or observability.
> Typically this means it should take you 15 minutes to solve and give them 45 minutes
They mean 3 x m where m is how much time you think it would take for you to solve; so the example is: if it takes you 15mins, then give the interviewee 3 x 15 = 45mins
This is the right answer. Questions of this type test for both experience (what you want from non-junior candidates - the fact that they have learned to program defensively, check edge cases, etc) and common sense (what you want from junior candidates - not making silly simplifying assumptions, thinking divergently about what could go wrong, etc).
Importantly, it also allows you to examine fluency. The candidate who can write a code/pseudocode solution as fast as they can type, and explain it verbally at the same time, is much more impressive than the candidate who pauses for a long time before starting haltingly and unconfidently. Fluency in solving leetcode problems just tests for having practiced leetcode, but fluency in writing real code tests for actual productivity.
If you have a question like this, you can drill down into performance characteristics just as the question in TFA does. Not necessarily using big-Oh notation, but "what if you have to do this millions of times? what if you have to provide results immediately? what if some of the files are too big to fit into RAM?". But you can also drill down into other aspects of the problem like changing specs, noisy input, constrained resources, observability.
FWIW, when I came up with a question like this (with the constraint that it had to represent a problem I had solved that morning), ChatGPT was not able to solve it correctly.
> Our biggest hit for a question that followed this for an SRE type role: we had a cron job that was legacy and buggy and caused a couple of issues over 6 months. We went back and created a very similar script with very similar bugs, added some similar data and re-seeding scripts, and told the candidates "customers say that feature $x is not working, and that is ran by this script. Here is how to run it, here is the user's id that can be found in the data seed." We added some other data validation problems. After they fixed it, we asked them what they would do to make this more production safe and dig in on what they have and have not done for improving existing systems. We expected discussions on structured logging, metrics, alerting, testing, code layout, etc.
No wonder it is a hit. It is an actual problem that makes me want to go for it - I want to take an interview like this, instead of the usual of dreading interviews! Keep it up.
I am not sure about this particular puzzle but I have noticed that I can learn a lot from observing how to approach such a problem. Even some senior people seem to have no ability to think about solutions. Other people seem to only be able to look up things on Google. I like people who at least try to attack the problem and think it through. I don't care so much if they succeed but I am happy if they are able and willing to think about something they haven't done before. From my experience this bodes well for working with them and them being able to adapt to new things.
One of the things I learned in the classical music world is that the things we ask people to do in auditions–play the hardest parts of all the most difficult orchestral music without any context–is really creating a new problem that doesn't need to exist.
And in my experience listening to auditions over the last several decades, what you have now is a bunch of musicians who can only do what's on the test. When you try to plug them into an orchestra, they are completely fucked.
My experience interviewing and hiring tech people is that this is one of the worst possible approaches. Anyone who needed to could figure this out. It's not relevant. What you need to figure out in an interview is if the person is curious enough to find the answer.
I don't ask for code or algos in my interviews. I ask about the person. What's your favorite programming language? Why is it your favorite? What do you not like about it?
What's the project you are most proud of? What was hard about it? What made you happy? What did you find challenging about that project?
These are 100% totally humane questions that tell you everything you could possibly need to know about a candidate in about a half hour. Maybe less.
If you can't figure out if this person is technically competent from this set of questions then you aren't competent to interview or hire.
Interviews don't have to be only about how good you are at interviews. They could be about trying to understand if the person would be good at the job and fit in well with the team.
I think your approach is fine, but I should mention that it will, like any interview approach, misfire with some people.
Episodic recall and emotional recognition are both talents that vary across the population. If I want to do well at an interview like this, I will have to spend a bunch of time in advance refreshing my memory of various projects I have worked on so that I can simulate a neurotypical response to those questions. If I don't, I may just stare at you nervously and break out in a sweat when I realize I don't have anything filed under, "project I am most proud of". Or that pulling up the narratively engaging details of a project I haven't thought about in years is a process that will take me hours of specific effort. And it's not just me; I've hired great developers who were also terrible at "humane" interview questions but who did great when we just sat down and coded together.
I agree this is true, but I think that's in contradiction to the notion that one can just ask some breezy "totally humane questions" and then make optimal hiring decisions. The more separate the domain, and the more preparation helps, the more you're testing for something pretty different than the work.
You don't make "optimal" hiring decisions by just talking to someone. I would say whether your hiring decision was optimal can only be judged in hindsight. Hiring is getting a limited pool of people and filtering down to find the ones that fit the role most.
In the end all you could actually do is guesstimating who would do best at the job. And sometimes the answer is: "none of the ones who showed up".
If you are a good engineer or programmer yourself you can tell a lot about a person by talking to them for an hour. You can learn what is important to them in the craft, how they deal with criticism, what they aspire to, what kind of problems they tend to work on, if they are more autodidactic or more influenced by other's opinions and so on. This is all knowledge directly inpacting the question whether they are the right person for the job.
And who the right person is depends on the job, so there might not be "right" answers to the questions. For a very niche database job you might actually want someone who is very accurate, very in the detail and very focused. For other jobs maybe some entirely different traits are better.
Of course the problem here is that the people you hire could just be very good actors or liars who cannot do the things they say, so a little technical testing might also be needed.
I think the issue is that, and I'm paraphrasing something which someone else said but which I think reflects what I've seen, nobody (at least in larger companies) wants to be responsible for a bad hiring decision.
While yes, you can get someone who has a good track record of being a good judge of character to make hiring decisions. If that decision goes wrong and the blame game starts then you inevitably ask this person to explain their hiring decision. This person will then reply: well it was my opinion that X, Y and Z.
In the alternative case where you just get someone to follow a rigid process you can answer: Well he scored well on this exercise and the opinion of the team was in his favour and the work history ticked the right boxes. This effectively dilutes the responsibility. You can no longer blame one person for the bad hire.
Lastly there's also the diversity aspect. With companies increasingly being scrutinized for their hiring practices, "it was my opinion" just gets translated to "this person's internal biases guided the hiring process and as such it was not fair."
I agree this is all making hiring much harder than it needs to be. And certainly you can still find companies where the hiring decisions are made on highly experienced and well honed gut instinct (its the only kind of interview I have been a part of) but it also makes sense how in our increasingly overcomplicated world we are developing increasingly overcomplicated hiring processes.
My recommendation is if you want a sensible hiring process (with maybe a telephone screen followed up by one normal interview) you should stick to smaller and less corporate companies.
Unfortunately, "gut instinct" is just another phrase for "unconscious bias". Sometimes those biases are helpful, some less so. And some can result in hiring results that are unfair enough to invite lawsuits.
I know plenty of smaller, less corporate companies that still use careful hiring processes with thoughtful rubrics. They do that not because of risk avoidance; they are generally still ok firing people who don't work out. They do it because they want to run a fair process while maximizing ROI.
This very thing happened to me recently in an interview. This was my first interview after not having actively interviewed for a few years now, so I was quite rusty. I was asked what some issues were that I worked on at an initial phase of the project and I blanked the fuck out and then instantly went into self-scrutiny and sweating as I spiralled into "oh crap I should really know this" and "this is making me look stupid" and wondering how I was coming across to the interviewer. I have some anxiety problems, that's there too - but point is that if you're not really prepared with answers to questions like these, it can seriously throw you off mid-interview.
And lots of good developers skew anxious! What in normal life counts as being overly careful or or overly sensitive is just good practice in coding.
That's why I think it's especially important to make interviews as low-anxiety as possible. They'll always be worse than the job, of course, but the closer you get them, the more you're likely to see how people will really perform on the job.
Out of curiousity, did your high school or college teach you much about interview prep?
Both of mine did. Much of their advice was irrelevant (nobody in tech gives a shit about your suit or how firm your handshake is) but they both stressed the importance of preparing in advance to show how good your skills are; and giving thought to cliche lines of discussion like 'what's your biggest weakness?'
I too have to prepare for such questions. I thought everyone else also did.
Not only do I not remember past successes very well, preparing for these questions is literally the first time I asked myself what I'm proud of. I didn't even consider doing this and reject it as irrelevant before. It just never came up.
I have arbitrarily terrible episodic memory, especially so for professional stuff. If I don't have the commit history to check, I have trouble describing what I did in the last month in anything like a lucid level of detail.
I've always had trouble with the kind of behavioral interviews that are "Tell me about a time when . . ." since I can often recognize that I've been in relevant situations but can't for the life of me remember the details (even with time to prepare).
This honestly makes me more nervous about interviews than leetcode shenanigans. At least with those, I know how to improve.
(At work I rely on a combination of having the code in front of me, written notes, and whatever project management tools we have so it's not much of an issue, but most of that isn't available to me in an interview setting.)
From what I've seen, getting a regular job in classical music is difficulty and pressure on a level few of us can imagine. Might be easier to get tenure at Harvard than a rostered spot in an orchestra.
I think the odds of getting a high-profile orchestra slot are far lower than that.
Source: Multiple orchestra musicians and management speaking about the audition process and the now-defunct myauditions.com website
Process:
Show early talent
Get the right instruction
Get into a preparatory program
Make it into a conservatory
Do well once there
Get a spot in an ensemble, probably lesser-known (not easy) and establish a reputation
See an audition notice with repertoire to prepare, apply
Spend a few weeks or months intensively practicing (on top of other commitments)
Maybe get an audition, realizing the Music Director may be promoting his buddy past these rounds
Travel at your own expense to the audition
Play demanding repertoire behind a screen and respond to any directions
Most likely get rejected
Play in any following rounds
If not rejected, maybe you get a qualifying week rehearsing with your potential colleagues and playing a couple of concerts when the Music Director is in town
If you beat out the couple of stellar artists who've also gotten that far, you may get an offer
Or, the MD's buddy may get the offer
Or, there may be a no-hire
If you get and accept the offer, you are "on approval" for a couple of years at which point there's the Tenure Decision
I love the comparison to music auditions, and I mostly agree with the advice.
I would still require the candidate however to write some code. Something rather simple, not leetcode, ok, not fizzbuzz either, and something that proves their familiarity with at least one language and platform.
I should be a GM by now simply watching chess analysis videos on Youtube, learning the names of some openings etc. I can talk about it all day long. But since I don't play at all (I'm not interested) when I actually do play on occasions I revert to 500 ELO...
You can easily tell a seasoned veteran from a rookie just by looking at them code for a few minutes, working on a simple task. If you can't, you have no business in interviewing others :)
Aesthetic judgements, and the ability to justify and defend them, are very important, but not the only important thing IMO.
Someone who can explain why they love Rust and hate Python (or vice versa) is a convincing candidate but I think you need to see a couple of other things from them. In addition, sometimes you just don't hit on the right question to get evidence of their aesthetic judgement. (Like the candidate who doesn't care about Rust vs Python, but who hates Postgres and loves MariaDB..)
It was not uncommon for speech synthesis systems to have an algorithm much like the one in the interview question to pronounce e.g. words in URLs ("ycombinator"), brand names ("Bitcoin"), or words in languages that like to agglomerate ("Donaudampfschiff"). Admittedly, though, this task is increasingly being delegated to machine learning models.
> just give candidates realistic programming challenges
Not precisely a SWE, but every single piece of code I write at work is more about knowing how the immense codebases are laid out and where to insert my change which is typically simple.
Given this, any "write self contained thing" is unrealistic. The only thing a coding question tells me is whether someone is happy writing simple code to solve a vaguely fun problem.
It was an ok question until around 2015 when i started noticing junior-ish candidates blurted out “trie” immediately and proceeded to write very crappy code for it. In short, it got gamed by the lc types into oblivion. I changed my strategy then to ask very simple algo problem (i would explain the algorithm) with ~20 lines of code solution then aggressively rejected candidates who weren’t fluent in their choice of language. Pros were it was immediately obvious in first two minutes if they coded day to day or just copypastad SO, cons were that it probably was biased against the nervous type. Not my fault though the latter group got shafted by the leetcoders
Yeah, once you get the job after the grueling interview you realize that your actual responsibility will be for the "More" button in Gmail. You need to make sure that it sticks to the "Refresh" button at all times, because it apparently likes to drift.
To be fair, if you are dealing a lot with indexes and word tokenization/lemmatization, as Google engineers presumably are, then this seems to be a relatively "real world" problem.
I agree. One of the best interviews I ever had was for an iOS position at a company. The interviewer himself had a little bit of experience with iOS development and he lent me his laptop and asked me to write a simple app.
It was great because he was testing the very thing I was going to be hired for. Additionally, he asked how I would design X or Y and I explained the pros and cons of certain designs and I could show him right there on the screen how I'd do it. This wasn't a whiteboard where I'd have to slowly write out code in a medium I'm not used to. I literally was typing on a keyboard, using intellisense, etc.
As someone who does iOS development day to day, it was a very easy way for me to show that I knew what I was doing and the guy was quite pleased when I plowed through all the requests he had.
This is very interesting, thank you for sharing! I do have one tangential comment based on this:
> 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.)
Thanks for the comment. By saying "I get good signal" I mean that it's not a binary yes/no, but gives a range to score the candidate. You are right about actual correlation to job performance. I know the HR at Google performed correlation analysis between interview scores and job performance and made internal observations, which as you note is biased because only includes hired candidates.
Most people who say this think the question gives them a good ability to distinguish whether a candidate will be good if hired into a given role, however honestly mostly it gives them a good sense of whether they like the person and/or the person is like them.
As an example, the author of TFA clearly is selecting for people who have the patience to sit around and be told how smart the author is. That is the signal in this “great interview question”: candidate will suck it up for hours while I tell them stuff.
At google you used to see scores and feedback of everyone on the panel and whether hire/no hire decision was made by the Hiring Committee (which you otherwise didn't have any visibility into except sometimes they would leaver you feedback). You could also see your histogram of scores as well as other peoples' on the panel colored by recency and hiring decision which was very useful to calibrate your internal sense. Something so simple can go a long way and I haven't seen it in any of those crappy interviewing saas products out there. Did they scrap that system?
> 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²).
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) ...
You still need to query every byte of the input string...
Any better than that you can do would be O(min(n, k)) where k is the length of the longest word in the dictionary. But without loss of generality that would be O(n).
Good point, though I guess the point of the disagreement is then for me that the question's "dictionary words" implies to me an english dictionary, rather than an abstract dictionary of words of potentially infinite length
You take the first n bytes of your input string. You hash them. You look them up in the dictionary. The lookup is O(1) but hashing your input is O(n).
But there's a simple way around this.
We have incremental hash functions. When you add a byte to the string and you use an incremental hash, you do a fixed amount of extra work to update the hash. Like that you only need to O(1) extra work to compute the new hash.
One trivial incremental hash is to break your input into fixed size chunks, hash each chunk, and xor the chunks together.
It's not at all like the trie solution!
Not in performance and certainly not in terms of complexity.
A trie is a pretty nasty datastructure memory wise. It involves chasing pointers all over the place. The constants on a trie are not going to be very good.
For an incremental hash, you hash your string, and then you fix your hash up as you go. Then you look up your hash in a hash table. Code-wise it's far simpler to implement. And performance wise it will be far faster!
The two solutions have nothing to do with one another. Except that they're both O(n).
Yup, pre-processing with a rolling hash allows you to get away with truly O(1) comparison (after the initial O(w) fixed cost). I don't know if the stdlib of any programming language does this internally if you request a hash of a substring, but it's trivial to implement yourself anyhow.
If you're writing a smug blog post about your "great" interview question, you should at least not make such "obvious" mistakes, especially considering rolling hashes are a "common" interview question trick for string problems. And in practice this hash'd solution probably might end up performing better than the Trie (of course needs benchmarking, etc., but it's not unreasonable to think it might). In an alternate universe you could easily imagine author himself getting failed for overlooking such an "obvious" solution.
You either care about the order of complexity, which is the big O, or you care about real-world performance of byte level operations. You can't have it both ways.
You are technically right. Though if we assume that the size of the dictionary is at least o(n), then the size of such DFA will be exponential in n, and indexing it will be o(n), resulting in a o(n^2) solution again, I think.
The number of states is exponential for a general regex. This regex has an NFA closely resembling the trie for the dictionary. There could be at most one live state per depth in the trie. So the number of possible states is bounded at least by (words in dictionary)^(length of longest word). Really much smaller because the states at different levels have to share prefixes.
They are completely correct. If the DFA fits in RAM, following state transitions will be O(1) and using the DFA for a concatenated string of length N will be O(N). You simply missed a good solution.
> 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²).
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?
n is the length of the string. As for why it matters whether it's linear or quadratic, we are assessing the candidates ability to analyze a problem and possibly improve an algorithm. It might not matter in the problem at hand.
Surely there is a longest word in the dictionary, so you can short circuit for any string longer than twice that. So an asymptotic analysis in the length of the string doesn't really make sense.
I'm a big fan of trie-based interview questions because if an individual can call them out immediately, they know their data structures -- awesome.
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!
"A great interview question" for what? The author sings their praises, but never actually explains what this question is good at testing or what makes it worth an interviewer and candidate's time. Results might favor younger or earlier-in-career folks -- okay, why is that a good thing?
Younger/earlier in career folks are usually cheaper, which companies like.
Though I imagine they could just ask "when was your last algorithms course?" (and possibly where, and what grade you got) and save a lot of time. Or they could just ask "what year did you graduate from (whatever school level)?"
But that wouldn't be as useful for making the candidate "jump through more hoops" and reinforcing compliance as well as status hierarchy - important things at most companies.
And some people may have cheated their way through their algorithms class, so maybe they can be detected if it was recent enough.
A question I used for a number of years was a simple "compression" algorithm that would turn a string of lower case letters into a shorter string by length encoding using the capital equivalent:
abbbbbcdddddde => aB5cD6e
The number of developers who struggled or utterly failed with this was depressing.
The interviewer is not thinking logically. How does he know it's a good interview problem? Let's look at the data:
>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".
As a hiring manager, I’ve noticed most peer hiring managers vastly overestimate their ability to hire.
What I’ve seen happen is that there are two narratives they flip on: I hired this great person and they are doing amazing so I am amazing; I hired this person and they aren’t doing great so I fired them so I am amazing.
Of course, they also tend to be terrible at assessing who is actually good/bad.
I call it the “arbitrary onion”: layer after layer of plausible claims that each turn out to be just as arbitrary as the outer claim.
I guess I’ve always been confused by this question. If the dictionary isn’t infinitely large, and you have plenty of space, why can’t you put the dictionary in a Set and look up words in O(1), reducing the overall complexity to O(n)? Obviously hashing has its limitations, but i thought we could hand wave over that part. If we’re limited by space can we assume that the dictionary is ordered and make the lookup in log(n) via a simple binary search? Or are we obsessing over the string equality operation? I feel like I’m missing something.
Yea, I dislike it (a bit) for that reason. The "meme" in leetcode interviews is that "hashmap lookup is O(1)". It does feel like a bit of a gotcha to (correctly, mind you) expect an answer of O(n) for the lookup.
That being said, I think you could get around this with careful prompting (ie, ask first "what is the Big-O for dictionary lookup with the respect to the number of letters" before asking the overall big O). But I think there is a bit too much wiggle room to make this a completely consistent question, too much variance candidate to candidate.
I like the problem a lot, but wouldn't feel comfortable using it.
Because the author didn’t bother to explain that this is what she’s looking for in a well thought out blog post, I assume she also didn’t explain this is what she was looking for in the interview, leaving a lot of candidates who didn’t have the same educational background floundering.
In general, hash map lookups are considered O(1) in the size of the hash map. Which is not the n the author is using, to begin with.
But.
Hashmap lookups require calculation of a hash of the key. Calculating the hash of a key requires examining all of the bits in the key. If the keys are int32s, then the hash algorithm has to read 32 bits. If they're int64s, then the hash algorithm has to read 64 bits.
And if your hash map contains n distinct values, then at a minimum they must be drawn from a key space where each key contains O(log n) bits. If you want a hash map to contain more than a few billion values, you'll need bigger-than int32-sized keys to distinguish them, right?
So for any hashmap of size n, that means there's an O(log n) hash calculation in there. (especially when we are considering the asymptotic case where the hash map grows infinitely large... such hash maps will necessarily have infinitely long keys, too)
Yet we call hash map lookups O(1).
Because in practice we imagine a hash map has a key space of a fixed size (even though such a constraint would mean that the hash map has a fixed maximum size and therefore no asymptotic performance case since it can't scale to infinity).
By playing around with big-O on hash table lookups with keys of size n, the interviewer is skating dangerously close to this contradiction at the heart of big-O analysis of hashmaps...
But unnecessarily so, since the key space they're using is dictionary words, which have a maximum length, so their length isn't the n you're looking for.
(Note - for the same reason, big-O analyses of sorting algorithms don't usually take an extra O(log n) factor (in n being the size of the valuespace) for the time it takes to compare entries, even though obviously it takes 'longer' to compare two 64bit numbers for size than two 32bit numbers. Is it a hand wave? Probably not when you're dealing with numbers. Maybe when you're dealing with strings)
> Note - for the same reason, big-O analyses of sorting algorithms don't usually take an extra O(log n) factor (in n being the size of the valuespace) for the time it takes to compare entries, even though obviously it takes 'longer' to compare two 64bit numbers for size than two 32bit numbers
This is a great point. If you're sorting an array of strings, you would never add an extra m in that complexity analysis for the size of the longest string, in bits (not length, because unicode)
Another thing we ignore in big-O analyses: as a hashtable grows arbitrarily large, the physical media in which it’s data is stored must also take up more and more physical space. Since we live in three-dimensional space, the retrieval time for a hashtable containing n entries must be bounded by the fact that the entries are located a distance of at least O(n^1/3) away.
(Not actually purely an academic concern - this physical constraint is what drives the difference in performance between using data in L1cache, RAM, disk, or on remote networked nodes.)
So yeah, O(1) hashmap reads are a convenient lie we tell ourselves, which are really only true for ‘small hashmaps’.
What kind of programming will be done on the job by these candidates? Probably nothing like this puzzle.
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.
I can't believe what I'm reading here. Architecture goes hand in hand with which datastructures and algorithms you "unlock". How exactly do you define "Architecture"?
In the small vs in the large. How are responsibilities split up along the modules? Are there layering violations? Is the right problem even being solved, or is there maybe a way to avoid the "is this a concatenation of two words" check altogether?
I would define "architecture" (as it appears in applied software development) as working on the structure and interaction of system components much larger than a single data structure or a single algorithm; where many of those components might be separate systems themselves. When "architecture" handles specific data representations, it's usually talking about the data representation and encoding at some API or "API-like" (e.g. file, message, etc) interface between two systems or persistent storage, not about the temporary representation of that data during some processing; and "architecture" is generally much more about the semantics of that data and possibly differing assumptions/expectations about that data between different components, rather than the performance characteristics of that representation for a particular algorithm except in the relatively rare case when a single algorithm represents the majority of that system's purpose and performance.
How do you define architecture, and 'beyond'? IMHO addressing almost any real problem involves much wider concerns, and actually of a different nature, than just basic data structures and algorithms and their properties, that these puzzles test. They are just a small part of what it takes to produce something useful, and often not needed at all, or can be easily googled.
Maybe surprisingly, junior candidates sometimes rank better at this problem because their Data Structure & Algorithms knowledge is more fresh.
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 expect any candidate to be hired to be able to produce code for the brute-force cases, and do the runtime analysis on them.
It's a whole other debate that most software engineers, even at BigCo end up writing CSS code to move pixels only and lose their DSA knowledge over time...
That’s probably also what happened with your ‘disappointing’ PhD student.
They probably did know how to code, but they’ve spent the last 5 years working on something quite a bit different from string wrangling in Python. Add in the stress of a (first-time?) interview and a reasonable candidate can look like a total fool…
It's fair to expect any candidate to hire to produce the brute-force code and do some rudimentary/rough analysis. That's not why it's a bad question.
It's a bad question because _how well_ a candidate does past that minimum threshold has _no correlation_ with their ability to do the job.
You can treat it as a binary question for that minimum floor. To use it for rating, you're doing your org and the candidate a disservice and you're wasting interviewing time that could be spent more productively and humanely.
> even at BigCo end up writing CSS code to move pixels only
Is this common at Google?
If by DSA knowledge you mean leetcode puzzle knowledge, yes, quite certainly. But from my experience fresh grads are less effective engineers before they mature by working with industry scale systems for a few years. And at that point they would have been less able to do your problem but a far better engineer.
Which means your interview question is aimed backwards, maybe if you only used it against fresh college grads then the gain function would be positive, but you applied it against everyone.
Dynamic programming problems are banned at a number of companies, and with good reason. Candidates ability to do well on them is largely a function of how much they’ve practiced those problems. I’ve never needed to do dynamic programming with caching of recursive overlapping sub problems ever, and only learned it recently during interview practice.
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
I would do that straight away. I don't see the point of implementing the more complex and longer to code "double dictionary checking for all partitions of the string"
I've never seen this problem before and arrived at the optimal solution to the first section, sans code, in about 10 seconds. Despite that, there's almost no way I would pass a technical interview at Google.
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.
> Despite that, there's almost no way I would pass a technical interview at Google.
You could get lucky and have each question have a similar relationship to past knowledge. It's happened to me before, I blew through an Amazon interview once that way, but got knocked for technical leadership. So maybe you mean something like that, but that too is random. I had passed the leadership but failed the algorithms at Amazon a few years prior.
> 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.
I believe these tests are more about compliance and baseline cognitive ability than anything else, which is good for the nature of the FAANG role. They are testing that you are willing to study what they tell you and that you are able to retain material of that level of difficultly and demonstrate that in an adversarial situation.
I also came up with the optimal solution in 3 seconds, because for my side “hustle” I work on scrabble apps all night and compressed tries are an integral part of move generation.
This interview question is good for kids recently out of school, but for everyone else I think it doesn’t really show if the candidate is a good developer.
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 :)
I hate this industry so much. I know what a trie is, but having it dangled over my head by some smarmy git like this: Just the thought of it fills me with so much sadness. These "Junior year computer science problems" just make me so angry even reading about them. I'll start interviewing in a year or so, it just fills me with despair knowing this is what I'll face when I do.
Been at it for the past 3 months. It is soul crushing and demoralizing. I'm starting to accept that I would rather work in a toxic company than have to go back job searching.
Is it really that bad? I've taken the time to go back to some great books I never got a chance to fully study, like Udi Manber's Introduction to Algorithms and Jeff Erickson's Algorithms and even found some new gems like Guide to Competitive Programming and Competitive Programming 4 Book 1.
I don't know if this is sarcasm or not, but in case you're serious. The fact that you feel the need to approach this like you're a gladiator preparing for mortal combat in the arena of the mind, is really not OK. Our industry's interviews shouldn't be like this
I majored in computer engineering and skipped algorithms so it was pretty intense studying for a couple of months before I felt comfortable. Overall I really enjoyed learning it but I made it through so many successful years of software engineering without learning it that I don’t think it’s relevant to most people. Even now I write an O(n) algorithm to merge sorted lists and people comment on my PR just tell me to throw everything in an array and use the sort function.
The mindfuck when you realize cache locality can make an O(log n) algo faster than an O(1) algo, and the big-O analysis only really matters for extremely large data sets. :D
I recommend you keep at it, I also hated interviewing and it would give me anxiety which made me draw blanks and under perform embarrassingly a couple interviews.
The trick for me was diligently applying to as many places as possible (that were at least somewhat of a fit), and eventually coming across one where the main technical part of it was "take home". Coding and discussing thought processes on the spot for an audience isn't something I'm good at it turns out, but solving a practical problem on my own time was fine.
It's ultimately a numbers game, the more places you apply to, the more likely you'll find an interview process that fits. That is the most important thing to keep in mind--shotgun blast those applications. It's hard not to take rejection personally, but don't give up and settle for a toxic job, that's even worse.
If you can, take some time off and do something for yourself. I got way too caught up in the grind, was spending every spare moment on leetcode and algorithms, and all I felt was a gnawing desperation to succeed and get an offer. I took time off and refocused on what was important to me. I started hiking and biking and doing things that interested me. I stopped leetcoding at all. When I next interviewed a couple of months later, I didn’t even study and I didn’t need to, I came across as confident, and I got 2 offers right away. Fortunately I had a job at the time so I was able to go back to business as usual without it affecting my finances, but being in that situation without a job terrifies me.
this reminds me of the whole zeitgeist that was around a long time ago around the smug interviewer that really just wanted to have some shine to the fact that he knew what a bloom filter was and that anything other than that wouldn't be someone worth hiring. iirc they got the deserved drubbing at the time for it because knowledge of some esoteric at the time concept wasn't really a great signal.
I like this post. It's very honest. What you say is true. Sadly, I recommend to grind LeetCode for at least one month before your interviews start. Make sure you can solve most medium difficulty and a few hard difficulty. It will give you a head start over many of your peers.
As I age, one thing that I realise about interviewing: It is scary as hell. It is basically performance art. And, most nerds are terrible about public performance & speaking. Some days you are really on it; other days: way off. Every single job that I ever got in my life feels like a lucky day. Also, the tech universe is infinitely wide at this point, so somebody somewhere can ask a question that you will fail.
Since this industry is so dominated by men, it also feels like a lot of machismo. So many interviews are just a jerk dude on the other side of the table (probably working for an amazing company) that wants to make himself feel better by making me look foolish. There are too many stories to tell. I have also kept my mouth shut when interviewers were insistent about a technical point that was 100% verifiably incorrect with a simple Google search. It helps to stroke their ego during an interview. When they give you a hint, or explain a better solution, try: "Oh, that's really impressive! How did you discover that algorithm?" You are more likely to make it to the next round. The goal of interviewing is to get the offer. You can always turn it down. If you had one jerk in the interview stream, but they work on a different team, it should be OK to accept the offer.
Another thing that I say to all interviewees now: I know that interviewing is scary. We are interested in what you do know, not what you do not know. Together, we will dive as deep as possible on a few topics to find the outer limit of what you know. If we come to a topic that you don't know about (or not deeply), tell us; we will move to a new topic.
> Every single job that I ever got in my life feels like a lucky day.
I think I read on here about the concept of successful people really just doing more things to increase their luck surface area.
In other words, you set yourself up to interview as best as you can, then make a bunch of connections and schedule a bunch of interviews, and (hopefully) at least one of those will be on a good day.
It's such a weird and, frankly, shitty way to make hiring decisions though. But at the same time, we don't have much better.
I think I read on here about the concept of successful people really just doing more things to increase their luck surface area.
Mike Bloomberg famously wrote in his (a bit shoddy) auto-biography: "Work hard and you might get lucky." (paraphrased) I complete agree. In _some_ form, it is a bit like "Fake it until you make it" -- but the better side of the same coin!
I hear you. Here is a quick tip. For the next year try contributing to open source projects that you like and that have companies behind them.
After a while, either they will make you offers to work for them on the spot, or they will at least "fast-track" you through the interview process.
It doesn't work in all software areas (it is pretty difficult to do it if you are an embedded systems developer) but it works especially well in others (e.g. cloud)
Perhaps spend some time on a real-world toy problem, the kind where you spend a lot of time dealing with small practical things like error handling?
I have interviewed a lot of people for coding jobs, and I usually try to test ability at doing things like this, and when I find someone junior who already knows how to approach problems like this, I am always very in favor of hiring them. Based on the discussion here I'm definitely not the only one.
You studied field X to work in field X, and in a job interview the "smarmy git" considering to employ and pay you has the temerity to ask you things about field X to see whether you've understood the basics of field X, can apply them, explain your reasoning, and think on your feet?
And that engenders (and I quote) hate, sadness, anger and despair?
I'm sorry, but this mainly reads like the signal you'll get from running through this script is learning whether or not this candidate enjoys being walked through how clever you are.
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.
Yeah. I'm much more interested in discovering an interview subject's strengths, so I tend to give broad things that can be solved many ways.
One interview I had years ago that I really liked was where they gave a sample of code with a number of issues and asked me to describe how I'd improve it. I really appreciated that a) it was much more like actual work than many questions, b) you could start with obvious things and work deeper, and c) there were many valid ways to improve the code, so you weren't just trying to guess the answer the interviewer had in mind.
Do you have a reason to believe (c) is true in practice?
I strongly suspect many interviewers (myself included) would have a few "top issues" and significantly favour candidates who pointed them out.
But as the candidate you don't really know which issues will seem important to the interviewer.
It's not an irrelevant exercise though - code reviews are a real part of many roles and making sensible choices about what to comment on is a necessary skill.
But it is hard to avoid turning the interview into an exercise in "guess what's on the top of my list"
The first part of (c) is true, so I guess you're asking about how the interviewers would react?
These folks were obviously interested in differing approaches; we had a good conversation about it. And that's how I use broad questions.
But I agree a huge problem of interviews is the "guess what I'm thinking" interviewer. Most interviewing processes are not primarily about making good hires. They're about making interviewers feel smart and important.
I don't think that's fair. The kind of candidates who are good at these questions won't view it as being walked through how clever the interviewer is, but as an opportunity to solve an interesting problem (and show how clever they are).
That is, if your reaction to the problem is "Eww what a 'clever' problem, are you showing off that you know such stuff?" then you are not someone Google is looking for. (Of course, whether Google is right here is a separate question ...)
The author calls out several points where it's usually necessary for the interviewer to explain something to the candidate - or rather, to push them to have the insight you want them to have to progress the interview. Too bad if they have other insights they want to share! The interviewer needs you to buy into his view that the time it takes to generate your hash keys is an important part of your big-O analysis of this problem!
The danger here is that when you explain something to someone, and they get it, you get a warm fuzzy rush of happy brain chemicals. You will feel well-disposed towards candidates who appreciate and enjoy taking the breadcrumbs you feed them. Candidates who didn't think your clever insights were as clever as all that, or who fail to respond to your tutelage and try to solve it their own way... you'll get a negative feeling towards them. They're not playing your game.
That's great if you're interviewing a student to figure out if they will enjoy learning from you, and you will enjoy teaching them!
But while teacher/learner relationships might be part of your relationship with colleagues at work, it seems an odd part of the relationship to compatibility filter in an interview.
Yeah, sorry, I don't think I'm following your argument. When you compute hash keys of a string, of course you want to read the whole string at least once, so the time complexity is at least O(N) (where N is the length of the string) - sure it's easy to overlook, but once explained there's not really much to disagree. It's not like the interviewer is asking a matter of opinion and punishing those who have different viewpoints.
Also, once you used the same problem half a dozen times in interviews, you no longer get any "warm and fuzzy" feelings for having to explain something which is now blindingly obvious to you: if anything, you'll give higher scores to candidates to whom you don't have to explain such things.
Of course, if you are a candidate and (hypothetically) your response is "Actually it can be less than O(N), because a hash function does not have to read the entire string, and I know how it works because I've been dealing with string hash functions for years in my professional career," then by all means, fire away, I'm pretty sure any reasonable interviewer would consider it as a big plus sign.
The length of that word does not grow arbitrarily long, causing the asymptotic behavior of your algorithm to dominate. Because it’s a word.
In the case of ‘is this word of length n the result of concatenation two English words’, the time complexity as n approaches infinity is constant, because once you get past floccinaucinihipilificationantidisestablishmentarianism, any longer word than that you can just return ‘false’ immediately.
Right, for all practical purposes if the reader assumes the words are from the English language, you can assume that comparisons will be constant (both from the pedantic CS perspective since words are bounded in length, and also from a practical perspective since the bound is small, and with SIMD can be done fast enough for most words). See also responses from https://news.ycombinator.com/item?id=35550842 and https://news.ycombinator.com/item?id=35551114 which say the same better than I could.
It feels really disingenuous when interview questions start off posing a seemingly innocent problem where the intuitive and practical answer is usually the one that'd you go for if you wanted to implement this in the real-world, then as soon as you answer the interviewer turns around and throws a hidden assumption at you. You could argue that the point of the interview is to have the candidate suss out these things, but it's usually a one-way discussion where you're not allowed to even question if the assumptions make sense in the real-world (which is what you ultimately care about).
And if the words are truly big enough to be an issue then you better start being rigorous and benchmarking different approaches rather than just handwaving big-o.
Ultimately when you get down to it, the whole point seems to see if the interviewee can be led down the pre-determined golden path, even if the path is only fools gold.
I see, yes I think you do raise a very good point, but on the other hand, the issue could be quickly resolved by talking about it. Any good interviewer would say something like "Ah yes that's a very good point, I forgot to consider the implication of the English vocabulary. However, for the sake of this interview, let's assume the 'vocabulary' is made of strings that can be arbitrarily long. Does that change your answer?"
After all, if we assume that all words are at most, say, 50 characters long, then there's no asymptotic complexity to speak of. Any string longer than 100 characters is trivially not a concatenation of two words.
Absolutely right. I once had an interview where the interviewer asked me for a way of calculating pi, along certain specific lines. When I didn't get it, he 'explained' to me how such an approach could work. I pointed out correctly that his idea was wrong. I was rejected. I'm pretty sure that he never found anyone who came up with this approach just based on the initial vague prompt, and was actually interested in people who nodded in an impressed way when he explained his idea.
What the interviewer is looking for and what Google is looking for are not the same thing.
Google used to look for people who were excited about interesting problems. This is a question about basic complexity analysis and I would have chastised the interviewer if his feedback was ever on one of my interviews.
Questions like these test to see how good you are at remembering your algorithms class. But I thought we’d all learned that the best interview question is one that tests the kind of work that you will actually be doing at your job. This is the equivalent of hiring a journalist by testing how well they remember that class they took on the Critique of Pure Reason. Not entirely useless, but not far from it.
I've done several dozen technical interviews in my career and approximately 89% of them have felt like the interviewer is walking me through how technical they are.
472 comments
[ 3.8 ms ] story [ 256 ms ] threadThe sad reality was that it was waaaay too effective as a fizzbuzz eliminator (> 80%) which I don't know what it tells me about the candidates in general or just about our recruiting :-)
I suspect there are a lot more people who frequently choke on easy coding questions, under the very specific conditions of interview-stress (which is very different from, "the client is unhappy and is also onsite and you'll be in a meeting with them later" stress, and from "production broke" stress, so no, I don't think it's a good proxy for general "grace under fire", as it were, either) than there are actual full-on bullshitters who manage to land software jobs while being truly incapable of doing even the basics of the job.
For one thing, I think such top-tier, extremely-convincing bullshitters would have an easier and less-stressful time applying that skill directly to some other role, since there are some well-paid roles where that kind of thing is exactly what companies want, so it doesn't pass the smell test for me that so very many would be trying to land software jobs—not just ones who exaggerate skill or try to get into the industry while woefully unprepared, but who also are able to fool interviewers at a reasonably-high rate in conversational interviews, yet fail simple coding tests.
That is, I suspect a large majority of "ha! I caught a faker!" anecdotes or anec-data are actually a false-negative on the test from people choking under interview conditions, and that most real fakers would also have been caught in any half-competent conversational interview anyway.
The remainder should be probably be hired regardless, then re-homed to sales when you realize what's going on, since they're evidently top-percentile bullshitters and social chameleons. Joking, of course... kinda. Maybe.
(Top tier Ivy League university acceptance rate is 3-10%, so if you're looking for someone of at least that caliber among the general population (or even among developers), an 80% rejection rate might not be crazy. FAANG (or its ilk) are the "Ivy League" of Software Development jobs)
Over the years, I have seen significant numbers of applicants who couldn't write FizzBuzz, and even one who couldn't sum up the numbers in an array (ignoring overflow). Some of these people had reasonable resumes, and many of them could talk about software development in the abstract.
This was usually a sign of poor phone screening, but it always blew my mind.
Out of curiosity, how do you think you might do in a 1-on-1 coding interview doing something incredibly basic, like:
- Sum an array.
- Write FizzBuzz.
- Count the words in a string.
- Compute the length of a linked list.
Assume you get to use the language of your choice and a familiar text editor. You aren't being graded on semicolons or gotchas. And the interviewer isn't hovering too closely.
Because that's the situation that always mystified me. How many people freeze up under reasonably favorable interview conditions to the point that they can't write even basic code? (And would those people be able to pair on a tricky bug when production is down?)
I absolutely do read a candidate's online code, if they mention it in their resume. That only seems respectful. And I think it might be reasonable to waive in-person coding tests if someone is obviously competent.
(Of course, now that Copilot is getting smarter, it's going to be harder to evaluate people's GitHub repositories or to include trivial problems in pre-interview screens.)
In my 20ish-year career, I've had... oh, ballpark 30 interviews, and I am certain I convinced at least two of those that I had absolutely no idea what I was doing, one on something about as hard as what you list, another on something only barely harder. One was around the middle of that span, another, four or so years ago. The number would be higher, but most of my interviews have not featured coding questions. I have an incredibly high offer rate from interviews that haven't done those (70%? Maybe higher), and near-zero from ones that did.
I can, in fact, code. I've taken complex projects from zero to production, solo, with companies that couldn't have afforded to keep me on for years if I couldn't pull my weight. I've developed a reputation at multiple places as the one to go to with tricky or low-level problems, or the one to hand odd-ball problems with tech no-one's familiar with. I collaborate well, I do the solo thing well, I'm good in a meeting with stakeholders, I can take a support call like a champ. I figure things out, I deliver, I ship. I am not bad at this whole thing. But interview coding? LOL.
> (And would those people be able to pair on a tricky bug when production is down?)
I'm cool enough under pressure that it's been remarked upon throughout my career, over and over. Interviews still get me—specifically, the performing part of coding questions, the rest is no problem.
I think it's because they're kinda hostile (yes, yes, "we're both just deciding if we're right for one another" and "you're interviewing them too", but c'mon, see exactly all the chatter about interviewers trying to find liars and expecting there to be lots of them—you're under a microscope). Production-down is collaborative. Angry-client is collaborative (from your co-workers, anyway). Not just that you're working together, but supporting one another, everyone's got everyone else's back. Most stressful work situations are fundamentally safe in a way that interviews are entirely not. There's nothing to prove, only a problem to solve.
I'm also shit at public speaking—not talking to people, not meetings, but speaking before an audience, and I mean shit—and playing music in front of strangers is basically my nightmare (and yeah, I've done it). I suspect both those are true for most people. The stress of coding in front of someone while they judge me is identical to those situations, for me.
I bet the above is a pretty common.
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).
One is the length of the word. The other is the number of dictionary elements.
If your language is constrained to 1,000 words, then the dictionary will be pretty small and the hash table can be constructed with no chains. That should have constant-time lookup no matter how long the query concatenation is.
I don't see why O(n^2) should be optimal. The question is only to determine if a match exists, and that can be expressed as a regular expression. In the following I omit all 1-letter words since my dictionary includes all the letters.
Python uses backtracking, so this probably isn't O(n), especially with the ability to choose the dictionary.But with there are non-backtracking matchers which would make this O(n). Here's re2 from https://github.com/google/re2 :
This is first time I've used re2. There's probably a way to prevent that warning message - I believe this is falling back to an NFA, which might not be O(n)?Anyway, here it is processing the concatenation of 100,000 words selected at random (I've omitted the warning message):
Cut the size by 10 and it's about 10x faster: For this test it appears to be linear in the query size.Edit: if I increase max_mem to 2_000_000_000 then I don't get the warning message. But then the DFA-based search takes 141.5 seconds. That should be O(n) time in the query length, but an order of magnitude slower than the NFA-based search.
That's why O(n) analysis isn't enough to really figure out "a faster solution."
In the common case, where s is short and the dictionary is big, the size of the dictionary probably matters most to the running time. s is likely a cache line and a handful of instructions to compare — whereas the dictionary probably doesn't fit in L1 or L2, maybe not L3. Obsessing about algorithmic analysis based on the string size instead of the size of the dictionary gives good signal for whether the candidate is a pedant, and poor signal about engineering.
> 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²).
I think the point is in the initial algorithm given there are (n-1) lookups of two substrings whose combined length is n, requiring the hash function to process (n-1)n characters, because the hash algorithm is O(n) in the query string length.
That said, the dictionary words have a finite size. The largest word in my /usr/share/dict/words is 24 characters - formaldehydesulphoxylate. That means for an input of size n only 24n bytes need to be processed to identify if it's composed of two dictionary words. And if it's 49 bytes long, or longer, it's a simple calculation - "not".
Under Big-O analysis, this is O(1) time.
The lazy DFA is technically O(m*n) just like the NFA. The "lazy" part of the "lazy DFA" is why. Because it builds itself during the search. A real DFA would be truly O(n) because it would be fully built before starting a search.
In any case, my point is that we know this problem can be solved in O(n) time.
And yeah sorry, I was only commenting narrowly on RE2 based on my knowledge of its internals.
But then, that means that my candidate string can only be a maximum of twice the length of the longest dictionary word, so the entire process is O(1).
For realistic English words, we're talking about a typical candidate string of length, what, 20 maybe? I need to do somewhere between 19-38 dictionary lookups of 1-19-letter strings to test every splitting of such a word. Why are we even doing big-O analysis here?
Only when you start looking at arbitrarily long strings to see if they are word sequences does this analysis even make sense.
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.
I agree. We do work sample tests, and in addition to the code and docs the candidates hand in, what really matters is the walkthroughs we do with them. Why did they do it that way? What alternatives did they consider? What are the pros and cons? What past projects did they draw on? How did they research this?
Candidates usually enjoy this - most programmers enjoy talking about a just-finished project, especially when they feel good about the result - and you get to learn a lot about them.
If someone turned in an LLM-assisted work and lied about it, I doubt they'd fare well. And if they did use LLM assist - could be an interesting conversation all the same. What did you reject? What did you correct? Why?
If so, how do you solve the problem of the assignment just taking way too much time compared to a more typical process, where you do a phone screen and 3-5 hours of technical interviews with a behavioral or 2 thrown in there? I know that if you send me a take home that's any like most of the ones I've gotten in the past, and your competitor says I can do a recruiter chat and technical phone screen to qualify for a 4-5 hour onsite, I'm going with them just on the sheer amount of time and effort needed from me for each process.
How do you get around the fact that if you give such a test to enough people, some of them will eventually put it up on Github for the world to see and crib from? Even for those willing to accept the time commitment, how do you account for the bias involved in giving the same assignment to working candidates and people just out of school? There's a good bit of implicit age discrimination going on there, since folks who have been working a while are far more likely to have families than those just out of school. And then there's the old "fraudulent candidate hires someone else who's actually good to do the assignment." Granted, that person won't succeed at the job, but it'll take at least some weeks before most companies will give up on someone they hired, even if they're completely hopeless at the actual job.
I could go on and on, but I think you get the idea.
B) you replace time in interviews with the test you don’t just add it on as another thing.
C) you change the test regularly and implement basic plagiarism filters on the tests you do have.
As a person who has been in the industry a fair bit I think the flexibility of take home work samples gives me a leg up over day long in person interviews (and the last time I interviewed it was multi day not 4 or 5 hours).
I don’t have to take time off of work or not pick up my kid from school or anything. Just do it in my free time.
Seriously though, you've basically outlined the only reasonable way to go about it. The problem is really that that's a lot of fucking work you're opting into with 3 little sentences, and after all that, you actually end up with a non-repeatable process, which is not really ideal. I'm still highly skeptical that it's not biased toward people without families, either.
But my real issue here is that at least 75-80% of companies that do this crap obviously don't implement any of that stuff, and most of the rest don't do all 3. You really need all 3 in order to maintain any integrity to the process, and that's, unfortunately, one of the strengths of whiteboard hazing from the employer side. I know I'm never doing another 2+ hour take-home again, and the fact that employers generally don't do any of that stuff are more or less my reasons.
To me it’s a strong signal if a company has a work sample test because it shows they have at least one part of their process that has a chance to be a good filter. It’s an even stronger signal if they’ve replaced the majority of their pipeline with it.
I won’t say I won’t accept a job that didn’t do a work sample component but it would definitely jade my thinking against the firm. And I’ve certainly told companies I wouldn’t continue with their hiring process after hearing what it entails.
That said, I believe an engineer with the answers it gave, would easily figure out from its output what the right complexity is. (Figuring out the trie, may not be so easy.)
That said, meanwhile, ChatGPT is not yet at a point where it can write out a full working repository solving a nontrivial problem. It can help, but it is not autonomous; and realistically, if someone can get that help to reach a good solution for a test, they can do so for a salary.
With O(n) memory, precomputing the rolling hash in O(n) time, you can get a hash of a prefix/suffix (or any substring) in constant time.
https://cp-algorithms.com/string/string-hashing.html#calcula...
Better than the candidates I interview would do, and probably better than I would do, I would probably need a hint to use a trie and I haven't analyzed algorithmic complexity in a quarter of a century.
- While DP might be rare, memoize is quite common alternative. Sticking a @functools.cache in Python for example. They are functionally equivalent in many cases,
- I believe knowing their data-structures and algorithms is the difference between an okay programmer and a good one,
- When interviewing entry-level software-engineers, there's not much else you can ask them except for what they learned in class, which is these kinds of questions.
For me, the difference between and okay programmer and a good one is: how much Linux/Unix they know (processes, core system calls, networking, sockets, awk/sed/bash). Whether you are writing apis for ecommerce platforms or writing custom k8s providers, Linux knowledge is a must. Knowing how to implement a trie? I bet most of us have never been in that situation.
Likewise, there are jobs where being able to reason on complexity and data structures is important.
Your broad strokes don’t account for the domain knowledge of a job. If all you’re doing is interviewing college grads, then I guess you have no choice, but this interview question sucks in just about any other context.
They're not just functionally equivalent. They are the same thing. There are two things you need for a dynamic programming solution:
1. You remember the answer every time your function is called. ("Memoization".)
2. You structure your function calls so that they will ask for a lot of answers that have already been computed.
What you don't want is: say you're computing the sums of contiguous subsections of an array. You've already figured out that indices [2:5] sum to 3 and indices [5:8] sum to 8. When you need the sum of indices [2:8], you need to make sure you get it by asking for sum(2,5)+sum(5,8), and not by asking for sum(2,6)+sum(6,8).
At a high level they are the same, but it makes sense to distinguish between the techniques based on whether you need random access to the already-computed data.
For example, if you are computing the nth fibonacci number f(n), a DP solution needs only the state f(n-1) and f(n), but a typical memoized solution keeps around all the state f(1) through f(n-1). For tougher problems, you can't always convert between them trivially while keeping performance the same.
That's all true, but is it comparing like with like?
The "generic DP" solution to the problem is to allocate an array of n elements and fill it in from f(1) to f(n). That's the same amount of storage the "typical" memoized solution uses; cutting it down to an array of 2 elements plus an (implicit) offset between the part of the array that's in use and the full array seems to be an optimization on top of the DP solution.
You could apply the same optimization to a memoized form of the solution. I certainly agree that you most likely wouldn't do that, but you could.
What do we learn by comparing a tightly optimized DP solution against a "typical" memoized solution? Why do we give the DP solution credit for not using what it "doesn't need" while penalizing the memoized solution for what the programmer probably added unnecessarily?
I worked a SWE job years ago which was heavily reliant on dynamic programming and string search/alignment/etc. It really depends.
IMO, the disdain from LeetCode from developers vs. its continued use disconnect stems from the fact that we developers tend to assume that the goal of the hiring process is to find the very best possible candidate, whereas the goal in reality is to find somebody "good enough" as efficiently as possible.
At the end of the day, you can't test for negatives and just pick a random person that doesn't fail anything. You need to have a defined set of values to look for in a candidate, and to design an interview that tests for those values. That's why I hate DSAs -- for most (all?) companies, they're treated as dogma rather than a pragmatic solution to a difficult problem.
I ask multiple related questions, and if a candidate struggles with one of them, I probe for strengths in other areas.
No one answer to a question in that interview is a pass or fail. But the interview, holistically, is a pass or fail, or a conditional[1] pass.
[1] I was impresssed by some aspects of the candidate, but there are notable, significant weaknesses. Please determine if other interviewers have detected similar weaknesses, or if the candidate just got unlucky with my particular question.
Unfortunately the OP seems to be using it in the former sense (when applied to the tries solution that he things will separate the "good" candidates from the plodding lunkheads).
I suppose that's why mathematicians came up with the idea of "optimal stopping." There are literally tons of scenarios out there where the goal isn't to get "the very best possible candidate," but to get someone "good enough," or maybe even the best person you can get after putting a reasonable amount of time and effort into searching.
https://en.wikipedia.org/wiki/Optimal_stopping
This is also an unproven statement with dubious validity.
I come from the trading world where the leetcode equivalent is a brain teaser. After much deliberation, the only thing we could think of for why a brain teaser was useful was that it often proved someone wanted the job so badly that they memorized all the brain teasers. And that type of dedication and drive is what we really wanted.
To me, I don't understand why someone who develops with advanced IDEs, using complex tools and libraries, is in the least bit judged by putting them in front of what is essentially a text editor, and asking them to solve a problem that's of no relevance to their job, using no tools that they're comfortable with
Period. If someone tells me they can develop software in a language, and they can't write ~10 lines of code, that tells me they lied. It's like when getting lifeguard certified they require you to dive down to the bottom and grab a brick. Nothing at all in the day-to-day job of lifeguard requires retrieving submerged bricks, but the set of people who possess the swimming skills to be a lifeguard is fully included within the set of people who dive to the bottom to grab a brick.
This qualified me to sit next to a pool in a condo complex where no one ever swam for eight hours a day. Best job I ever had.
Your question has no scientific justification. It just is a problem you can do, and you like yourself and think you're awesome. So you think it finds people like you. But even that isn't scientifically supported.
I'll take someone whose Github repo shows talent, dedication and passion, but who misspelled an include header in their brain teaser over the inverse any day of the week. But you do you. Neither you nor I have a lot of evidence to support our preferences either way.
Digging through a couple GitHub repos is a good way to find good developers versus poor ones. The goal of a leetcode question is to separate the developers from the non-developers. And you can do that pretty adequately with 2 questions: "Tell me about something you've worked on" and "Hack together a solution to this trivial question".
The question did not "weed out someone who couldn't code." It weeded out someone who couldn't use a totally unfamilliar dev environment while being stared at and asked to "walk me through your thoughts" instead of letting me think. It left me distracted, thinking both "this is easy, what's the catch" and "wtf is the point of this?"
"Tell me about something you've worked on" is a totally fine question. I'm not arguing with that. But anything leetcode is not, IME. This becomes increasingly true as people's careers develop. If you've spent your last two years writing hyper low latency deserialization engines and packet processing, then you'd know that's what the job is about. In the macro, trading engines and game engines are one medium leetcode problem from an algorithms point of view, but they require teams of people and years of optimization and customization to make truly effective. I don't want to test for the person who can make a really basic solution in 30 minutes. I want to test for the person who can optimize a tiny fraction of it in 2 days.
1) most people here, I believe, don’t have a problem testing a developer’s code writing acumen.
2) People weigh something. Bricks weigh something. It’s the same exercise. The analogy in software would be the difference between asking someone to write _an_ function that can do x vs write _the_ function your company uses to do x.
3) the lions share of counterarguments here propose using real world exercises vs toy problems
Programmers skew anxious. In theory there's no difference between writing basic code on a whiteboard and writing it in an IDE. But in practice, an interview is a novel, high-stakes environment with a bunch of judgy strangers. So if you then have people do the interview using tools that are unfamiliar, a notable percentage of them will be thrown off.
Once I switched to encouraging people to bring their own tools (own laptop, own editor, preferred language), I saw a marked decrease in people bombing interviews. Some of the people you might have put in the "they lied" bucket were, at least for me, just ones who got really nervous and so were unable to grab the brick.
To me, that's a bad interview, because the job isn't going to be high-stakes whiteboard coding. It's going to be sitting quietly in a comfortable and safe place and gradually improving things. The more an interview can be like that, the better.
I've always assumed the brick was meant to simulate a drowning swimmer, whose rescue is pretty clearly part of the lifeguard's job. I guess a mannequin would be more realistic, but it still seems pretty close.
Sadly everyone who makes it to an on-site is now a competitive programming enthusiast who is probably a really poor fit to actually working in software development.
Many people are vaguely aware of this problem, but nobody has a strong incentive to put in the work to come up with anything better.
And most programming jobs involve no complex algorithms at all. At most you have to be a little careful to avoid N^2 occasionally.
Leetcode is great for filtering out bad candidates but if your solution involves dynamic programming it is too hard for an interview.
OTOH re the concern for O(n^2) time when n is bounded by word lengths, and when the inner loop was in already-optimized string comparisons in your language's hashtable library -- I think that part is very artificial.
Yes! The candidate already optimized for the important thing (which the author forgot about and added in a footnote), which is that the list of words could be very long, and that the words in an English dictionary are relatively short.
Optimising for the important factors based on an assessment of the problem domain is actually a more important skill than regurgitating the best algorithm from the book. If the author wanted to suggest a solution suitable for very long needles, he should have used a different domain like, say, gene sequencing.
Give me any problem related to algorithms+ds to be solved in 45mins without internet access and someone looking over my shoulder and I will give you a poor solution. But give me a day and internet connection and I will solve the problem in the most efficient/readable/maintainable way possible.
The interview question is not just about knowing data structures and is not about Behdad showing off either. It's the starting point for a Socratic discussion.
OK, but every program is literally one line of code. We only put line breaks in to make them easier to read.
The author makes this terrible comment about his "one-liner":
> Most candidates though write a for loop, which is equally acceptable.
He has also written a for loop. Specifically, he's written this for loop:
What is important is that the candidate’s skills generalize well to both the challenge in the interview as well as the day job. A question like this might be a good indicator or not depending on the job.
If people completely fail at this question it can reveal a lot of relevant information.
I've given this same advice for _years_ for designing technical interviews. Take a problem that you or your team has actually faced in the last n months. Distill it down to remove tribal knowledge and get it to something you or a capable colleague can hammer out in m minutes. Give the candidate 3m minutes to solve it. Typically this means it should take you 15 minutes to solve and give them 45 minutes.
Our biggest hit for a question that followed this for an SRE type role: we had a cron job that was legacy and buggy and caused a couple of issues over 6 months. We went back and created a very similar script with very similar bugs, added some similar data and re-seeding scripts, and told the candidates "customers say that feature $x is not working, and that is ran by this script. Here is how to run it, here is the user's id that can be found in the data seed." We added some other data validation problems. After they fixed it, we asked them what they would do to make this more production safe and dig in on what they have and have not done for improving existing systems. We expected discussions on structured logging, metrics, alerting, testing, code layout, etc.
Over time, the roles that you are looking to fill and the weaknesses on the existing team that you want to shore up will change and you will need different interview questions. Maybe more towards distributed systems or more towards testing or observability.
I think they're using "m" there as a variable, to frame that you should give the candidate 3 times however long it takes for an insider to solve it.
They mean 3 x m where m is how much time you think it would take for you to solve; so the example is: if it takes you 15mins, then give the interviewee 3 x 15 = 45mins
Importantly, it also allows you to examine fluency. The candidate who can write a code/pseudocode solution as fast as they can type, and explain it verbally at the same time, is much more impressive than the candidate who pauses for a long time before starting haltingly and unconfidently. Fluency in solving leetcode problems just tests for having practiced leetcode, but fluency in writing real code tests for actual productivity.
If you have a question like this, you can drill down into performance characteristics just as the question in TFA does. Not necessarily using big-Oh notation, but "what if you have to do this millions of times? what if you have to provide results immediately? what if some of the files are too big to fit into RAM?". But you can also drill down into other aspects of the problem like changing specs, noisy input, constrained resources, observability.
FWIW, when I came up with a question like this (with the constraint that it had to represent a problem I had solved that morning), ChatGPT was not able to solve it correctly.
No wonder it is a hit. It is an actual problem that makes me want to go for it - I want to take an interview like this, instead of the usual of dreading interviews! Keep it up.
And in my experience listening to auditions over the last several decades, what you have now is a bunch of musicians who can only do what's on the test. When you try to plug them into an orchestra, they are completely fucked.
My experience interviewing and hiring tech people is that this is one of the worst possible approaches. Anyone who needed to could figure this out. It's not relevant. What you need to figure out in an interview is if the person is curious enough to find the answer.
I don't ask for code or algos in my interviews. I ask about the person. What's your favorite programming language? Why is it your favorite? What do you not like about it?
What's the project you are most proud of? What was hard about it? What made you happy? What did you find challenging about that project?
These are 100% totally humane questions that tell you everything you could possibly need to know about a candidate in about a half hour. Maybe less.
If you can't figure out if this person is technically competent from this set of questions then you aren't competent to interview or hire.
Interviews don't have to be only about how good you are at interviews. They could be about trying to understand if the person would be good at the job and fit in well with the team.
Episodic recall and emotional recognition are both talents that vary across the population. If I want to do well at an interview like this, I will have to spend a bunch of time in advance refreshing my memory of various projects I have worked on so that I can simulate a neurotypical response to those questions. If I don't, I may just stare at you nervously and break out in a sweat when I realize I don't have anything filed under, "project I am most proud of". Or that pulling up the narratively engaging details of a project I haven't thought about in years is a process that will take me hours of specific effort. And it's not just me; I've hired great developers who were also terrible at "humane" interview questions but who did great when we just sat down and coded together.
I usually have a project or two that I can speak-to in depth, to give examples of decisions made, challenges handled.
In the end all you could actually do is guesstimating who would do best at the job. And sometimes the answer is: "none of the ones who showed up".
If you are a good engineer or programmer yourself you can tell a lot about a person by talking to them for an hour. You can learn what is important to them in the craft, how they deal with criticism, what they aspire to, what kind of problems they tend to work on, if they are more autodidactic or more influenced by other's opinions and so on. This is all knowledge directly inpacting the question whether they are the right person for the job.
And who the right person is depends on the job, so there might not be "right" answers to the questions. For a very niche database job you might actually want someone who is very accurate, very in the detail and very focused. For other jobs maybe some entirely different traits are better.
Of course the problem here is that the people you hire could just be very good actors or liars who cannot do the things they say, so a little technical testing might also be needed.
While yes, you can get someone who has a good track record of being a good judge of character to make hiring decisions. If that decision goes wrong and the blame game starts then you inevitably ask this person to explain their hiring decision. This person will then reply: well it was my opinion that X, Y and Z.
In the alternative case where you just get someone to follow a rigid process you can answer: Well he scored well on this exercise and the opinion of the team was in his favour and the work history ticked the right boxes. This effectively dilutes the responsibility. You can no longer blame one person for the bad hire.
Lastly there's also the diversity aspect. With companies increasingly being scrutinized for their hiring practices, "it was my opinion" just gets translated to "this person's internal biases guided the hiring process and as such it was not fair."
I agree this is all making hiring much harder than it needs to be. And certainly you can still find companies where the hiring decisions are made on highly experienced and well honed gut instinct (its the only kind of interview I have been a part of) but it also makes sense how in our increasingly overcomplicated world we are developing increasingly overcomplicated hiring processes.
My recommendation is if you want a sensible hiring process (with maybe a telephone screen followed up by one normal interview) you should stick to smaller and less corporate companies.
I know plenty of smaller, less corporate companies that still use careful hiring processes with thoughtful rubrics. They do that not because of risk avoidance; they are generally still ok firing people who don't work out. They do it because they want to run a fair process while maximizing ROI.
And lots of good developers skew anxious! What in normal life counts as being overly careful or or overly sensitive is just good practice in coding.
That's why I think it's especially important to make interviews as low-anxiety as possible. They'll always be worse than the job, of course, but the closer you get them, the more you're likely to see how people will really perform on the job.
Both of mine did. Much of their advice was irrelevant (nobody in tech gives a shit about your suit or how firm your handshake is) but they both stressed the importance of preparing in advance to show how good your skills are; and giving thought to cliche lines of discussion like 'what's your biggest weakness?'
Not only do I not remember past successes very well, preparing for these questions is literally the first time I asked myself what I'm proud of. I didn't even consider doing this and reject it as irrelevant before. It just never came up.
I've always had trouble with the kind of behavioral interviews that are "Tell me about a time when . . ." since I can often recognize that I've been in relevant situations but can't for the life of me remember the details (even with time to prepare).
This honestly makes me more nervous about interviews than leetcode shenanigans. At least with those, I know how to improve.
(At work I rely on a combination of having the code in front of me, written notes, and whatever project management tools we have so it's not much of an issue, but most of that isn't available to me in an interview setting.)
Source: Multiple orchestra musicians and management speaking about the audition process and the now-defunct myauditions.com website
Process:
Show early talent
Get the right instruction
Get into a preparatory program
Make it into a conservatory
Do well once there
Get a spot in an ensemble, probably lesser-known (not easy) and establish a reputation
See an audition notice with repertoire to prepare, apply
Spend a few weeks or months intensively practicing (on top of other commitments)
Maybe get an audition, realizing the Music Director may be promoting his buddy past these rounds
Travel at your own expense to the audition
Play demanding repertoire behind a screen and respond to any directions
Most likely get rejected
Play in any following rounds
If not rejected, maybe you get a qualifying week rehearsing with your potential colleagues and playing a couple of concerts when the Music Director is in town
If you beat out the couple of stellar artists who've also gotten that far, you may get an offer
Or, the MD's buddy may get the offer
Or, there may be a no-hire
If you get and accept the offer, you are "on approval" for a couple of years at which point there's the Tenure Decision
I would still require the candidate however to write some code. Something rather simple, not leetcode, ok, not fizzbuzz either, and something that proves their familiarity with at least one language and platform.
I should be a GM by now simply watching chess analysis videos on Youtube, learning the names of some openings etc. I can talk about it all day long. But since I don't play at all (I'm not interested) when I actually do play on occasions I revert to 500 ELO...
You can easily tell a seasoned veteran from a rookie just by looking at them code for a few minutes, working on a simple task. If you can't, you have no business in interviewing others :)
Someone who can explain why they love Rust and hate Python (or vice versa) is a convincing candidate but I think you need to see a couple of other things from them. In addition, sometimes you just don't hit on the right question to get evidence of their aesthetic judgement. (Like the candidate who doesn't care about Rust vs Python, but who hates Postgres and loves MariaDB..)
Not precisely a SWE, but every single piece of code I write at work is more about knowing how the immense codebases are laid out and where to insert my change which is typically simple.
Given this, any "write self contained thing" is unrealistic. The only thing a coding question tells me is whether someone is happy writing simple code to solve a vaguely fun problem.
That still feels useful?
It was great because he was testing the very thing I was going to be hired for. Additionally, he asked how I would design X or Y and I explained the pros and cons of certain designs and I could show him right there on the screen how I'd do it. This wasn't a whiteboard where I'd have to slowly write out code in a medium I'm not used to. I literally was typing on a keyboard, using intellisense, etc.
As someone who does iOS development day to day, it was a very easy way for me to show that I knew what I was doing and the guy was quite pleased when I plowed through all the requests he had.
> 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.)
These are hard to do if you think of an interview question like a high school quiz or a college final.
As an example, the author of TFA clearly is selecting for people who have the patience to sit around and be told how smart the author is. That is the signal in this “great interview question”: candidate will suck it up for hours while I tell them stuff.
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) ...
Any better than that you can do would be O(min(n, k)) where k is the length of the longest word in the dictionary. But without loss of generality that would be O(n).
Therefore, either the question is nonsensical, or there must exist a word (or words) of a maximum length.
You take the first n bytes of your input string. You hash them. You look them up in the dictionary. The lookup is O(1) but hashing your input is O(n).
But there's a simple way around this.
We have incremental hash functions. When you add a byte to the string and you use an incremental hash, you do a fixed amount of extra work to update the hash. Like that you only need to O(1) extra work to compute the new hash.
One trivial incremental hash is to break your input into fixed size chunks, hash each chunk, and xor the chunks together.
A trie is a pretty nasty datastructure memory wise. It involves chasing pointers all over the place. The constants on a trie are not going to be very good.
For an incremental hash, you hash your string, and then you fix your hash up as you go. Then you look up your hash in a hash table. Code-wise it's far simpler to implement. And performance wise it will be far faster!
The two solutions have nothing to do with one another. Except that they're both O(n).
Hash collisions don't matter unless they're pathological. Just choose an out of the box hash that works well.
The article is just wrong.
If you're writing a smug blog post about your "great" interview question, you should at least not make such "obvious" mistakes, especially considering rolling hashes are a "common" interview question trick for string problems. And in practice this hash'd solution probably might end up performing better than the Trie (of course needs benchmarking, etc., but it's not unreasonable to think it might). In an alternate universe you could easily imagine author himself getting failed for overlooking such an "obvious" solution.
The maximum number of iterations is length of the largest word in the dictionary.
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?
This is a negative hiring signal you're looking for, right?
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!
Though I imagine they could just ask "when was your last algorithms course?" (and possibly where, and what grade you got) and save a lot of time. Or they could just ask "what year did you graduate from (whatever school level)?"
But that wouldn't be as useful for making the candidate "jump through more hoops" and reinforcing compliance as well as status hierarchy - important things at most companies.
And some people may have cheated their way through their algorithms class, so maybe they can be detected if it was recent enough.
I would stop in an instant if someone could come up with a better option.
abbbbbcdddddde => aB5cD6e
The number of developers who struggled or utterly failed with this was depressing.
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.
Big in space but O(1) (wrt word len at least)
The only way to evaluate if this is a good or bad solution is the actual operational context.
If you had a service that had to do millions of these matches per second with low latency, then this might be a reasonable solution.
>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".
What I’ve seen happen is that there are two narratives they flip on: I hired this great person and they are doing amazing so I am amazing; I hired this person and they aren’t doing great so I fired them so I am amazing.
Of course, they also tend to be terrible at assessing who is actually good/bad.
I call it the “arbitrary onion”: layer after layer of plausible claims that each turn out to be just as arbitrary as the outer claim.
That being said, I think you could get around this with careful prompting (ie, ask first "what is the Big-O for dictionary lookup with the respect to the number of letters" before asking the overall big O). But I think there is a bit too much wiggle room to make this a completely consistent question, too much variance candidate to candidate.
I like the problem a lot, but wouldn't feel comfortable using it.
But.
Hashmap lookups require calculation of a hash of the key. Calculating the hash of a key requires examining all of the bits in the key. If the keys are int32s, then the hash algorithm has to read 32 bits. If they're int64s, then the hash algorithm has to read 64 bits.
And if your hash map contains n distinct values, then at a minimum they must be drawn from a key space where each key contains O(log n) bits. If you want a hash map to contain more than a few billion values, you'll need bigger-than int32-sized keys to distinguish them, right?
So for any hashmap of size n, that means there's an O(log n) hash calculation in there. (especially when we are considering the asymptotic case where the hash map grows infinitely large... such hash maps will necessarily have infinitely long keys, too)
Yet we call hash map lookups O(1).
Because in practice we imagine a hash map has a key space of a fixed size (even though such a constraint would mean that the hash map has a fixed maximum size and therefore no asymptotic performance case since it can't scale to infinity).
By playing around with big-O on hash table lookups with keys of size n, the interviewer is skating dangerously close to this contradiction at the heart of big-O analysis of hashmaps...
But unnecessarily so, since the key space they're using is dictionary words, which have a maximum length, so their length isn't the n you're looking for.
(Note - for the same reason, big-O analyses of sorting algorithms don't usually take an extra O(log n) factor (in n being the size of the valuespace) for the time it takes to compare entries, even though obviously it takes 'longer' to compare two 64bit numbers for size than two 32bit numbers. Is it a hand wave? Probably not when you're dealing with numbers. Maybe when you're dealing with strings)
This is a great point. If you're sorting an array of strings, you would never add an extra m in that complexity analysis for the size of the longest string, in bits (not length, because unicode)
The OP seems wrong to make candidates do this
(Not actually purely an academic concern - this physical constraint is what drives the difference in performance between using data in L1cache, RAM, disk, or on remote networked nodes.)
So yeah, O(1) hashmap reads are a convenient lie we tell ourselves, which are really only true for ‘small hashmaps’.
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.
It's a whole other debate that most software engineers, even at BigCo end up writing CSS code to move pixels only and lose their DSA knowledge over time...
They probably did know how to code, but they’ve spent the last 5 years working on something quite a bit different from string wrangling in Python. Add in the stress of a (first-time?) interview and a reasonable candidate can look like a total fool…
It's a bad question because _how well_ a candidate does past that minimum threshold has _no correlation_ with their ability to do the job.
You can treat it as a binary question for that minimum floor. To use it for rating, you're doing your org and the candidate a disservice and you're wasting interviewing time that could be spent more productively and humanely.
Is this common at Google?
If by DSA knowledge you mean leetcode puzzle knowledge, yes, quite certainly. But from my experience fresh grads are less effective engineers before they mature by working with industry scale systems for a few years. And at that point they would have been less able to do your problem but a far better engineer.
Which means your interview question is aimed backwards, maybe if you only used it against fresh college grads then the gain function would be positive, but you applied it against everyone.
Annnnnnnnd I’m out.
sure, some will trip over themselves.
20m was the best?
poor screener?
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.
You could get lucky and have each question have a similar relationship to past knowledge. It's happened to me before, I blew through an Amazon interview once that way, but got knocked for technical leadership. So maybe you mean something like that, but that too is random. I had passed the leadership but failed the algorithms at Amazon a few years prior.
> 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.
I believe these tests are more about compliance and baseline cognitive ability than anything else, which is good for the nature of the FAANG role. They are testing that you are willing to study what they tell you and that you are able to retain material of that level of difficultly and demonstrate that in an adversarial situation.
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 :)
The trick for me was diligently applying to as many places as possible (that were at least somewhat of a fit), and eventually coming across one where the main technical part of it was "take home". Coding and discussing thought processes on the spot for an audience isn't something I'm good at it turns out, but solving a practical problem on my own time was fine.
It's ultimately a numbers game, the more places you apply to, the more likely you'll find an interview process that fits. That is the most important thing to keep in mind--shotgun blast those applications. It's hard not to take rejection personally, but don't give up and settle for a toxic job, that's even worse.
As I age, one thing that I realise about interviewing: It is scary as hell. It is basically performance art. And, most nerds are terrible about public performance & speaking. Some days you are really on it; other days: way off. Every single job that I ever got in my life feels like a lucky day. Also, the tech universe is infinitely wide at this point, so somebody somewhere can ask a question that you will fail.
Since this industry is so dominated by men, it also feels like a lot of machismo. So many interviews are just a jerk dude on the other side of the table (probably working for an amazing company) that wants to make himself feel better by making me look foolish. There are too many stories to tell. I have also kept my mouth shut when interviewers were insistent about a technical point that was 100% verifiably incorrect with a simple Google search. It helps to stroke their ego during an interview. When they give you a hint, or explain a better solution, try: "Oh, that's really impressive! How did you discover that algorithm?" You are more likely to make it to the next round. The goal of interviewing is to get the offer. You can always turn it down. If you had one jerk in the interview stream, but they work on a different team, it should be OK to accept the offer.
Another thing that I say to all interviewees now: I know that interviewing is scary. We are interested in what you do know, not what you do not know. Together, we will dive as deep as possible on a few topics to find the outer limit of what you know. If we come to a topic that you don't know about (or not deeply), tell us; we will move to a new topic.
I think I read on here about the concept of successful people really just doing more things to increase their luck surface area.
In other words, you set yourself up to interview as best as you can, then make a bunch of connections and schedule a bunch of interviews, and (hopefully) at least one of those will be on a good day.
It's such a weird and, frankly, shitty way to make hiring decisions though. But at the same time, we don't have much better.
After a while, either they will make you offers to work for them on the spot, or they will at least "fast-track" you through the interview process.
It doesn't work in all software areas (it is pretty difficult to do it if you are an embedded systems developer) but it works especially well in others (e.g. cloud)
and you suggest providing free labour for an entire year to some companies. No wonder GP hates this industry.
>For the next year try contributing to open source projects that you like and that have companies behind them.
I have interviewed a lot of people for coding jobs, and I usually try to test ability at doing things like this, and when I find someone junior who already knows how to approach problems like this, I am always very in favor of hiring them. Based on the discussion here I'm definitely not the only one.
You studied field X to work in field X, and in a job interview the "smarmy git" considering to employ and pay you has the temerity to ask you things about field X to see whether you've understood the basics of field X, can apply them, explain your reasoning, and think on your feet?
And that engenders (and I quote) hate, sadness, anger and despair?
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.
One interview I had years ago that I really liked was where they gave a sample of code with a number of issues and asked me to describe how I'd improve it. I really appreciated that a) it was much more like actual work than many questions, b) you could start with obvious things and work deeper, and c) there were many valid ways to improve the code, so you weren't just trying to guess the answer the interviewer had in mind.
I strongly suspect many interviewers (myself included) would have a few "top issues" and significantly favour candidates who pointed them out. But as the candidate you don't really know which issues will seem important to the interviewer.
It's not an irrelevant exercise though - code reviews are a real part of many roles and making sensible choices about what to comment on is a necessary skill. But it is hard to avoid turning the interview into an exercise in "guess what's on the top of my list"
These folks were obviously interested in differing approaches; we had a good conversation about it. And that's how I use broad questions.
But I agree a huge problem of interviews is the "guess what I'm thinking" interviewer. Most interviewing processes are not primarily about making good hires. They're about making interviewers feel smart and important.
That is, if your reaction to the problem is "Eww what a 'clever' problem, are you showing off that you know such stuff?" then you are not someone Google is looking for. (Of course, whether Google is right here is a separate question ...)
The danger here is that when you explain something to someone, and they get it, you get a warm fuzzy rush of happy brain chemicals. You will feel well-disposed towards candidates who appreciate and enjoy taking the breadcrumbs you feed them. Candidates who didn't think your clever insights were as clever as all that, or who fail to respond to your tutelage and try to solve it their own way... you'll get a negative feeling towards them. They're not playing your game.
That's great if you're interviewing a student to figure out if they will enjoy learning from you, and you will enjoy teaching them!
But while teacher/learner relationships might be part of your relationship with colleagues at work, it seems an odd part of the relationship to compatibility filter in an interview.
Also, once you used the same problem half a dozen times in interviews, you no longer get any "warm and fuzzy" feelings for having to explain something which is now blindingly obvious to you: if anything, you'll give higher scores to candidates to whom you don't have to explain such things.
Of course, if you are a candidate and (hypothetically) your response is "Actually it can be less than O(N), because a hash function does not have to read the entire string, and I know how it works because I've been dealing with string hash functions for years in my professional career," then by all means, fire away, I'm pretty sure any reasonable interviewer would consider it as a big plus sign.
The length of that word does not grow arbitrarily long, causing the asymptotic behavior of your algorithm to dominate. Because it’s a word.
In the case of ‘is this word of length n the result of concatenation two English words’, the time complexity as n approaches infinity is constant, because once you get past floccinaucinihipilificationantidisestablishmentarianism, any longer word than that you can just return ‘false’ immediately.
It feels really disingenuous when interview questions start off posing a seemingly innocent problem where the intuitive and practical answer is usually the one that'd you go for if you wanted to implement this in the real-world, then as soon as you answer the interviewer turns around and throws a hidden assumption at you. You could argue that the point of the interview is to have the candidate suss out these things, but it's usually a one-way discussion where you're not allowed to even question if the assumptions make sense in the real-world (which is what you ultimately care about).
And if the words are truly big enough to be an issue then you better start being rigorous and benchmarking different approaches rather than just handwaving big-o.
Ultimately when you get down to it, the whole point seems to see if the interviewee can be led down the pre-determined golden path, even if the path is only fools gold.
After all, if we assume that all words are at most, say, 50 characters long, then there's no asymptotic complexity to speak of. Any string longer than 100 characters is trivially not a concatenation of two words.
Google used to look for people who were excited about interesting problems. This is a question about basic complexity analysis and I would have chastised the interviewer if his feedback was ever on one of my interviews.