This gist lists the things important for preparing a technical interview.

Algorithm Tips.md

• Consider using HashMap when comparing two strings or arrays.
• When handling string problems, ask if it is ASCII. Use an array of length 256 if it is.
• When comparing two strings or arrays, sort them first.
• Using StringBuffer for the temporary result for string concatenate.
• Prepend a dummy node for linked list problems.
• Remember integer might be negative!
• Computer cannot accurately represent float/double, use epsilon for equality check.

Common tricks:

• Interval intersection: 1) sort by start point, binary search the end point 2) sort both start and end points, go through the array, for start point i++, for end point i--.
• For interval scheduling, use greedy algorithm: earliest time first.
• Median for a random generated integer stream, using a min and a max heap.
• For kth smalless element, using the quicksort partition or a k maxheap.
• Consider suffix tree or trie, when dealing with string match problems.
• Consider segment tree, when needs preprocessor and min/max value in a range.
• Randomly generate m elements from array of n, using the array shuffle algorithm.
• Preoder, inorder, postorder tree traverse, using a stack and another pointer to remember what is the prev node.
• If elements have slightly difference with other, construct a graph and find the hamilton cycle or Eulerian cycle.
• When looking for string with the same characters, sort the string first.

Common Mistakes.md

• While we can use DP or Kadane's algorithm to get the maximum subarray, it cannot be used directly for minimum subarray. It can be used by changing the sign, find the maximum and change the sign back.

Interview Tips.md

• When finish writing code in an interview, "run" (or walk through) the code to test it.
• Tell the interviewer if previously heard the problem.
• Review the preparation grid for behavioral questions

Resume Tips.md

• Keep the resume to one page
• Write strong bullets for employment history
• List most languages you've used, but add your experience level.
• For US positions, do not include age, marital status, or nationality.

Summary.md

Data Structures

• HashMap
• Heap/PriorityQueue

Strategies

• Binary search: achieve log(n) complexity
• Dynamic programming
• Greedy
• Backtracing

Common tricks

• Leetcode Two Sum: use a hash map to keep already traversed values.
• Leetcode Median of Two Sorted Arrays: binary search(a lot of special cases), find the kth smallest number.
• Leetcode Longest Substring Without Repeating Characters: for continuous subsequence problem, consider using two index pointer, one for current and the other for a previous location.
• Leetcode Add Two Numbers: make code as consice as possible for easy problem.
• Leetcode Longest Palindromic Substring: a palindromic can be validated from ends to center, and also can be expaned from center to ends.
• Leetcode ZigZag Conversion: pay attention to nRows == 1.
• Leetcode Palindrome Number: consider integer overflow.
• Leetcode Container With Most Water: shrink from two ends.
• Leetcode 3Sum: to remove duplicates, sort the array and skip the element if it is equal to the previous one.
• Leetcode Valid Parentheses: to use O(1) space, encode (), [] and {} to 1,-1, 2,-2, 3,-3 and do the arithmetic.
• Leetcode Merge k Sorted Lists: use PriorityQueue(reuse the lists for O(1) space), or use merge sort(two each, O(nlgk) time).
• Leetcode Divide Two Integers: binary search.
• Leetcode Next Permutation: iterate from the end, find the first decrease pair, iterate from back to find the first number that is greater than the decreased number, swap, and reverse the tailing numbers.
• Leetcode Longest Valid Parentheses: 1) use a stack to keep the index of '(', and a variable to keep the last unmatched ')'. For each match, calculate the length. 2) DP, from the end, calculate the length of valid parentheses starting with the character at i.
• Leetcode Search for a Range: binary search for the lower and upper bounds respectively.
• Leetcode Trapping Rain Water: for each bar, the amount of water it can contains is min(lefthighest, righthighest) - itsheight. Traverse the array to save the left highest for each bar and then go from the right handside.
• Leetcode Multiply Strings: allocate a integer array of length m1+m2, multiple the first mulitpler to each digit in the second and add up the result to the array. Carry and don't forget to remove leading 0s.
• [Cracking interview 18.1 adds number without arithmetic]: and and xor.
• Leetcode Wildcard Matching: remember the previous '*', go back whenever a mismatch is found.
• Leetcode Jump Game II: remember the current and previous positions, for each move, go through the values from previous to current and choose the max position as the next position.
• Leetcode Permutations II: use a HashMap to remember the integer that is already swapped.
• Leetcode Anagrams: to compare if two strings have the same characters, sort the characters in the string and check if they are the same.
• Leetcode Pow(x, n): square of Pow(x, n/2). Consider n is negative.
• Leetcode N-Queens: in a matrix, use abs(x1-x2) == abs(y1-y2) to check if two are on the same diagonal.
• Leetcode N-Queens II: use bits to save the information, one for which columns are occupied, one for left diagonal(just keep the occupied columns on the current row) and one for right diagonal. Move row by row, ld<<1, rd>>1.
• Leetcode Permutation Sequence: don't generate the permutation one by one, but get it by calculating the number or permutations.
• Leetcode Unique Paths: only one dimension array is needed. Don't need M*N extra space.
• Leetcode Valid Number: use a two-dimensional array to keep the state transition of the finite automata.
• Leetcode Sqrt(x): binary search may have overflow problem.
• Leetcode Climbing Stairs: fibanacci numbers.
• Leetcode Edit Distance: dynamic programming.
• Leetcode Minimum Window Substring: use a integer to save unmatched characters, a HashMap to save count of each characters in T. Use two pointer, once unmatched characters is 0, move the left one until unmatched number is 1.
• Leetcode Largest Rectangle in Histogram: for each height, check the area which takes it as the shortest height. So we need to know the index which is shorter on its left and right. Use a stack to keep an increase list from the beginning.
• Leetcode Maximal Rectangle: find the maximal rectange with each row as the bottom, so the problem is reduced to the problem of Rectangle in Histogram.
• Leetcode Scramble String: 3-dimension dynamic programming.
• Leetcode Gray Code: prepand 1 to f(n-1).
• Leetcode Restore IP Addresses: backtracing. Pay attention to string length and index out of bound exception.
• Leetcode Binary Tree Inorder Traversal: using a stack and push null value. Or using a prev pointer to decide whether going down or up.
• Leetcode Recover Binary Search Tree: use three pointers: prev node, the first swapped node t1 and the second swapped node t2. Do an inorder search to find t1 and t2.
• Leetcode Symmetric Tree: recursive way is easy. Iterative ways: two stacks with inorder traversal and level traversal.
• Leetcode Convert Sorted List to Binary Search Tree: construct the tree from bottom to up. advance the pointer from head to tail one by one.
• Leetcode Distinct Subsequences: dyanmic programming. M[i][0] should be 1.
• Leetcode Best Time to Buy and Sell Stock III: use two arrays, one records the maxProfit from 0 to ith element, the other records the maxProfit from ith element to the end. Find the max for left[i] + right[i].
• Leetcode Binary Tree Maximum Path Sum: maximum path could be in the left subtree, right subtree, or across the root node.
• Leetcode Longest Consecutive Sequence: use a HashMap to keep all elements. Go through every element and check if its neighbors exist.
• Leetcode Surrounded Regions: scan each edge for 'O', go from each 'O' to find the live path. Scan the whole matrix, flip the 'O' which is not alive.
• Leetcode Gas Station: scan the array once. Total to record the total remaning gas. Sum to record the remaining from the current start. if Sum < 0, pick next station and start.
• Leetcode Candy: initial each child as 1. Go from front to end, if ratings[i+1] > ratings[i], set candy[i] = candy[i-1]+1; go from end to front and do the same thing.
• Leetcode Single Number: xor.
• Leetcode Single Number II: 1 appear once and twices. http://www.cnblogs.com/daijinqiao/p/3352893.html.
• Leetcode Copy List with Random Pointer: add the copied node after the original one and traverse three times. Pay attention to the null pointer.
• Leetcode Linked List Cycle: slow and fast pointers. Pay attention to null pointer.
• Leetcode Linked List Cycle II: check if it has cycle using slow and fast runner. Move slow to head and advance both pointers.
• Leetcode Binary Tree Postorder Traversal: stack with a prev pointer.
• Leetcode LRU Cache: use a double linked list and a hash map.
• Leetcode Insertion Sort List: compare with previous nodes from head to current, instead of from current back to head.
• Leetcode Max Points on a Line: check if three points on the same line, don't use slope. Pay attention, default number is 2.

Mistake

• When dealing with arrays, pay attention to empty array and index out of bound cases.
• When dealing with two arrays or linked list, consider the case that one is shorter and don't forget the carry value after the loop.
• For easy problem, pay attention to special/base cases.
• When dealing with integers in string representation, consider leading 0s and overflow problems.
• Regular expression matching, don't forget the "a*" in the pattern.
• Don't forget to increase/decrease index in the loop.
• When dealing integer division, consider the negative case.
• When get the permutation or combination of a collection, don't forget to avoid duplications.
• When dealing with multiplication, mod and power, don't forget negative integers.
• When traversing a binary tree using stack, don't forget to push right before left.

TODO

• String matching algorithms: KMP, BM and etc.

Technical Concepts.md

Should get familar with the following concepts and practise again and again.

Data Structure

• Binary search tree (E extends Comparable, null check for min() and max())
• Hash table implementing using array and binary search tree. (Generic, load factor and rehash)
• Linked list (inner Node class as static)
• Stack using array and linked list
• Queue using array and linked list (font/rare set to 0 at start, isFull() and isEmpty(), circular)
• Tree
• Graph (adjacency list vs adjacency matrix, store vertices in hashmap)
• In-order, pre-order, post-order and level-order tree traversal (pre-order and post-order cannot recover the tree)
• Red-Black trees and AVL trees (AVL slow insertion/removal, but fast search. Rotation)
• Tries (prefix tree, have multiple children)
• Graph traversal: breadth first search and depth first search (Queue for BFS, stack/recursion for DFS. DONOT pop in DFS if need to handle children first)
• Bit manipulation (Get, set, clear and update bit)
• Power of 2 table

Object-Oriented Design

• Singleton Pattern (static getInstance(), thread-safe)
• Factory Method Pattern (create instance based on type, defer creation to subclass)

Algorithm

• Resursion
• Dynamic Programming
• Merge sort (recursive sort and merge)
• Quicksort
• Bucket Sort (divide into several buckets and sort each one)
• Bubble sort
• Selection sort
• Raidx sort (buckets, sort from the least significant digit)
• Heapsort (siftDown, heapify and sort)
• Binary search
• String match algorithms