This article is inspired by Smilence Coding Notes

String and Array

  1. Calculate each element’s frequency. We often use hash table. If the question only cares about whether an element exit or not, we can use boolean value as hash table’s value.
    • Implement an algorithm to determine if a string has all unique characters.
    • Write a method to decide if one string is a permutation of the other.
    • Given a newspaper and message as two strings, check if the message can be composed using letters in the newspaper.
    • Find a line which passes the most number of points.
  2. For each element i, we need to search all its former elements between [0,i] to build the result of element i. If we know what values we are looking for, we can use hash table to save all its former elements as keys, so that for i the search time will be O(1)
  3. The common way to generate a unique value(usually a number) of any input, which is also known as a hash value of the input, is translating the input into a m-scale(m 进制) number. The m is the number of possibilities of each cell in the hash table. During the calculation, in case of overflow, we need to mod hash table size(how many cells in the hash table), of each calculation.
    • Design a hash function that is suitable for words in a dictionary.
    • A hash function for the state of a chess game.
    • Implement a method rand7() given rand5(). (Representing a number(0 to 7) using 5-scale )
  4. **If we need to handle 2 different size array or string, we often handle the part aIndex < aSize && bIndex < bSize first, then handle whatever left array or string **
  5. If we need to update or delete elements in-place, we can use two indexes to remember original index and updated index. If the updated version’s size is bigger, we will enlarge the input size and then update elements in reverse order. If the updated version’s size is smaller, we will update elements in order, and then shrink the input size.
    • Given input “Mr John Smith”, output “Mr%20John%20Smith”
    • Given input “Mr%20John%20Smith” , output “Mr John Smith”
    • Given two sorted arrays, merge B into A in sorted order.
  6. Most of revising string problems can be resolved by one-time (in order or reverse order)traverse, the time complexity will often be O(n). The common technique is using 2 indexes, one pointing to each piece’s starting point, and one pointing to each piece’s ending point. If the question is requiring to find sub array or string, we shall think of using sliding window techinuque
  7. If the question requires constant space and you can modify input, we can always try to sort it first and use with binary search or two pointer techniques.
  8. **To get max or min value of all elements or get sum of some elements, we can update the result as we traverse all elements without traversing multiple times. **
  9. 2D array is often traversed, row by row, column by column or from outside to inside
    • Given an NxN matrix, rotate the matrix by 90 degrees.
    • If matrix[i][j] is 0, then set the entire row and column to 0.

LinkedList

  1. Most of linked list problem need to update a node, or a pair of nodes (previous node, and current node). When we traverse a linked list node, we often update one node or a pair of node per each loop
  1. When we need to modify a linked list node, most of time, we need to find its previous node and modify its previous node’s next property.
  2. When we need to swap two nodes, no matter where the two nodes’ location are, we need to update two node’s previous nodes’ next property, and then update two nodes’ next property.

Tree & Graph

  1. Subtree or subgraph’s optimal solution can induce an overall optimal solution. It is a greedy algorithm. Those problems can often use divide and conquer techniques. Sub problems are independent to each other. Subtree problem can think as we need to visit all subtrees whose tops are all nodes, to get a final result

  2. Tree path problems often use top-down traverse with backtracking to collect result. The path here is the single path, which means, each level only pass one node.

  3. Converting a tree into other data structure

  4. Find a specific node

    • To find a specific node, we will start searching along bottom-up direction. If neither a left child nor right child of a node is the specific node, we will keep looking upwards.

      • If we have a parent node, we can look up through its parent node.
        • Find the in-order successor of a given node, with parent links.
        • Find the immediate right neighbour of the given node, with parent links given, but without root node.
      • If we don’t have a parent node, we will keep looking up through backtracking.

    • To find a specific node on a BST, we can start searching along top-down direction because we can pick either left or right child branch to look up when we visit the parent.

  5. Traverse a Graph

Sorting and Searching

  1. Dynamically manage data

  2. The sorted element’s key has a range or has many duplications, or we only need sort elements partially, we can use bucket sort. Key is the index of a table. If the key’s length is limited, we can use radix sort.

  3. Scalability & Memory Limits Problems

    Those problems are often solved by divide & conquer. We can divide, or sort input into chunks, handle their result and merge all chunks result. We often use hash table to lookup each chunk.

    • Find all documents that contain a list of words
    • Design the data structures for a very large social network and an algorithm to show the connection between two people.
    • Given an input file with one billion distinct non-negative integers, provide an algorithm to generate an integer not contained in the file.Assume you have only 10MB of Memory
    • You have 10 billion URLS.How do you detect the duplicate ones?

  4. Binary Search

    For any sorted container, if its data structure can not be changed, binary search will be the most efficient way.

    Even the container is only partially sorted. We can still use binary search.

    Implement a function which takes as input a float variable x and return its square root.

  5. Quick sort partition thought is often used to group elements into 2 or 3 parts. One of its famous extension is quick select

Bit Manipulation

  1. Basic bit manipulation target is counting 1 distribution
    • ^ has two famous property, 0 ^ a = a, and a ^ a = 0
    • n & (n - 1) can clear the lowest bit of 1
    • >> is divide by 2
    • >> is multiplied by 2.

Stack And Queues

  1. If we need to use stack to access data in order, we often use two stacks in same order or in two reversed order to implement it. If the two stacks are accessing data in reversed order, we often need to dump the data between 2 stacks.
  2. If one element’s result depends on its later element, we can use stack to save the former element and fetch it until all its later elements collected to form the final result.

Dynamic Programming