Google Interview: Software Engineer (SWE) Subject List

01 Oct 2011 | By Mihai Roman | Tags google SWE software engineer algorithms

Coding Knowledge

C++, Python and Java are the preferred programming languages. You must know at least one of them really well. You will be expected to write code in the phone screen interviews and most probably in the on site interviews too.

Recommended book on coding: Programming Interviews Exposed; Secrets to landing your next job by John Monagan and Noah Suojanen

Coding practice puzzles: Project Euler

Big-O

This should be the starting point in preparing for an algorithmic job interview. You must not struggle with basic complexity analysis, as it will guarantee not being hired. You should be familiar and understand the O, Θ and Ω notations.

General Problem and Puzzle Solving

There are many sites out there with programming puzzles. You will find some in this blog.

Sorting

You should be able to write O(n*lgn) algorithms like QuickSort and MergeSort with ease. Compare and understand the best, worst and average case complexities. You should practice with different data types and structures, understand how they work and adapt them for sorting, for example, large sets of data. Implement them in the external sorting variant.

HeapSort is also a key algorithm that will leverage the heap data structure. Practice CountingSort and RadixSort , learn how to sort in O(n). Understand the concept of sorting stability and apply it to QuickSort.

Don’t neglect the basic O(n^2) algorithms as well, they provide valuable insights. Take BubbleSort or InsertionSort and see several optimizations. Interviews are more about improving a basic idea, sorting algorithms will help with this process.

Hash Tables, Arrays, Linked Lists

These are the most important, basic data structure, you should know them perfectly and implement them in your favorite programming language (C++, Java or Python). Implement a hash table using vectors, practice FIFO and LIFO lists algoritmhs.

Heaps, Priority Queues

Understand the heap data structure and implement priority queues algorithms.

Graphs

In companies like Facebook and Google graphs are really important. Practice the three basic representation of graphs (objects and pointers, matrix, and adjacency list) and familiarize yourself with their pros & cons.

There is not much time during the phone screen interview so you should not expect something very complex. However, basic graph traversal algorithms (DFS and BFS) are a must, you should implement them in all basic representations.

You should be able to implement the Dijkstra or Floyd-Warshall algorithms as well as minimum spanning tree algorithms (Kruskal and Prim). Learn about topological sorting and bipartite matching.

Trees

Go through basic tree construction, traversal and manipulation algorithms. You should be able to implement an algorithms based on binary search trees during the phone interview.

You should be familiar with balanced trees, though you’ll not have time to implement algorithms during the interviews: AVL trees, Red/Black trees, Fibonacci trees, n-tier trees. Learn and compare complexities for basic operations for all these data structures.

Implement a sorting algorithm based in binary search trees, just for fun and remember what you’ve learned about the other sorting algorithms.

Know what the inorder, postorder and preorder transversal produce.

Backtracking, Greedy, Divide and Conquer

If, during the interview, you don’t get the optimal solution right away, don’t worry. The interview process is all about improving on naive, basic solutions; you should go into basic backtracking and brute-force algorithms, it’s the starting point.

You already encountered greedy algorithms when you went through the data structures. Familiarize yourself with the principles and be able to spot them.

Divide an conquer algorithms tend to be simple and efficient, e.g. QuickSort or binary search . I would recommend noting down the simplified use cases of the master theorem

Search and String Matching

You should be able to implement binary search algorithms with easy and speed. Practice on different data structures.

Learn about dictionaries and indexes and implement them within the context of larger problems. Searching and sorting are many times prerequisites for solving specific problems and you should be able to write live code implementation in a few minutes.

You should be able to implement the Knuth-Morris-Pratt algorithm during the interview. Go through problems counting the number of appearances of strings in large texts.

Dynamic Programming

This is probably the most important subject as the implementations are small. You should be able to implement 2-3 dynamic algorithms during a 35-40 minutes time. As you’ll check the resources on this blog or on the web, you’ll find that you should expect at least one dynamic programming question per phone interview.

Here you can find a list of DP puzzles, many of which have been asked in Google phone interviews.

Mathematics

You should familiarize yourself with counting, combinatorics and probability and basic geometry. It’s recommended you understand basic function types: monotone, injective, surjective, bijective (see how they apply in cryptography or hash tables). Understand basic regression algorithms and optimizations (local and global min/max points).

NP-complete

Learn about classes of NP-complete problems, such as traveling salesman and the knapsack problem, and be able to recognize them in disguise.

Google Stuff:

Google publications
Google File System
Google Bigtable
Google MapReduce

Threads, Processes

Learn about processes, threads and concurrency issues. Know about lock, mutexes, semaphores, monitors and how they work. Understand what deadlock and livelock are and how to avoid them. Learn the basics about context switching, scheduling, etc.


blog comments powered by Disqus