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

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.

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.

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)

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.

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

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.

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.

in other words, the shortest string in alphabetical order

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

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.

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.

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

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/ (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

> [1] https://leetcode.com/submissions/detail/292246392/ (Not sure if you can deep link in to leetcode like this?)

It seems you cannot, 404 error.

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.

Here's what I came up with after experimenting with handling the leetcode example ("given cbacdcbc, produce acdb") manually:

Build a suffix tree ( https://en.wikipedia.org/wiki/Suffix_tree ) of the input with two modifications:

1. When adding a letter to the suffix tree, skip any paths that already contain that letter. (Thus, each path will contain a given letter no more than once.)

2. Include accounting information in each node specifying the length of the longest suffix including that node.

From wikipedia, construction of an ordinary suffix tree takes time and space linear in the length of the input string. At this level of analysis, I'm just hoping that modification #2 doesn't affect that. #1 certainly won't, in that it involves spending less time and less space than otherwise (by bailing out early under some circumstances).

Once the tree is constructed, just walk it, selecting at every point the child that is lexicographically earliest among all children with the maximum suffix length.

Observation: constructing this tree by hand really feels exponential; I suspect that the linear time and space requirements lean on an assumption that the size of the alphabet is finite.

Observation #2: Based on the comment timestamps, this took about 40 minutes of thinking. I think it's a good solution, but it probably wouldn't look great in an interview. (Also, handwaving "construct a suffix tree" is fast, but actually producing the code to do it takes extra time.) :/

Observation #3: assuming your solution is correct, it is essentially a reduction by dynamic programming of this one, only doing the calculations that are necessary to produce the lexicographically earliest string where I produce them all.

After playing with suffix trees a little more, I need to make a correction:

This problem asks for subsequences rather than substrings. As a result, when adding a node to the "suffix tree", it will need to be added as the child of more nodes than it would if we were building an actual suffix tree.

This seems like the type of change that might make construction of the tree harder than O(n). In particular, it will violate the constraint that a suffix tree for a string of length n has only n leaves.

That solution as written is O(n^3)

This is not an easy problem.

You only check each character in the string once. A hashmap can check if the char is used already.

For each char in the original string there is: * 1 check in hashmap (let's assume it was found). This is O(1) * build a new string where we remove that char from the string we are building (string2) and add it to the end. This step may look O(n) initially since we need to find that char in string2 but string2 is capped at 26 characters so it's O(1) * One comparison between the string we are building and the altered version.

How does that make it O(n^3)? I can't see which step inside the initial loop is O(n) or greater.

EDIT: The solution is actually incorrect so this is now semantics.

> EDIT: The solution is actually incorrect so this is now semantics.

Interesting use of "semantics".

The question of "how fast does this algorithm run?" is totally independent from the question of "what does this algorithm do?"; the second one is semantic but you're discussing the first here.

The algorithm I described was O(n), you said it was O(3). I'm assuming this happened because my algorithm was actually an incorrect solution but you subconsciously added in steps to make it a correct algorithm which changed its complexity. Hence it's semantics because we seem to be discussing two different algorithms.

Can I ask about the suffix tree solution? A one-hour problem is still pretty easy in the grand scheme of things.

input: "bcabc"

  1. "b"
  2. "bc"
  3. "bca"
  4. "bca"
  5. "bca"

What am I missing?

Take all the possible answers with duplicates removed, and return the first one in alphabetical order.

input: "bcabc"

output: "abc"

Nothing. I hadn't fleshed out my idea yet and that's the error I thought could exist. My solution is wrong.

that is a single line of code in javascript, assuming you just want the value in #5 const foo = [...new Set('bcabc'.split(''))].join('')

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

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

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

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

>The proposed solution isn’t optimal but it works. Not sure what you think is wrong with it?

Consider the input “ba”

This solution will return “ab”, which is not a strong that can be generated by deleting characters from the input.

Won't that give you the letters in alphabetical order, which may not be correct? See example 2 on the problem page.

> 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

I think the problem statement wants the lexicographically least string of those obtainable by deleting characters.

Can you elaborate on how technical writing can help you excel at a google? I write docs at my company all the time (that garner a lot of views) but I feel like most of the time it goes unappreciated except for those few individuals that actually need them to finish a random one-off task they were assigned.

(At Facebook, not Google) when the technical writing is used to influence a technical outcome. Particularly a strategic one. a well written memo can change the way business is done and there’s not much ambiguity around where the idea came from.

That said, being an eager doc writer in an effort to claim credit or inflate the perception of your own work is a great way to lose friends and alienate people.

Why do they get offended that you are consolidating knowledge?

Not the OP, but there can be a perception (whether justified or not) that people who "just write docs" aren't coding (taken as "contributing in a meaningful way") but instead optimizing for their own career/promotion. (This is not a viewpoint I personally hold)

Just as one data point - I went through the onsite recently and I personally found that PDF to be unhelpful. While it does list everything you need to know, it also lists way too many things that you probably don't need to know. It's basically an exhaustive list of basically every resource and topic that could possibly show up in the algorithmic interview. In my view you just need to cover Cracking the Coding Interview and then do 50-100 Leetcode questions. If you have a strong grasp of intro algorithms that would work too, except for engineers like me who didn't major in CS and hence never took an algos course.

--- Here's the actual PDF contents -------

Algorithm Complexity: ○ Please review complex algorithms, including big O notation. For more information on algorithms, visit the links below and your friendly local algorithms textbook. ■ Online Resources: Topcoder - Data Science Tutorials, The Stony Brook Algorithm Repository ■ Book Recommendations: Review of Basic Algorithms: Introduction to the Design and Analysis of Algorithms by Anany Levitin, Algorithms by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani, Algorithms For Interviews by Adnan Aziz and Amit Prakash, Algorithms Course Materials by Jeff Erickson, Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein

● Sorting: ○ Know how to sort. Don't do bubble-sort. ○ You should know the details of at least one nlog(n) sorting algorithm, preferably two (say, quicksort and merge sort). Merge sort can be highly useful in situations where quicksort is impractical, so take a look at it.

● Hash Tables: ○ Be prepared to explain how they work, and be able to implement one using only arrays in your favorite language, in about the space of one interview.

● Trees and Graphs: ○ Study up on trees: tree construction, traversal, and manipulation algorithms. You should be familiar with binary trees, n-ary trees, and trie-trees at the very least. You should be familiar with at least one flavor of balanced binary tree, whether it's a red/black tree, a splay tree or an AVL tree, and you should know how it's implemented. ○ More generally, there are three basic ways to represent a graph in memory (objects and pointers, matrix, and adjacency list), and you should familiarize yourself with each representation and its pros and cons. ○ Tree traversal algorithms: BFS and DFS, and know the difference between inorder, postorder and preorder traversal (for trees). You should know their computational complexity, their tradeoffs, and how to implement them in real code.

○ If you get a chance, study up on fancier algorithms, such as Dijkstra and A (for graphs). ● Other data structures: ○ You should study up on as many other data structures and algorithms as possible. You should especially know about the most famous classes of NP-complete problems, such as traveling salesman and the knapsack problem, and be able to recognize them when an interviewer asks you them in disguise.

● Operating Systems, Systems Programming and Concurrency: ○ Know about processes, threads, and concurrency issues. Know about locks, mutexes, semaphores and monitors, and how they work. Know about deadlock and livelock and how to avoid them. ○ Know what resources a processes needs, a thread needs, how context switching works, and how it's initiated by the operating system and underlying hardware. ○ Know a little about scheduling. The world is rapidly moving towards multi-core, so know the fundamentals of "modern" concurrency constructs.

● Coding: ○ You should know at least one programming language really well, preferably C/C++, Java, Python, Go, or Javascript. (Or C# since it's similar to Java.) ○ You will be expected to write code in your interviews and you will be expected to know a fair amount of detail about your favorite programming language. ○ Book Recommendation: Programming Interviews Exposed; Secrets to landing your next job by John Monagan and Noah Suojanen (Wiley Computer Publishing)

● Recursion and Induction: ○ You should be able to solve a problem recursively, and know how to use and repurpose common recursive algorithms to solve new problems. ○ Conversely, you should be able to take a given algorithm and prove inductively that it will do what you claim it will do. ● Data Structure Analysis and Discrete Math: ○ Some interviewers ask basic discrete math questions. This is more prevalent at Google than at other companies because we are surrounded by counting problems, probability problems, and other Discrete Math 101 situations. ○ Spend some time before the interview on the essentials of combinatorics and probability. You should be familiar with n-choose-k problems and their ilk – the more the better.

● System Design: ○ You should be able to take a big problem, decompose it into its basic subproblems, and talk about the pros and cons of different approaches to solving those subproblems as they relate to the original goal. ○ Google solves a lot of big problems; here are some explanations of how we solved a few to get your wheels turning. ■ Online Resources: Research at Google: Distributed Systems and Parallel Computing ■ Google File System ■ Google Bigtable ■ Google MapReduce

● Development Practices and Open-Ended Discussion: ○ Sample topics include validating designs, testing whiteboard code, preventing bugs, code maintainability and readability, refactor/review sample code. ○ Sample topics: biggest challenges faced, best/worst designs seen, performance analysis and optimization, testing and ideas for improving existing products.

Once you get into a FAANG company, do you actually use these algorithms? OOP/FP design, "clean code", the System design I would see as important, but in an actual dev job how much does the hard-core algorithm stuff come up?

Big O is always extremely relevant. - A lot of the typical algorithms in djikstra, merge sort etc. are not important to know by heart, but they represent important concepts to know to solve complex problems. Divide and Conquer and Greedy or topics that come up implicitly at least once a week, usually more often.

> it also lists way too many things that you probably don't need to know

The list looks reasonable to me.

What things, in your opinion, should be considered optional/lowest priority on the list?

I've only interviewed twice at Google for engineering so take this with a grain of salt.

Here are some things I would depriotize: ● Sorting: ○ Know how to sort. Don't do bubble-sort. ○ You should know the details of at least one nlog(n) sorting algorithm, preferably two (say, quicksort and merge sort). > I don't know anyone who has had to write a sort in an interview. Obviously you should know big O notation and also how they work, but practicing the implementation seems like a waste of time. In fact in my onsite, I used the .sort() method mentioned it was O(nlog(n)) and moved on to the rest of the problem. It was a minute part of the solution.

● Hash Tables: ○ Be prepared to explain how they work, and be able to implement one using only arrays in your favorite language, in about the space of one interview. > Again, while you should know how to use Hash Tables, I really don't think they would ask you to implement one.

● Trees and Graphs: * You should be familiar with at least one flavor of balanced binary tree, whether it's a red/black tree, a splay tree or an AVL tree, and you should know how it's implemented. > I actually still don't know how to build a balanced tree. It's never come up on any Big N interview I've had. The rest of this section is really important though, tree problems are extremely common in interviews.

○ If you get a chance, study up on fancier algorithms, such as Dijkstra and A (for graphs). > I dont know Dijkstra and I don't think it comes up that often. I have no idea what A is.

● Other data structures: ○ You should study up on as many other data structures and algorithms as possible. > I think if you know trees, tries, arrays, linked lists, and hash tables you will do fine. I only had one interview which had a different data structure (rope data structure) and the only reason he asked me the question was because I had never used it before. It was an intro question and if I said I knew it he wouldn't have given it to me. So I think if they give you another data structure, they are gonna assume you don't know it and will give you an intro question.

● Operating Systems, Systems Programming and Concurrency: ○ Know about processes, threads, and concurrency issues. Know about locks, mutexes, semaphores and monitors, and how they work. Know about deadlock and livelock and how to avoid them. > I don't know anything in this area (besides real basics on processes, threads, and locks). Never had a question here. I wouldn't study unless you are interviewing at team where this is relevant.

○ Know what resources a processes needs, a thread needs, how context switching works, and how it's initiated by the operating system and underlying hardware. ○ Know a little about scheduling. The world is rapidly moving towards multi-core, so know the fundamentals of "modern" concurrency constructs. > Again I don't know anything about OSes. I am not a CS major and never had a question in this area.do

● Data Structure Analysis and Discrete Math: ○ Some interviewers ask basic discrete math questions. This is more prevalent at Google than at other companies because we are surrounded by counting problems, probability problems, and other Discrete Math 101 situations. ○ Spend some time before the interview on the essentials of combinatorics and probability. You should be familiar with n-choose-k problems and their ilk – the more the better. > Also don't think this is that important. You should know how n choose k works (because that is needed for measuring complexity), but I definitely wouldn't spend my time on discrete math.

Thanks for replying. This is helpful stuff.

Did you pass either of those 2 Google interviews? And/or get offers from other similar companies?

> I only had one interview which had a different data structure (rope data structure) and the only reason he asked me the question was because I had never used it before. It was an intro question and if I said I knew it he wouldn't have given it to me. So I think if they give you another data structure, they are gonna assume you don't know it and will give you an intro question.

Can you explain that a little more?

Specifically: “they are gonna assume you don't know it and will give you an intro question.”

I failed the first time and passed the 2nd. I'm interviewing now so waiting to see if I get other offers.

To explain, one of the interviewers walked in and asked "have you heard of the rope data structure?"

I said "no" because I hadn't and he was like "great because otherwise I would give you another question". He then asked me to build 2 key functions for the data structure. I didn't need to study it beforehand, and if I did he would have gave me another question.

I think if they give you an uncommon data structure the expectation is that you have prior knowledge of it. This question was the favorite part of my interview loop (we chatted a bit about how google uses rope data structures)

Thanks for elaborating!

Was this part of the interview challenging? Seems to me like a surprise data structure coming up in an interview could be a bad thing (in terms of doing well).

Edit: What have your other interview experiences been like? Similar to Google, or would different/more preparation be required?

Also, what level are you at/interviewing for at these companies?