8 ms·

You advice is sound but incomplete. > if you still understand your undergraduate level algorithms course and the corresponding vocabulary, then you know what

You advice is sound but incomplete. > if you still understand your undergraduate level algorithms course and the corresponding vocabulary, then you know what you need to know speaking from experience, this would not get you nowhere near the level you have to be for passing the Google interview (or any other FAANG interview for that matter). You need to study long and hard in addition to solving OJ problems and familiarize yourself with different problem patterns. Let me give you and example of what I got at Google: https://leetcode.com/problems/remove-duplicate-letters/ https://leetcode.com/problems/remove-duplicate-letters/ Solving this problem optimally with only what you remember from undergrad algo courses is impossible. You either need to have a knack for these types of challenges or solve enough of them to identify a solution pattern.

deleted 7y ago
[deleted]
matt-attack 7y ago
> You must make sure your result is the smallest in lexicographical order among all possible results. Can someone explain this? I can't even parse that sentence.
- kayoone 7y ago
  in other words, the shortest string in alphabetical order
  - shric 7y ago
    Smallest as in order not length. In the second example with input cbacdcbc a possible solution would be cbad but acdb is "smaller" (ordered before).
    - logfromblammo 7y ago
      It seems odd to want to preserve the ordering among the surviving letters while still involving alphabetical order somehow. Those motives are usually mutually exclusive in the real world. As an engineer, before starting to code, I'd first ask if the customer would prefer "abcd" or "cbad" for the second example, as either would be far cheaper in terms of development and maintenance costs to do. It's somewhat common to discover that they're just taking the "acdb" you're giving them because that's exactly what they asked for, and then they're alphabetizing it to "abcd" afterward on their end, anyway. But sometimes, there is a legit reason for the weirdness, and the customer is willing to pay for the extra effort. Whenever someone seems intent on aiming at foot and pulling trigger, always ask "Are you sure?" and "Why do you want that?" at least once before helping them do what they want. The "read hypothetical; code answer" type of test doesn't quite capture that like the interactive interview discussion does.
- Blakestr 7y ago
  Basically alphabetical order, but if you don't say lexicographical, it doesn't sound as smart. (I am assuming it's a more comprehensive term, having to do with other characters, other than simple letters, so that if integers were used, it would appear as 1234, where saying "in alphabetical order"doesn't make sense. But yeah, I did a double take.
- deleted 7y ago
  [deleted]
- grahamburger 7y ago
  If you remove the duplicates from the string: CACB You can get either CAB or ACB. If you were to order all of the possible results of removing duplicates (in this case only two, but obviously many more for more complex strings) and order them alphabetically, then take the lowest one, that would be the right answer.
jefftk 7y ago
For what it's worth, I've interviewed 200+ engineers at Google and I think the problem you linked is not a good interview problem. I'm sorry you were asked it! A good problem gives people with algorithms ability a space to demonstrate that, but it should also give space for demonstrating strengths in design, coding, communication, etc. This one is almost all algorithms, of the "have you seen things like this before" variety, plus a small amount of code.
- seanmcdirmid 7y ago
  Does Google interview training emphasize that? Even in companies that claim not to give leetcode questions, they do pop up; everyone isn't really on the same page and there seems to be a lot of luck involved.
  - jefftk 7y ago
    I went through interview training 5+ years ago, but that was covered then and I believe it's still covered now. Because interviews are mostly conducted by engineers who do it as an occasional thing there are many inexperienced interviewers. (Speaking only for myself)
  - joshuamorton 7y ago
    Yes. The other important bit is that you often don't need to just find the optimal solution to get good ratings. For the question I used to use, I've had perhaps one person get the optimal solution without any hints. None have solved the extensions without hints. I've given more than one Strong Hire rating.
krn 7y ago
> Let me give you and example of what I got at Google: [...] Solving this problem optimally with only what you remember from undergrad algo courses is impossible. You either need to have a knack for these types of challenges or solve enough of them to identify a solution pattern. I have never tried to solve such problems before, but wouldn't it be enough to convert the string into a set of chars, then into an array of chars, sort it, and return it as a string?
- decebalus1 7y ago
  > wouldn't it be enough to convert the string into a set of chars, then into an array of chars, sort it, and return as a string? No. Please re-read the problem statement. It's way more complicated than that. If you figure out how to do it, try to figure out how to do it in O(N).
  - mason55 7y ago
    The proposed solution isn’t optimal but it works. Not sure what you think is wrong with it? An optimal solution would be something like - create an array of 26 or 52 bytes depending on whether this is case sensitive - iterate over the string and set the byte corresponding to each letter’s position in the alphabet to 1 - iterate over the byte array and for each 1 you encounter print out the corresponding letter
    - jfk13 7y ago
      Won't that give you the letters in alphabetical order, which may not be correct? See example 2 on the problem page.
      - krn 7y ago
        > Won't that give you the letters in alphabetical order, which may not be correct? But that's what "lexicographical" means? > In mathematics, the lexicographical order is a generalization of the way words are alphabetically ordered based on the alphabetical order of their component letters. > This generalization consists primarily in defining a total order on the sequences (often called strings in computer science) of elements of a finite totally ordered set, often called an alphabet. https://en.wikipedia.org/wiki/Lexicographical_order https://en.wikipedia.org/wiki/Lexicographical_order
MaximumYComb 7y ago
I've just finished the 2nd year of my CS degree. In about 3 minutes I came up with: 1) create an empty string, call it "S2" 2) loop over each char in original string 3) if the char isn't in S2, add it to the end of S2. If the char is already present in S2 then lexicographically compare the prior S2 verse S2 with this char shifted to the end. Keep the lower ordered one. This took about 3-4 minutes of thinking and is O(n). It might not be optimal, it might not even be a correct solution as I've spent only a few minutes on it. However, I feel it's close and it wouldn't take much to flesh out. EDIT: This solution is incorrect.
- deleted 7y ago
  [deleted]
- 171243 7y ago
  input: "bcabc" 1. "b" 2. "bc" 3. "bca" 4. "bca" 5. "bca" What am I missing?
  - MaximumYComb 7y ago
    Nothing. I hadn't fleshed out my idea yet and that's the error I thought could exist. My solution is wrong.
  - deleted 7y ago
    [deleted]
  - deleted 7y ago
    [deleted]
  - kangnkodos 7y ago
    Take all the possible answers with duplicates removed, and return the first one in alphabetical order. input: "bcabc" output: "abc"
  - pizza_dave 7y ago
    that is a single line of code in javascript, assuming you just want the value in #5 const foo = [...new Set('bcabc'.split(''))].join('')
deleted 7y ago
[deleted]
deleted 7y ago
[deleted]
sfgweilr4f 7y ago
I think I'd rather solve real problems than some basic algo I'd never bother to write myself. If Google just wants basic algos and will likely filter me out during interview because of that, I'd sooner not bother. This is probably why big companies complain of talent shortages. Also why they forget real people and start going on very strange tangents. Stupid filters. Good. I'll stick with creating actual solutions for real people with real problems. So much easier. shrug
hiram112 7y ago
As I'm in a similar boat to the OP, this is exactly why I'm hesitant to even interview with any of these companies, even as a test to see where I stand, simply because I fear I'd be blacklisted on some list these companies might share, should I bomb one without a lot of time spent reviewing. I sometimes follow a Reddit sub geared for mostly recent CS grads. Every week or two will be a post from someone who got a FAANG job, detailing what he did in order to pass the interview. And some of these are pretty absurd - graduating last semester and since then spending 6 months going through leetcode 6 hours a day, studying algorithms, paying for interview training classes, etc. And as an older guy who has a decent CS degree but hasn't needed to use 90% of anything related to algorithms in 15 years, I'd have to study a lot, and along with the numerous days of vacation time used for these interviews in California, it doesn't seem worth the effort.
- hiyer 7y ago
  > I fear I'd be blacklisted on some list these companies might share, should I bomb one without a lot of time spent reviewing. AFAIK they only blacklist you for 6 months and then you can try again. Even that may be relaxed if you're trying for a different department or, especially, geographical location. > numerous days of vacation time used for these interviews in California, it doesn't seem worth the effort. In India at least, the big companies handle this better than smaller ones - they have one or two telephonic interviews to begin with and then finish off all the face-to-face interviews in a single day.
- deleted 7y ago
  [deleted]
grahamburger 7y ago
Well this was a fun distraction! Took my no-CS-degree self a few tries to get it, but I got it[1]. I doubt I could have done it very well in an interview setting, though. A bit trickier than it looks at first for sure. Good practice because I have a coding interview tomorrow.[2] 12ms w/ 2.1MB memory usage - apparently 25 percentile for speed and lower memory usage than 100% of submissions in ~50 lines of Go. [1] https://leetcode.com/submissions/detail/292246392/ https://leetcode.com/submissions/detail/292246392/ (Not sure if you can deep link in to leetcode like this?) [2] I am looking for a job! Hit me up! https://news.ycombinator.com/item?id=21937576 https://news.ycombinator.com/item?id=21937576
- Kaius 7y ago
  > [1] https://leetcode.com/submissions/detail/292246392/ https://leetcode.com/submissions/detail/292246392/ (Not sure if you can deep link in to leetcode like this?) It seems you cannot, 404 error.
deleted 7y ago
[deleted]

deleted 7y ago

[deleted]

matt-attack 7y ago

> You must make sure your result is the smallest in lexicographical order among all possible results. Can someone explain this? I can't even parse that sentence.

kayoone 7y ago
in other words, the shortest string in alphabetical order
- shric 7y ago
  Smallest as in order not length. In the second example with input cbacdcbc a possible solution would be cbad but acdb is "smaller" (ordered before).
  - logfromblammo 7y ago
    It seems odd to want to preserve the ordering among the surviving letters while still involving alphabetical order somehow. Those motives are usually mutually exclusive in the real world. As an engineer, before starting to code, I'd first ask if the customer would prefer "abcd" or "cbad" for the second example, as either would be far cheaper in terms of development and maintenance costs to do. It's somewhat common to discover that they're just taking the "acdb" you're giving them because that's exactly what they asked for, and then they're alphabetizing it to "abcd" afterward on their end, anyway. But sometimes, there is a legit reason for the weirdness, and the customer is willing to pay for the extra effort. Whenever someone seems intent on aiming at foot and pulling trigger, always ask "Are you sure?" and "Why do you want that?" at least once before helping them do what they want. The "read hypothetical; code answer" type of test doesn't quite capture that like the interactive interview discussion does.
Blakestr 7y ago
Basically alphabetical order, but if you don't say lexicographical, it doesn't sound as smart. (I am assuming it's a more comprehensive term, having to do with other characters, other than simple letters, so that if integers were used, it would appear as 1234, where saying "in alphabetical order"doesn't make sense. But yeah, I did a double take.
deleted 7y ago
[deleted]
grahamburger 7y ago
If you remove the duplicates from the string: CACB You can get either CAB or ACB. If you were to order all of the possible results of removing duplicates (in this case only two, but obviously many more for more complex strings) and order them alphabetically, then take the lowest one, that would be the right answer.

jefftk 7y ago

For what it's worth, I've interviewed 200+ engineers at Google and I think the problem you linked is not a good interview problem. I'm sorry you were asked it! A good problem gives people with algorithms ability a space to demonstrate that, but it should also give space for demonstrating strengths in design, coding, communication, etc. This one is almost all algorithms, of the "have you seen things like this before" variety, plus a small amount of code.

seanmcdirmid 7y ago
Does Google interview training emphasize that? Even in companies that claim not to give leetcode questions, they do pop up; everyone isn't really on the same page and there seems to be a lot of luck involved.
- jefftk 7y ago
  I went through interview training 5+ years ago, but that was covered then and I believe it's still covered now. Because interviews are mostly conducted by engineers who do it as an occasional thing there are many inexperienced interviewers. (Speaking only for myself)
- joshuamorton 7y ago
  Yes. The other important bit is that you often don't need to just find the optimal solution to get good ratings. For the question I used to use, I've had perhaps one person get the optimal solution without any hints. None have solved the extensions without hints. I've given more than one Strong Hire rating.

krn 7y ago

> Let me give you and example of what I got at Google: [...] Solving this problem optimally with only what you remember from undergrad algo courses is impossible. You either need to have a knack for these types of challenges or solve enough of them to identify a solution pattern. I have never tried to solve such problems before, but wouldn't it be enough to convert the string into a set of chars, then into an array of chars, sort it, and return it as a string?

decebalus1 7y ago
> wouldn't it be enough to convert the string into a set of chars, then into an array of chars, sort it, and return as a string? No. Please re-read the problem statement. It's way more complicated than that. If you figure out how to do it, try to figure out how to do it in O(N).
- mason55 7y ago
  The proposed solution isn’t optimal but it works. Not sure what you think is wrong with it? An optimal solution would be something like - create an array of 26 or 52 bytes depending on whether this is case sensitive - iterate over the string and set the byte corresponding to each letter’s position in the alphabet to 1 - iterate over the byte array and for each 1 you encounter print out the corresponding letter
  - jfk13 7y ago
    Won't that give you the letters in alphabetical order, which may not be correct? See example 2 on the problem page.
    - krn 7y ago
      > Won't that give you the letters in alphabetical order, which may not be correct? But that's what "lexicographical" means? > In mathematics, the lexicographical order is a generalization of the way words are alphabetically ordered based on the alphabetical order of their component letters. > This generalization consists primarily in defining a total order on the sequences (often called strings in computer science) of elements of a finite totally ordered set, often called an alphabet. https://en.wikipedia.org/wiki/Lexicographical_order https://en.wikipedia.org/wiki/Lexicographical_order

MaximumYComb 7y ago

I've just finished the 2nd year of my CS degree. In about 3 minutes I came up with: 1) create an empty string, call it "S2" 2) loop over each char in original string 3) if the char isn't in S2, add it to the end of S2. If the char is already present in S2 then lexicographically compare the prior S2 verse S2 with this char shifted to the end. Keep the lower ordered one. This took about 3-4 minutes of thinking and is O(n). It might not be optimal, it might not even be a correct solution as I've spent only a few minutes on it. However, I feel it's close and it wouldn't take much to flesh out. EDIT: This solution is incorrect.

deleted 7y ago
[deleted]
171243 7y ago
input: "bcabc" 1. "b" 2. "bc" 3. "bca" 4. "bca" 5. "bca" What am I missing?
- MaximumYComb 7y ago
  Nothing. I hadn't fleshed out my idea yet and that's the error I thought could exist. My solution is wrong.
- deleted 7y ago
  [deleted]
- deleted 7y ago
  [deleted]
- kangnkodos 7y ago
  Take all the possible answers with duplicates removed, and return the first one in alphabetical order. input: "bcabc" output: "abc"
- pizza_dave 7y ago
  that is a single line of code in javascript, assuming you just want the value in #5 const foo = [...new Set('bcabc'.split(''))].join('')

deleted 7y ago

[deleted]

deleted 7y ago

[deleted]

sfgweilr4f 7y ago

I think I'd rather solve real problems than some basic algo I'd never bother to write myself. If Google just wants basic algos and will likely filter me out during interview because of that, I'd sooner not bother. This is probably why big companies complain of talent shortages. Also why they forget real people and start going on very strange tangents. Stupid filters. Good. I'll stick with creating actual solutions for real people with real problems. So much easier. shrug

hiram112 7y ago

As I'm in a similar boat to the OP, this is exactly why I'm hesitant to even interview with any of these companies, even as a test to see where I stand, simply because I fear I'd be blacklisted on some list these companies might share, should I bomb one without a lot of time spent reviewing. I sometimes follow a Reddit sub geared for mostly recent CS grads. Every week or two will be a post from someone who got a FAANG job, detailing what he did in order to pass the interview. And some of these are pretty absurd - graduating last semester and since then spending 6 months going through leetcode 6 hours a day, studying algorithms, paying for interview training classes, etc. And as an older guy who has a decent CS degree but hasn't needed to use 90% of anything related to algorithms in 15 years, I'd have to study a lot, and along with the numerous days of vacation time used for these interviews in California, it doesn't seem worth the effort.

hiyer 7y ago
> I fear I'd be blacklisted on some list these companies might share, should I bomb one without a lot of time spent reviewing. AFAIK they only blacklist you for 6 months and then you can try again. Even that may be relaxed if you're trying for a different department or, especially, geographical location. > numerous days of vacation time used for these interviews in California, it doesn't seem worth the effort. In India at least, the big companies handle this better than smaller ones - they have one or two telephonic interviews to begin with and then finish off all the face-to-face interviews in a single day.
deleted 7y ago
[deleted]

grahamburger 7y ago

Well this was a fun distraction! Took my no-CS-degree self a few tries to get it, but I got it[1]. I doubt I could have done it very well in an interview setting, though. A bit trickier than it looks at first for sure. Good practice because I have a coding interview tomorrow.[2] 12ms w/ 2.1MB memory usage - apparently 25 percentile for speed and lower memory usage than 100% of submissions in ~50 lines of Go. [1] https://leetcode.com/submissions/detail/292246392/ https://leetcode.com/submissions/detail/292246392/ (Not sure if you can deep link in to leetcode like this?) [2] I am looking for a job! Hit me up! https://news.ycombinator.com/item?id=21937576 https://news.ycombinator.com/item?id=21937576

Kaius 7y ago
> [1] https://leetcode.com/submissions/detail/292246392/ https://leetcode.com/submissions/detail/292246392/ (Not sure if you can deep link in to leetcode like this?) It seems you cannot, 404 error.

deleted 7y ago

[deleted]