Boyer–Moore majority vote algorithm

169. Majority Element
Wiki: Boyer–Moore majority vote algorithm
http://www.geeksforgeeks.org/majority-element/

findCandidate(a[], size)
1.  Initialize index and count of majority element
     maj_index = 0, count = 1
2.  Loop for i = 1 to size – 1
    (a) If a[maj_index] == a[i]
          count++
    (b) Else
        count--;
    (c) If count == 0
          maj_index = i;
          count = 1
3.  Return a[maj_index]

Fenwick (Binary Indexed) Trees

https://www.hackerearth.com/practice/data-structures/advanced-data-structures/fenwick-binary-indexed-trees/tutorial/

Trie | (Insert and Search)

http://www.geeksforgeeks.org/trie-insert-and-search/

KMP string search algorithm

https://en.wikipedia.org/wiki/Knuth–Morris–Pratt_algorithm
In computer science, the Knuth–Morris–Pratt string searching algorithm (or KMP algorithm) searches for occurrences of a "word" W within a main "text string" S by employing the observation that when a mismatch occurs, the word itself embodies sufficient information to determine where the next match could begin, thus bypassing re-examination of previously matched characters.

Preprocessing Overview (geeksforgeeks.org):

• KMP algorithm does preproceses pat[] and constructs an auxiliary lps[] of size m (same as size of pattern) which is used to skip characters while matching.
• name lps indicates longest proper prefix which is also suffix.. A proper prefix is prefix with whole string not allowed. For example, prefixes of “ABC” are “”, “A”, “AB” and “ABC”. Proper prefixes are “”, “A” and “AB”. Suffixes of the string are “”, “C”, “BC” and “ABC”.
• For each sub-pattern pat[0..i] where i = 0 to m-1, lps[i] stores length of the maximum matching proper prefix which is also a suffix of the sub-pattern pat[0..i].

     lps[i] = the longest proper prefix of pat[0..i] 
                which is also a suffix of pat[0..i]. 

The pattern is:

1. Initialization: longest prefix suffix len = 0, i =1, lps[0] = 0

2. Assume the current index is i; and lps[0,...,i-1] are known.

    the length of the previous longest prefix suffix is 

    lps[i-1] = len. That means pat[0,...,len-1] = pat[i-len,...,i-1].

3. If pat[len] == pat[i], then lps[i] = lps[i-1]+1 = len +1. 

    Continue with len = len+1 and i = i+1 and do step 3 again.

4. If then pat[len] != pat[i] 

    4.0 if len != 0. 

         4.01 Let len' = lps[len-1], 

              that means pat[0,...,len'-1] = pat[len-len',...,len-1] = pat[i-len',...,i-1].

          To find lps[i], we need to check if pat[len'] matches pat[i]. 

          4.02 if: pat[len'] == pat[i]

                  then pattern in the green boxes matches each other: 

                  pat[0,...,len'] = pat[i-len',...,i], and we get 

                  lps[i] = len' + 1 = lps[len-1] +1.

          4.03 else: pat[len'] != pat[i]

                  repeat step 4.01 and 4.02 as: 

                  assume len'' = lps[len'-1], check if pat[len''] matches pat[i].

           Note that steps 4.01, 4.02 and 4.03 is just a repeat of steps 2, 3, 4.

     4.1 if len == 0.

           lps[i] = 0, i = i+1 and do step 3 and 4 again.

The code to get lps[] 

(http://www.geeksforgeeks.org/searching-for-patterns-set-2-kmp-algorithm/)

// Fills lps[] for given patttern pat[0..M-1] void computeLPSArray(char *pat, int M, int *lps) { // length of the previous longest prefix suffix int len = 0; lps[0] = 0; // lps[0] is always 0 // the loop calculates lps[i] for i = 1 to M-1 int i = 1; while (i < M) { if (pat[i] == pat[len]) { len++; lps[i] = len; i++; } else // (pat[i] != pat[len]) { // This is tricky. Consider the example. // AAACAAAA and i = 7. The idea is similar // to search step. if (len != 0) { len = lps[len-1]; // Also, note that we do not increment // i here } else // if (len == 0) { lps[i] = 0; i++; } } } }

Tree traversal

Depth first search:
  pre-order, implementation

1. Check if the current node is empty / null.
2. Display the data part of the root (or current node).
3. Traverse the left subtree by recursively calling the pre-order function.
4. Traverse the right subtree by recursively calling the pre-order function

preorder(node) if (node = null) return visit(node) preorder(node.left) preorder(node.right)

iterativePreorder(node) if (node = null) return s ← empty stack s.push(node) while (not s.isEmpty()) node ← s.pop() visit(node) //right child is pushed first so that left is processed first if (node.right ≠ null) s.push(node.right) if (node.left ≠ null) s.push(node.left)

  in-order, implementation

1. Check if the current node is empty / null.
2. Traverse the left subtree by recursively calling the in-order function.
3. Display the data part of the root (or current node).
4. Traverse the right subtree by recursively calling the in-order function.

inorder(node) if (node = null) return inorder(node.left) visit(node) inorder(node.right)

iterativeInorder(node) s ← empty stack while (not s.isEmpty() or node ≠ null) if (node ≠ null) s.push(node) node ← node.left else node ← s.pop() visit(node) node ← node.right

  post-order, implementation

1. Check if the current node is empty / null.
2. Traverse the left subtree by recursively calling the post-order function.
3. Traverse the right subtree by recursively calling the post-order function.
4. Display the data part of the root (or current node).

postorder(node) if (node = null) return postorder(node.left) postorder(node.right) visit(node)

iterativePostorder(node) s ← empty stack lastNodeVisited ← null while (not s.isEmpty() or node ≠ null) if (node ≠ null) s.push(node) node ← node.left else peekNode ← s.peek() // if right child exists and traversing node // from left child, then move right if (peekNode.right ≠ null and lastNodeVisited ≠ peekNode.right) node ← peekNode.right else visit(peekNode) lastNodeVisited ← s.pop()

Breadth-first search:

  queue based:

levelorder(root)
  q ← empty queue
  q.enqueue(root)
  while (not q.isEmpty())
    node ← q.dequeue()
    visit(node)
    if (node.left ≠ null)
      q.enqueue(node.left)
    if (node.right ≠ null)
      q.enqueue(node.right)