This is not a great interview question. It’s not even a good interview question. It barely evaluates any technical abilities and it ignores most technical abilities that matter.
This question could be improved as follows:
* present the naive solution. Explain that this is a PR that was submitted in 20 minutes by our new intern from Waterloo. Ask them to help improve it.
* suggest to them the intern’s argument why the lookup is O(1) and explain that it’s actually O(n). Ask them to write a PR comment to break the news to the intern.
* explain the optimal solution with tries. Ask what happens if the vocabulary is big enough—and the prod environment is resource constrained—so that the trie is rarely in memory when the function is called. How would the trie solution compare to a binary search through a length normalized list of words?
This kind of question is barely useful to interview new hires—when you still may have basic questions about how much undergrad material “stuck”. Within a few years when they hit full-performance level you should care much less about this kind of question and much more about “higher order” thinking about engineering.
How do you communicate bad news? How do you identify, communicate, and mitigate risk? How do you plan large tasks at at appropriate level without over engineering the solution? What questions should you ask at different project stages to capture the right requirements, anticipate issues, and successfully execute over time?
But whatever, I’m sure you get lots of signal out of repeating “a hash table lookup is O(1)” “nuh uh” on loop for 10 years. :eyeroll:
For the past decade Google has seemed like a deer in headlights, unable to move in any direction, failing at introducing new products, now getting crushed on AI.
Maybe the problem has something to do with the way they hire. The article mentions that this string-processing problem had to be approved by a committee:
”Twice I asked the hiring committee if I should stop using this and they had no problem with it.”
Not even the Soviet Union had a process where job interview questions were regularly approved by a committee. The level of bureaucracy in administering these brain puzzles at mass scale is absurd.
The article mentions that the candidate who did best on this question was “the type who did high-school competitions.” I wonder if anyone stopped at any point to question whether that’s the ideal type of hire.
> The article mentions that the candidate who did best on this question was “the type who did high-school competitions.” I wonder if anyone stopped at any point to question whether that’s the ideal type of hire.
I think this is the most telling bit. Time after time, I've seen excellent competitive programmers end up being mediocre engineers. Almost none of them are bad and it's also a very objective (at least on paper) process which is probably why Google is happy to stick with the process but most of them also aren't amazing innovators.
I'm sure that university student who aced the interview turned out to be very smart - they went to a great university and can solve challenging puzzles. But I don't think they'll end up being the engineer that builds Google's competition to ChatGPT. I wonder whether a course correction where Google starts looking for people who create really cool projects even at the risk of not being able to solve any coding challenges would actually help.
This problem is not great. It is a classic of the programming puzzle kind, and does not measure metrics which are important for most engineering. For some roles, like working deep in the weeds of a compiler or database optimizer, I think it's not that bad. That kind of programming has a puzzle feel: searches for near optimality in combinatorial (or worse) solution spaces. But it's not very applicable to most engineering.
On the point of committees, though. Hiring committees make a hire/no-hire decision. They don't approve questions, but they do make decisions based on the results of asking a question. So they rely on the signal that the question generates, and if a question is not giving good signal, they will have an opinion.
There's a different reason for wanting to standardize on interview questions. It's very easy to embed cultural bias. If the topic of a programming problem uses the rules of a game, for example, that will probably mean that people who are familiar with the game will understand the gist of the problem much faster than people who've never played the game.
I suck at those questions, and I hated those competitions. Yet I was the only one who would create things (hard- and software) in their spare time. I think some of these questions are insulting. Do you wanna get someone who solves actual realworld issues and interacts with real world challenges or what?
That being said I am easily the best/fastest programmer in my organization despite there being people who have 20 years more experience.
> Not even the Soviet Union had a process where job interview questions were regularly approved by a committee.
Not defending Google's practices here, but this claim is nonsense. Many public sector/third sector jobs in Western society will only use interview questions which have been pre-approved by explicit policy.
The article does not state that "interview questions were regularly approved by a committee". It says that this question was banned because it was leaked to the public. And that he, very reasonably, asked the hiring committee if he could use it anyway.
No, its not the interviews. Its the proliferation of the idea that Google (and co) as the "final boss" interviews/companies and once you get in its just resting and vesting. Back in the day these companies were spots for hackers and innovators, now they are mostly just the final destination for clout or TC chasers. That is what stifles innovation, not a few innocious coding questions. IMO any interview type would be gameable. Also at Googles scale this is the most realistic pipeline to hire people, and having it go through a committee ensures that candidates are deterministically and fairly assessed.
Also I recommend you try these "high school problems" you seem to be talking down on. I for one greatly respect people who can solve those types of problems, regardless of their age. These are not trivial problems, mind you. They require a lot of mathematical and logical intuition that 99% of people (and I'd wager the majority of SWEs) don't have.
HC is just a team of very senior engineers who make a final determination based on interview feedback. It has existed since pretty early and was a good way to massively scale the hiring pipeline without compromising on quality which ime is not true for many other big shops which did not have this
> suggest to them the intern’s argument why the lookup is O(1) and explain that it’s actually O(n).
I think any discussion of complexity for this problem is misguided.
I mean, it's fine to talk about a hash lookup being o(n) for pseudocode in some hypothetical context. But if you're talking about actual code that you intend to run in Python or JS or whatever, it doesn't make sense - are the strings interned or not? When your language hashes the key of a dictionary lookup, does it cache the result? If you're using a JITTed language, won't any native o(n) hash lookups vanish in comparison to your non-native o(n) for-loop?
On top of all of which - why are we even talking about o(n) complexity for an n that cannot grow? If we're given a fixed dictionary then we can ignore any substring longer than its largest element, so the "n" for hash lookups is not the size of the original input - which is the n we realistically care about!
Basically, once TFA mentions complexity I feel like the only correct answer is to say "this isn't a situation where complexity analysis would be useful - we should benchmark the code".
Your comment is exactly the kind of thing I’d like to see a candidate simulate explaining to an enthusiastic, overachieving intern. Is the candidate helpful? Are they toxic? “Explain the the intern” implies a hierarchy imbalance—does that make them rude or patronizing?
All of these are useful signals for a hiring decision. Much more than quibbling about big-O of hash table lookups.
> How do you communicate bad news? How do you identify, communicate, and mitigate risk? How do you plan large tasks at at appropriate level without over engineering the solution?
Like these can’t be prepared for? I think there are now whole chapters in those interview prep books/courses on how to answer these.
Even if there weren’t this is a good way to hire people who sound very professional on slack and in meetings but don’t produce any actual code (unless you got very lucky)
I’m suggesting that it’s better to test these in your coding interview. What’s not worth testing is factual knowledge that you can look up.
You would be absolutely stunned how many people cannot give you back the correct answer even after you literally give it to them. If you don‘t know some programming and I give you code and explain what it does, that still doesn’t help you.
There’s some tiny signal of your ability by asking you to memorize and regurgitate something; and maybe a tiny bit more signal in this question by implicitly testing “how do you respond to unexpected technical details in a high stress situation”. But they aren’t worth the trouble. You could measure both much more directly. You’d get more detail about their coding ability by directly asking about code they’ve written and know well.
My life experience has been that it's much easier to spot someone has a prepared answer to a soft question than a technical one. I immediately feel like I'm not having a conversation with them. That's why even in technical interviews, I try to stick to broad, conceptual questions that serve as a conversation starter.
Agree, this is a bad question that gives absolutely no indication on whether the candidate will perform well in the role as a software engineer.
> 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.
> lookup is O(1) and explain that it’s actually O(n)
I don't get why the dictionary solution is actually O(n).
Surely you can have the hash function be O(1) by only looking at a subsets of characters something like
hash(s) = (s[0 %s.length ] ^ (s[6 %s.length]<<c1) ^ (s[7 %s.length]<<c2) ) % (size of the hash table)
You can trade-off memory for speed to avoid collisions by having a mostly empty big table (like 9/10 empty table). And you can also use multiple hash functions that must both simultaneously collide to avoid having too big a table (kinda like fronting your hash-table with bloom filters).
And you can pick the selected sub-index at random such that they split well your dictionary. Maybe you can even build a "Perfect hash function" so that all your dictionary words have distinct keys.
You only have to check for the whole string when the hash match, probability of which you can make as small as you want.
> > About Part 2 :“Write a function that given a string, determines if it’s a concatenation of a number of dictionary words.”
Isn't it just recognize if a string belongs to a regular language, where the language is defined by words in a dictionary ?
So you just build a parser for your language and you test for belonging.
I'm quite rusty in non-deterministic finite automatons and regular languages, but surely there exists algorithm that build an automaton from the dictionary to recognize the language in something better than n^2, no? (We are moving the states of the automaton once per character, and we likely won't have n active states (except maybe for pathological dictionaries), complexity should be something like O(k*n) where k is a constant depends on the dictionary).
The hash table is O(1) even without your modification. Because there is a fixed dictionary, the length of the longest possible word is known in advance. That provides a constant bounds that does not grow. Let's say the longest word is 25 letters. Your hash computation is O(25) which is equivalent to O(1).
What this means in practice is that there is no polynomial curve for very long words. You don't bother hashing them, so the curve peaks and then flattens.
Obviously a trie is an interesting and possibly faster solution, though the hash has the benefit of being more cache friendly. But the big O analysis presented for this problem is flawed.
"Surely you can have the hash function be O(1) by only looking at a subsets of characters something like"
I seem to remember that in the very early days of Java the standard hashing method for strings only looked at a small prefix - turns out that very common use case was to be storing URLs as keys which, of course, mostly start with the same letters...
I got stuck in that too, but I think it’s right. No matter how smart you do the hashing, in the end you need to do an equality check, and that has to be O(n).
Eg you can’t just do equality on collision, you need to do equality on every lookup at least once.
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.
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.
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.
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 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..)
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 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.
"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
> ...[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.
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 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).
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.
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 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.
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.
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.
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.
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
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.
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.
> 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.
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.
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.
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'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.
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 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.
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.
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"
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.
While the interview question is a fun exercise, the complexity analysis presented is wrong.
For part 1 using a hashtable to look up the dictionary words, the complexity is not O(n^2) where n is the length of the input string. It should be O(w^2) where w is the length of the longest word in the dictionary.
The hash key material of the dictionary words has at most w characters. When computing the hash key for the input string, it can be truncated at w, as any longer input won't lead to a hash key making a match in the hashtable.
For part 1 using a trie, the complexity is O(w) rather than O(n). This is actually more obvious since walking down a trie tree will stop at the last character of a dictionary word.
Again for part2, the complexity is O(w 2^n) using bruteforce with hashtable, O(w^2 n) using DP with hashtable, and O(w n) using DP with trie.
Edit: Also for short strings like dictionary words, O(w) is kind of meanless since with SIMD or SWAR the short word can be folded into one or two DWORD. You can effectively treat it as O(1).
You are absolutely right. I should have been more clear about the dictionary size being large compared to n, and similar about the length of the longest word in it for all my analysis to follow.
Also, while trie looks better on paper than hashtable in regarding to complexity analysis, in reality hashtable can be 2X~3X faster than trie. This is because the hash key can be computed very fast with the key data fitted in a L1 cache line and with much less branching jumps in the hashing function, while trie does a separate memory load on each node going down the tree plus each character comparison causes a branching jump. It's always good to benchmark before settling on a scheme.
This feels really weird to consider in terms of "O(..)" notation as presented to be honest. Once you get into the trie and other lookups the "n" vs "w" is not something you can ignore. The real effects of cache usage and implementation details render it true-but-meaningless as written.
I don't think the function "inDict" is even defined as either local or remote query (unless I missed it), which really influences the answers. Querying a short string against in-memory structure will be based on "n", but querying a long string against any remote database will be based on "w".
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.
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.
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.
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.
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 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)
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.
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?
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.
> 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 linked to article explains this is a real problem that the author needed to solve at scale.
(I still think the question is unfair, but my objection is more about the stressful interview situation where the real problem you're solving is "desperately trying to pass this or N other interviews you're currently doing").
Pretty much every good programmer I know, senior or not, will have no problem solving this unless they have a particularly bad day or brain fart; at worst, they may take slightly more time remembering/reinventing aspects of a trie to work out the optimal solution.
What folks need to remember is the employers who are primarily known for asking this generally have no problem hiring people who are good programmers and ALSO good at e.g. Dynamic Programming. And no, as much as some try to frame it, the two skills are not directly at odds with each other. Therefore, between a good programmer who can “Leetcode” and one who cannot, why wouldn’t they pick ones that are good at both?
And sure, if your company don’t have that luxury, don’t cargo cult. Hire a good enough domain expert for your specific needs.
Yea people on here get so worked up about coding interviews lol, if you were a successful competitive programmer I am going to be very likely to hire you, just like how I'd be very likely to hire a Google SWE with 10 yoe.
Its just another signal of aptitude, its not some magical catch all heuristic. However, people here suddenly expect like they are allowed to forget all the (very fundamental) basics and get into a job that involves coding without any coding at all. Now that leads to a bad hire.
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...
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.
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…
> 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.
I've asked variants of this question before, and although it is kind of good *for it's kind*, it's still a sort of algo leetcode-style question.
Actually the best questions I ask, and the ones that give me the best candidate "signal" are what I call the "clean code" style questions (as in code that is simple, easy to extend, not necessarily Uncle Bob Clean Code).
I'd rather not post examples here because I still use these questions, but the theme is as follows:
* These questions ask to implement functionality that you could see in a (super simple) real world application.
* They start super simple, and include several follow ups that increase in complexity.
* No data structures and algos beyond the basics. Loops, lists, hash maps and little else. What most programmers would use on the job on a daily basis.
I found in practice these work really well, specially with experienced programmers who can flex their low level design skills. People who ace leetcode style questions tend to do worse here, but no wonder, since they've been trained in a complete different style of interview.
Readit News
This question could be improved as follows:
* present the naive solution. Explain that this is a PR that was submitted in 20 minutes by our new intern from Waterloo. Ask them to help improve it.
* suggest to them the intern’s argument why the lookup is O(1) and explain that it’s actually O(n). Ask them to write a PR comment to break the news to the intern.
* explain the optimal solution with tries. Ask what happens if the vocabulary is big enough—and the prod environment is resource constrained—so that the trie is rarely in memory when the function is called. How would the trie solution compare to a binary search through a length normalized list of words?
This kind of question is barely useful to interview new hires—when you still may have basic questions about how much undergrad material “stuck”. Within a few years when they hit full-performance level you should care much less about this kind of question and much more about “higher order” thinking about engineering.
How do you communicate bad news? How do you identify, communicate, and mitigate risk? How do you plan large tasks at at appropriate level without over engineering the solution? What questions should you ask at different project stages to capture the right requirements, anticipate issues, and successfully execute over time?
But whatever, I’m sure you get lots of signal out of repeating “a hash table lookup is O(1)” “nuh uh” on loop for 10 years. :eyeroll:
Maybe the problem has something to do with the way they hire. The article mentions that this string-processing problem had to be approved by a committee:
”Twice I asked the hiring committee if I should stop using this and they had no problem with it.”
Not even the Soviet Union had a process where job interview questions were regularly approved by a committee. The level of bureaucracy in administering these brain puzzles at mass scale is absurd.
The article mentions that the candidate who did best on this question was “the type who did high-school competitions.” I wonder if anyone stopped at any point to question whether that’s the ideal type of hire.
I think this is the most telling bit. Time after time, I've seen excellent competitive programmers end up being mediocre engineers. Almost none of them are bad and it's also a very objective (at least on paper) process which is probably why Google is happy to stick with the process but most of them also aren't amazing innovators.
I'm sure that university student who aced the interview turned out to be very smart - they went to a great university and can solve challenging puzzles. But I don't think they'll end up being the engineer that builds Google's competition to ChatGPT. I wonder whether a course correction where Google starts looking for people who create really cool projects even at the risk of not being able to solve any coding challenges would actually help.
On the point of committees, though. Hiring committees make a hire/no-hire decision. They don't approve questions, but they do make decisions based on the results of asking a question. So they rely on the signal that the question generates, and if a question is not giving good signal, they will have an opinion.
There's a different reason for wanting to standardize on interview questions. It's very easy to embed cultural bias. If the topic of a programming problem uses the rules of a game, for example, that will probably mean that people who are familiar with the game will understand the gist of the problem much faster than people who've never played the game.
That being said I am easily the best/fastest programmer in my organization despite there being people who have 20 years more experience.
Not defending Google's practices here, but this claim is nonsense. Many public sector/third sector jobs in Western society will only use interview questions which have been pre-approved by explicit policy.
Also I recommend you try these "high school problems" you seem to be talking down on. I for one greatly respect people who can solve those types of problems, regardless of their age. These are not trivial problems, mind you. They require a lot of mathematical and logical intuition that 99% of people (and I'd wager the majority of SWEs) don't have.
It's unavoidable when you allow too many different interests to have a say in the process.
Deleted Comment
I think any discussion of complexity for this problem is misguided.
I mean, it's fine to talk about a hash lookup being o(n) for pseudocode in some hypothetical context. But if you're talking about actual code that you intend to run in Python or JS or whatever, it doesn't make sense - are the strings interned or not? When your language hashes the key of a dictionary lookup, does it cache the result? If you're using a JITTed language, won't any native o(n) hash lookups vanish in comparison to your non-native o(n) for-loop?
On top of all of which - why are we even talking about o(n) complexity for an n that cannot grow? If we're given a fixed dictionary then we can ignore any substring longer than its largest element, so the "n" for hash lookups is not the size of the original input - which is the n we realistically care about!
Basically, once TFA mentions complexity I feel like the only correct answer is to say "this isn't a situation where complexity analysis would be useful - we should benchmark the code".
All of these are useful signals for a hiring decision. Much more than quibbling about big-O of hash table lookups.
Like these can’t be prepared for? I think there are now whole chapters in those interview prep books/courses on how to answer these.
Even if there weren’t this is a good way to hire people who sound very professional on slack and in meetings but don’t produce any actual code (unless you got very lucky)
You would be absolutely stunned how many people cannot give you back the correct answer even after you literally give it to them. If you don‘t know some programming and I give you code and explain what it does, that still doesn’t help you.
There’s some tiny signal of your ability by asking you to memorize and regurgitate something; and maybe a tiny bit more signal in this question by implicitly testing “how do you respond to unexpected technical details in a high stress situation”. But they aren’t worth the trouble. You could measure both much more directly. You’d get more detail about their coding ability by directly asking about code they’ve written and know well.
> 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.
This should’ve been the interviewer’s first clue.
I don't get why the dictionary solution is actually O(n).
Surely you can have the hash function be O(1) by only looking at a subsets of characters something like
hash(s) = (s[0 %s.length ] ^ (s[6 %s.length]<<c1) ^ (s[7 %s.length]<<c2) ) % (size of the hash table)
You can trade-off memory for speed to avoid collisions by having a mostly empty big table (like 9/10 empty table). And you can also use multiple hash functions that must both simultaneously collide to avoid having too big a table (kinda like fronting your hash-table with bloom filters).
And you can pick the selected sub-index at random such that they split well your dictionary. Maybe you can even build a "Perfect hash function" so that all your dictionary words have distinct keys.
You only have to check for the whole string when the hash match, probability of which you can make as small as you want.
> > About Part 2 :“Write a function that given a string, determines if it’s a concatenation of a number of dictionary words.”
Isn't it just recognize if a string belongs to a regular language, where the language is defined by words in a dictionary ? So you just build a parser for your language and you test for belonging.
I'm quite rusty in non-deterministic finite automatons and regular languages, but surely there exists algorithm that build an automaton from the dictionary to recognize the language in something better than n^2, no? (We are moving the states of the automaton once per character, and we likely won't have n active states (except maybe for pathological dictionaries), complexity should be something like O(k*n) where k is a constant depends on the dictionary).
What this means in practice is that there is no polynomial curve for very long words. You don't bother hashing them, so the curve peaks and then flattens.
Obviously a trie is an interesting and possibly faster solution, though the hash has the benefit of being more cache friendly. But the big O analysis presented for this problem is flawed.
I seem to remember that in the very early days of Java the standard hashing method for strings only looked at a small prefix - turns out that very common use case was to be storing URLs as keys which, of course, mostly start with the same letters...
Eg you can’t just do equality on collision, you need to do equality on every lookup at least once.
Deleted Comment
Deleted Comment
This seems like a really great question, thank you :)
Great prompt!
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'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.
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 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..)
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.
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
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
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.
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).
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.
- 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 worked a SWE job years ago which was heavily reliant on dynamic programming and string search/alignment/etc. It really depends.
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.
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.
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.
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?
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.
Dead Comment
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.
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.
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.
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"
For part 1 using a hashtable to look up the dictionary words, the complexity is not O(n^2) where n is the length of the input string. It should be O(w^2) where w is the length of the longest word in the dictionary.
The hash key material of the dictionary words has at most w characters. When computing the hash key for the input string, it can be truncated at w, as any longer input won't lead to a hash key making a match in the hashtable.
For part 1 using a trie, the complexity is O(w) rather than O(n). This is actually more obvious since walking down a trie tree will stop at the last character of a dictionary word.
Again for part2, the complexity is O(w 2^n) using bruteforce with hashtable, O(w^2 n) using DP with hashtable, and O(w n) using DP with trie.
Edit: Also for short strings like dictionary words, O(w) is kind of meanless since with SIMD or SWAR the short word can be folded into one or two DWORD. You can effectively treat it as O(1).
I don't think the function "inDict" is even defined as either local or remote query (unless I missed it), which really influences the answers. Querying a short string against in-memory structure will be based on "n", but querying a long string against any remote database will be based on "w".
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.
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.
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.
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 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.
That is who you're optimizing for.
(I still think the question is unfair, but my objection is more about the stressful interview situation where the real problem you're solving is "desperately trying to pass this or N other interviews you're currently doing").
It's an extremely simplified but recognizable version of a real problem: natural language input tokenization, which of course has real consequences.
What folks need to remember is the employers who are primarily known for asking this generally have no problem hiring people who are good programmers and ALSO good at e.g. Dynamic Programming. And no, as much as some try to frame it, the two skills are not directly at odds with each other. Therefore, between a good programmer who can “Leetcode” and one who cannot, why wouldn’t they pick ones that are good at both?
And sure, if your company don’t have that luxury, don’t cargo cult. Hire a good enough domain expert for your specific needs.
I only know 1 guy who did coding competitions. He was in fact a good developer.
Why would you think a person that enjoys such a thing wouldn't be?
Its just another signal of aptitude, its not some magical catch all heuristic. However, people here suddenly expect like they are allowed to forget all the (very fundamental) basics and get into a job that involves coding without any coding at all. Now that leads to a bad hire.
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...
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.
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…
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.
Actually the best questions I ask, and the ones that give me the best candidate "signal" are what I call the "clean code" style questions (as in code that is simple, easy to extend, not necessarily Uncle Bob Clean Code).
I'd rather not post examples here because I still use these questions, but the theme is as follows:
* These questions ask to implement functionality that you could see in a (super simple) real world application.
* They start super simple, and include several follow ups that increase in complexity.
* No data structures and algos beyond the basics. Loops, lists, hash maps and little else. What most programmers would use on the job on a daily basis.
I found in practice these work really well, specially with experienced programmers who can flex their low level design skills. People who ace leetcode style questions tend to do worse here, but no wonder, since they've been trained in a complete different style of interview.