Tuesday 22 December 2015

Am I ready for Google Interviews?

I have been preparing for the Google Interview for 4 weeks. I spent most of the time on coding and algorithms following the Cracking-the-Coding-Interview (V5).pdf. After I finished the book, I wonder "Am I ready to send my CV and ready to take interviews?" Following this thought, I list down the key criteria for interviews and how well prepared I am right now.

Criteria 1: Coding (using Java)
1.1: Coding style [DONE]
I found the Google Java coding style here: https://google.github.io/styleguide/javaguide.html
examples:
a) correctly use spaces
b) use functions to make code more readable.

1.2: Coding speed
There is no good way to speed up coding in 1 week, especially when I cannot use any IDE.
So, just keep practice.

1.3: Code readability
I found one website that I can read and comment others' code here:
http://codereview.stackexchange.com/

1.4: Know Java
I found this place great. Spending spare time on this website and check whether I know the topics in the website.
http://www.tutorialspoint.com/java_technology_tutorials.htm

1.5: Know the coding environment
Google Document
and
Coderpad

Criteria 2: Algorithm

2.1: Searching and sorting algorithms

Simple:
Bubble Sort
Insertion Sort
Selection Sort

Efficient:
Merge Sort
Heap Sort
Quick Sort

Special:
Counting Sort
Radix Sort

2.2: Hash tables
Linked List
Initial Capacity
Load factor
Hash function

2.3: Trees
Traversal
InOrderTraversal -> Stack + Pointer p
PreOrderTraversal -> Stack + Right & Left
PostOrderTraversal -> Stack + Stack
LevelTraversal -> ArrayList + ArrayList

Rebuild
Pre + In -> Recursive + Map of In
Post + In -> Recursive + Map of In
Pre + Post -> No unique Tree

Balanced Tree
Black-Red Tree
R*-Tree & R+-Tree

Graph:
Breath First Search
Depth First Search

2.4: Classic computer science problems
Graph Shortest Path: Dijkstra and A* Algorithm

Knapsack problem:
  • 0-1 knapsack problem: Dynamic Programming with v[I][W]
  • bounded knapsack problem: displace all values;
  • unbounded knapsack problem: 
Traveling Salesman Problem:

Minimum Spanning Tree:prime算法、kruskal算法


2.5: Theory of Computing
Big-O for space and time
Basic:
Master theorem

Criteria 3: System Design
3.1: System Definition 


3.2: Rough calculation of system requirement


3.3: Communication skills


3.4: Solutions: Data Storage, Data Processing Framework, Hardware, GUI


3.5: Features sets, interfaces, class hierarchies


Criteria 4: Interview Hints
4.1: Talk through your thought processes.

4.2: Ask clarifying questions if you do not understand the problem or need more information.

4.3: Think about ways to improve the solution you'll present.

4.4: Show an interest in Google products.

Criteria 5: Training Interview
5.1: https://leetcode.com/

5.2: glassdoor