Review of Tech Developer Guide by Google

2018-04-11

Table of Contents

When I was applying for software development engineer to Google, one of the Google employees told me to checkout Google’s technical developer guide. Here is my review, my comments, and suggestions of what I found there.

Introduction

By the time of writing this post, the guide contains three paths: foundations, advanced, and for faculty. Basically, as a developer you do not need to follow the “for faculty” path; therefore, I am not going to cover it either. The foundations is consisted of so many easy and interesting programming challenges. Sometimes, I thought some of the items do not fit in this path and should be in the advanced path (that’s true for the advanced path). In the advanced path, as well as some again interesting challenges, there are valuable blog posts talking about real world software engineering. In what follows, I am going to cover the paths but not item by item; for some of the items, I do not have any specific comments, especially in the basic path. For covering the topics, the recommended sequence for the paths will be followed. After that, I will have some comments and suggestions about the whole guides in general.

![Foundations, Advanced, and For Faculty paths](paths.png)

Foundations Path

This path contains 33 items. I can remember I finished 16 items of it in about two hours. But some of the items were new for me, even after 9 years of coding; so you should never be arrogant. However, this path and the advanced path contain some of the previous Google interview questions which made me (maybe falsely) optimistic that Google’s interview is not so tough.

Google interview question: longest subsequence

Although the question is fairly easy to solve, there is a very thorough solution written for that which it is better not to miss. I also suggest to solve this question in a programming language which you are not familiar with.

In-fix Interpreter

Using Java and Python, you are asked to write an in-fix expression evaluator. This reminded me some concepts which I haven’t dealt with for a long time. It was good. You (like me) can add unary operators, paranthesis, and power (which expands from right) to make it more difficult. This gives you the basic answer.
Nevertheless, the compilers do not necessarily handle set up complex if-else statements to manage so many operators and their precedences, in fact what they do is usually using a parser (like YACC or ANTLR) to give parse the text with a given set of grammar rules; once the parse tree is ready, evaluation is trivial.

Hash Tables

In item “Hash Tables”, the basics of hash table is discussed. But it only talks about chaining and concludes that the complexity stays linear with hash tables; which is in fact not completely correct. At least, it could be said that some methods like Extendible Hashing, can keep the complexity constant on average (if there is no deletion); even if those methods are not explained. If it was meant to cover hash tables at basic levels, this was ok but the next item which is comparison of 3 different hash table management methods indicates that they wanted to go beyond the basics. In that item, 3 methods are discussed by taking CPU cache line length into account which makes it very concrete. I think it’s better to put the article about comparison of hash table management methods to the Advanced path. As people are going to implement one hash table in the “Movie Review Sentiment Analysis” item.

I think it’s better to put the article about comparison of hash table management methods to the Advanced path. As people are going to implement one hash table in the “Movie Review Sentiment Analysis” item.

“withoutString” Problem

It is an somewhat easy question to solve. The reason which made me talk about it is lacking one test case. The first solution which I wrote for the problem which passed all the test cases was this:

public String withoutString_bad_solution(String base, String removing) {
    String result = "";
    int count = 0;
    for(int i = 0; i < base.length(); i++) {
        char bc = Character.toLowerCase(base.charAt(i));
        char rc = Character.toLowerCase(removing.charAt(count));
        result += base.charAt(i);
        if(bc != rc)
            count = 0;
        if(bc == rc)
            count ++;
        if(count == removing.length()) {
            count = 0;
            result = result.substring(0,
                result.length() - removing.length());
        }
    }
    return result;
}

But when after some minutes, I said wait a minute. I already implemented a string search code and it was O(N²) in the worst case. I realized that removing “aab” from “aaab” should be tested. The above code fails it but the code below passes it.

public String withoutString(String base, String removing) {
    if(removing.length() == 0)
        return base;

    String result = "";
    int count = 0;
    for(int i = 0; i < base.length(); ) {
        int j=0;
        if(base.length() - i >= removing.length()) {
            for(j=0; j < removing.length() && i + j < base.length(); j++) {
                char bc = Character.toLowerCase(base.charAt(i + j));
                char rc = Character.toLowerCase(removing.charAt(j));
                if(bc != rc)
                    break;
            }
        }
        if(j==removing.length())
            i += removing.length();
        else {
            result += base.charAt(i);
            i++;
        }
    }
    return result;
}

I realized that removing “aab” from “aaab” should be tested in “withoutString” problem.

Boyer–Moore string search algorithm

After doing some more searches, I discovered Boyer–Moore string search algorithm which is a somewhat complicated but effective string search algorithm. In fact, its complexity is always O(N) where N is the length of the text. Here is a good demonstration of the algorithm.

5 Java Debugging Problems You Probably Have and How to Solve Them

Absolutely invaluable. A very well written and informative post. Although I haven’t used Java for back-end development so far (I have only used Ruby, JS, and Python) I found the tools and the ideas interesting.
If I find free time, I will design an exercise series to simulate such problems. I already had the chance to run a simulator for most common Git problems (can be found here).

If I find free time, I will design an exercise series to simulate such problems. I already had the chance to run a simulator for most common Git problems (can be found here).

Advanced Path

This path contains 21 items. A few of them can be really easy for you but some of the items are very challenging. I found some of the items invaluable. We will go over almost all of them one by one.

Compression and Decompression

The decompression is fairly easy. Especially if you use regular expressions to extract what is inside [] (usually, the regext matchers are not greedy). Personally, I avoid regular expressions when I can; sometimes they are write-only. Check the compression algorithm if you want to see a beautiful dynamic programming solution.

Testing and Confidence

I think on this path people should be warned about overconfidence in unit testing. We already covered the importance of unit testing in the foundation path.
Sometimes you are biased and miss some specifications to test, in these situations Code Review can help; also, if you want to go further, you can use some automatic test generation tools: Randoop for Java codes, for example.
Sometimes, your tests are “evergreen”: it means they pass even the implementation is wrong. It’s a bold example of overconfidence, and it is not always obvious that your tests are evergreen. I myself had the experience of the panic after realizing that the tests are evergreen. My situation was writing unit tests for my promise objects in Node.js (You can find further info about Node.js example here). For those situations, you can leverage mutation testing tools; but this method is usually expensive. Two of the famous tools are Stryker for Node.js and Pitest for Java.

People should be warned about overconfidence in unit testing.

Challenge: Which tests should you run?

I just want to add this comment. You don’t have to repeat yourself when you are doing white box testing especially on data structures. One of my favorite methods to do that is writing a “repOk” function which verifies the internal structure and specification (e.g. no dangling pointer). Also, there are some tools (Korat for example) which can automatically generate tests based on your formal specification (your “repOk” function). Therefore, instead of white box testing, you can assert “repOk” before and after your operations. Below is an example of repOk to verify a binary tree structure (got from here):

public boolean repOK() {
    if (root == null)
        return size == 0;
    // checks that tree has no cycle
    Set visited = new HashSet();
    visited.add(root);
    LinkedList workList = new LinkedList();
    workList.add(root);
    while (!workList.isEmpty()) {
        Node current = (Node) workList.removeFirst();
        if (current.left != null) {
            if (!visited.add(current.left))
                return false;
            workList.add(current.left);
        }
        if (current.right != null) {
            if (!visited.add(current.right))
                return false;
            workList.add(current.right);
        }
    }
    // checks that size is consistent
    return (visited.size() == size);
}

I myself used this method when I wanted to implement a Red-black tree.

Google’s Applied CS Skills program

This is the most challenging part. You are going to write 10+ Android apps (not from scratch). The most painful part is to install Android Studio and deal with its slowness. Personally, I never liked Android development with Java/Kotlin (I may write a post about it) and I always tried to escape from it by using Apache Cordova and recently React Native. However, it is a very good chance to reconciliate Android Studio and deal with the XML view files.
Nevertheless, this item is very valuable to teach some interesting problems in computer science. In the following paragraphs, some of the topics in this item are covered.

Touring Musician

In this part, you will implement 2 constructive heuristics for the Travelling Salesman Problem. In these methods, the nodes are randomly ordered and are added one by one to the current cycle (partial answer). Each method uses one of these insertion methods to complete the cycle: insert nearest (adding the new node to closest node in the current cycle) and insert smallest (adding the new node to the current cycle to minimize the length of the current cycle).
A good practice is to find examples to show that none of them out perform the other.

Binary Search Tree Viewer

It’s a good chance to implement AVL tree.

![AVL trees - a type of balanced binary (k-ary) trees. Animation showing the insertion of several elements into an AVL tree. It includes left, right, left-right and right-left rotations. (Source: Wikipedia)](https://upload.wikimedia.org/wikipedia/commons/f/fd/AVL_Tree_Example.gif)

### Ghost II In this part, you will implement [Trie data sctructure](https://en.wikipedia.org/wiki/Trie). It is one of the efficient ways to implement a dictionary. ### Black Hole This part challenges you in working with [triangular indexes](https://en.wikipedia.org/wiki/Triangular_number); they are not as straightforward as normal loops we write. Also, you will see an application of [Monte Carlo method](https://en.wikipedia.org/wiki/Monte_Carlo_method) to write a smart agent to play against human player. I had the chance to contrast it with traditional [Minimax trees](https://en.wikipedia.org/wiki/Minimax) which I used it for the game ["Four in a Row"](https://en.wikipedia.org/wiki/Connect_Four). I liked it because it was really easy to understand and implement comparing to traditional Minimax trees and proning them. Furthermore, it's a more practical solution as the Minimax tree grows exponentially and requires more resources to process. ### Puzzle 8 You will implement a solver for the nostalgic childhood game Puzzle 8. You will have the chance to implement [A\* Search Algorithm](https://en.wikipedia.org/wiki/A*_search_algorithm). ### Continental Divide A good example of dynamic programming. You will really enjoy it if you challenge yourself by handling neighbor cells with equal heights.

Learning Multiple Languages: Java, Python

I did not check out these resources as I knew Java and Python for 5 years and have written more than 10k lines of codes. I do not claim that I know all constructs in Java/Python but I can solve my problems by searching.

Working in multiple languages

There are three problems to solve: Distributing Candies, Palindrome Permutation II, Maximum Vacation Days. However, you need to pay money to be able to see those questions, I think it is better to keep this tutorial free by replacing these questions with some free problems.
At first, I solved the questions in Python. Then I had the chance to implement the solutions in Go which I haven’t used before.

Unfortunately, you need to pay to see these problems. I think it is better to keep this tutorial free by replacing these problems with free ones.

Movie Review Sentiment Analysis

In this part, you will implement a hash table and see how it is used in sentiment analysis. If you are really interested in sentiment analysis, you may check out the Standford Classifier. I already had the chance to use it for a course project and I found it easy to use.

Google summer of code projects

I really wished I had time to refactor them. Especially “Wikipedia Accuracy Review” had so many redundant codes.
By checking “App development for infectious microbial genomics” you will see a real example of Web Assembly (a way to use almost any language for front-end). The technology is not still mature but it is promising. However, I think this project suffers from a (Dockerfile)[https://docs.docker.com/engine/reference/builder], setting it up was painful for me. After understanding the value of Dockerfile, I went back to my undergraduate project (which was about network monitoring) and wrote a docker file for it. When I was wrting the Dockerfile, I was surprised how difficult how it is difficult to setup even my own project again. I promised to write dockerfile for all of my big projects.

I promised to write dockerfile for all of my big projects.

Git and Github

Git is covered in items: “Open source skills: GitHub usage and workflows” and “Open source skills: Commonly used GitHub tips and tricks”. The later is a handy cheat sheet for Git. For the first item, as I have been TA for a while (3+ years), I created a set of exercises simulating most common issues my students had with Git (you may check it out from here). I was happy to see almost all of the issues in the first page of most frequently asked questions in Git was already covered by my exercise set.

As I have been TA for a while (3+ years), I created a set of exercises simulating most common issues my students had with Git (you may check it out from here).

Legacy Code

The items “How to Read Code: 8 Things to Remember” and “Existing code base: Working on someone else’s code” are about legacy codes. They have so many valueable points. I just want to complement them by adding two tricks which I use.

grep and find
In fact the command grep is very more helpful than git blame. It must be mentioned in this tutorial set, same for find.

grep and find are missing and must be mentioned in this tutorial set
A small hack to see the stacktrace without using debugger.
Personally, I do not like debuggers because they make me lazy and they are not practical solutions. (What you usually need to do is to track the logs, sometimes match them from different componenets. In fact, you cannot put breakpoint in a production environment. That’s why I say debuggers make you lazy.) So, here is a simple track to track the function calls. This works for Java but might be used in other languages as well.
1
2
3
4
5
6
7
void instanceMain() {
try {
throw new RuntimeException("find stack trace in instanceMain.");
} catch (RuntimeException e) {
e.printStackTrace();
}
}

Existing Code Base: Hug Life

A fun Java graphics project. You will like to play with the final program as it will look good.

Former Coding Interview Question: Find the Volume of Each Lake Created by Rainwater

In fact, that was the first item I finished in this path. It’s a tricky program to solve.

Conclusion

In one sentence: do not miss it. It helps you review the topics you have learned, and learn new tools and technologies. I myself found it very valuable and I am glad that I could finish it. Thank you Google.