For background information on this post, please see Preparing for Programming Interviews.
The two authors of this book are intelligent and experienced computer scientists:
• Dr. Adnan Aziz is a professor at the University of Texas at Austin and also worked at Google.
• Dr. Amit Prakash is a member of the technical staff at Google.
The first half of the book is dedicated to problem-solving techniques, interview strategies, and algorithm problems. The last half of the book lists the solutions to the problems. This post has some notes from the book. The book itself has much more information as well as helpful examples.
Problem Solving Techniques
• Divide and Conquer – dividing a problem into smaller subproblems
• Recursion and Dynamic Programming – creating a solution to a problem by looking at solutions to smaller subproblems0
• Case Analysis – splitting input and execution into cases and solving each case separately
• Generalization – generalizing from the problem to a problem that is easier to solve
• Data structures – finding a data structure that directly applies to the problem
• Iterative refinement – formalizing a brute force approach to a problem
• Small examples – finding a solution to concrete instances and creating a solution that can be used in arbitrary instances of the problem
• Reduction – using a problem with a known solution as a subroutine
• Graph modeling – describing the problem using a graph and solving it using an existing algorithm
• Write an equation – expressing the relationships in the problem in the form of equations or inequalities
• Auxiliary elements – adding some new element to the problem
• Variation – solving a slightly different problem and applying the solution to the current problem
• Parallelism – identifying subproblems that can be solved independently on different machines
• Caching – storing some of the computation to look it up later
• Symmetry – finding and exploiting symmetry in the input space or solution space
Searching
• binary search
• hashing
• binary search trees
Sorting
• mergesort
• heapsort
• quicksort
• radixsort
• max-heap
Meta-algorithms
• dynamic programming
• greedy algoritms
Algorithms on Graphs
• graph search
• advanced graph algorithms (matching, shortest paths, max flow, minimum spanning tree)
Algorithms on Strings
• manipulating strings
Intractability
• solving intractable problems with: brute-force solutions, branch-and-bound techniques, approximation algorithms, heuristics, and parallel algorithms
Parallel Computing
• provides high performance, better use of resources, fairness, convenience
• shared memory model
Design Problems
• making a high level sketch of a system and describing the tradeoffs, algorithms, and data structures involved
Discrete Mathematics
• invariants
Probability
• random variables
• option pricing
Programming
• bit fiddling
• arrays
• linked lists
• complexity analysis
• basics
• libraries
• building and maintaining programs
• shell tools
Interview Strategies
• clarifying the question
• working on small examples
• describing the brute-force solution
• thinking out loud
• searching for isomorphic problems
• testing for corner cases
• ensuring correct function signatures
• avoiding memory management
• checking for syntax errors
• showing that you can communicate complex ideas in simple ways
• showing your passion for the work
• demonstrating how your interests match the needs of a project
