7 ms·

That's certainly your opinion, but the subsequence problem is a very general, abstract question that offers the candidate a number of ways to arrive a progressi

by akanet 8y ago

That's certainly your opinion, but the subsequence problem is a very general, abstract question that offers the candidate a number of ways to arrive a progressively better solution by following their intuitions. It's not the greatest interview question, but it's certainly not the worst. This website appears to be for people who already know how to code, and offers many different paths as well.

m0zg 8y ago
It doesn't. This seems like a typical Google interview question. If you didn't know how to solve it before the interview started, you aren't going to figure out anything other than a brute force solution in 45 minutes. And brute force solution will not get you a good grade in a tech interview at Google. It's idiotic: once you do get hired by Google, easily 80% of your work is copying one proto buffer into another, and the remaining 20% is mostly yak shaving and figuring out how things work in the absence of documentation. Dynamic programming should be the least of their concerns.
- ascar 8y ago
  That's probably the issue with algorithm solving is not software engineering and if you mostly select on the first, you do not necessarily get good people in the second, broader and more important area. Then you end up with a terrible system to work with. It's like hiring construction engineers only based on their performance in structural analysis. Sure, it's important that the house doesn't collapse, but this will not get it build.
- snaky 8y ago
  > figuring out how things work in the absence of documentation That would be great interview test actually. Given a bunch of unknown code, add some simple functions, not breaking it apart. Keeping the style (not only syntactically) would be a bonus.
  - m0zg 8y ago
    Yes, I actually implemented such a thing at a company I worked at after Google. We'd give the candidate a fairly simple and self contained codebase, and ask them to add a simple, incremental feature in the span of an hour. No limits on legitimate internet access, stack overflow, etc, and using their favorite text editor (we had several already set up). This worked great for us, as it selects for people who can solve practical problems in code they're not familiar with, which is bulk of the work of any software engineer.
  - rhizome 8y ago
    While I'm not in a position to test it, I've thought for a while that companies should save their bugs, make an app that is similar enough to the work that these saved-off bugs can be put into it, then compare the candidate solutions with what your existing people came up with.
- AzzieElbab 8y ago
  oh no. are you saying google tech interviews are basically trivia
- SamReidHughes 8y ago
  > If you didn't know how to solve it before the interview started, you aren't going to figure out anything other than a brute force solution in 45 minutes. I'd never heard this problem before and it took a few seconds to think of something better than brute force. Many colleagues I've worked with would too, and could probably improve on their first non-brute-force idea over the span of 25 minutes.
  - m0zg 8y ago
    The problem here is the only non-bruteforce solution worth pursuing here involves DP with less-than-straightforward memoization rules, which the engineer is unlikely to actually use before or after the interview. So she has to waste a month studying _specifically for the interview_ and "refreshing" the skills she won't actually need on the job. It's like you're hiring a welder, but you want them to be good at juggling as well, just for the interview. Don't get me wrong, I'm not saying DP is useless, it came in handy a couple of times over the course of my 20+ year career. I'm just saying that you could always look it up, and the amount of signal you get out of someone solving this problem is very close to zero, because it amounts to: "this person solved this problem before the interview", whereas the question you really need to answer is "can this person solve the problems we need solved".
    - AlexCoventry 8y ago
      > only non-bruteforce solution worth pursuing here involves DP What's wrong with starting with a hashtable of substrings of fixed length? For inputs with low autocorrelation, that'll get you a good average-case speed up.
    - kagol 8y ago
      > The problem here is the only non-bruteforce solution worth pursuing here involves DP with less-than-straightforward memoization rules The solution commentary [1] doesn't mention DP. [1]: https://techdevguide.withgoogle.com/resources/find-longest-word-in-dictionary-that-subsequence-of-given-string/ https://techdevguide.withgoogle.com/resources/find-longest-w...
    - 8y ago
- AlexCoventry 8y ago
  > If you didn't know how to solve it before the interview started, you aren't going to figure out anything other than a brute force solution in 45 minutes Not with that attitude.
- dbt00 8y ago
  As someone who's done a ton of tech interviewing for a blue chip silicon valley firm, viewing this as a homework problem to which there is one correct answer is exactly not what I'm looking for. I want to see your problem solving skills and I'm curious about your knowledge base, but if you don't know any of the specific techniques and/or don't get to the specific optimal solution I'm looking for I really don't give a shit.
  - jakebasile 8y ago
    Everyone says "it's not about the solution but how you go about solving it", but it's never been my experience as an interviewee. Every time I've been interviewed with one of these godawful trivia questions I've been denied even though I do my best to work with the interviewer to solve it. On the rare occasion I get feedback it has been because I didn't solve the problem optimally or some other nonsense.
  - SmirkingRevenge 8y ago
    This is the reassuring story every interviewer has to tell themselves to feel good about their decisions... and its the story every interview consultant tells the tech firm. But I tend to think its probably a just-so story, most of the time. All this work is done in the tech world to eliminate the subjectivity from interviews - this is how the subjectivity is re-introduced through the back door.
    - webmaven 8y ago
      > this is how the subjectivity is re-introduced through the back door. Exactly. You'd think that the large tech companies would insert "mystery shopper" candidates into the pipeline to uncover and measure the objectivity/subjectivity/bias of the interview process.
- onion2k 8y ago
  You're assuming that it's important to actually solve the problem. I'm not sure that's the case - it's really asking whether or not the candidate understands that brute forcing is a poor solution and determining whether they're capable of even looking for a better solution. A lot of developers find it very hard to look past the obvious first solution they find to a more efficient algorithm instead. Specifically companies like Google want to hire people who can do that deeper work. The real issue with problems like this is when much smaller companies hiring a dev who'll be bolting together APIs and won't ever need to know an answer start to copy the technique believing "it's how you hire devs".
  - thwy12321 8y ago
    This is false.
  - ryacko 8y ago
    People buy SSDs so that FAANG single page apps take a minute to load.
raverbashing 8y ago
Yes but Google wants the right answer, regardless of the way you think and regardless of the fact that you came up with a proof for P=NP on the interview
- joshuamorton 8y ago
  This isn't really true. I've asked a few different interview questions in my time, and the number of candidates who have gotten the "optimal" solution currently sits at 0, to any of the questions. Despite this, I've suggested that we hire some of those "wrong" answer candidates. And given the interview feedback I've seen, I'm not the only one like this.
  - raverbashing 8y ago
    Might be something more recent then, though I agree that there are questions which are more flexible than others
    - chaosite 8y ago
      This was the way I was taught to conduct interviews at Google when I was there ~3 years ago, so it can't be that recent. That was the ideal though, I'm not that surprised that in practice it doesn't actually work.
      - raverbashing 8y ago
        Ah my experience with them was before that timeframe.
  - webmaven 8y ago
    > Despite this, I've suggested that we hire some of those "wrong" answer candidates. And were they hired?
    - joshuamorton 8y ago

by akanet 8y ago

m0zg 8y ago

It doesn't. This seems like a typical Google interview question. If you didn't know how to solve it before the interview started, you aren't going to figure out anything other than a brute force solution in 45 minutes. And brute force solution will not get you a good grade in a tech interview at Google. It's idiotic: once you do get hired by Google, easily 80% of your work is copying one proto buffer into another, and the remaining 20% is mostly yak shaving and figuring out how things work in the absence of documentation. Dynamic programming should be the least of their concerns.

ascar 8y ago
That's probably the issue with algorithm solving is not software engineering and if you mostly select on the first, you do not necessarily get good people in the second, broader and more important area. Then you end up with a terrible system to work with. It's like hiring construction engineers only based on their performance in structural analysis. Sure, it's important that the house doesn't collapse, but this will not get it build.
snaky 8y ago
> figuring out how things work in the absence of documentation That would be great interview test actually. Given a bunch of unknown code, add some simple functions, not breaking it apart. Keeping the style (not only syntactically) would be a bonus.
- m0zg 8y ago
  Yes, I actually implemented such a thing at a company I worked at after Google. We'd give the candidate a fairly simple and self contained codebase, and ask them to add a simple, incremental feature in the span of an hour. No limits on legitimate internet access, stack overflow, etc, and using their favorite text editor (we had several already set up). This worked great for us, as it selects for people who can solve practical problems in code they're not familiar with, which is bulk of the work of any software engineer.
- rhizome 8y ago
  While I'm not in a position to test it, I've thought for a while that companies should save their bugs, make an app that is similar enough to the work that these saved-off bugs can be put into it, then compare the candidate solutions with what your existing people came up with.
AzzieElbab 8y ago
oh no. are you saying google tech interviews are basically trivia
SamReidHughes 8y ago
> If you didn't know how to solve it before the interview started, you aren't going to figure out anything other than a brute force solution in 45 minutes. I'd never heard this problem before and it took a few seconds to think of something better than brute force. Many colleagues I've worked with would too, and could probably improve on their first non-brute-force idea over the span of 25 minutes.
- m0zg 8y ago
  The problem here is the only non-bruteforce solution worth pursuing here involves DP with less-than-straightforward memoization rules, which the engineer is unlikely to actually use before or after the interview. So she has to waste a month studying _specifically for the interview_ and "refreshing" the skills she won't actually need on the job. It's like you're hiring a welder, but you want them to be good at juggling as well, just for the interview. Don't get me wrong, I'm not saying DP is useless, it came in handy a couple of times over the course of my 20+ year career. I'm just saying that you could always look it up, and the amount of signal you get out of someone solving this problem is very close to zero, because it amounts to: "this person solved this problem before the interview", whereas the question you really need to answer is "can this person solve the problems we need solved".
  - AlexCoventry 8y ago
    > only non-bruteforce solution worth pursuing here involves DP What's wrong with starting with a hashtable of substrings of fixed length? For inputs with low autocorrelation, that'll get you a good average-case speed up.
  - kagol 8y ago
    > The problem here is the only non-bruteforce solution worth pursuing here involves DP with less-than-straightforward memoization rules The solution commentary [1] doesn't mention DP. [1]: https://techdevguide.withgoogle.com/resources/find-longest-word-in-dictionary-that-subsequence-of-given-string/ https://techdevguide.withgoogle.com/resources/find-longest-w...
  - 8y ago
AlexCoventry 8y ago
> If you didn't know how to solve it before the interview started, you aren't going to figure out anything other than a brute force solution in 45 minutes Not with that attitude.
dbt00 8y ago
As someone who's done a ton of tech interviewing for a blue chip silicon valley firm, viewing this as a homework problem to which there is one correct answer is exactly not what I'm looking for. I want to see your problem solving skills and I'm curious about your knowledge base, but if you don't know any of the specific techniques and/or don't get to the specific optimal solution I'm looking for I really don't give a shit.
- jakebasile 8y ago
  Everyone says "it's not about the solution but how you go about solving it", but it's never been my experience as an interviewee. Every time I've been interviewed with one of these godawful trivia questions I've been denied even though I do my best to work with the interviewer to solve it. On the rare occasion I get feedback it has been because I didn't solve the problem optimally or some other nonsense.
- SmirkingRevenge 8y ago
  This is the reassuring story every interviewer has to tell themselves to feel good about their decisions... and its the story every interview consultant tells the tech firm. But I tend to think its probably a just-so story, most of the time. All this work is done in the tech world to eliminate the subjectivity from interviews - this is how the subjectivity is re-introduced through the back door.
  - webmaven 8y ago
    > this is how the subjectivity is re-introduced through the back door. Exactly. You'd think that the large tech companies would insert "mystery shopper" candidates into the pipeline to uncover and measure the objectivity/subjectivity/bias of the interview process.
onion2k 8y ago
You're assuming that it's important to actually solve the problem. I'm not sure that's the case - it's really asking whether or not the candidate understands that brute forcing is a poor solution and determining whether they're capable of even looking for a better solution. A lot of developers find it very hard to look past the obvious first solution they find to a more efficient algorithm instead. Specifically companies like Google want to hire people who can do that deeper work. The real issue with problems like this is when much smaller companies hiring a dev who'll be bolting together APIs and won't ever need to know an answer start to copy the technique believing "it's how you hire devs".
- thwy12321 8y ago
  This is false.
- ryacko 8y ago
  People buy SSDs so that FAANG single page apps take a minute to load.

raverbashing 8y ago

Yes but Google wants the right answer, regardless of the way you think and regardless of the fact that you came up with a proof for P=NP on the interview

joshuamorton 8y ago
This isn't really true. I've asked a few different interview questions in my time, and the number of candidates who have gotten the "optimal" solution currently sits at 0, to any of the questions. Despite this, I've suggested that we hire some of those "wrong" answer candidates. And given the interview feedback I've seen, I'm not the only one like this.
- raverbashing 8y ago
  Might be something more recent then, though I agree that there are questions which are more flexible than others
  - chaosite 8y ago
    This was the way I was taught to conduct interviews at Google when I was there ~3 years ago, so it can't be that recent. That was the ideal though, I'm not that surprised that in practice it doesn't actually work.
    - raverbashing 8y ago
      Ah my experience with them was before that timeframe.
- webmaven 8y ago
  > Despite this, I've suggested that we hire some of those "wrong" answer candidates. And were they hired?
  - joshuamorton 8y ago