Chapter 10: Heap Algorithm from Elements of Programming Interviews

K Stars
  public static ArrayList<Star> findClosestKStars(InputStream sin, int k) {
    // Use maxHeap to find the closest k stars.
    PriorityQueue<Star> maxHeap = new PriorityQueue<Star>();
    try {
      ObjectInputStream osin = new ObjectInputStream(sin);

      // Record the first k stars.
      while (true) {
        Star s = (Star) osin.readObject();

        if (maxHeap.size() == k) {
          // Compare the top of heap with the incoming star.
          Star farStar = maxHeap.peek();
          if (s.compareTo(farStar) < 0) {
            maxHeap.remove();
            maxHeap.add(s);
          }
        } else {
          maxHeap.add(s);
        }
      }
    } catch (IOException e) {
      // Do nothing, was read last element in stream
    } catch (ClassNotFoundException e) {
      System.out.println("ClassNotFoundException: " + e.getMessage());
    }

    // Store the closest k stars.
    ArrayList<Star> closestStars = new ArrayList<Star>();
    while (!maxHeap.isEmpty()) {
      closestStars.add(maxHeap.remove());
    }
    return closestStars;
  }

Almost sorted: at most k positions away
ApproximateSort
  public static void approximateSort(InputStream sin, int k) {
    PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();
    try {
      ObjectInputStream osin = new ObjectInputStream(sin);
      // Firstly push k elements into minHeap.
      for (int i = 0; i < k; ++i) {
        minHeap.add((Integer) osin.readObject());
      }

      // Extract the minimum one for every incoming element.
      while (true) {
        minHeap.add((Integer) osin.readObject());
        System.out.println(minHeap.remove());
      }
    } catch (IOException e) {
      // Do nothing, was read last element in stream
    } catch (ClassNotFoundException e) {
      System.out.println("ClassNotFoundException: " + e.getMessage());
    }

    // Extract the remaining elements in minHeap.
    while (!minHeap.isEmpty()) {
      System.out.println(minHeap.remove());
    }
  }
K elements closes to median of array
  public static List<Integer> findKClosestToMedian(List<Integer> a, int k) {
    // Find the element i where |a[i] - median| is k-th smallest.
    final double m = findMedian(a);
    nthElement(a, k - 1, new Comparator<Integer>() {
      @Override
      public int compare(Integer a, Integer b) {
        return Double.valueOf(Math.abs(a - m)).compareTo(Math.abs(b - m));
      }
    });
    return new ArrayList<Integer>(a.subList(0, k));
  }
==> How to Comparator
  public static void onlineMedian(InputStream sin) {
    // Min-heap stores the bigger part of the stream.
    PriorityQueue<Integer> H = new PriorityQueue<Integer>();
    // Max-heap stores the smaller part of the stream.
    PriorityQueue<Integer> L = new PriorityQueue<Integer>(11,
        new Comparator<Integer>() {
          @Override
          public int compare(Integer o1, Integer o2) {
            return o2.compareTo(o1);
          }
        });

    Scanner s = new Scanner(sin);
    while (s.hasNextInt()) {
      int x = s.nextInt();
      if (!L.isEmpty() && x > L.peek()) {
        H.add(x);
      } else {
        L.add(x);
      }
      if (H.size() > L.size() + 1) {
        L.add(H.remove());
      } else if (L.size() > H.size() + 1) {
        H.add(L.remove());
      }

      if (H.size() == L.size()) {
        System.out.println(0.5 * (H.peek() + L.peek()));
      } else {
        System.out.println((H.size() > L.size() ? H.peek() : L.peek()));
      }
    }
  }

GeneratingABSqrt2
  public static ArrayList<Num> generateFirstK(int k) {
    PriorityQueue<Num> minHeap = new PriorityQueue<Num>();
    ArrayList<Num> smallest = new ArrayList<Num>();
    HashSet<Num> hash = new HashSet<Num>();

    // Initial for 0 + 0 * sqrt(2).
    minHeap.add(new Num(0, 0));
    hash.add(new Num(0, 0));

    while (smallest.size() < k) {
      Num s = minHeap.remove();
      smallest.add(s);
      hash.remove(s);

      // Add the next two numbers derived from s.
      Num c1 = new Num(s.a + 1, s.b);
      Num c2 = new Num(s.a, s.b + 1);
      if (hash.add(c1)) {
        minHeap.add(c1);
      }
      if (hash.add(c2)) {
        minHeap.add(c2);
      }
    }
    return smallest;
  }

  public static List<Num> generateFirstK(int k) {
    List<Num> res = new ArrayList<Num>(); // stores the first-k Num.
    res.add(new Num(0, 0));
    int i = 0, j = 0;
    for (int n = 0; n < k; ++n) {
      Num x = new Num(res.get(i).a + 1, res.get(i).b);
      Num y = new Num(res.get(j).a, res.get(j).b + 1);
      if (x.val < y.val) {
        ++i;
        res.add(x);
      } else if (x.val > y.val) {
        ++j;
        res.add(y);
      } else { // x == y.
        ++i;
        ++j;
        res.add(x);
      }
    }
    return res;
  }
Compare Kth Largest In Heap: can't modify heap
  private static void compareKthLargestHeapHelper(List<Integer> maxHeap, int k,
      int x, int idx, Data data) {
    if (data.larger >= k || idx >= maxHeap.size() || maxHeap.get(idx) < x) {
      return;
    } else if (maxHeap.get(idx) == x) {
      if (++data.equal >= k) {
        return;
      }
    } else { // max_heap[idx] > x.
      ++data.larger;
    }
    compareKthLargestHeapHelper(maxHeap, k, x, (idx << 1) + 1, data);
    compareKthLargestHeapHelper(maxHeap, k, x, (idx << 1) + 2, data);
  }

  // -1 means smaller, 0 means equal, and 1 means larger.
  public static int compareKthLargestHeap(List<Integer> maxHeap, int k, int x) {
    Data data = new Data();
    data.larger = 0;
    data.equal = 0;
    compareKthLargestHeapHelper(maxHeap, k, x, 0, data);
    return data.larger >= k ? 1 : (data.larger + data.equal >= k ? 0 : -1);
  }

Chapter 9: Tree Algorithm from Elements of Programming Interviews

Inorder Traversal With Parent Node
  public static <T> void inOrderTraversal(BinaryTree<T> r) {
    // Empty tree.
    if (r == null) {
      return;
    }

    BinaryTree<T> prev = null, curr = r, next;
    while (curr != null) {
      if (prev == null || prev.getLeft() == curr || prev.getRight() == curr) {
        if (curr.getLeft() != null) {
          next = curr.getLeft();
        } else {
          System.out.println(curr.getData());
          next = (curr.getRight() != null ? curr.getRight() : curr.getParent());
        }
      } else if (curr.getLeft() == prev) {
        System.out.println(curr.getData());
        next = (curr.getRight() != null ? curr.getRight() : curr.getParent());
      } else {
        next = curr.getParent();
      }

      prev = curr;
      curr = next;
    }
  }

Find Kth node with size field
  public static <T> BinaryTree<T> findKthNodeBinaryTree(BinaryTree<T> root,
      int k) {
    BinaryTree<T> n = root;
    while (n != null) {
      int leftSize = n.getLeft() != null ? n.getLeft().getSize() : 0;
      if (leftSize < k - 1) {
        k -= (leftSize + 1);
        n = n.getRight();
      } else if (leftSize == k - 1) {
        return n;
      } else { // leftSize > k - 1.
        n = n.getLeft();
      }
    }
    throw new RuntimeException("no k-th node in binary tree");
  }

Reconstruct Binary Tree PreInOrders
  public static <T> BinaryTree<T> reconstructPreInOrders(ArrayList<T> pre,
      ArrayList<T> in) {
    return reconstructPreInOrdersHelper(pre, 0, pre.size(), in, 0, in.size());
  }
 
  private static <T> BinaryTree<T> reconstructPreInOrdersHelper(
      ArrayList<T> pre, int preS, int preE, ArrayList<T> in, int inS, int inE) {
    if (preE > preS && inE > inS) {
      int it = in.subList(inS, inE).indexOf(pre.get(preS));
      it = it < 0 ? inE : (it + inS);
      int leftTreeSize = it - inS;

      return new BinaryTree<T>(pre.get(preS), reconstructPreInOrdersHelper(pre,
          preS + 1, preS + 1 + leftTreeSize, in, inS, it),
          reconstructPreInOrdersHelper(pre, preS + 1 + leftTreeSize, preE, in,
              it + 1, inE));
    }
    return null;
  }

Reconstruct Binary Tree Post InOrders
  private static <T> BinaryTree<T> reconstructPostInOrdersHelper(
      ArrayList<T> post, int postS, int postE, ArrayList<T> in,
          int inS, int inE) {
    if (postE > postS && inE > inS) {
      int it = in.subList(inS, inE).indexOf(post.get(postE - 1));
      it = it < 0 ? inE : (it + inS);
      int leftTreeSize = it - inS;
      return new BinaryTree<T>(post.get(postE - 1),
      // Recursively build the left subtree.
          reconstructPostInOrdersHelper(post, postS, postS + leftTreeSize, in,
              inS, it),
          // Recursively build the right subtree.
          reconstructPostInOrdersHelper(post, postS + leftTreeSize, postE - 1,
              in, it + 1, inE));
    }
    return null;
  }

  public static <T> BinaryTree<T> reconstructPostInOrders(ArrayList<T> post,
      ArrayList<T> in) {
    return reconstructPostInOrdersHelper(post, 0, post.size(), in, 0, in.size());
  }

Reconstruct Preorder With Null for empty children
  public static <T> BinaryTree<T> reconstructPreorder(ArrayList<T> preorder) {
    LinkedList<BinaryTree<T>> s = new LinkedList<BinaryTree<T>>();
    for (int i = preorder.size() - 1; i >= 0; i--) {
      if (preorder.get(i) == null) {
        s.push(null);
      } else {
        BinaryTree<T> l = s.pop();
        BinaryTree<T> r = s.pop();
        s.push(new BinaryTree<T>(preorder.get(i), l, r));
      }
    }
    return s.peek();
  }
Connect Leaves Binary Tree
  private static <T> void connectLeavesHelper(BinaryTree<T> n,
      ArrayList<BinaryTree<T>> L) {
    if (n != null) {
      if (n.getLeft() == null && n.getRight() == null) {
        L.add(n);
      } else {
        connectLeavesHelper(n.getLeft(), L);
        connectLeavesHelper(n.getRight(), L);
      }
    }
  }

Exterior Binary Tree - todo
  private static <T> void leftBoundaryBTree(BinaryTree<T> n, boolean isBoundary) {
    if (n != null) {
      if (isBoundary || (n.getLeft() == null && n.getRight() == null)) {
        System.out.print(n.getData() + " ");
      }
      leftBoundaryBTree(n.getLeft(), isBoundary);
      leftBoundaryBTree(n.getRight(), isBoundary && n.getLeft() == null);
    }
  }

  private static <T> void rightBoundaryBTree(
      BinaryTree<T> n, boolean isBoundary) {
    if (n != null) {
      rightBoundaryBTree(n.getLeft(), isBoundary && n.getRight() == null);
      rightBoundaryBTree(n.getRight(), isBoundary);
      if (isBoundary || (n.getLeft() == null && n.getRight() == null)) {
        System.out.print(n.getData() + " ");
      }
    }
  }

  public static <T> void exteriorBinaryTree(BinaryTree<T> root) {
    if (root != null) {
      System.out.print(root.getData() + " ");
      leftBoundaryBTree(root.getLeft(), true);
      rightBoundaryBTree(root.getRight(), true);
    }
  }
 
Lowest common ancestor without parent node
  public static <T> BinaryTree<T> LCA(BinaryTree<T> n, BinaryTree<T> a,
      BinaryTree<T> b) {
    if (n == null) { // empty subtree.
      return null;
    } else if (n == a || n == b) {
      return n;
    }

    BinaryTree<T> lRes = LCA(n.getLeft(), a, b), rRes = LCA(n.getRight(), a, b);
    if (lRes != null && rRes != null) {
      return n;
    } else {
      return lRes != null ? lRes : rRes;
    }
  }

Lowest common ancestor with parent node
  private static <T> int getDepth(BinaryTree<T> n) {
    int d = 0;
    while (n != null) {
      ++d;
      n = n.getParent();
    }
    return d;
  }

  public static <T> BinaryTree<T> LCA(BinaryTree<T> i, BinaryTree<T> j) {
    int depthI = getDepth(i), depthJ = getDepth(j);
    if (depthJ > depthI) {
      BinaryTree<T> temp = i;
      i = j;
      j = temp;
    }

    // Advance deeper node first.
    int depthDiff = Math.abs(depthI - depthJ);
    while (depthDiff-- > 0) {
      i = i.getParent();
    }

    // Both pointers advance until they found a common ancestor.
    while (i != j) {
      i = i.getParent();
      j = j.getParent();
    }
    return i;
  }

LowestCommonAncestorHash
  public static <T> BinaryTree<T> LCA(BinaryTree<T> i, BinaryTree<T> j) {
    HashSet<BinaryTree<T>> hash = new HashSet<BinaryTree<T>>();
    while (i != null || j != null) {
      if (i != null) {
        if (hash.add(i) == false) {
          return i; // adds a failed because a exists in hash.
        }
        i = i.getParent();
      }
      if (j != null) {
        if (hash.add(j) == false) {
          return j; // adds a failed because a exists in hash.
        }
        j = j.getParent();
      }
    }
    // Throw error if a and b are not in the same tree.
    throw new RuntimeException("a and b are not in the same tree");
  }
Shortest Unique Prefix
    public String getShortestUniquePrefix(String s) {
      TrieNode p = root;
      StringBuilder prefix = new StringBuilder();
      for (char c : s.toCharArray()) {
        prefix.append(c);
        if (!p.getLeaves().containsKey(c)) {
          return prefix.toString();
        }
        p = p.getLeaves().get(c);
      }
      return "";
    }
  public static String findShortestPrefix(String s, HashSet<String> D) {
    // Build a trie according to given dictionary D.
    Trie T = new Trie();
    for (String word : D) {
      T.insert(word);
    }
    return T.getShortestUniquePrefix(s);
  }

Chapter 8: Stack and Queue Algorithm from Elements of Programming Interviews

RPN
  public static int eval(String s) {
    LinkedList<Integer> evalStack = new LinkedList<Integer>();
    String[] symbols = s.split(",");
    for (String symbol : symbols) {
      if (symbol.length() == 1 && "+-*/".contains(symbol)) {
        int y = evalStack.pop();
        int x = evalStack.pop();
        switch (symbol.charAt(0)) {
        case '+':
          evalStack.push(x + y);
          break;
        case '-':
          evalStack.push(x - y);
          break;
        case '*':
          evalStack.push(x * y);
          break;
        case '/':
          evalStack.push(x / y);
          break;
        default:
          throw new IllegalArgumentException("Malformed RPN at :" + symbol);
        }
      } else { // number.
        evalStack.push(Integer.parseInt(symbol));
      }
    }
    return evalStack.pop();
  }

Search Postings List
  private static int searchPostingsListHelper(PostingListNode L, int order) {
    if (L != null && L.getOrder() == -1) {
      L.setOrder(order++);
      order = searchPostingsListHelper(L.getJump(), order);
      order = searchPostingsListHelper(L.getNext(), order);
    }
    return order;
  }

  public static void searchPostingsList(PostingListNode L) {
    searchPostingsListHelper(L, 0);
  }

  public static void searchPostingsList(PostingListNode L) {
    LinkedList<PostingListNode> s = new LinkedList<PostingListNode>();
    int order = 0;
    s.push(L);
    while (!s.isEmpty()) {
      PostingListNode curr = s.pop();
      if (curr != null && curr.getOrder() == -1) {
        curr.setOrder(order++);
        s.push(curr.getNext());
        s.push(curr.getJump());
      }
    }
  }
TowerHanoi - todo: iterative version
  private static void transfer(int n, ArrayList<LinkedList<Integer>> pegs,
      int from, int to, int use) {
    if (n > 0) {
      transfer(n - 1, pegs, from, use, to);
      pegs.get(to).push(pegs.get(from).pop());
      System.out.println("Move from peg " + from + " to peg " + to);
      transfer(n - 1, pegs, use, to, from);
    }
  }

  public static void moveTowerHanoi(int n) {
    ArrayList<LinkedList<Integer>> pegs = new ArrayList<LinkedList<Integer>>();
    for (int i = 0; i < 3; i++) {
      pegs.add(new LinkedList<Integer>());
    }

    // Initialize pegs.
    for (int i = n; i >= 1; --i) {
      pegs.get(0).push(i);
    }

    transfer(n, pegs, 0, 1, 2);
  }

ViewSunset
Stream from East to West
  public static <T extends Comparable<T>> LinkedList<Pair<Integer, T>>
      examineBuildingsWithSunset( InputStream sin) {
    int idx = 0; // building's index.
    T height;
    // Stores (building_idx, building_height) pair with sunset views.
    LinkedList<Pair<Integer, T>> buildingsWithSunset = new LinkedList<>();
    try {
      ObjectInputStream osin = new ObjectInputStream(sin);
      while (true) {
        height = (T) osin.readObject();
        while (!buildingsWithSunset.isEmpty()
            && height.compareTo(buildingsWithSunset.getLast().getSecond()) >= 0) {
          buildingsWithSunset.removeLast();
        }
        buildingsWithSunset.addLast(new Pair<Integer, T>(idx++, height));
      }
    } catch (ClassNotFoundException e) {
      System.out.println(e.getMessage());
    } catch (IOException e) {
      // Catching when there no more objects in InputStream
    }
    return buildingsWithSunset;
  }

Sort a Stack
  private static <T extends Comparable<T>> void insert(LinkedList<T> S, T e) {
    if (S.isEmpty() || S.peek().compareTo(e) <= 0) {
      S.push(e);
    } else {
      T f = S.pop();
      insert(S, e);
      S.push(f);
    }
  }

  public static <T extends Comparable<T>> void sort(LinkedList<T> S) {
    if (!S.isEmpty()) {
      T e = S.pop();
      sort(S);
      insert(S, e);
    }
  }

Normalized Path names
  public static String normalizedPathNames(String path) {
    LinkedList<String> s = new LinkedList<String>(); // Use LinkedList as a
                                                     // stack.
    // Special case: starts with "/", which is an absolute path.
    if (path.startsWith("/")) {
      s.push("/");
    }
    for (String token : path.split("/")) {
      if (token.equals("..")) {
        if (s.isEmpty() || s.peek().equals("..")) {
          s.push(token);
        } else {
          if (s.peek().equals("/")) {
            throw new RuntimeException("Path error");
          }
          s.pop();
        }
      } else if (!token.equals(".") && !token.isEmpty()) { // name.
        for (char c : token.toCharArray()) {
          if (c != '.' && !Character.isDigit(c) && !Character.isLetter(c)) {
            throw new RuntimeException("Invalid directory name");
          }
        }
        s.push(token);
      }
    }
    StringBuilder normalizedPath = new StringBuilder();
    if (!s.isEmpty()) {
      Iterator<String> it = s.descendingIterator();
      String prev = it.next();
      normalizedPath.append(prev);
      while (it.hasNext()) {
        if (!prev.equals("/")) {
          normalizedPath.append("/");
        }
        prev = it.next();
        normalizedPath.append(prev);
      }
    }
    return normalizedPath.toString();
  }
Binary TreeLevel Order -- Java Queue, better use ArrayQueue
public static <T> void printBinaryTreeLevelOrder(BinarySearchTree<T> n) {
// Prevent empty tree
if (n == null) {
return;
}
LinkedList<BinarySearchTree<T>> q = new LinkedList<BinarySearchTree<T>>();
q.push(n);
int count = q.size();
while (!q.isEmpty()) {
BinarySearchTree<T> front = q.pollLast();
System.out.print(front.getData() + " ");
if (front.getLeft() != null) {
q.push(front.getLeft());
}
if (front.getRight() != null) {
q.push(front.getRight());
}
if (--count == 0) {
System.out.println();
count = q.size();
}
}
}
Circular Queue
  public static class Queue<T> {
    private int head = 0, tail = 0, count = 0;
    private Object[] data;

    public Queue(int cap) {
      data = new Object[cap];
    }

    public void enqueue(T x) {
      // Dynamically resize due to data_.size() limit.
      if (count == data.length) {
        // Rearrange elements.
        Collections.rotate(Arrays.asList(data), -head);
        head = 0;
        tail = count;
        data = Arrays.copyOf(data, count << 1);
      }
      // Perform enqueue
      data[tail] = x;
      tail = (tail + 1) % data.length;
      ++count;
    }

    public T dequeue() {
      if (count != 0) {
        --count;
        T ret = (T) data[head];
        head = (head + 1) % data.length;
        return ret;
      }
      throw new RuntimeException("empty queue");
    }

    public int size() {
      return count;
    }
  }

Queue Using Two Integers
  public static class Queue {
    private int val = 0;
    private int size = 0, maxSize = (int) Math.floor(Math
        .log10(Integer.MAX_VALUE));

    public void enqueue(int x) {
      if (size >= maxSize) {
        throw new RuntimeException("queue overflow");
      }
      val = val * 10 + x;
      ++size;
    }

    public int dequeue() {
      if (size != 0) {
        int ret = 0, d = (int) Math.floor(Math.log10(val));
        if (d + 1 == size) {
          int powVal = (int) Math.pow(10, d);
          ret = val / powVal;
          val -= powVal * ret;
        }
        --size;
        return ret;
      }
      throw new RuntimeException("empty queue");
    }
  }

Queue From Stacks
 public static class Queue<T> {
    private LinkedList<T> a = new LinkedList<T>();
    private LinkedList<T> b = new LinkedList<T>();

    public void enqueue(T x) {
      a.push(x);
    }

    public T dequeue() {
      if (b.isEmpty()) {
        while (!a.isEmpty()) {
          b.push(a.pop());
        }
      }
      if (!b.isEmpty()) {
        return b.pop();
      }
      throw new RuntimeException("empty queue");
    }
  }

Queue With Max Using Deque
  public static class Queue<T extends Comparable<T>> {
    private LinkedList<T> q = new LinkedList<T>();
    private LinkedList<T> d = new LinkedList<T>();

    public void enqueue(T x) {
      q.addFirst(x);
      while (!d.isEmpty() && d.getLast().compareTo(x) < 0) {
        d.removeLast();
      }
      d.addLast(x);
    }

    public T dequeue() {
      if (!q.isEmpty()) {
        T ret = q.removeLast();
        if (ret.equals(d.getFirst())) {
          d.removeFirst();
        }
        return ret;
      }
      throw new RuntimeException("empty queue");
    }
      public T max() {
      if (!d.isEmpty()) {
        return d.getFirst();
      }
      throw new RuntimeException("empty queue");
    }

Maximum of A Sliding Window - O(n)
  public static void trafficVolumes(List<TrafficElement> A, int w) {
    QueueWithMaxUsingDeque<TrafficElement> Q = new QueueWithMaxUsingDeque<TrafficElement>();
    for (int i = 0; i < A.size(); i++) {
      Q.enqueue(A.get(i));
      while (A.get(i).getTime() - Q.head().getTime() > w) {
        Q.dequeue();
      }
      System.out.println("Max after inserting " + i + " is "
          + Q.max().getVolume());
    }
  }

Chapter 7: LinkedList Algorithm from Elements of Programming Interviews

reverses a singly linked list:
  public static <T> Node<T> reverseLinkedList(Node<T> head) {
    if (head == null || head.next == null) {
      return head;
    }

    Node<T> newHead = reverseLinkedList(head.next);
    head.next.next = head;
    head.next = null;
    return newHead;
  }

  public static <T> Node<T> reverseLinkedList(Node<T> head) {
    Node<T> prev = null, curr = head;
    while (curr != null) {
      Node<T> temp = curr.next;
      curr.next = prev;
      prev = curr;
      curr = temp;
    }
    return prev;
  }
Write a function that returns null if there does not exist a cycle, and the reference to the start of the cycle if a cycle is present.

Copying Posting List
public static <T> PNode<T> copyPostingsList(PNode<T> l) {
// Return empty list if l is nullptr.
if (l == null) {
return null;
}

// 1st stage: Copy the nodes from l.
PNode<T> p = l;
while (p != null) {
PNode<T> temp = new PNode<T>(p.data, p.next, null);
p.next = temp;
p = temp.next;
}

// 2nd stage: Update the jump field.
p = l;
while (p != null) {
if (p.jump != null) {
p.next.jump = p.jump.next;
}
p = p.next.next;
}

// 3rd stage: Restore the next field.
p = l;
PNode<T> copied = p.next;
while (p.next != null) {
PNode<T> temp = p.next;
p.next = temp.next;
p = temp;
}
return copied;
}

 
  static void rotateMatrix(int[][] A) {
    for (int i = 0; i < (A.length >> 1); ++i) {
      for (int j = i; j < A.length - i - 1; ++j) {
        int temp = A[i][j];
        A[i][j] = A[A.length - 1 - j][i];
        A[A.length - 1 - j][i] = A[A.length - 1 - i][A.length - 1 - j];
        A[A.length - 1 - i][A.length - 1 - j] = A[j][A.length - 1 - i];
        A[j][A.length - 1 - i] = temp;
      }
    }
  }

 
CheckingCycle
class CheckingCycle {
// @include
  public static <T> Node<T> hasCycle(Node<T> head) {
    Node<T> fast = head;
    Node<T> slow = head;

    while (slow != null && slow.next != null && fast != null
        && fast.next != null && fast.next.next != null) {
      slow = slow.next;
      fast = fast.next.next;
      if (slow == fast) { // there is a cycle.
        // Calculates the cycle length.
        int cycleLen = 0;
        do {
          ++cycleLen;
          fast = fast.next;
        } while (slow != fast);

        // Tries to find the start of the cycle.
        slow = head;
        fast = head;
        // Fast pointer advances cycleLen first.
        while (cycleLen-- > 0) {
          fast = fast.next;
        }
        // Both pointers advance at the same time.
        while (slow != fast) {
          slow = slow.next;
          fast = fast.next;
        }
        return slow; // the start of cycle.
      }
    }
    return null; // no cycle.
  }
MedianSorted CircularLinkedList
  public static double findMedianSortedCircularLinkedList(Node<Integer> rNode) {
    if (rNode == null) {
      // no node in this linked list.
      throw new IllegalArgumentException("empty list");
    }

    // Checks all nodes are identical or not and identify the start of list.
    Node<Integer> curr = rNode;
    Node<Integer> start = rNode;
    int count = 0;
    do {
      ++count;
      curr = curr.next;
      // start will point to the largest element in the list.
      if (start.data.compareTo(curr.data) <= 0) {
        start = curr;
      }
    } while (curr != rNode);
    // start's next is the begin of the list.
    start = start.next;

    // Traverses to the middle of the list and return the median.
    for (int i = 0; i < ((count - 1) >> 1); ++i) {
      start = start.next;
    }
    return (count & 1) != 0 ? start.data : 0.5 * (start.data + start.next.data);
  }
OverlappingLists
  public static <T> Node<T> overlappingLists(Node<T> L1, Node<T> L2) {
    // Store the start of cycle if any.
    Node<T> s1 = CheckingCycle.hasCycle(L1), s2 = CheckingCycle.hasCycle(L2);

    if (s1 == null && s2 == null) {
      return OverlappingListsNoCycle.overlappingNoCycleLists(L1, L2);
    } else if (s1 != null && s2 != null) { // both lists have cycles.
      Node<T> temp = s2;
      do {
        temp = temp.next;
      } while (temp != s1 && temp != s2);
      return (temp == s1) ? s1 : null;
    }
    return null; // one list has cycle, and one list has no cycle.
  }
Reverse LinkedList
  public static <T> Node<T> reverseLinkedList(Node<T> head) {
    if (head == null || head.next == null) {
      return head;
    }

    Node<T> newHead = reverseLinkedList(head.next);
    head.next.next = head;
    head.next = null;
    return newHead;
  }

  public static <T> Node<T> reverseLinkedList(Node<T> head) {
    Node<T> prev = null, curr = head;
    while (curr != null) {
      Node<T> temp = curr.next;
      curr.next = prev;
      prev = curr;
      curr = temp;
    }
    return prev;
  }
Palindrome LinkedList
  public static <T> boolean isLinkedListAPalindrome(Node<T> L) {
    // Find the middle point of L if L is odd length,
    // and right-middle point if L is even length.
    Node<T> slow = L, fast = L;
    while (fast != null) {
      fast = fast.next;
      if (fast != null) {
        fast = fast.next;
        slow = slow.next;
      }
    }

    // Compare the first half and reversed second half lists.
    Node<T> reverse = ReverseLinkedListIterativeTemplate
        .reverseLinkedList(slow);
    while (reverse != null && L != null) {
      if (reverse.data != L.data) {
        return false;
      }
      reverse = reverse.next;
      L = L.next;
    }
    return true;
  }
ZippingList
  public static <T> Node<T> zippingLinkedList(Node<T> L) {
    Node<T> slow = L, fast = L, preSlow = null;

    // Find the middle point of L.
    while (fast != null) {
      fast = fast.next;
      if (fast != null) {
        preSlow = slow;
        fast = fast.next;
        slow = slow.next;
      }
    }

    if (preSlow == null) {
      return L; // only contains one node in the list.
    }
    preSlow.next = null; // splits the list into two lists.
    Node<T> reverse = ReverseLinkedListIterativeTemplate
        .reverseLinkedList(slow);
    Node<T> curr = L;

    // Zipping the list.
    while (curr != null && reverse != null) {
      Node<T> temp = curr.next;
      curr.next = reverse;
      curr = temp;
      // Connect curr->next to reverse, and advance curr.
      // connectANextToBAdvanceA(ref_curr, reverse);
      if (curr != null) {
        // Connect reverse->next to curr, and advance reverse.
        Node<T> temp2 = reverse.next;
        reverse.next = curr;
        reverse = temp2;
        // connectANextToBAdvanceA(ref_reverse, curr);
      }
    }

    return L;
  }
Copying Postings List
public static <T> PNode<T> copyPostingsList(PNode<T> l) {
// Return empty list if l is nullptr.
if (l == null) {
return null;
}

// 1st stage: Copy the nodes from l.
PNode<T> p = l;
while (p != null) {
PNode<T> temp = new PNode<T>(p.data, p.next, null);
p.next = temp;
p = temp.next;
}

// 2nd stage: Update the jump field.
p = l;
while (p != null) {
if (p.jump != null) {
p.next.jump = p.jump.next;
}
p = p.next.next;
}

// 3rd stage: Restore the next field.
p = l;
PNode<T> copied = p.next;
while (p.next != null) {
PNode<T> temp = p.next;
p.next = temp.next;
p = temp;
}
return copied;
}

Chapter 6: String Algorithm From Elements of Programming Interviews

 Run Length Encoding
   static String decoding(String s) {
    int count = 0;
    StringBuilder ret = new StringBuilder();
    for (char c : s.toCharArray()) {
      if (Character.isDigit(c)) {
        count = count * 10 + c - '0';
      } else { // isalpha.
        for (int i = 1; i <= count; i++) {
          ret.append(c);
        }
        count = 0;
      }
    }
    return ret.toString();
  }

  static String encoding(String s) {
    int count = 1;
    StringBuilder ss = new StringBuilder();
    for (int i = 1; i < s.length(); ++i) {
      if (s.charAt(i) == s.charAt(i - 1)) {
        ++count;
      } else {
        ss.append(count);
        ss.append(s.charAt(i - 1));
        count = 1;
      }
    }
    ss.append(count);
    ss.append(s.charAt(s.length() - 1));
    return ss.toString();
  }
Remove b and Replace b with dd
Main idea is to process backward
   static String replaceAndRemove(String s) {
    char[] sChars = s.toCharArray();
    // Removes "b" and count the number of "a".
    int writeIdx = 0, aCount = 0;
    for (char c : sChars) {
      if (c != 'b') {
        sChars[writeIdx++] = c;
      }
      if (c == 'a') {
        ++aCount;
      }
    }

    // Allocates space according to the number of "a".
    sChars = Arrays.copyOf(sChars, writeIdx + aCount);
    // Replace "a" with "dd".
    int curIdx = writeIdx - 1;
    writeIdx = sChars.length - 1;
    while (curIdx >= 0) {
      if (sChars[curIdx] == 'a') {
        sChars[writeIdx--] = 'd';
        sChars[writeIdx--] = 'd';
      } else {
        sChars[writeIdx--] = sChars[curIdx];
      }
      --curIdx;
    }
    return new String(sChars);
  }
PhoneMnemonic
  static void phoneMnemonicHelper(String num, int d, char[] ans) {
    if (d == num.length()) { // get enough characters and output answer.
      System.out.println(ans);
    } else {
      for (char c : M[num.charAt(d) - '0'].toCharArray()) { // try all
                                                            // combinations.
        ans[d] = c;
        phoneMnemonicHelper(num, d + 1, ans);
      }
    }
  }

  static void phoneMnemonic(String num) {
    char[] ans = new char[num.length()];
    phoneMnemonicHelper(num, 0, ans);
  }

EPI: Extended Simple Regular Expression

ESRE - Extended Simple Regular Expression
static boolean isMatchHere(String r, String s) {
// Case (1.)
if (r.isEmpty()) {
return true;
}

// Case (2) : ends with '$'.
if ("$".equals(r)) {
return s.isEmpty();
}

// Case (4.)
if (r.length() >= 2 && r.charAt(1) == '*') {
for (int i = 0; i < s.length()
&& (r.charAt(0) == '.' || r.charAt(0) == s.charAt(i)); ++i) {
if (isMatchHere(r.substring(2), s.substring(i + 1))) {
return true;
}
}
return isMatchHere(r.substring(2), s);
}

// Case (3.)
return !s.isEmpty()
&& (r.charAt(0) == '.' || r.charAt(0) == s.charAt(0))
&& isMatchHere(r.substring(1), s.substring(1));
}

static boolean isMatch(String r, String s) {
// Case (2.) : starts with '^'.
if (r.charAt(0) == '^') {
return isMatchHere(r.substring(1), s);
}

for (int i = 0; i <= s.length(); ++i) {
if (isMatchHere(r, s.substring(i))) {
return true;
}
}
return false;
}

LeetCode - Permutation Sequence | Darren's Blog

Given n and k , return the k-th permutation sequence. Note: given n will be between 1 and 9 inclusive.

the permutations with the same first number are in a group. you will realize there is 
n groups, each of (n−1)! numbers. The permutations in each group are sorted as they are as a universal group. So our algorithm can work as follows: find which group the k-th permutation belongs to, extract the common first number from the list of numbers and append it to the construction of the permutation, and iteratively find within that group the (((k−1)%(n−1)!)+1)-th permutation.
From http://fisherlei.blogspot.com/2013/04/leetcode-permutation-sequence-solution.html
那么这里，我们把a1去掉，那么剩下的permutation为
a2, a3, .... .... an, 共计n-1个元素。 n-1个元素共有(n-1)!组排列，那么这里就可以知道

设变量K1 = K
a1 = K1 / (n-1)!

同理，a2的值可以推导为
a2 = K2 / (n-2)!
K2 = K1 % (n-1)!
 .......
a(n-1) = K(n-1) / 1!
K(n-1) = K(n-2) /2!

an = K(n-1)

public String getPermutation(int n, int k) {

        // Create a list of 1, 2, ..., n, and compute the number of permutations as "groupSize"

        List<Integer> list = new LinkedList<Integer>();

        int groupSize = 1;

        for (int i = n; i >= 1; i--) {

            list.add(0, i);

            groupSize *= i;

        }

        // Invalid k

        if (k > groupSize)

            return null;

        // Construct the k-th permutation with a list of n numbers

        // Idea: group all permutations according to their first number (so n groups, each of

        // (n-1)! numbers), find the group where the k-th permutation belongs, remove the common

        // first number from the list and append it to the resulting string, and iteratively

        // construct the (((k-1)%(n-1)!)+1)-th permutation with the remaining n-1 numbers

        StringBuilder builder = new StringBuilder();

        while (n > 0) {

            groupSize /= n;

            int groupIndex = (k-1) / groupSize;

            builder.append(list.remove(groupIndex));

            n--;

            k = ((k-1) % groupSize) + 1;

        }

 

        return builder.toString();

    }

Read full article from LeetCode - Permutation Sequence | Darren's Blog