7 ms·

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 abili

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:

pavlov 4y ago
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.
- alex_sf 4y ago
  > The level of bureaucracy in administering these brain puzzles at mass scale is absurd. It's unavoidable when you allow too many different interests to have a say in the process.
  - atoav 4y ago
    The question is why you would have to many interests in one hire? That hints to me that there are problems of an organisational nature.
- xmprt 4y ago
  > 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.
  - fifilura 4y ago
    > 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. Oh, wow, if I could get that kind of result ("almost none of them bad", my addition: "possibly great") from an interview, I would stick with that process. I have also conducted interviews in a company with heavy focus on code tests, which obviously favors competitive programmers, and my anecdata was that I got very good results compared to the alternative (i.e. not doing that).
fenomas 4y ago
> 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".
- throwawaylinux 4y ago
  He was asking about the complexity in relation to the size of the input string, not dictionary size.
  - deleted 4y ago
    [deleted]
  - IanCal 4y ago
    > He was asking about the complexity in relation to the size of the input string, But you don't try checking if the entire string is in the dictionary regardless of n - you only ever check if it's in the dictionary if it's shorter than X+1 where X is the longest string in the dictionary. As the input string size grows, the dictionary lookups are capped.
    - throwawaylinux 4y ago
      And I'm sure he would have accepted that in a discussion about the complexity.
psd1 4y ago
> ask them to write a PR comment Great prompt!
dilyevsky 4y ago
> 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)
- activitypea 4y ago
  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.
- cgearhart 4y ago
  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.
GistNoesis 4y ago
> 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).
- deleted 4y ago
  [deleted]
- jakewins 4y ago
  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.
  - GistNoesis 4y ago
    Total O(n) using hashes, but not total O(n^2). > you need to do equality on every lookup at least once. I still don't think so. You only need for when the split would correspond to a good partial match. There are also other smarter hashing thing you can do to help convince you. For example if hash( s ) = sum_over_i( g(s[i]) ) if you pick g(x) = x or g(x) = xx or g(x)=xxx (or any function you are free to choose) (it's kind a like matching statistical moments of words). You can calculate this hashes in amortized O(1) because of sliding window trick. You can also index on split length. You can filter your set of candidate split positions so much that you only have very probably valid split positions in your candidate set, and therefore the complexity is just verifying the validity of the candidates splits, so still O(n(number of candidates after filter) ). > > Part 2 A solution based on filtering a candidate set could also probably be made to work for multiple words. You use the matching statistics to get candidates starting positions and length for words of the dictionary that appear in the string and you verify if they touch each other. Pathological cases are when words overlap each other but this may not appear very often in practice. You can also add some filter based on pairs of words (or triplets..., or n-grams) . All in all, I think the problem is rather bad because smart candidates will often have a solution that the interviewer may not be able to comprehend, and as a candidate you have just put yourself in a possible ego battle with the interviewer were even explaining the proof is not easy. In fact if the alternative solution is more interesting than the rest of the problem, you might get your candidate be focusing on that instead of your simpler but boring trie based solution.
brolumir 4y ago
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. This should’ve been the interviewer’s first clue.
deleted 4y ago
[deleted]
handoflixue 4y ago
> Ask them to write a PR comment to break the news to the intern. This seems like a really great question, thank you :)

pavlov 4y ago

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.

alex_sf 4y ago
> The level of bureaucracy in administering these brain puzzles at mass scale is absurd. It's unavoidable when you allow too many different interests to have a say in the process.
- atoav 4y ago
  The question is why you would have to many interests in one hire? That hints to me that there are problems of an organisational nature.
xmprt 4y ago
> 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.
- fifilura 4y ago
  > 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. Oh, wow, if I could get that kind of result ("almost none of them bad", my addition: "possibly great") from an interview, I would stick with that process. I have also conducted interviews in a company with heavy focus on code tests, which obviously favors competitive programmers, and my anecdata was that I got very good results compared to the alternative (i.e. not doing that).

fenomas 4y ago

> 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".

throwawaylinux 4y ago
He was asking about the complexity in relation to the size of the input string, not dictionary size.
- deleted 4y ago
  [deleted]
- IanCal 4y ago
  > He was asking about the complexity in relation to the size of the input string, But you don't try checking if the entire string is in the dictionary regardless of n - you only ever check if it's in the dictionary if it's shorter than X+1 where X is the longest string in the dictionary. As the input string size grows, the dictionary lookups are capped.
  - throwawaylinux 4y ago
    And I'm sure he would have accepted that in a discussion about the complexity.

psd1 4y ago

> ask them to write a PR comment Great prompt!

dilyevsky 4y ago

> 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)

activitypea 4y ago
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.
cgearhart 4y ago
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.

GistNoesis 4y ago

> 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).

deleted 4y ago
[deleted]
jakewins 4y ago
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.
- GistNoesis 4y ago
  Total O(n) using hashes, but not total O(n^2). > you need to do equality on every lookup at least once. I still don't think so. You only need for when the split would correspond to a good partial match. There are also other smarter hashing thing you can do to help convince you. For example if hash( s ) = sum_over_i( g(s[i]) ) if you pick g(x) = x or g(x) = xx or g(x)=xxx (or any function you are free to choose) (it's kind a like matching statistical moments of words). You can calculate this hashes in amortized O(1) because of sliding window trick. You can also index on split length. You can filter your set of candidate split positions so much that you only have very probably valid split positions in your candidate set, and therefore the complexity is just verifying the validity of the candidates splits, so still O(n(number of candidates after filter) ). > > Part 2 A solution based on filtering a candidate set could also probably be made to work for multiple words. You use the matching statistics to get candidates starting positions and length for words of the dictionary that appear in the string and you verify if they touch each other. Pathological cases are when words overlap each other but this may not appear very often in practice. You can also add some filter based on pairs of words (or triplets..., or n-grams) . All in all, I think the problem is rather bad because smart candidates will often have a solution that the interviewer may not be able to comprehend, and as a candidate you have just put yourself in a possible ego battle with the interviewer were even explaining the proof is not easy. In fact if the alternative solution is more interesting than the rest of the problem, you might get your candidate be focusing on that instead of your simpler but boring trie based solution.

brolumir 4y ago

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. This should’ve been the interviewer’s first clue.

deleted 4y ago

[deleted]

handoflixue 4y ago

> Ask them to write a PR comment to break the news to the intern. This seems like a really great question, thank you :)