Linked List

There is an interview question asked about what data structure can be used to perform insertion and removal in FIFO. The answer is Singly - linked list with head and tail pointers. This motivated me to summarize the linked list structure.


Singly-Linked List with head and tail pointers

This is the answer for the above question. The singly linked list is a sequence of dynamically allocated storage elements, each containing a pointer to its successor. Keeping a second pointer, tail, which points to the last element of the list, allows the retrieve and remove elements in O(1) time.

How?

Adding at tail and remove at the head.

public class SinglyLinkedList {
 protected ListNode head;
 protected ListNode tail;
 protected long size;
 
 public SinglyLinkedList() {
  head = null;
  tail = null;
  size = 0;
 }
 /**
  * add to the head
  */
 public void add(T value) {
  ListNode node = new ListNode (value);
  //if no node is in the list, 
  //set the tail to the first node added to the list
  if (tail == null)
   tail = node;
  node.setNext(head);
  head = node;
  size++;
 }
 /**
  * insert a node at desired position
  * @param curr
  * @param toInsert
  * O(n)
  */
 public void insert(int index, T value) {
  if (index < 0 || index > size - 1)
   throw new IllegalArgumentException("index must be greater than 0 and less than number of elements in the list!");
  
  if (index == 0) {
   add(value);
   return;
  }
  if (index == size - 1) {
   addLast(value);
   return;
  }
  ListNode toInsert = new ListNode (value);
  ListNode prev = getNode(index - 1);
  ListNode next = prev.getNext();
  prev.setNext(toInsert);
  toInsert.setNext(next);
 }
 
 
 /**
  * add the node at tail
  * O(1)
  */
 public void addLast(T value) {
  ListNode node = new ListNode (value);
  if (head == null) {
   head = node;
  }
  else {
   tail.setNext(node);
  }
  node.setNext(null);
  tail = node;
  size++;
 }
 /**
  * remove the first element in the list
  * O(n)
  * @return
  */
 public ListNode removeFirst() {
  if (head == null)
   throw new NullPointerException("Empty list!");
  ListNode tmp = head;
  head = head.getNext();
  tmp.setNext(null);
  size--;
  return tmp;
 }
 /**
  * need to traverse the list
  * @return
  */
 public ListNode removeLast() {
  if (size == 0)
   throw new NullPointerException("Empty list!");
  ListNode node = head;
  ListNode toRemove = tail;
  while (!node.getNext().equals(tail))
   node = node.getNext();
  node.setNext(null);
  tail = node;
  size--;
  return toRemove; 
 }
 /**
  * remove a node
  * @param node
  * O(n)
  */
 public void remove(ListNode toRemove) {
  if (size == 0)
   throw new NullPointerException("Empty list!");
  if (toRemove.equals(head))
   removeFirst();
  if (toRemove.equals(tail))
   removeLast();
  ListNode node = head;
  while (node != null && !node.getNext().equals(toRemove)) {
   node = node.getNext();
  }
  if (node == null)
   throw new IllegalArgumentException("No such element in the list!");
  node.setNext(node.getNext().getNext());
 }
 public ListNode getFirst() {
  return head;
 }
 public ListNode getLast() {
  return tail;
 }
 public long getSize() {
  return size;
 }
 public void clear() {
  for (ListNode node = head; node != null;) {
   ListNode next = node.getNext();
   node.setValue (null);
   node.setNext(null);
   node = next;
  }
  head = null;
  tail = null;
  size = 0;
 }
 public String toString() {
  ListNode node = head;
  String rst = "";
  while (node != null) {
   rst += String.valueOf(node.getValue());
   rst += " -> ";
   node = node.getNext();
  }
  return rst.substring(0, rst.length() - 4);
 }
 private ListNode getNode(int index) {
  int count = 0;
  if (index == size - 1)
   return tail;
  if (index == 0)
   return head;
  ListNode node = head;
  while (count < index && node != null) {
   node = node.getNext();
   count++;
  }
  return node;
 }
}

If you notice, this implementation actually can be used as a queue. However, since it is singly linked list, find any node in the list takes O(n) time.

Note that if a singly - linked list with only head pointer, it can be implemented as a stack.


(Singly) - Circular - Linked - List with a sentinel

The sentinel element is never used to hold data and it is always present. The principle is that it simplifies the programming of certain operations. E.g., we don't have to modify the head pointer. However, the disadvantage is that extra space is required.

One application for the circular linked list is to keep track of whose turn it is in a multi - player board game. Put all the players in a circular linked list, after the current player takes her turn, advance to the next player in the list. Break the cycle if the game is over.

Circular linked list can also be used as an implementation of queue. Here, we only need to maintain one pointer: the last inserted pointer. The first element is always the next of the last. Note this is also an FIFO container.

Moreover, when multiple applications are running on a PC, it is common for the OS to put the running applications on a list and then to cycle through them, giving each of them a slice of time to execute, and then making them wait while the CPU is given to another application. It is common to use a circular list so that when it reaches the end of the list, it can cycle around to the front of the list.

Note my implementation keeps track the element that has just been operated, so this cannot be used as an FIFO container.

/**
 * this class implements a circular singly linked list
 * since it's a circular list, there is no "head" and "tail"
 * a pointer points to the current location
 * any operation will set "current" to the node that has just been operated
 * Note this class does not include addLast() and removeLast() method
 * a "tail" pointer can be added to perform the these two operations
 * @author shirleyyoung
 *
 * @param 
 */
public class CircularSinglyLinkedList {
 private ListNode sentinel;
 private ListNode current;
 private long size;
 
 /**
  * construct a new list
  * current points to sentinel
  */
 public CircularSinglyLinkedList () {
  sentinel = new ListNode (null);
  //current = sentinel;
  //current.setNext(sentinel);
  clear();
  size = 0;
  //System.out.println("Construct an empty list!");
  //System.out.println(sentinel == null ? "sentinel equals null" : current.getValue());
 }
 public void clear() {
  sentinel.setNext(sentinel);
  current = sentinel;
  size = 0;
 }
 /**
  * insert an element after the current position
  * @param value
  * O(1)
  */
 public void add(T value) {
  ListNode node = new ListNode (value);
  //System.out.println(node.getValue());
  node.setNext(current.getNext());
  //System.out.println(node.getNext() == null ? "Null" : node.getNext().getValue());
  current.setNext(node);
  //System.out.println(current.getNext() == null ? "Null" : current.getNext().getValue());
  current = node;
  size++;
 }
 /**
  * add at desired position
  * @param index
  * @param value
  * O(n)
  */
 public void add(int index, T value) {
  if (index < 0 || index >= size)
   throw new IllegalArgumentException("Index must be greater than zero and less than list size!");
  if (index == 0)
   addFirst(value);
  int count = 0;
  ListNode node = sentinel.getNext();
  while (node != sentinel && count < index - 1) {
   node = node.getNext();
   count++;
  }
  ListNode toAdd = new ListNode (value);
  toAdd.setNext(node.getNext().getNext());
  node.setNext(toAdd);
  current = toAdd;
  size++;
 }
 /**
  * add at the head
  * O(1)
  * @param value
  */
 public void addFirst(T value) {
  current = sentinel;
  add(value);
  size++;
 }
 /**
  * remove the node at current position
  * makes its successor the current position
  * singly linked list, need to traverse the list
  * O(1)
  */
 public void remove() {
  if (sentinel.getNext() == sentinel) 
   throw new NullPointerException("Empty list!");
  ListNode node = sentinel;
  while (node.getNext() != current)
   node = node.getNext();
  node.setNext(current.getNext());
  current = current.getNext();
 }
 
 
 /**
  * if an object is in the list
  * Note it returns the first occurrence of the object
  * @param value
  * @return
  * O(n)
  */
 public boolean contains(T value) {
  //put the  value in sentinel, if the value cannot be 
  //found in the list, then the node will return to sentinel
  sentinel.setValue(value);
  ListNode node = sentinel.getNext();
  while (node.getValue() != value) 
   node = node.getNext();
  if (node == sentinel)
   return false;
  sentinel.setValue(null);
  //set current node to the desired node
  current = node;
  return true;
 }
 public boolean isEmpty() {
  return sentinel.getNext() == sentinel;
 }
 /**
  * return the current object
  * @return
  * O(1)
  */
 public T getCurrent() {
  if (current == sentinel)
   throw new NullPointerException("Empty list!");
  return current.getValue();
 }
 /**
  * get the first object in the list
  * makes the current be the head of the list
  * @return
  */
 public T getFirst() {
  current = sentinel.getNext();
  return getCurrent();
 }
 
 
 /**
  * set the value of the current element
  */
 public void setCurrent(T value) {
  if (current == sentinel)
   throw new NullPointerException("Empty list!");
  current.setValue(value);
 }
 /**
  * return the next object after the current element
  * @return
  */
 public T next() {
  if (!hasNext()) {
   System.err.println("No next element!");
   return null;
  }
  current = current.getNext();
  return current.getValue();
 }
 public boolean hasNext() {
  return current.getNext() != sentinel;
 }
 public String toString() {
  ListNode node = sentinel;
  //System.out.println(node == null ? "Null" : node.getValue());
  String rst = "";
  node = node.getNext();
  while (node != sentinel) {
   rst += String.valueOf(node.getValue());
   rst += " -> ";
   node = node.getNext();
  }
  return rst.substring(0, rst.length() - 4);
 }
}

Doubly - Linked -List

Java's LinkedList is a doubly linked list implementation. Doubly Linked list with both head and tail allows for add and remove from either head or tail in O(1) time, i.e., both queue and stack. However, if only head pointer is maintained, the list can be used as a stack.

Doubly linked list can be used to implement an LRU cache.

import java.util.NoSuchElementException;

public class DoublyLinkedList {
 int size;
 ListNode head;
 ListNode tail;
 public DoublyLinkedList () {
  head = null;
  tail = null;
  //head.next = tail;
  //tail.prev = head;
  size = 0;
 }
 /**
  * add at head
  * O(1)
  * @param obj
  */
 public void addFirst(T obj) {
  ListNode h = head;
  ListNode node = new ListNode (null, obj, h);
  head = node;
   if (tail == null)
    tail = node;
   else
    h.prev = node;
  size++;
 }
 /**
  * add at tail
  * O(1)
  * @param obj
  */
 public void addLast(T obj) {
  ListNode t = tail;
  ListNode node = new ListNode (t, obj, null);
  tail = node;
  if (head == null)
   head = node;
  else
   t.next = node;
  size++;
 }
 /**
  * insert at a desired position
  * O(n)
  */
 public void insert(int index, T obj) {
  isPositionIndex(index);
  if (index == 0) {
   addFirst(obj);
   return;
  }
  if (index == size) {
   addLast(obj);
   return;
  }
  ListNode prev = getNode(index - 1);
  ListNode curr = prev.next;
  ListNode toAdd = new ListNode(prev, obj, curr);
  curr.prev = toAdd;
  prev.next = toAdd;
  size++;
  
 }
 /**
  * remove first element in the list
  * O(1)
  * @return
  */
 public T removeFirst() {
  if (head == null)
   throw new NoSuchElementException("Probably empty list?");
  T obj = head.value;
  ListNode next = head.next;
  head.value = null;
  head.next = null;
  head = next;
  if (next == null)
   tail = null;
  else
   next.prev = null;
  size--;
  return obj;
 }
 /**
  * remove the last element
  * O(1) 
  * @return
  */
 public T removeLast() {
  if (tail == null)
   throw new NoSuchElementException("Probably empty list?");
  T obj = tail.value;
  ListNode prev = tail.prev;
  tail.value = null;
  tail.prev = null;
  tail = prev;
  if (prev == null)
   head = null;
  else 
   prev.next = null;
  size--;
  return obj;
 }
 /**
  * remove the element at given index
  * O(n)
  * @param index
  * @return
  */
 public T remove(int index) {
  isPositionIndex(index);
  if (index == size)
   throw new NoSuchElementException("Probably empty list?");
  if (index == 0) {
   return removeFirst();
  }
  if (index == size - 1) {
   return removeLast();
  }
  ListNode toRemove = getNode(index);
  T obj = toRemove.value;
  ListNode prev = toRemove.prev;
  ListNode next = toRemove.next;
  prev.next = next;
  next.prev = prev;
  toRemove.value = null;
  toRemove.prev = null;
  toRemove.next = null;
  size--;
  return obj;
  
 }
 
 public T getFirst() {
  if (head == null)
   throw new NoSuchElementException("Probably empty list?");
  return head.value;
 }
 public T getLast() {
  if (tail == null)
   throw new NoSuchElementException("Probably empty list?");
  return tail.value;
 }
 public int getSize() {
  return size;
 }
 public void clear() {
  for (ListNode node = head; node != null;) {
   ListNode next = node.next;
   node.value = null;
   node.next = null;
   node = next;
  }
  head = null;
  tail = null;
  size = 0;
 }
 public String toString() {
  ListNode node = head;
  String rst = "";
  while (node != null) {
   rst += String.valueOf(node.value);
   rst += " -> ";
   node = node.next;
  }
  return rst.substring(0, rst.length() - 4);
 }
 
 private ListNode getNode(int index) {
  //in the first half of the list
  //traverse from the head
  if (index < (size >> 1)) {
   ListNode node = head;
   for (int i = 0; i < index; i++)
    node = node.next;
   return node;
  }
  //in the second half
  //traverse from the tail
  else {
   ListNode node = tail;
   for (int i = size - 1; i > index; i--) {
    node = node.prev;
   }
   return node;
  }
 }
 private boolean isPositionIndex(int index) {
  if (index < 0 || index > size)
   throw new IndexOutOfBoundsException("Index must be greater than 0 and smaller than list size!");
  return true;
 }
 

}

Knapsack

This is the first DP algorithm I learned when I started learning algorithm at the first time. I was so stupid back then that I didn't know what the matrix really means, so I literally wrote a code and "calculated" the matrix.

Uh, those time...

Ok, back to the problem.

The version of the question I learned back then is that a thief is breaking into a museum. He has a bag that can carry at most weight W. There are n items in the museum[0, ...i, ... n - 1]. Each is weighted w_i and has value v_i. None of the items can be broken down to pieces. The thief needs to decide which items to carry in order to get the maximum value.

Yeah, we are trying to help a crime... -_-

As we mentioned, the solution is a DP approach. So how to build the matrix?
If we break down the problems to 1 item and weight w, then if the item is heavier than weight, the thief cannot carry it, then the remaining weight will be w - w_1. Let's assume we can carry the item 1. Now if we add one more item, we either choose to carry the item 2, and the remaining weight will be w _ w_1 - w_2, and the value will be v_1 + v_2. Or we choose not to carry it, then there is only item 1 in the bag. Yup, it is Max(bag[i - 1][w], bag[i - 1][w - w_[i - 1]] + v[i - 1]).

public static int maxValue(int[] value, int[] weight, int maxW) {
  if (value == null || weight == null || value.length != weight.length)
   throw new NullPointerException("Invalid input!");
  int[][] values = new int[value.length + 1][maxW + 1];
  for (int i = 1; i <= value.length; i++) {
   for (int w = 1; w <= maxW; w++) {
    if (weight[i - 1] <= w) {
     values[i][w] = Math.max(values[i - 1][w], values[i - 1][w - weight[i - 1]] + value[i - 1]);
    }
    else
     values[i][w] = values[i - 1][w];
   }
  }
  return values[value.length][maxW];
 }

Dijkstra Algorithm

The Dijkstra Algorithm finds the shortest path from a source to all destination in a directed graph, i.e., single source shortest path problem. During the process, it will also determine a spanning tree for the graph.

Dijkstra partitions all nodes into two distinct sets. Unsettled and settled. Initially all nodes are in the unsettled sets, e.g., they must be still evaluated. A node is move to the settled set if a shortest path from the source to this node has been found.
Initially the distance of each node to the source is set to a very high value, e.g., Integer.MAX_VALUE.

The algorithms runs until the unsettledNodes are empty. In each iteration it selects the node with the lowest distance from the source out the unsettled nodes.

I used my previous Graph class. However, I added a new method chooseSource(int label) to select a node in the graph as the source node. In the node class, I added one more variable, initially assigned to Integer.MAX_VALUE, if a source node is chosen, the distance of the source is set to 0. Then when we construct the Dijkstra class, all shortest paths to the source node can be acquired.

public void chooseSource(int label) {
  Node source = getNode(label);
  source.dist = 0;
  
 }

The Dijkstra class:

import java.util.*;
public class Dijkstra {
 private Graph g;
 private int[] distTo;
 Node source;
 private int[] predecessor;
 private PriorityQueue pq;
 
 public Dijkstra(Graph G, int s) {
  this.g = G;
  g.chooseSource(s);
  pq = new PriorityQueue (new NodeComparator());
  source = g.getNode(s);
  pq.add(source);
  distTo = new int[g.getSize()];
  distTo[s - 1] = 0; 
  predecessor = new int[g.getSize() + 1];
  predecessor[s] = -1;
 }
 public void getShortestPath() {
  while (!pq.isEmpty()) {
   Node curr = pq.poll();
   for (Node w : curr.neighbors) {
    int distanceToSource = curr.dist + curr.edges.get(w).getWeight(curr, w);
    if (distanceToSource < w.dist) {
     pq.remove(w);
     w.dist = distanceToSource;
     predecessor[w.label] = curr.label;
     pq.add(w);
    }
   }
  }
 }
 /**
  * get the shortest path from source to target node
  * @param n
  */
 public void getShortestPath(int target) {
  boolean found = false;
  while (!pq.isEmpty() && !found) {
   Node curr = pq.poll();
   for (Node w : curr.neighbors) {
    int distanceToSource = curr.dist + curr.edges.get(w).getWeight(curr, w);
    if (distanceToSource < w.dist) {
     pq.remove(w);
     w.dist = distanceToSource;
     predecessor[w.label] = curr.label;
     pq.add(w);
    }
    if (w.label == target) {
     found = true;
     break;
    }
   }
  }
  
 }
 public String shortestPath(int label) {
  Node target = g.getNode(label);
  String NEWLINE = System.getProperty("line.separator");
  StringBuilder sb = new StringBuilder();
  sb.append("The shortest distance from " + label + " to source " + source.label 
    + " is: " + target.dist);
  sb.append(NEWLINE);
  int x;
  for (x = label; g.getNode(x).dist != 0; x = predecessor[x]) {
   sb.append(x + " -> ");
  }
  sb.append(source.label);
  //sb.delete(sb.length() - 4, sb.length() - 1);
  sb.append(NEWLINE);
  return sb.toString();
 }
 private class NodeComparator implements Comparator {
  
  public int compare(Node a, Node b) {
   if (a.dist - b.dist < 0)
    return -1;
   else if (a.dist - b.dist > 0)
    return 1;
   return 0;
  }
 }
}

The amazing maze II: searching the maze

This post I will talk about how to solve a maze. If you are interested in how to build a maze. Take a look at my last post.

There are couple ways to solve a maze, the easiest ones are using DFS and BFS. Here, I implemented DFS using recursion, DFS using a stack, and BFS.

package mazeDFS;
import java.util.*;
public class SolveMaze {
 
 List path;
 private Maze m;
 
 public SolveMaze(Maze m) {
  path = new ArrayList ();
  this.m = m;
 }
 /**
  * Using DFS to solve the maze
  */
 public void solveByDFS() {
  boolean[] visited = new boolean[m.grid.length];
  //Stack stack = new Stack ();
  dfs(path, visited, 0);
 }
 //using recursion
 private void dfs(List path, boolean[] visited, int curr) {
  if (curr == m.grid.length - 1) {
   visited[curr] = true; 
   path.add(curr);
   return;
  }
  path.add(curr);
  visited[curr] = true;
  int cell = m.grid[curr];
  if ((cell & Maze.LEFT) == 0 && (curr - 1) >= 0 && !visited[curr - 1] && !visited[m.grid.length - 1] && !visited[m.grid.length - 1])
   dfs(path, visited, curr - 1);
  if ((cell & Maze.RIGHT) == 0 && (curr + 1) < m.grid.length && !visited[curr + 1] && !visited[m.grid.length - 1])
   dfs(path, visited, curr + 1);
  if ((cell & Maze.UP) == 0 && (curr - m.columns) >= 0 && !visited[curr - m.columns] && !visited[m.grid.length - 1])
   dfs(path,visited, curr - m.columns);
  if ((cell & Maze.DOWN) == 0 && (curr + m.columns) < m.grid.length && !visited[curr + m.columns] && !visited[m.grid.length - 1])
   dfs(path, visited, curr + m.columns);
  if (visited[m.grid.length - 1])
   return;
  path.remove(path.size() - 1);
 }
 //using a stack
 public void solveByDFS2() {
  Stack stack = new Stack ();
  boolean[] visited = new boolean[m.grid.length];
  int[] distTo = new int[m.grid.length];
  int[] predecessor = new int[m.grid.length];
  Arrays.fill(distTo, Integer.MAX_VALUE);
  stack.push(0);
  visited[0] = true;
  distTo[0] = 0;
  predecessor[0] = -1;
  while (!stack.isEmpty() && !visited[m.grid.length - 1]) {
   int curr = stack.pop();
   int cell = m.grid[curr];
   if (curr == m.grid.length - 1) {
    break;
   }
   if ((cell & Maze.LEFT) == 0 && (curr - 1) >= 0 && !visited[curr - 1]) {
    stack.push(curr - 1);
    visited[curr - 1] = true;
    distTo[curr - 1] = distTo[curr] + 1;
    predecessor[curr - 1] = curr;
   }
   if ((cell & Maze.RIGHT) == 0 && (curr + 1) < m.grid.length && !visited[curr + 1]) {
    stack.push(curr + 1);
    visited[curr + 1] = true;
    distTo[curr + 1] = distTo[curr] + 1;
    predecessor[curr + 1] = curr;
   }
   if ((cell & Maze.UP) == 0 && (curr - m.columns) >= 0 && !visited[curr - m.columns]) {
    stack.push(curr - m.columns);
    visited[curr - m.columns] = true;
    distTo[curr - m.columns] = distTo[curr] + 1;
    predecessor[curr - m.columns] = curr;
   }
   if ((cell & Maze.DOWN) == 0 && (curr + m.columns) < m.grid.length && !visited[curr + m.columns]) {
    stack.push(curr + m.columns);
    visited[curr + m.columns] = true;
    distTo[curr + m.columns] = distTo[curr] + 1;
    predecessor[curr + m.columns] = curr;
   }
  }
  int x;
  for (x = m.grid.length - 1; distTo[x] != 0; x = predecessor[x]) {
   path.add(x);
  }
  path.add(0);
  Collections.reverse(path);
  
 }
 
 public void solveByBFS() {
  Queue q = new LinkedList ();
  boolean[] visited = new boolean[m.grid.length];
  int[] distTo = new int[m.grid.length];
  int[] predecessor = new int[m.grid.length];
  Arrays.fill(distTo, Integer.MAX_VALUE);
  q.offer(0);
  visited[0] = true;
  distTo[0] = 0;
  predecessor[0] = -1;
  while (!q.isEmpty() && !visited[m.grid.length - 1]) {
   int curr = q.poll();
   int cell = m.grid[curr];
   if (curr == m.grid.length - 1) {
    break;
   }
   if ((cell & Maze.LEFT) == 0 && (curr - 1) >= 0 && !visited[curr - 1]) {
    q.offer(curr - 1);
    visited[curr - 1] = true;
    distTo[curr - 1] = distTo[curr] + 1;
    predecessor[curr - 1] = curr;
   }
   if ((cell & Maze.RIGHT) == 0 && (curr + 1) < m.grid.length && !visited[curr + 1]) {
    q.offer(curr + 1);
    visited[curr + 1] = true;
    distTo[curr + 1] = distTo[curr] + 1;
    predecessor[curr + 1] = curr;
   }
   if ((cell & Maze.UP) == 0 && (curr - m.columns) >= 0 && !visited[curr - m.columns]) {
    q.offer(curr - m.columns);
    visited[curr - m.columns] = true;
    distTo[curr - m.columns] = distTo[curr] + 1;
    predecessor[curr - m.columns] = curr;
   }
   if ((cell & Maze.DOWN) == 0 && (curr + m.columns) < m.grid.length && !visited[curr + m.columns]) {
    q.offer(curr + m.columns);
    visited[curr + m.columns] = true;
    distTo[curr + m.columns] = distTo[curr] + 1;
    predecessor[curr + m.columns] = curr;
   }
  }
  int x;
  for (x = m.grid.length - 1; distTo[x] != 0; x = predecessor[x]) {
   path.add(x);
  }
  path.add(0);
  Collections.reverse(path); 
 }
}

Performance

Average memory usage on a 50 by 50 maze

Average running time on a 50 by 50 maze

As we can see, DFS by recursion outperforms the other two methods in both time and memory. It is understandable that BFS is slower in this circumstance. If we search layer by layer, we probably need to traverse the whole maze to find the end point. Yet if we use DFS, any path leads to the end point can terminate the searching. 

Recursive solutions often result in smaller code, which means it's more likely that the code will fit into the CPU cache. A no-recursive solution that requires an explicitly managed stack can result in larger code, more cache misses, and slower performance than recursive solution. 

Find minimum "swaps" needed to sort an array

An operation "swap" means removing an element from the array and appending it at the back of the same array. Find the minimum number of "swaps" needed to sort that array. 

Eg :- 3124 
Output: 2 (3124->1243->1234) 

How to do it less than O(n^2) ?

Doing it in less than O(n^2) time means that we cannot actually perform the "swap". The idea is that we need to calculate the number of elements that are already sorted in the array, and the rest elements needs to be "swapped".

e.g., 3124: 1, 2 are sorted, swap 3, 4
7, 9, 8, 3, 5: 3, 5 are sorted, swap 7, 9, 8

public static int minSwap(int[] array) {
  if (array == null || array.length == 0)
   throw new IllegalArgumentException("Invalid input!");
  int[] sorted = new int[array.length];
  for (int i = 0; i < array.length; i++) {
   sorted[i] = array[i];
  }
  Arrays.sort(sorted);
  int j = 0;
  for (int i = 0; i < array.length; i++) {
   if (array[i] == sorted[j])
    j++;
  }
  return array.length - j;
 }

Determine if two strings are match

Two texts are considered to "match" if they have a common substring of at least length n. Describe an algorithm to determine if two strings are matches.

This is another FB interview question. The reason I am writing this blog is that lots of people are talking about using DP, i.e., find the longest common substring. However, I find it unnecessary and more expensive. I implemented both methods and did some performance test.

//hashset method
 public static boolean isMatch(String s1, String s2, int n) {
  if (s1 == null || s2 == null || s1.length() < n || s2.length() < n)
   return false;
  Set substrings = new HashSet ();
  for (int i = 0; i <= s1.length() - n; i++) {
   substrings.add(s1.substring(i, i + n));
  }
  for (int i = 0; i <= s2.length() - n; i++) {
   if(substrings.contains(s2.substring(i, i + n)))
    return true;
  }
  return false;
 }
 //DP method
 public static boolean isMatch2(String s1, String s2, int n) {
  if (s1 == null || s2 == null || s1.length() < n || s2.length() < n)
   return false;
  int lcs = longestCommonSubstring(s1, s2);
  return lcs >= n;
 }
 public static int longestCommonSubstring(String s1, String s2) {
  if (s1 == null || s2 == null)
   throw new NullPointerException("Null string(s)!");
  int[][] lcs = new int[s1.length() + 1][s2.length() + 1];
  int max = 0;
  for (int i = 1; i <= s1.length(); i++) {
   for (int j = 1; j <= s2.length(); j++) {
    if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
     lcs[i][j] = lcs[i - 1][j - 1] + 1;
    }
    max = Math.max(lcs[i][j], max);
   }
  }
  return max;
 }

The hashset method takes O(m + n) time but DP takes O(mn) time. And the memory usage is almost same.

Search element in an array

I went over three questions that require us to search for max/min values in an unsorted array using different algorithms. This post summarizes them.

Given an unsorted array, extract the second max/min using the least number of comparison 

The total comparisons will be n + log n - 2. The algorithm is called tournament method. A detailed explanation can be found here. I simplified this guy's implementation. 

public static int secondMax(int[] array) {
  if (array == null || array.length == 0)
   throw new IllegalArgumentException("Null or empty array");
  int[][]tree = reverseTree(array);
  int secondMax = Integer.MIN_VALUE;
  int max = tree[tree.length - 1][0];
  int rootPos = 0;
  for (int i = tree.length - 2; i >= 0; i--) {
   rootPos = tree[i][rootPos * 2] == max ? rootPos * 2 : (rootPos * 2 + 1);
   if (i < tree.length - 2 && rootPos == tree[i].length - 1)
    continue;
   if (rootPos % 2 == 0) {
    secondMax = Math.max(secondMax, tree[i][rootPos + 1]);
   }
   else 
    secondMax = Math.max(secondMax, tree[i][rootPos - 1]);
  }
  return secondMax;
 }
 private static int[][] reverseTree(int[] array) {
  int depth = (int)Math.ceil((double)Math.log((double)array.length)/Math.log(2.0)) + 1;
  int[][] tree = new int[depth][];
  tree[0] = array;
  for (int i = 1; i < depth; i++) {
   tree[i] = getRow(tree[i - 1]);
  }
  return tree;
 }
 private static int[] getRow(int[] lastRow) {
  int length = (lastRow.length % 2 == 0) ? (lastRow.length/ 2) : (lastRow.length / 2 + 1); 
  int[] currRow = new int[length];
  int index = 0;
  for (int i = 0; i < lastRow.length - 1; i += 2) {
   if (lastRow[i] < lastRow[i + 1])
    currRow[index] = lastRow[i + 1];
   else
    currRow[index] = lastRow[i];
   index++;
  }
  if (index < currRow.length) {
   currRow[index] = lastRow[lastRow.length - 1];
  }
  return currRow;
 }

Note:
I tried to use a map at first to make it easier, it gave me ConcurrentModificationException, and it's second time. Yeah, I will remember never try to modify a map in a loop...

Write a function that finds the minimum and maximum values   within an unsorted array using divide-and-conquer.

Just to make life easier, this method finds both max and min at the same time. 

public static int[] maxNMin(int[] array) {
  if (array == null || array.length == 0)
   throw new IllegalArgumentException("Null or empty array!");
  return findLimits(array, 0, array.length - 1);
 }
 private static int[] findLimits(int[] array, int start, int end) {
  int[] limits = new int[2];
  if (end - start <= 0) {
   limits[0] = array[start];
   limits[1] = array[start];
   return limits;
  }
  if (end - start == 1) {
   if (array[start] < array[end]) {
    limits[0] = array[start];
    limits[1] = array[end];
   }
   else {
    limits[0] = array[end];
    limits[1] = array[start];
   }
   return limits;
  }
  int mid = (start + end) / 2;
  int[] leftLimits = findLimits(array, start, mid);
  int[] rightLimits = findLimits(array, mid + 1, end);
  if (leftLimits[0] < rightLimits[0])
   limits[0] = leftLimits[0];
  else
   limits[0] = rightLimits[0];
  if (leftLimits[1] > rightLimits[1])
   limits[1] = leftLimits[1];
  else
   limits[1] = rightLimits[1];
  return limits; 
 }

Given an unsorted array, extract the max and min value using the least number of comparison

Use pairwise comparison, 3 comparisons for 2 elements, so total 3/2 * n comparisons. See here.

public static int[] limit(int[] array) {
  if (array == null || array.length == 0)
   throw new IllegalArgumentException("Wrong input!");
  int max = array[0];
  int min = array[0];
  int start = 0;
  if (array.length % 2 != 0)
   start = 1;
  for (int i = start; i < array.length - 1; i += 2) {
   if (array[i] < array[i + 1]) {
    max = Math.max(max, array[i + 1]);
    min = Math.min(min, array[i]);
   }
   else {
    max = Math.max(max, array[i]);
    min = Math.min(min, array[i + 1]);
   }
  }
  int[] limits = new int[2];
  limits[0] = min;
  limits[1] = max;
  return limits;
 }

Regular Expression Match II

The first one is a LeetCode problem, and can be found here.

This one, is similar, with the only difference that now we need to take into account '+'. Here is the problem statement:

Write a Simple regex parser, where pattern can contain *, + or .
* -> 0 or none
+ -> one or more
. -> Exactly one character
Examples:
Input - Pattern = a*b+c. data= bcOutput - true
Input - Pattern - abc+ data=abcOutput - true
Input - Pattern - ab* data=c
Output - false

I will still use the recursion method as the first one. When the s.charAt(1) = '+', since there is at least one proceeding character needs to be matched, we need to check if s.charAt(0) == p.charAt(0) or p.charAt(0) == '.'. Moreover, if s is an empty string, it definitely means that they don't match, so simply return false. Now if the first character matches, we need to check how many characters are matched by '+'. I use a loop, if any character in s matches p.charAt(2) (e.g., bbbbbc, and b+c), recursively check the substring of s and p.

Update: 2015 - 03 - 18
I notice the code below has a mistake because I didn't understand regex. '+' matches the proceeding character one or more times, that means the format must be bbbbbc matches b+c, but bbbddc doesn't match b+c.

Here is the updated code.

public static boolean isMatch(String s, String p){
  if(s == null)
   return p == null;
  if(p == null)
   return false;
  if(p.length() == 0)
   return s.length() == 0;
  if(s.equals(p))
   return true;
  if(p.length() == 1 || (p.charAt(1) != '*' && p.charAt(1) != '+')){
   if(s.length() < 1 || (s.charAt(0) != p.charAt(0) && p.charAt(0) != '.'))
    return false;
   return isMatch(s.substring(1), p.substring(1));
  }
  if(p.charAt(1) == '+'){
   //must match at least once
   if(s.length() < 1 || (s.charAt(0) != p.charAt(0) && p.charAt(0) != '.'))
    return false;
   char match = s.charAt(0);
   int index = 0;
   while(index < s.length()){
    if(s.charAt(index) != match)
     break;
    index++;
   }
   return isMatch(s.substring(index), p.substring(2));
  }
  int index_s = -1;
  while(index_s < s.length() && (index_s < 0 || s.charAt(index_s) == p.charAt(0) || p.charAt(0) == '.')){
   if(isMatch(s.substring(index_s + 1), p.substring(2)))
    return true;
   index_s++;
  }
  return false;
 }

public static boolean isMatch(String s, String p) {
  if (p == null || s == null)
   return false;
  if (p.length() == 0)
   return s.length() == 0;
  if (p.equals(s))
   return true;
  if (p.length() == 1 || (p.charAt(1) != '*' && p.charAt(1) != '+')) {
   if (s.length() < 1 || (s.charAt(0) != p.charAt(0) && p.charAt(0) != '.'))
    return false;
   return isMatch(s.substring(1), p.substring(1));
  }
  if (p.charAt(1) == '+') {
   if (s.length() < 1 || (s.charAt(0) != p.charAt(0) && p.charAt(0) != '.')) {
    return false;
   }
   for (int i = 1; i <= s.length(); i++) {
    if (i < s.length() && p.length() > 2 && s.charAt(i) != p.charAt(2))
     continue;
    if (isMatch(s.substring(i), p.substring(2)))
     return true;
   }
   return false;
  }
  int index_s = -1;
  while (index_s < s.length() && (index_s < 0 || s.charAt(index_s) == p.charAt(0) || p.charAt(0) == '.')) {
   if (isMatch(s.substring(index_s + 1), p.substring(2)))
    return true;
   index_s++;
  }
  return false;
 }

Reverse a BST, find the kth largest element in BST

This is a FB interview question.
1. Reverse the BST;
2. find the kth largest element in O(n) time;
3. find the kth largest element in O(log n) time.

The first one is easy, recursively flip the left and right child of the tree.
The second one too, use in order traversal.
Now comes the third one. Here is an answer I found.

Here's just an outline of the idea:

Let each node in the BST have a field that returns the number of elements in its left and right subtree. Let the left subtree of node T contain only elements smaller than T and the right subtree only elements larger than or equal to T.

Now, suppose we are at node T:

1. k == num_elements(left subtree of T), then the answer we're looking for is the value in nodeT
2. k > num_elements(left subtree of T) then obviously we can ignore the left subtree, because those elements will also be smaller than the kth smallest. So, we reduce the problem to finding the k - num_elements(left subtree of T) smallest element of the right subtree.
3. k < num_elements(left subtree of T), then the kth smallest is somewhere in the left subtree, so we reduce the problem to finding the kth smallest element in the left subtree.

This is O(log N) on average (assuming a balanced tree).

But the problem is, how to get the size of the tree? In the end, I wrote a Tree class. However, there is a bug in this class: I can only build the tree bottom up: otherwise the children of the subtree will not be added into the parent's children list.

import java.util.*;
public class Tree {
 private int size;
 TreeNode node;
 Tree left;
 Tree right;
 List children;
 public Tree() {
  children = new ArrayList();
  size = 0;
 }
 public Tree(int rootVal) {
  node = new TreeNode(rootVal);
  children = new ArrayList ();
  left = new Tree();
  right = new Tree();
  size++;
 }
 private void addChildren(Tree tree) {
  children.addAll(tree.children);
  size += tree.children.size();
 }
 public void buildLeft(Tree leftTree) {
  node.left = leftTree.node;
  left = leftTree;
  children.add(leftTree.node);
  size++;
  addChildren(leftTree);
 }
 
 public void buildRight(Tree rightTree) {
  node.right = rightTree.node;
  right = rightTree;
  children.add(rightTree.node);
  size++;
  children.addAll(rightTree.children);
  size += rightTree.children.size();
 }
 public int size() {
  return size;
 }

}
public class TreeNode {

  int val;
  TreeNode left;
  TreeNode right;
  //TreeNode parent;
  TreeNode(int x) { val = x;}

}

Here are the methods for the three problems:

public static void reverseBST (TreeNode root) {
  if (root == null || (root.left == null && root.right == null))
   return;
  TreeNode tmp = root.left;
  root.left = root.right;
  root.right = tmp;
  reverseBST(root.right);
  reverseBST(root.left);
 }
 static int count = 0;
 /**
  * O(n) complexity
  * @param root
  * @param k
  * @return
  */
 public static int kthLargest(Tree root, int k) {
  if (root == null)
   return -1;
  return findKth(root.node, k).val;
  
 }
 private static TreeNode findKth (TreeNode root, int k) {
  if (root == null)
   return root;
  TreeNode right = findKth(root.right, k);
  if (count == k)
   return right;
  ++count;
  if (count == k)
   return root;
  return findKth(root.left, k);
 }
 /**
  * O(log n) complexity
  * @param root
  * @param k
  * @return
  */
    public static TreeNode findKth(Tree root, int k) {
     if (root.right.size() == k - 1)
      return root.node;
     else if (root.right.size() < k - 1)
      return findKth(root.left, k - root.right.size() - 1);
     else
      return findKth(root.right, k);
  
 }

Isomorphic Trees

An easier version of Scramble String. Two trees are called isomorphic if one of them can be obtained from other by a series of flips, i.e., by swapping left and right children of a number of nodes. Two empty trees are isomorphic.

Image source: http://www.geeksforgeeks.org/tree-isomorphism-problem/

The above two trees are isomorphic because : 2 & 3, Null & 6, 7 & 8 are flipped.

public boolean isIsomorphic(TreeNode p, TreeNode q){
    if(p == null)
        return q == null;
    if(q == null)
        return false;
    if(p.val != q.val)
        return false;
    return (isIsomorphic(p.left, q.left) && isIsomorphic(p.right, q.right)) 
    || (isIsomorphic(p.left, q.right) && isIsomorphic(p.right, q.left));
}

The amazing maze

The idea came from a FB interview question: design a maze. So I googled, and found tremendous solutions. Mainly there are three ways to design a maze:

• Depth-first search;
• Randomized Kruskal's algorithm;
• Randomized Prim's algorithm;
• and so on.

See Wikipedia for more information.

The goal here is to design a "perfect" maze:

• There are no cycles;
• There is a unique path from the start cell in the maze to the end cell. 

Here I use randomized Kruskal's algorithm with a disjoint set data structure to perform union method.  It works in the following way:

1. Create a list of all walls that potentially can be destroyed;
2. Randomly choose a wall index;
3. Union the two adjacent cells that are separated by the wall;
4. Repeat until all cells are in the same set.

The union method acts like knocking down the wall, i.e., if two cells are in the same set, they are connected. When all cells are in the same set, there must be one path from the start cell to the end cell. Moreover, since every time we union two cells that are in different sets, there is no path between the cell before union, and since after the union, no other wall will be knocked down between these two cells, so there will be a unique path from any cell to another cell in the maze. Thus fulfill the "perfect" maze requirement.

public class Maze {
 private int[] grid;
 private int rows;
 private int columns;
 
 private Maze(int rows, int columns) {
  //using 1D array to represent cells
  //index / columns = row in the maze
  //index % columns = col in the maze
  this.grid = new int[rows * columns];
  //one cell is surrounded by walls in four directions
  //initially create cells with all walls up
  Arrays.fill(grid, UP | RIGHT | DOWN | LEFT);
  this.rows = rows;
  this.columns = columns;
 }
 
 private static final int UP = 1;
 private static final int RIGHT = 2;
 private static final int  DOWN = 4;
 private static final int LEFT = 8;
 
 public static Maze createRandomMaze(int rows, int columns) {
  Maze maze = new Maze(rows, columns);
  //create all walls that potentially can be broken
  List walls = new ArrayList();
  for (int row = 0; row < rows; row++) {
   for (int col = 0; col < columns; col++) {
    if (row > 0) 
     //cell = row * columns + col
     //cell / columns = row
     //cell % columns = col
     // represent the grid in the maze
     //the upper wall of the lower cell is the lower wall of the upper cell
     // the left wall of the right cell is the right wall of the left cell
     //so we only need to consider two directions
     walls.add(new Wall(row * columns + col, UP));
    if (col > 0)
     walls.add(new Wall(row * columns + col, LEFT));
   }
  }
  
  DisjointSet diset = new ArrayDisjointSet(rows * columns);
  //Object for generating random numbers
  Random rand = new Random();
  while (diset.size() > 1) {
   //get an index randomly
   int wallIndex = rand.nextInt(walls.size());
   int cell1 = walls.get(wallIndex).cell;
   int cell2 = (walls.get(wallIndex).direction == UP) ?
     cell1 - columns ://choose the cell and the one above it, break the upper wall
      cell1 - 1;//choose the one left to it, break the left wall
   //if there is no path between two cells
   //i.e., they are not in the same set
   if (diset.find(cell1) != diset.find(cell2)) {
    if (walls.get(wallIndex).direction == UP) {
     //break the upper wall of cell1 
     //which is also the lower wall of cells2
     maze.grid[cell1] ^= UP;
     maze.grid[cell2] ^= DOWN;
    }
    else {
     maze.grid[cell1] ^= LEFT;
     maze.grid[cell2] ^= RIGHT;
    }
    diset.union(cell1, cell2);
   }
   //the wall is knocked down, dead, disappeared, over...
   walls.remove(wallIndex);
  }
  return maze;
 }
 public static class Wall {
  private final int cell;
  private final int direction;
  public Wall(int cell, int direction) {
   this.cell = cell;
   this.direction = direction;
  }
 }
}

The result of a 30 by 30 grids:

The source code can be found on my Github: https://github.com/shirleyyoung0812/mazeDFS.git

To people who devote their lives to the dream they have. 

Write all solutions for a^3+b^3 = c^3 + d^3, where a, b, c, d lie between [0, 10^5]

This is a FB interview question. Here are some feasible approaches. I followed the priority queue method:

Using a priority queue is almost certainly the simplest solution, and also the most practical one, since it's O(n) storage (with a log factor if you require bignums). Any solution which involves computing all possible sums and putting them in a map will require O(n^2) storage, which soon becomes impractical.

My naive, non-optimized implementation using a priority queue is O(n^2 log(n)) time. Even so, it took less than five seconds for n = 10000 and about 750 seconds for n = 100000, using a couple of megabytes of storage. It certainly could be improved.

The basic idea, as per your comment, is to initialize a priority queue with pairs (a, a+1) for a in the range [1, N), and then repeatedly increment the second value of the smallest (by sum of cubes) tuple until it reaches N. If at any time the smallest two elements in the queue are equal, you have a solution. (I could paste the code, but you only asked for a hint.)

I certainly didn't fully understand how he maintained O(n) storage in the Queue. When I increment the second value, I still have to store the pairs that has a cube sum that is not equal to the smallest element in the queue. The total space for the queue is still O(n^2), or more accurately O(n^2 / 2).
So when the range goes up to 10^5, it gives me OutOfMemoryError().

However, just for comparison, I also tried the HashMap method, the memory leak occurs even when range only goes to 10^4. This means the Map has a worse performance than the Priority Queue.

public class CubePair implements Comparable {
 //num1 will always be smaller than num2
 private int num1;
 private int num2;
 private int cubeSum;
 public CubePair(int a, int b) {
  if (a > b) {
   int tmp = a;
   a = b;
   b = tmp;
  }
  num1 = a;
  num2 = b;
  cubeSum = (int)(Math.pow(num1, 3) + Math.pow(num2, 3));
 }
 public boolean hasEqualSum(CubePair cp) {
  return cp.cubeSum == cubeSum;
 }
 public boolean equals(CubePair cp) {
  return num1 == cp.num1 && num2 == cp.num2;
 }
 public int getFirst() {
  return num1;
 }
 public int getSecond() {
  return num2;
 }
 public String toString() {
  return String.valueOf(num1) + ", " + String.valueOf(num2) + ";";
 }
 @Override
 public int compareTo(CubePair cp) {
  return cubeSum - cp.cubeSum;
 }
}
import java.util.*;
public class FindCube {
 public List> sameCubeSums(int range) {
  if (range <= 0)
   throw new IllegalArgumentException("range must be positive");
  List> rst = new ArrayList> ();
  PriorityQueue pq = new PriorityQueue ();
  for (int i = 1; i < range; i++) {
   pq.add(new CubePair(i, i + 1));
  }
  int prev = 0;
  int maxSize = 0;
  while (!pq.isEmpty()) {
   maxSize = Math.max(maxSize, pq.size());
   CubePair curr = pq.poll();
   if (pq.isEmpty())
    break;
   if (curr.hasEqualSum(pq.peek())) {
    addList(rst, curr, pq.peek());
    if (curr.getFirst() < pq.peek().getFirst())
     curr = pq.poll();
    else
     pq.poll();
   }
   if (curr.getFirst() <= prev)
    continue;
   for (int i = curr.getSecond() + 1; i <= range; i++) {
    CubePair tmp = new CubePair(curr.getFirst(), i);
    if (tmp.hasEqualSum(pq.peek())) {
     addList(rst, tmp, pq.peek());
    }
    else {
     pq.add(tmp);
    }
   }
   prev = curr.getFirst();
  }
  System.out.println("max queue size: " + maxSize);
  return rst;
 }
 private void addList(List> rst, CubePair pair1, CubePair pair2) {
  List pair = new ArrayList ();
  pair.add(pair1.toString());
  pair.add(pair2.toString());
  rst.add(new ArrayList (pair));
 }
}

Teaser: the HashMap method:

public List> sameCubeSums2(int range) {
  if (range <= 0)
   throw new IllegalArgumentException("range must be positive");
  Map> map = new HashMap>();
  List> rst = new ArrayList> ();
  for (int i = 1; i < range; i++) {
   for (int j = i + 1; j <= range; j++) {
    int cubeSum = (int)(Math.pow(i, 3) + Math.pow(j, 3));
    if (!map.containsKey(cubeSum)) {
     map.put(cubeSum, new ArrayList ());
     map.get(cubeSum).add(String.valueOf(i) + "; " + String.valueOf(j));
    }
    else 
     map.get(cubeSum).add(String.valueOf(i) + "; " + String.valueOf(j));
   }
  }
  for (List pairs : map.values()) {
   if (pairs.size() > 1) 
    rst.add(pairs);
  }
  return rst;
 }

Disjoint Set Union/Find ADT

Definition

• Set U = {a1, a2, ..., an}
• Maintain a partition of U, a set of subsets of U {S1, S2, ..., Sk} such that:
•    each pair of subsets Si and Sj are disjoint;
•    together, the subsets cover U;
•    each subset has a unique name. 
• Union(a, b) creates a new subset which is the union of a and b;
• Find(a) returns the representative member of a set: similar to find parent of a TreeNode in a tree; 
• Thus Disjoint Set can be represented by an up-tree;
• Disjoint set equivalence property: every element of a DS U/F structure belongs to exactly one set;
• Dynamic equivalence property: the set of an element can change after execution of a union.

Up-Tree Union-Find Data Structure

Image source: http://courses.cs.washington.edu/courses/cse326/00wi/handouts/lecture18/sld015.htm

• Each subset is an up-tree with its root as its representative member;
• All members of a given set are nodes in that set's up-tree;
• Not necessarily binary;
• Find(a): traverse from the leaf to the root;
• Union(a, b): union the root with the other;

Path Compression

Image source: http://courses.cs.washington.edu/courses/cse326/00wi/handouts/lecture18/sld034.htm

Points everything along the path of a find to the root;
Thus reduces the height of the entire access path to 1.


Union-by-rank 

Use an extra array to store the rank of a given node. Rank[a] is the depth of the tree rooted at a.

Image source: http://courses.cs.washington.edu/courses/cse326/00wi/handouts/lecture18/sld029.htm

Union(a, b): pick the shallower tree and point it at the deeper one.

Image source: http://courses.cs.washington.edu/courses/cse326/00wi/handouts/lecture18/sld031.htm

This can cut down on height of the new tree;
Find(a) complexity: a tree of height h must have at least 2 ^h nodes. Find(a) takes O(max height) time. Thus Find(a) takes O(log(n)) time.


Complexity of Union-by-rank path compression

Tarjan proved that the find operation on a set of n elements in a union with m union-by-rank subsets has worst complexity O(m * alpha(m,n)).

Implementation
This implementation uses an array.
The test data set: 16 integers range from 0 to 15.
After union, each set should contain 4 integers.

public class DisjointSets {
 //array[x] stores the root of the tree (representative of the set)
 //if array[x] is less than 0, that means x is the root of the tree (representative of the set)
 private int[] array;
 
 //initial number of elements;
 //also the initial number of disjoint sets
 //since every element is initially in its own set
 public DisjointSets(int numElements) {
  array = new int [numElements];
  //since every element is the root of its tree,
  //set each element in the array to negative
  Arrays.fill(array, -1);
 }

Every element is the root of the tree it belongs

Initial Array: every element is negative

public void union(int root1, int root2) {
  if (array[root2] < array[root1]) 
   array[root1] = root2; // root2 is taller; make root2 new root
  else {
   if (array[root1] == array[root2]) 
    array[root1]--;
   array[root2] = root1; // root1 equal or taller; make root1 new root
  }
 }

After first union

Array after first union

After second union

Array after second union

public int find(int x) {
  if (array[x] < 0)
   return x; //x is the root of the tree; return it
  else {
   //find the root of the tree
   array[x] = find(array[x]);
   return array[x];
  }
 }

Test code and result:

public static void main(String[] args) {
  int NumElements = 16;
  int NumInSameSet = 4;
  DisjointSets s = new DisjointSets(NumElements);
  int set1, set2;
  for (int k = 1; k < NumInSameSet; k *= 2) {
   for (int j = 0; j + k < NumElements; j += 2 * k) {
    set1 = s.find(j);
    System.out.println("set1: " + set1);
    set2 = s.find(j + k);
    System.out.println("set2: " + set2);
    s.union(set1, set2);
   }
  }
  for (int i = 0; i < NumElements; i++) {
   System.out.print(s.find(i) + "*");
   if (i % NumInSameSet == NumInSameSet - 1)
    System.out.println();
  }
  System.out.println(); 
 }

Longest Common Subsequence

Very typical 2D DP.

public static int longestCommonSubsequence (String a, String b) {
  if (a == null || b == null || a.length() == 0 || b.length() == 0)
   return 0;
  int len1 = a.length();
  int len2 = b.length();
  int[][] lcs = new int[len1 + 1][len2 + 1];
  lcs[0][0] = 0;
  for (int j = 0; j <= len2; j++) 
   lcs[0][j] = 0;
  for (int i = 0; i <= len1; i++) 
   lcs[i][0] = 0;
  for (int i = 1; i <= len1; i++) {
   for (int j = 1; j <= len2; j++) {
    if (a.charAt(i - 1) == b.charAt(j - 1)) {
     lcs[i][j] = Math.max(Math.max(lcs[i - 1][j], lcs[i][j - 1]), lcs[i - 1][j - 1] + 1);
    }
    else {
     lcs[i][j] = Math.max(Math.max(lcs[i - 1][j], lcs[i][j - 1]), lcs[i - 1][j - 1]);
    }
   }
  }
  return lcs[len1][len2];
 }

Number of ones in the binary representation of a number

Write a function that takes in an integer and returns the number of ones set in the binary representation.

This problem looks very easy. The way we do it is to compare the number  with 1 and left shift the number until it reaches zero.
Yeah...
But what about negative number? It is always less than zero.

The trick is, every negative number XOR with -1 will gives its positive counterpart less one (LO). For example, -123 ^ -1 = 122, -1 ^ -1 = 0. Since -1 has 32 ones, so the number of ones in any negative number is the number of zeros in LO. For example, the number of ones in -123 is the number of zeros in 122. So we only need to convert the negative number into its LO, then we can use the old method for positive integers.

public static int countOnes(int n) {
  if (n == 0)
   return 0;
  if (n == -1)
   return 32;
  int count = 0;
  boolean isNegative = false;
  if (n < 0) {
   isNegative = true;
   n = (-n) - 1;
  }
  while (n > 0) {
   if ((n & 1) == 1)
    count++;
   n = n >> 1;
  }
  return isNegative? 32 - count : count;
 }

Two Sum III Data Structure design

Two Sum III - Data structure design

 Total Accepted: 311 Total Submissions: 1345

Design and implement a TwoSum class. It should support the following operations:add and find.

add - Add the number to an internal data structure.
find - Find if there exists any pair of numbers which sum is equal to the value.

For example,

add(1); add(3); add(5);
find(4) -> true
find(7) -> false

I use a list, I see other implementations that use a map. But my implementation is faster. O(1) add, and O(n) find.

import java.util.*;
public class TwoSum {
 private List list;
 public TwoSum() {
  list = new ArrayList ();
 }
 public void add(int num) {
  list.add(num);
 }
 public boolean find (int sum) {
  for (int i = 0; i < list.size(); i++) {
   if (list.contains(sum - list.get(i))) {
    if (list.indexOf(sum - list.get(i)) == i)
     continue;
    return true;
   }
  }
  return false;
 }
}

Largest Number

Given a list of non negative integers, arrange them such that they form the largest number.

For example, given [3, 30, 34, 5, 9], the largest formed number is 9534330.

Note: The result may be very large, so you need to return a string instead of an integer.

I was in the approach when I tried to sort the array. In fact, we do need to sort the array, but not in the traditional way.

If we look at the example, we will quickly figure out that we need to compare the most significant digit in the array, then probably the next, and so on. But the question is, how to do it in an acceptable time manner? Besides, why do we need to put 3 in front of 30?

Thinking the problem in another way: Randomly pick two numbers XYZ and ABC from the array, why do we want to put XYZ (ABC) in advance of ABC(XYC)? Because if we combine two numbers, XYZABC (ABCXYZ) will be larger than ABCXYZ (XYZABC). For example, 3 and 30, 330 is larger than 303, so we want to put 3 in front of 30.

So the only thing we need to do is to write a comparator to compare the concatenations of two numbers, and sort the entire array!

Easier than you thought, right?

Note on string.concat() and +
String.concat() will throw a NullPointerException if either of the string is null, but a + b will return, very interesting:

It treats b as b = "null". Another way to look at + can be like this: 

public static String plus(String a, String b) {
  StringBuilder sb = new StringBuilder();
  return sb.append(a).append(b).toString();
 }

The concat() method, from Java src is like this:

public String concat(String str) {
        int otherLen = str.length();
        if (otherLen == 0) {
            return this;
        }
        char buf[] = new char[count + otherLen];
        getChars(0, count, buf, 0);
        str.getChars(0, otherLen, buf, count);
        return new String(0, count + otherLen, buf);
    }

Update: 2015 - 03 - 01

Update comparator method, note the number may be very large and overflow. 

private class StringComparator implements Comparator{
        public int compare(String s1, String s2){
            return (int)(Long.parseLong(s1 + s2) - Long.parseLong(s2 + s1));
        }
    }

public String largestNumber(int[] num) {
        if (num == null || num.length == 0)
            return "";
        String[] s = new String[num.length];
        for (int i = 0; i < num.length; i++) {
            s[i] = String.valueOf(num[i]);
        }
        Arrays.sort(s, new StringComparator ());
        String rst = "";
        for (int i = s.length - 1; i >= 0; i--) {
            rst += s[i];
        }
        int i = 0;
        while (i < rst.length() && rst.charAt(i) == '0')
            i++;
        if (i == rst.length())
            return "0";
        return rst.substring(i);
        
    }
    private class StringComparator implements Comparator {
        public int compare (String a, String b) {
            return Integer.parseInt(a.concat(b)) - Integer.parseInt(b.concat(a));
        }
    }

Graph traversal and a simple recommender system

I was practicing graph traversal when I found a video about FB's recommender system, so I thought, hey, why not try implementing one.

Apparently, I am not capable of implementing a real recommender system, but based on some concepts in the video, I did this small project.

There are three main parts in this project:
1. The network, which is implemented by a graph.(Graph, Node, Edge)
2. Find recommendations for a user(node) in the graph. (FindFriend)
3. Find connections from a node to another node.(FindFriend)

The Graph

Update: 2015 - 03 - 12

My first version of the graph looks, well, memory expensive, I optimized a little bit. Here is the new version.

/**
 * undirected graph
 * user can only retrieve the node by its label
 * all labels are unique
 * @author shirleyyoung
 *
 */
public class Graph {
 Map vertices;
 Set edges;
 Map> neighbors;
 
 
 public Graph (){
  vertices = new HashMap();
  edges = new HashSet();
  neighbors = new HashMap>();
 }
 
 /**
  * construct a graph from another graph
  * @param G
  */
 public Graph (Graph G) {
  this.vertices = new HashMap();
  this.edges = new HashSet();
  copyGraph(G);
 }
 /**
  * clone a graph from another one
  * ConcurrentModificationException: 
  * For example, it is not generally permissible 
  * for one thread to modify a Collection 
  * while another thread is iterating over it.
  */
 private void copyGraph(Graph G) {
  //clone nodes
  for (Node n : G.vertices.values()) {
   this.vertices.put(n.label, new Node(n));
  }
  //clone edges
  for(Edge e : G.edges){
   List nodes = (List) e.getNodes();
   Node n1 = nodes.get(0);
   Node n2 = nodes.get(1);
   this.edges.add(new Edge(vertices.get(n1.label), vertices.get(n2.label)));
   if(!neighbors.containsKey(n1))
    neighbors.put(n1, new ArrayList());
   if(!neighbors.containsKey(n2))
    neighbors.put(n2, new ArrayList());
   neighbors.get(n1).add(n2);
   neighbors.get(n2).add(n1);
  }
 }
 
 /**
  * Add vertex
  * @param label
  */
 public boolean addVertex(int label) {
  if(containsVertex(label))
   return false;
  vertices.put(label, new Node(label));
  return true;
 }
 
 /**
  * connect two nodes
  * @param l1
  * @param l2
  * @param distance
  * @return
  */
 public double addEdge(int l1, int l2, double distance) {
  if(!containsVertex(l1) || !containsVertex(l2))
   throw new NullPointerException("Graph doesn't contain such nodes");
  Edge e = getEdge(l1, l2);
  if(e != null)
   e.modifyWeight(distance);
  else{
   Node n1 = getNode(l1);
   Node n2 = getNode(l2);
   e = new Edge(n1, n2, distance);
   edges.add(e);
   if(!neighbors.containsKey(n1))
    neighbors.put(n1, new ArrayList());
   if(!neighbors.containsKey(n2))
    neighbors.put(n2, new ArrayList());
   neighbors.get(n1).add(n2);
   neighbors.get(n2).add(n1);
  }
  return e.weight;
 }
 public void chooseSource(int label) {
  Node source = getNode(label);
  source.dist = 0;
  
 }
 /**
  * if a node exists
  * @param label
  * @return
  */
 public boolean containsVertex(int label) {
  return vertices.containsKey(label);
 }
 
 /**
  * get the node 
  * @param label
  * @return
  */
 Node getNode(int label) {
  if (containsVertex(label))
   return vertices.get(label);
  return null;
 }
 /**
  * if there exists an edge between two node
  * @param l1
  * @param l2
  * @return
  */
 public boolean isConnected(int l1, int l2) {
  if(!containsVertex(l1) || !containsVertex(l2))
   throw new NullPointerException("Graph doesn't contain such node!");
  Edge tmp = new Edge(getNode(l1), getNode(l2));
  for(Edge e : edges){
   if(e.equals(tmp))
    return true;
  }
  return false;
  
 }
 /**
  * get an existing edge from the graph
  * @param l1
  * @param l2
  * @return
  */
 Edge getEdge(int l1, int l2){
  if(!containsVertex(l1) || !containsVertex(l2))
   throw new NullPointerException("Graph doesn't contain such node!");
  Edge tmp = new Edge(getNode(l1), getNode(l2));
  for(Edge e : edges){
   if(e.equals(tmp))
    return e;
  }
  return null;
 }
 /**
  * @return number of vertices in the graph
  */
 public int getSize() {
  return vertices.size();
 }
 /** 
  * @return number of edges in the graph
  */
 public int numEdges(){
  return edges.size();
 }
 
 
 public String toString() {
  StringBuilder s = new StringBuilder();
  String NEWLINE = System.getProperty("line.separator");
  s.append(getSize() + " vertices, " + numEdges() + " edges " + NEWLINE);
  for (Node v : vertices.values()) {
   s.append("Node: " + v.label + "\n");
   s.append("neighbors: \n");
   for (Node nb: neighbors.get(v)){
    s.append(nb.label + " ");
   }
   s.append(NEWLINE);
  }
  s.append(NEWLINE);
  for(Edge e : edges){
   List nodes = (List) e.getNodes();
   s.append(nodes.get(0).label).append(" - ").append(nodes.get(1).label + "\n");
  }
  s.append(NEWLINE);
  return s.toString();
 }
}
public class Node {
 int label;
 double dist;
 
 
 Node(int x) {
  label = x;
  dist = Integer.MAX_VALUE;
 }
 Node(Node n) {
  //only copy the label from another node, 
  //neighbors and edges need
  //to be redefined
  this.label = n.label;
  dist = Integer.MAX_VALUE;
 }
 
 
 public boolean equals(Node n) {
  return label == n.label;
 }
}
public class Edge implements Comparator {
 double weight;
 Node n1;
 Node n2;
 /**
  * default weight = 1.0
  * @param n1
  * @param n2
  */
 public Edge(Node n1, Node n2) {
  if (n1.equals (n2))
   throw new IllegalArgumentException("Cannot form an edge with itself!");
  this.n1 = n1;
  this.n2 = n2;
  weight = 1.0;
 }
 /**
  * constructor that allows user defined weight
  * @param n1
  * @param n2
  * @param weight
  */
 public Edge(Node n1, Node n2, double weight) {
  if (n1.equals (n2))
   throw new IllegalArgumentException("Dont't cheat, connecting with yourself doens't mean you have one more fan!");
  this.n1 = n1;
  this.n2 = n2;
  this.weight = weight;
 }
 /**
  * to modify the weight
  * @param w
  */
 public void modifyWeight(double w) {
  if (w <= 0.0)
   throw new IllegalArgumentException("Weight must be positive!");
  weight = w;
 }
 
 /**
  * get the nodes that are connected by this edge
  * @return
  */
 public Collection getNodes() {
  List nodes = new ArrayList ();
  nodes.add(n1);
  nodes.add(n2);
  return nodes;
 }
 /**
  * get the weight
  * @return
  */
 public double getWeight() {
  return weight;
 }
 public int compare(Edge e1, Edge e2){
  if(e1.weight > e2.weight)
   return 1;
  else if(e1.weight < e2.weight)
   return -1;
  return 0;
 }
 public boolean equals(Edge e){
  for(Node n : e.getNodes()){
   if(!this.getNodes().contains(n))
    return false;
  }
  return true;
 }
}

The graph is implemented by three classes: Node, Edge and Graph.

Node
Node class has three objects: a unique label, a list of neighbors and a map that stores edge and the neighbor node it connects. My initial idea is to include duplicate label conditions, because in reality it is possible that two people have the same name, sex, age, etc. Then I realize no matter how similar two nodes are, there must be something to distinguish them, so I finalized with unique label. If in future other data needs to be included in the calculation of distance between two nodes, a map<label, data> can be used to store extra data.

There are two methods in the Node class, getHash() and equals(), they have the same purpose: two check the equality of two nodes. I wrote the getHash() because initially I was thinking about duplicate labels, so I need to include neighbors to check the equality. However, if unique labels are used, this method is unnecessary.

import java.util.*;
public class Node {
 int label;
 List neighbors;
 //
 Map edges;
 
 Node(int x) {
  label = x;
  neighbors = new ArrayList ();
  edges = new HashMap ();
 }
 Node(Node n) {
  //only copy the label from another node, 
  //neighbors and edges need
  //to be redefined
  this.label = n.label;
  neighbors = new ArrayList();
  edges = new HashMap ();
 }
 //the hash function to determine the equality of two nodes
 //for graphs with unique nodes, this is not required
 private int getHash() {
  int hash_a = 378551;
  int hash_b = 63689;
  int hash = 0;
  for (Node neighbor : neighbors) {
   hash += hash * hash_a + neighbor.label;
   hash_a = hash_a * hash_b;
  }
  //hash += label;
  return hash;
 }
 public boolean equals(Node n) {
  return label == n.label && (getHash() == n.getHash());
 }
}

Edge
Initially I used a map in the node class to store the distance and connecting nodes, but I want the graph to look concrete, so I separated it and wrote this class. There are three objects in this class, two connecting nodes, and the weight. The weights are used to calculate the distance among nodes. There are two constructors, the first one set default weight to 1 and only require two nodes as inputs. The second one allows user to define weights. When Edge is initialized, both nodes will be added to the neighbor list of the other.

getNodes() method is used to get the two nodes that are connected by the edge and getWeight(), obviously, is used to get the weight.

import java.util.*;
public class Edge {
 int weight;
 Node n1;
 Node n2;
 //default weight = 1
 public Edge(Node n1, Node n2) {
  if (n1.equals (n2))
   throw new IllegalArgumentException("Cannot form an edge with itself!");
  if (n1.neighbors.contains(n2)) 
   throw new IllegalArgumentException("Edege exists!");
  this.n1 = n1;
  this.n2 = n2;
  n1.neighbors.add(n2);
  n2.neighbors.add(n1);
  weight = 1;
 }
 //constructor that allows user defined weight
 public Edge(Node n1, Node n2, int weight) {
  if (n1.equals (n2))
   throw new IllegalArgumentException("Dont't cheat, connecting with yourself doens't mean you have one more fan!");
  if (n1.edges.containsKey(n2) && n2.edges.containsKey(n1)) 
   throw new IllegalArgumentException("Edege exists!");
  this.n1 = n1;
  this.n2 = n2;
  n1.neighbors.add(n2);
  n2.neighbors.add(n1);
  this.weight = weight;
 }
 //to modify the weight
 public void modifyWeight(int w) {
  if (w <= 0)
   throw new IllegalArgumentException("Weight must be positive!");
  weight = w;
 }
 
 //get the nodes that are connected by this edge
 public List getNodes() {
  List nodes = new ArrayList ();
  nodes.add(n1);
  nodes.add(n2);
  return nodes;
 }
 //get the weight
 public int getWeight(Node n1, Node n2) {
  if (!(n1.equals(this.n1) && n2.equals(this.n2)) && !(n1.equals(this.n2) && n2.equals(this.n1)))
   throw new IllegalArgumentException("Wrong input node!");
  return weight;
 }
}

Graph
The Graph class is used to construct the "social network". It is an undirected graph (I don't see the reason if I connect with you but you cannot connect with me). I used a map to store <label, node> assuming users can only access the node by its label. A graph can be initialized as an empty graph or by clone another graph.

Some necessary methods include addVertex(), addEdge(), containsVertex(), isConnected() and toString(). Initially I mad getNode() method private, because I want the node can only be accessed within the class (accessed by label outside the class). Then my FindFriends class need to access the node, so I made it public. I am making a note here to make the modifications later. I commented out the Iterable version of getNeighbors() method because the user outside the class may only want to "see" the neighbors.

import java.util.*;


//undirected graph
//user can only retrieve the node by its label
//all labels are unique
//if other data needs to be stored in the node, a  map can be used
public class Graph {
 private Map vertices;
 //# of vertices
 private int size;
 //# of edges
 private int edges;
 
 
 public Graph (){
  size = 0;
  vertices = new HashMap();
  edges = 0;
 }
 
 //construct a graph from another graph
 public Graph (Graph G) {
  this.size = G.size;
  this.vertices = new HashMap();
  this.edges = G.edges;
  copyGraph(G);
 }
 //clone a graph from another one
 /*
  * ConcurrentModificationException: 
  * For example, it is not generally permissible 
  * for one thread to modify a Collection 
  * while another thread is iterating over it.
  */
 private void copyGraph(Graph G) {
  //clone nodes
  for (Node n : G.vertices.values()) {
   this.vertices.put(n.label, new Node(n));
  }
  //clone edges
  for (Node n : G.vertices.values()) {
   Node curr = getNode(n.label);
   for (Node w : n.neighbors) {
    Node neighbor = getNode(w.label);
    if (!isConnected(curr, neighbor)) {
     int weight = n.edges.get(w).getWeight(n, w);
     Edge e = new Edge(curr, neighbor, weight);
     curr.edges.put(neighbor, e);
     neighbor.edges.put(curr, e);
    }
    
   }
  }
 }
 
 //Add vertex
 public void addVertex(int label) {
  Node n = new Node(label);
  vertices.put(label, n);
  size++;
 }
 
 //Add edge
 //The edge class will take care of adding neighbors to the neighbor list of the node
 public void addEdge(int l1, int l2, int distance) {
  Node v = getNode(l1);
  Node w = getNode(l2);
  if (v.neighbors.contains(w) && w.neighbors.contains(v)) {
   System.out.println("Edge exists!");
   return;
  }
  Edge e = new Edge(v, w, distance);
  v.edges.put(w, e);
  w.edges.put(v, e);
  edges++;
 }
 
 //if a node exists
 public boolean containsVertex(int label) {
  return vertices.containsKey(label);
 }
 
 //if there exists an edge between two node
 public boolean isConnected(int l1, int l2) {
  return getNode(l1).edges.containsKey(getNode(l2)) 
    && getNode(l2).edges.containsKey(getNode(l1));
 }
 private boolean isConnected(Node n1, Node n2) {
  return n1.edges.containsKey(n2) && n2.edges.containsKey(n1);
 }
 
 public Node getNode(int label) {
  if (containsVertex(label))
   return vertices.get(label);
  return null;
 }
 
 /*public Iterable getNeighbors(int label) {
  if(!containsVertex(label))
   throw new IllegalArgumentException("Graph doesn't contain such node!");
  return getNode(label).neighbors;
 }*/
 
 //get neighbors of a node
 public String getNeighbors(int label) {
  String neighbor = "";
  for (Node n : getNode(label).neighbors) {
   neighbor += n.label + ", ";
  }
  return neighbor.substring(0, neighbor.length() - 2);
 }
 
 public int neighborSize(int label) {
  if (!containsVertex(label))
   throw new IllegalArgumentException("Graph doesn't contain such node!");
  return getNode(label).neighbors.size();
 }
 
 
 public String toString() {
  StringBuilder s = new StringBuilder();
  String NEWLINE = System.getProperty("line.separator");
  s.append(size + " vertices, " + edges + " edges " + NEWLINE);
  for (Node v : vertices.values()) {
   s.append("Node: " + v.label + "\n");
   for (Node w : v.neighbors) {
    s.append(w.label +  "; edge: " + v.edges.get(w).getWeight(v, w) + NEWLINE);
   }
   s.append(NEWLINE);
  }
  return s.toString();
 }
}

FindFriends
The purpose of this class is to, first, find desired number of recommendations for the user and, second, find connections between the user and a target.

This class is aimed to one user, so the constructor will require user to input a "user", kidding, a node. A list of potential friends will be generated upon initialization.

The potential friends list is generated from FOF, i.e., friends of friends. According to the FB video, a FB user on average has 100 friends, so FOF will be in the order of 10^4, if we consider third degree connection, it will be 10^6, so don't worry, you don't want to know that many people in your life.

Another map, distanceFOF is used to store the distance of FOF from the user. getDistance() is calculated by the following equation:

Of course it is from that interesting FB video. Make it simple, this equation calculate the priority of an FOF to the friend, to smaller the value, the high priority the FOF is, i.e., he or she will be highly recommended. Delta is the number of days that a person is connected with the other (user, friend i; friend i, FOF). I used the weight of the edge to represent delta. I didn't fully understand what "friends" in the divisor means, I guess it means the friends size(neighbor list) of the friend i. The equation then adds up all friends of the user that are friends with the FOF. 

In fact, I don't have to make things that complicated, I am not going to need this equation anyway, but , just for fun. :)

Update: 2015 - 03 - 30

So this class is finally updated too. :)

import java.util.*;
/**
 * This class is used for 
 * 1. find recommendations from friends of friends of the user
 * 2. find the closest connections between the user and a person
 * @author shirleyyoung
 *
 */
public class FindFriends {
 Node user;
 Graph g;
 Set potentialFriends;
 Map scoreFOF;
 int numRecommendations;
 
 /**
  * this constructor will find the potential friends list for the user 
  * and generate the distance between the user and a potential friend (fof)
  */
 public FindFriends(int label, int numRecommendations, Graph g){
  if (numRecommendations <= 0)
   throw new IllegalArgumentException("At least one recommendation, please...");
  this.g = g;
  if(!g.containsVertex(label))
   throw new IllegalArgumentException("No such user!");
  user = g.getNode(label);
  potentialFriends = new HashSet ();
  scoreFOF = new HashMap ();
  this.numRecommendations = numRecommendations;
  getPotentialFriends();
 }
 
 //find all fof from user's friends
 private void getPotentialFriends() {
  List neighbors = g.neighbors.get(user);
  for (Node w : neighbors) {
   for (Node fof : g.neighbors.get(w)) {
    if (!neighbors.contains(fof) && !fof.equals(user) 
      && potentialFriends.add(fof)) 
     getDistance(fof);
   }
  }
 }
 
 
 /**
  * distance is calculated by a formula from FB
  * the weight of the edge is actually the number of days 
  * that two people are connected
  * @param fof
  */
 private void getDistance(Node fof) {
  if(scoreFOF.containsKey(fof))
   return;
  double v = 0;
  for (Node ffof : g.neighbors.get(fof)) {
   if(g.isConnected(ffof.label, user.label)){
    //distance between user and friend
    double u_f = g.getEdge(user.label, ffof.label).weight;
    //distance between friend and fof
    double f_fof = g.getEdge(fof.label, ffof.label).weight;
    v += Math.pow(u_f * f_fof, -0.3) / Math.sqrt(g.neighbors.get(ffof).size());
   }
  }
  scoreFOF.put(fof, v);
 }
 
 /**
  * find recommendations
  * fofs with shortest distance will be recommended
  * Greedy approach
  * @return
  */
 private Collection getRecommendations() {
  NodeComparator nc = new NodeComparator() ;
  PriorityQueue recommendedFriend = new PriorityQueue(numRecommendations, nc);    
  
  for (Node fof : potentialFriends) {
   //System.out.println(fof.label);
   if (recommendedFriend.size() < numRecommendations) {
    recommendedFriend.add(fof);
   } else {
    if(nc.compare(fof, recommendedFriend.peek()) < 0) {
     recommendedFriend.poll();
     recommendedFriend.offer(fof);
    }
   }
  }
  return recommendedFriend;
 }
 public String recommendedFriend() {
  Collection pq = getRecommendations();
  StringBuilder sb = new StringBuilder();
  sb.append("People you may know: \n");
  for (Node n : pq) {
   sb.append(n.label).append(", ");
  }
  return sb.delete(sb.length() - 2, sb.length() - 1).append("\n*****").toString();
 }
 private class NodeComparator implements Comparator {
  public int compare(Node a, Node b) {
   double da = scoreFOF.get(a);
   double db = scoreFOF.get(b);
   if (da - db < 0)
    return 1;
   else if (da - db > 0)
    return -1;
   return 0;
   
  }
 
 }
 
 
 /**
  * find the shortest path from the user to a random (-.-)person
  * BFS is used
  * @param target
  * @param termination
  * @return
  */
 private List> findConnections(Node target, int termination) {
  if(termination < 3){
   termination = 3;
  }
  //
  Map> predecessor = new HashMap>();
  //
  Map distance = new HashMap(); 
  List> connections = new ArrayList> ();
  getConnections(target, predecessor, distance, termination);
  if (distance.size() == 1)
   return connections;
  getList(target, predecessor, distance, connections, new ArrayList());
  return connections;
 }
 
 private void getConnections(Node target, Map> predecessor, 
   Map distance, int termination) {
  Queue q = new LinkedList ();
  predecessor.put(user, new ArrayList());
  distance.put(user, 0);
  q.offer(user);
  boolean found = false;
  //terminate the search after certain degree or if the whole graph has been searched
  int degree = 0;
  while (distance.size() < g.getSize() && degree < termination && !found) {
   Node curr = q.poll();
   if (curr.equals(target)) {
    found = true;
    break;
   }
   for (Node neighbor : g.neighbors.get(curr)) {
    if (neighbor.equals(user))
     continue;
    if (!predecessor.containsKey(neighbor)) {
     predecessor.put(neighbor, new ArrayList());
     predecessor.get(neighbor).add(curr);
    }
    else {
     if (!predecessor.get(neighbor).contains(curr))
      predecessor.get(neighbor).add(curr);
    }
    if (!distance.containsKey(neighbor)) {
     distance.put(neighbor, distance.get(curr) + 1);
    }
    q.add(neighbor);
   }
  }
 }
 private void getList(Node curr, Map> predecessor, Map distance, 
   List> connections, List path) {
  path.add(curr);
  if (curr.equals(user)) {
   Collections.reverse(path);
   connections.add(new ArrayList (path));
   //Never ever forget this!
   Collections.reverse(path);
  }
  else {
   for (Node n : predecessor.get(curr)) {
    if (distance.containsKey(n) && distance.get(curr) == distance.get(n) + 1) {
     getList(n, predecessor, distance, connections, path);
    }
   }
  }
  path.remove(path.size() - 1);
 }
 public String connection(int label, int termination) {
  if(!g.containsVertex(label))
   throw new IllegalArgumentException("No such user!");
  Node target = g.getNode(label);
  List> connections = findConnections(target, termination);
  String NEWLINE = System.getProperty("line.separator");
  StringBuilder sb = new StringBuilder();
  sb.append("You can be connected with " + target.label + " through: " + NEWLINE);
  for (List path : connections) {
   for (Node n : path) {
    sb.append(n.label + " -> ");
   }
   sb.delete(sb.length() - 4, sb.length() - 1);
   sb.append(NEWLINE);
   
  }
  return sb.toString();
 }
 
}

After initialization, all the FOFs and distances will be generated. 

public class FindFriends {
 Node user;
 List potentialFriends;
 //all friends of the user that connect with fof 
 Map> connectingFriends;
 Map distanceFOF;
 int numRecommendations;
 int GraphSize;
 
 /*
  * this constructor will find the potential friends list for the user 
  * and generate the distance between the user and a potential friend (fof)
  */
 public FindFriends(Node n, int numRecommendations, int GraphSize){
  if (numRecommendations <= 0)
   throw new IllegalArgumentException("At least one recommendation, please...");
  user = n;
  potentialFriends = new ArrayList ();
  connectingFriends = new HashMap>();
  distanceFOF = new HashMap ();
  this.numRecommendations = numRecommendations;
  this.GraphSize = GraphSize;
  getPotentialFriends(n);
  getDistance();
 }
 
 //find all fof from user's friends
 private void getPotentialFriends(Node n) {
  for (Node w : n.neighbors) {
   for (Node fof : w.neighbors) {
    if (!n.neighbors.contains(fof) && !fof.equals(user)) {
     if (!potentialFriends.contains(fof))
      potentialFriends.add(fof);
     if (!connectingFriends.containsKey(fof)) {
      connectingFriends.put(fof, new ArrayList());
      connectingFriends.get(fof).add(w);
     }
     else 
      connectingFriends.get(fof).add(w);
    }
   }
  }
 }
 /*
  * distance is calculated by a formula from FB
  * the weight of the edge is actually the number of days 
  * that two people are connected
  */
 private void getDistance() {
  for (Node fof : potentialFriends) {
   double v = 0;
   for (Node friend : connectingFriends.get(fof)) {
    //distance between user and friend
    double u_f = user.edges.get(friend).getWeight(user, friend);
    //distance between friend and fof
    double f_fof = friend.edges.get(fof).getWeight(friend, fof);
    v += Math.pow(u_f * f_fof, -0.3) / Math.sqrt(friend.neighbors.size());
   }
   distanceFOF.put(fof, v);
  }
 }

Find recommendations

Now all we need to do is to return the number of recommendations required. I used a priority queue with a fixed size, the number of recommendations. The queue will be sorted by the distance of the FOF with the user. If the queue reaches its initialized size, the queue will remove the last element, if it is larger than the current FOF.

/*
  * find recommendations
  * fofs with shortest distance will be recommended
  */
 private PriorityQueue getRecommendations() {
  NodeComparator nc = new NodeComparator() ;
  PriorityQueue recommendedFriend = new PriorityQueue(numRecommendations, nc);    
  Collections.sort(potentialFriends, nc);
  Node last = null;
  for (Node fof : potentialFriends) {
   //System.out.println(fof.label);
   if (recommendedFriend.size() < numRecommendations) {
    recommendedFriend.add(fof);
    last = fof;
   }
   else {
    if(nc.compare(fof, last) < 0) {
     System.out.println(last.label);
     recommendedFriend.remove(last);
     recommendedFriend.add(fof);
     last = fof;
    }
   }
  }
  return recommendedFriend;
 }
 public String recommendedFriend() {
  PriorityQueue pq = getRecommendations();
  StringBuilder sb = new StringBuilder();
  sb.append("People you may know: \n");
  for (Node n : pq) {
   sb.append(n.label).append(", ");
  }
  return sb.delete(sb.length() - 2, sb.length() - 1).append("\n*****").toString();
 }
 private class NodeComparator implements Comparator {
  public int compare(Node a, Node b) {
   double da = distanceFOF.get(a);
   double db = distanceFOF.get(b);
   if (da - db < 0)
    return -1;
   else if (da - db > 0)
    return 1;
   return 0;
   
  }
 
 }

Find connections
This is not my initial plan. After I finished recommendation part, I thought, eh, my purpose is to learn BFS and DFS, but there is no BFS and DFS in this project. I know there is this find connections product on Linkedin, so I decided to try it myself. When I googled "the shortest path" yesterday, all it showed were some advanced algorithms like A*. I was ready to take the pain and try one, but my friend reminded me that BFS actually works. And indeed, it worked. These three methods combine BFS and DFS, it will return all the shortest path from the user to the target, i.e., you can ask anyone you are more familiar with to introduce you. :)

The idea came from a LeetCode problem Word Ladder, take a look at my blog if you are interested. Probably that problem is the origin of all of these: I wasn't familiar with BFS and DFS.

/*
  * find the shortest path from the user to a random (-.-)person
  * BFS is used
  */
 private List> findConnections(Node target) {
  //
  Map> predecessor = new HashMap>();
  //
  Map distance = new HashMap(); 
  List> connections = new ArrayList> ();
  getConnections(target, predecessor, distance);
  if (distance.size() == 1)
   return connections;
  getList(target, predecessor, distance, connections, new ArrayList());
  return connections;
 }
 
 private void getConnections(Node target, Map> predecessor, 
   Map distance) {
  Queue q = new LinkedList ();
  predecessor.put(user, new ArrayList());
  distance.put(user, 0);
  q.offer(user);
  boolean found = false;
  //is it possible to terminate the recursion without knowing the graph size
  //if no path is found? 
  while (distance.size() < GraphSize && predecessor.size() < GraphSize && !found) {
   Node curr = q.poll();
   if (curr.equals(target)) {
    found = true;
    continue;
   }
   for (Node neighbor : curr.neighbors) {
    if (neighbor.equals(user))
     continue;
    if (!predecessor.containsKey(neighbor)) {
     predecessor.put(neighbor, new ArrayList());
     predecessor.get(neighbor).add(curr);
    }
    else {
     if (!predecessor.get(neighbor).contains(curr))
      predecessor.get(neighbor).add(curr);
    }
    if (!distance.containsKey(neighbor)) {
     distance.put(neighbor, distance.get(curr) + 1);
    }
    q.add(neighbor);
   }
  }
 }
 private void getList(Node curr, Map> predecessor, Map distance, 
   List> connections, List path) {
  path.add(curr);
  if (curr.equals(user)) {
   Collections.reverse(path);
   connections.add(new ArrayList (path));
   //Never ever forget this!
   Collections.reverse(path);
  }
  else {
   for (Node n : predecessor.get(curr)) {
    if (distance.containsKey(n) && distance.get(curr) == distance.get(n) + 1) {
     getList(n, predecessor, distance, connections, path);
    }
   }
  }
  path.remove(path.size() - 1);
 }
 public String connection(Node target) {
  List> connections = findConnections(target);
  String NEWLINE = System.getProperty("line.separator");
  StringBuilder sb = new StringBuilder();
  sb.append("You can be connected with " + target.label + " through: " + NEWLINE);
  for (List path : connections) {
   for (Node n : path) {
    sb.append(n.label + " -> ");
   }
   sb.delete(sb.length() - 4, sb.length() - 1);
   sb.append(NEWLINE);
   
  }
  return sb.toString();
 }

Test

I drew this graph randomly for tests. Honestly, it took me a while to figure out what I was drawing. 

Graph

Well, at least my code gives me the correct answer, worth the pain.

FindFriends

It took me a while to figure out that I forgot to reverse the reversed path list. -_-||| Eh, otherwise I should be sleeping right now.


Source code
All source code can be found on GitHub: https://github.com/shirleyyoung0812/Graph.git

import java.util.*;


//undirected graph
//user can only retrieve the node by its label
//all labels are unique
//if other data needs to be stored in the node, a  map can be used
public class Graph {
 private Map vertices;
 //# of vertices
 private int size;
 //# of edges
 private int edges;
 
 
 public Graph (){
  size = 0;
  vertices = new HashMap();
  edges = 0;
 }
 
 //construct a graph from another graph
 public Graph (Graph G) {
  this.size = G.size;
  this.vertices = new HashMap();
  this.edges = G.edges;
  copyGraph(G);
 }
 //clone a graph from another one
 /*
  * ConcurrentModificationException: 
  * For example, it is not generally permissible 
  * for one thread to modify a Collection 
  * while another thread is iterating over it.
  */
 private void copyGraph(Graph G) {
  //clone nodes
  for (Node n : G.vertices.values()) {
   this.vertices.put(n.label, new Node(n));
  }
  //clone edges
  for (Node n : G.vertices.values()) {
   Node curr = getNode(n.label);
   for (Node w : n.neighbors) {
    Node neighbor = getNode(w.label);
    if (!isConnected(curr, neighbor)) {
     int weight = n.edges.get(w).getWeight(n, w);
     Edge e = new Edge(curr, neighbor, weight);
     curr.edges.put(neighbor, e);
     neighbor.edges.put(curr, e);
    }
    
   }
  }
 }
 
 //Add vertex
 public void addVertex(int label) {
  Node n = new Node(label);
  vertices.put(label, n);
  size++;
 }
 
 //Add edge
 //The edge class will take care of adding neighbors to the neighbor list of the node
 public void addEdge(int l1, int l2, int distance) {
  Node v = getNode(l1);
  Node w = getNode(l2);
  if (v.neighbors.contains(w) && w.neighbors.contains(v)) {
   System.out.println("Edge exists!");
   return;
  }
  Edge e = new Edge(v, w, distance);
  v.edges.put(w, e);
  w.edges.put(v, e);
  edges++;
 }
 
 //if a node exists
 public boolean containsVertex(int label) {
  return vertices.containsKey(label);
 }
 
 //if there exists an edge between two node
 public boolean isConnected(int l1, int l2) {
  return getNode(l1).edges.containsKey(getNode(l2)) 
    && getNode(l2).edges.containsKey(getNode(l1));
 }
 private boolean isConnected(Node n1, Node n2) {
  return n1.edges.containsKey(n2) && n2.edges.containsKey(n1);
 }
 
 public Node getNode(int label) {
  if (containsVertex(label))
   return vertices.get(label);
  return null;
 }
 
 /*public Iterable getNeighbors(int label) {
  if(!containsVertex(label))
   throw new IllegalArgumentException("Graph doesn't contain such node!");
  return getNode(label).neighbors;
 }*/
 
 //get neighbors of a node
 public String getNeighbors(int label) {
  String neighbor = "";
  for (Node n : getNode(label).neighbors) {
   neighbor += n.label + ", ";
  }
  return neighbor.substring(0, neighbor.length() - 2);
 }
 
 public int neighborSize(int label) {
  if (!containsVertex(label))
   throw new IllegalArgumentException("Graph doesn't contain such node!");
  return getNode(label).neighbors.size();
 }
 
 
 public String toString() {
  StringBuilder s = new StringBuilder();
  String NEWLINE = System.getProperty("line.separator");
  s.append(size + " vertices, " + edges + " edges " + NEWLINE);
  for (Node v : vertices.values()) {
   s.append("Node: " + v.label + "\n");
   for (Node w : v.neighbors) {
    s.append(w.label +  "; edge: " + v.edges.get(w).getWeight(v, w) + NEWLINE);
   }
   s.append(NEWLINE);
  }
  return s.toString();
 }
}
import java.util.*;

public class Node {
 int label;
 List neighbors;
 //
 Map edges;
 
 Node(int x) {
  label = x;
  neighbors = new ArrayList ();
  edges = new HashMap ();
 }
 Node(Node n) {
  //only copy the label from another node, 
  //neighbors and edges need
  //to be redefined
  this.label = n.label;
  neighbors = new ArrayList();
  edges = new HashMap ();
 }
 //the hash function to determine the equality of two nodes
 //for graphs with unique nodes, this is not required
 private int getHash() {
  int hash_a = 378551;
  int hash_b = 63689;
  int hash = 0;
  for (Node neighbor : neighbors) {
   hash += hash * hash_a + neighbor.label;
   hash_a = hash_a * hash_b;
  }
  //hash += label;
  return hash;
 }
 public boolean equals(Node n) {
  return label == n.label && (getHash() == n.getHash());
 }
}
import java.util.*;
public class Edge {
 int weight;
 Node n1;
 Node n2;
 //default weight = 1
 public Edge(Node n1, Node n2) {
  if (n1.equals (n2))
   throw new IllegalArgumentException("Cannot form an edge with itself!");
  if (n1.neighbors.contains(n2)) 
   throw new IllegalArgumentException("Edege exists!");
  this.n1 = n1;
  this.n2 = n2;
  n1.neighbors.add(n2);
  n2.neighbors.add(n1);
  weight = 1;
 }
 //constructor that allows user defined weight
 public Edge(Node n1, Node n2, int weight) {
  if (n1.equals (n2))
   throw new IllegalArgumentException("Dont't cheat, connecting with yourself doens't mean you have one more fan!");
  if (n1.edges.containsKey(n2) && n2.edges.containsKey(n1)) 
   throw new IllegalArgumentException("Edege exists!");
  this.n1 = n1;
  this.n2 = n2;
  n1.neighbors.add(n2);
  n2.neighbors.add(n1);
  this.weight = weight;
 }
 //to modify the weight
 public void modifyWeight(int w) {
  if (w <= 0)
   throw new IllegalArgumentException("Weight must be positive!");
  weight = w;
 }
 
 //get the nodes that are connected by this edge
 public List getNodes() {
  List nodes = new ArrayList ();
  nodes.add(n1);
  nodes.add(n2);
  return nodes;
 }
 //get the weight
 public int getWeight(Node n1, Node n2) {
  if (!(n1.equals(this.n1) && n2.equals(this.n2)) && !(n1.equals(this.n2) && n2.equals(this.n1)))
   throw new IllegalArgumentException("Wrong input node!");
  return weight;
 }
}
import java.util.*;

/*
 * This class is used for 
 * 1. find recommendations from friends of friends of the user
 * 2. find the closest connections between the user and a person
 */
public class FindFriends {
 Node user;
 List potentialFriends;
 //all friends of the user that connect with fof 
 Map> connectingFriends;
 Map distanceFOF;
 int numRecommendations;
 int GraphSize;
 
 /*
  * this constructor will find the potential friends list for the user 
  * and generate the distance between the user and a potential friend (fof)
  */
 public FindFriends(Node n, int numRecommendations, int GraphSize){
  if (numRecommendations <= 0)
   throw new IllegalArgumentException("At least one recommendation, please...");
  user = n;
  potentialFriends = new ArrayList ();
  connectingFriends = new HashMap>();
  distanceFOF = new HashMap ();
  this.numRecommendations = numRecommendations;
  this.GraphSize = GraphSize;
  getPotentialFriends(n);
  getDistance();
 }
 
 //find all fof from user's friends
 private void getPotentialFriends(Node n) {
  for (Node w : n.neighbors) {
   for (Node fof : w.neighbors) {
    if (!n.neighbors.contains(fof) && !fof.equals(user)) {
     if (!potentialFriends.contains(fof))
      potentialFriends.add(fof);
     if (!connectingFriends.containsKey(fof)) {
      connectingFriends.put(fof, new ArrayList());
      connectingFriends.get(fof).add(w);
     }
     else 
      connectingFriends.get(fof).add(w);
    }
   }
  }
 }
 /*
  * distance is calculated by a formula from FB
  * the weight of the edge is actually the number of days 
  * that two people are connected
  */
 private void getDistance() {
  for (Node fof : potentialFriends) {
   double v = 0;
   for (Node friend : connectingFriends.get(fof)) {
    //distance between user and friend
    double u_f = user.edges.get(friend).getWeight(user, friend);
    //distance between friend and fof
    double f_fof = friend.edges.get(fof).getWeight(friend, fof);
    v += Math.pow(u_f * f_fof, -0.3) / Math.sqrt(friend.neighbors.size());
   }
   distanceFOF.put(fof, v);
  }
 }
 /*
  * find recommendations
  * fofs with shortest distance will be recommended
  */
 private PriorityQueue getRecommendations() {
  NodeComparator nc = new NodeComparator() ;
  PriorityQueue recommendedFriend = new PriorityQueue(numRecommendations, nc);    
  Collections.sort(potentialFriends, nc);
  Node last = null;
  for (Node fof : potentialFriends) {
   //System.out.println(fof.label);
   if (recommendedFriend.size() < numRecommendations) {
    recommendedFriend.add(fof);
    last = fof;
   }
   else {
    if(nc.compare(fof, last) < 0) {
     System.out.println(last.label);
     recommendedFriend.remove(last);
     recommendedFriend.add(fof);
     last = fof;
    }
   }
  }
  return recommendedFriend;
 }
 public String recommendedFriend() {
  PriorityQueue pq = getRecommendations();
  StringBuilder sb = new StringBuilder();
  sb.append("People you may know: \n");
  for (Node n : pq) {
   sb.append(n.label).append(", ");
  }
  return sb.delete(sb.length() - 2, sb.length() - 1).append("\n*****").toString();
 }
 private class NodeComparator implements Comparator {
  public int compare(Node a, Node b) {
   double da = distanceFOF.get(a);
   double db = distanceFOF.get(b);
   if (da - db < 0)
    return -1;
   else if (da - db > 0)
    return 1;
   return 0;
   
  }
 
 }
 
 /*
  * find the shortest path from the user to a random (-.-)person
  * BFS is used
  */
 private List> findConnections(Node target) {
  //
  Map> predecessor = new HashMap>();
  //
  Map distance = new HashMap(); 
  List> connections = new ArrayList> ();
  getConnections(target, predecessor, distance);
  if (distance.size() == 1)
   return connections;
  getList(target, predecessor, distance, connections, new ArrayList());
  return connections;
 }
 
 private void getConnections(Node target, Map> predecessor, 
   Map distance) {
  Queue q = new LinkedList ();
  predecessor.put(user, new ArrayList());
  distance.put(user, 0);
  q.offer(user);
  boolean found = false;
  //is it possible to terminate the recursion without knowing the graph size
  //if no path is found? 
  while (distance.size() < GraphSize && predecessor.size() < GraphSize && !found) {
   Node curr = q.poll();
   if (curr.equals(target)) {
    found = true;
    continue;
   }
   for (Node neighbor : curr.neighbors) {
    if (neighbor.equals(user))
     continue;
    if (!predecessor.containsKey(neighbor)) {
     predecessor.put(neighbor, new ArrayList());
     predecessor.get(neighbor).add(curr);
    }
    else {
     if (!predecessor.get(neighbor).contains(curr))
      predecessor.get(neighbor).add(curr);
    }
    if (!distance.containsKey(neighbor)) {
     distance.put(neighbor, distance.get(curr) + 1);
    }
    q.add(neighbor);
   }
  }
 }
 private void getList(Node curr, Map> predecessor, Map distance, 
   List> connections, List path) {
  path.add(curr);
  if (curr.equals(user)) {
   Collections.reverse(path);
   connections.add(new ArrayList (path));
   //Never ever forget this!
   Collections.reverse(path);
  }
  else {
   for (Node n : predecessor.get(curr)) {
    if (distance.containsKey(n) && distance.get(curr) == distance.get(n) + 1) {
     getList(n, predecessor, distance, connections, path);
    }
   }
  }
  path.remove(path.size() - 1);
 }
 public String connection(Node target) {
  List> connections = findConnections(target);
  String NEWLINE = System.getProperty("line.separator");
  StringBuilder sb = new StringBuilder();
  sb.append("You can be connected with " + target.label + " through: " + NEWLINE);
  for (List path : connections) {
   for (Node n : path) {
    sb.append(n.label + " -> ");
   }
   sb.delete(sb.length() - 4, sb.length() - 1);
   sb.append(NEWLINE);
   
  }
  return sb.toString();
 }
 
}