Cracking the Coding Interview reflection

1. When test multiple cases, be careful about resetting global or shared variables for next test case! (i.e. vertex visited or not in problem Search Route In A Graph, previous value in problem Validate Binary Search Tree)

2. Code in Google Java Style, which is widely used in Google Projects
http://google-styleguide.googlecode.com/svn/trunk/javaguide.html

For example,
1) add braces {} for one statement block like if, else, for, while.
2) Class name use UpperCamelCase. Method, Local Variable and Parameter name use lowerCaseCamel.
3) Noun for Class name, verb for method name, adjective for interface name.
4) null is not instance of anything.
5) package files for easy management and name space separation

3. My solution:
https://github.com/yao23/InterviewPreparation

4. OOD
1) Communication with the interviewer to clarify ambiguity for system sketch
2) Abstract objects from scenario, sometimes simplify the case, like corner pieces array in pro 6
3) Extract relationship between objects for inheritance, interface and property
4) Confirm action for methods, use key words in the problem
5) Divide large objects into components (i.e. online reading system into library, user manager and display)
6) HashMap is useful for fields or attribute design, Create/ Read/ Update/ Delete (CRUD) for methods design
7) Focus on core steps in the problem, such as attach edges, remove the edge from open edge lists, find next exposed edge in pro 6
8) use pseudo-code or comment to express ideas, what you did is less important than why you did, discuss trade-off with interviewer
9) use array for frequent searching, linked list for frequent adding and deleting

5. Database
1) trade-off between flexibility and complexity
2) Make assumptions. Incorrect assumptions can be dealt with as long as they were acknowledged in both reality and interview
3) Normalized database is designed to reduce redundancy and denormalized  one is to optimize read time with redundancy, but expensive to update and insert, sometimes inconsistent, need more storage

6. Stack can replace array when don't need to store immediate values, like Largest Rectangle in Histogram.

Elements of Programming Interview
1. Approaching the problem
Clarify the question
Work on small examples
Spell out the brute-force solution
Think out loud
Apply patterns(D&C, recursion, DP, graph, hashmap, binary tree, stack, etc.)

2. Presenting the solution
Libraries
Focus on the top-level algorithm
Manage the whiteboard
Test for corner cases
Syntax
Memory management

3. General conversation
Can the candidate clearly communicate a complex idea?
Is the candidate passionate about his work?
Is there a potential interest match with some project?

4. Other advice
Be honest
Keep a positive spirit
Don't apologize
Appearance
Be aware of your body language
Keep money and perks out of the interview

5. Stress interviews

6. Learning from bad outcomes

7. Data Structure
Primitive types, Array & String, List, Stack and Queue, Binary Tree, Heap, Hash Table, Binary Search Tree. (Skip List, Treap, Fibonacci Heap, Disjoint-set data structures, Tries)

8. Algorithm
Sorting, Recursion, Divide and Conquer, Dynamic Programming, Greedy, Incremental Improvement, Elimination, Parallelism, Caching, Randomization, Approximation, State

9. Abstract analysis techniques
Case analysis, Small examples, Iterative refinement, Reduction, Graph modeling, Write an equation, Variation, Invariants