Merge k sorted arrays

Merge 'k' sorted arrays, each array may have max 'n' elements 

This question follows the same approach as Merge k sorted lists.  The only difference is that now we are dealing with array, we lose the advantage of the "next" pointer. I use a structure that record the array's position at the input list, the index of the element in the array and the element itself to solve the problem.

/**
 * Merge 'k' sorted arrays, each array may have max 'n' elements
 * @author shirleyyoung
 *
 */
import java.util.*;
public class MergeKSortedArrays {
 private static class Position {
  //the position of the array in the list
  int listPos;
  //the index of current element
  int index;
  //the element
  int element;
  public Position(int listPos, int index, int element) {
   this.listPos = listPos;
   this.index = index;
   this.element = element;
  }
 }
 public static List mergeArrays(List arrays) {
  if (arrays == null || arrays.size() == 0) {
   throw new IllegalArgumentException("Invalid input!");
  }
  PriorityQueue pq = new PriorityQueue (new Comparator() {
   public int compare(Position a, Position b) {
    if (a.element - b.element < 0) 
     return -1;
    else if (a.element - b.element > 0)
     return 1;
    else if (a.listPos - b.listPos < 0)
     return -1;
    else if (a.listPos - b.listPos > 0)
     return 1;
    else if (a.index - b.index < 0)
     return -1;
    else if (a.index - b.index > 0)
     return 1;
    else
     return 0;
   }
  });
  
  for (int i = 0; i < arrays.size(); i++) {
   pq.add(new Position(i, 0, arrays.get(i)[0]));
  }
  List rst = new ArrayList ();
  while (!pq.isEmpty()) {
   Position curr = pq.poll();
   rst.add(curr.element); 
   if (curr.index < arrays.get(curr.listPos).length - 1) {
    int nextIndex = curr.index + 1;
    int next = arrays.get(curr.listPos)[nextIndex];
    pq.add(new Position(curr.listPos, nextIndex, next)); 
   }
  }
  return rst;
 }

 public static void main(String[] args) {
  List arrays = new ArrayList ();
  int[] a = {1, 3, 5, 7, 10};
  int[] b = {2, 4, 6, 8};
  int[] c = {9, 12, 15};
  int[] d = {11, 13, 14, 16, 17};
  int[] e = {11, 12, 13, 14, 15};
  arrays.add(a);
  arrays.add(b);
  arrays.add(c);
  arrays.add(d);
  arrays.add(e);
  
  //System.out.println(arrays.size());
  List rst = mergeArrays(arrays);
  for (Integer i : rst) {
   System.out.print(i + " ");
  }
  System.out.println();
 }
}

Find number of online users given a list of user's login and logout time

A period of time where users login and logout, given a sets of login and logout

time pairs, write a function that can show the number of users online at any given time

Using interval tree  to solve the problem.

public class findNumberOfUsers {
 private static class LogTime implements Comparable{
  int start;
  int end;
  LogTime(int start, int end) {
   if (end < start)
    throw new IllegalArgumentException("Illegal input time interval");
   this.start = start;
   this.end = end;
  }
  public boolean contains(int time) {
   return start <= time && end >= time;
  }
  public int compareTo(LogTime timeInterval) {
   if (start < timeInterval.start)
    return -1;
   else if (start > timeInterval.start)
    return 1;
   else if (end < timeInterval.end)
    return -1;
   else if (end > timeInterval.end)
    return 1;
   else
    return 0;
  }
  public String toString() {
   return "[" + String.valueOf(start) + ", " + String.valueOf(end) + "]";
  }
 }
 
 private class Node {
  LogTime timeInt;
  V label;
  Node left, right;
  //int N;
  int max;
  Node (LogTime time, V label) {
   timeInt = time;
   this.label = label;
   this.max = time.end;
  } 
 }
 private Node root;
 
 /************************
  * find a LogTime
  ***********************/
 public boolean contains(LogTime time) {
  return get(time) != null;
 }
 public V get(LogTime time) {
  return get(root, time);
 }
 private V get(Node node, LogTime time) {
  if (node == null)
   return null;
  int cmp = time.compareTo(node.timeInt);
  if (cmp == 0)
   return node.label;
  else if (cmp < 0) {
   return get(node.left, time);
  }
  else {
   return get(node.right, time);
  }
 }
 
 /************************
  * insertion
  ***********************/
 public void put(LogTime time, V label) {
  if (contains(time)) {
   System.out.println("Node exists!");
   return;
  }
  root = insert(root, time, label);
 }
 private Node insert(Node node, LogTime time, V label) {
  if (node == null) {
   return new Node(time, label);
  }
  int cmp = time.compareTo(node.timeInt);
  if (cmp < 0) 
    node.left = insert(node.left, time, label);
  else 
   node.right = insert(node.right, time, label);
  fix(node);
  return node;
 }
 private void fix(Node node) {
  if (node == null)
   return;
  node.max = max3(node.timeInt.end, max(node.left), max(node.right));
 }
 private int max(Node node) {
  if (node == null)
   return Integer.MIN_VALUE;
  return node.max;
 }
 private int max3(int a, int b, int c) {
  return Math.max(a, Math.max(b, c));
 }
 
 /**
  * given a time t, return number of users online
  * @param t
  * @return
  */
 
 public int search(int t) {
  return search(root, t);
 }
 
 private int search(Node node, int t) {
  if (node == null)
   return 0;
  int left = 0;
  int right = 0;
  int ro = 0;
  if (node.timeInt.contains(t))
   ro = 1;
  if (node.left != null && t < node.left.max)
   left = search(node.left, t);
  if (node.right != null && t  fu = new findNumberOfUsers ();
  for (int i = 0; i < N; i++) {
   int start = (int) (Math.random() * 100);
   int end = (int)(Math.random() * 50) + start;
   LogTime time = new LogTime(start, end);
   System.out.println(time.toString());
   fu.put(time, String.valueOf(i));
  }
  
  System.out.println(fu.search(79));
  
 }

}

Interval Search Tree

Consider we have a situation where we have a list of intervals and we need the following operations:

1. Add an interval;
2. Remove an interval;
3. Given an interval, search if it overlaps with any intervals in the list and return all those intervals.

Yup, the answer is the title; interval search tree.

The interval search tree follows a binary search tree structure. Each node of the tree stores the following information:

1. interval: the interval;
2. label: a unique label;
3. max: the high value of all intervals in the subtree of the current node is smaller than this one.

The compare method of the interval follows to following rule:

1. The interval with the lower low value is always smaller

2. If the low is the same, the interval with the lower high is smaller

Insertion: insert the interval based on the BST rule, i.e., recursively find the right position and insert at that position. 

However, if we want to insert a new interval and make it as the new root, a swap node operation is needed. Note this operation may make the tree unbalanced. 

Find the correct position and insert

Right rotate 

Left rotate

Deletion: Still follows the BST recursion rules. When the interval is found and both left and right child exist, join two children and their subtrees. Either child can be selected as the new root, yet the one with larger subtree sizes is preferred. 

Search: Follows the BST recursion rules. If root intersects with the interval, return root (add root to the list), recursively search the left subtree and right subtree. 

package intervalSearchTree;
import java.util.*;
public class IntervalSearchTree {
 /**
  * tree node class
  *
  */
 private class Node {
  Interval interval;
  V label;
  Node left, right;
  int N;//size of subtree (number of nodes) rooted at this node
  int max;
  Node (Interval interval, V label) {
   this.interval = interval;
   this.label = label;
   this.N = 1;
   this.max = (int) interval.high;
  }
 }
 private Node root;
 
 /***************************************
  * search if an interval is in the tree
  * @param interval
  * @return
  ***************************************/
 public boolean contains(Interval interval) {
  return get(interval) != null;
 }
 public V get(Interval interval) {
  return get(root, interval);
 }
 private V get(Node node, Interval interval) {
  if (node == null)
   return null;
  int cmp = interval.compareTo(node.interval);
  if (cmp < 0)
   return get(node.left, interval);
  else if (cmp > 0)
   return get(node.right, interval);
  else
   return node.label;
 }
 
 
 /*****************************
  * insertion 
  *****************************/
 public void put(Interval interval, V label) {
  if (contains(interval)) {
   System.out.println("Duplicate interval!");
   return;
  }
  root = insert(root, interval, label);
 } 
 /**
  * insert a node based on BST rule
  * @param node
  * @param interval
  * @param label
  * @return
  */
 private Node insert(Node node, Interval interval, V label) {
  if (node == null)
   return new Node(interval, label);
  int cmp = interval.compareTo(node.interval);
  if (cmp < 0) {
   node.left = insert(node.left, interval, label);
  }
  else {
   node.right = insert(node.right, interval, label);
  }
  fix(node);
  return node;
 }
 /**
  * insert the new interval as the root of the tree
  * @param interval
  * @param label
  */
 public void insertRoot(Interval interval, V label) {
  if (contains(interval)) {
   System.out.println("Duplicate interval!");
   return;
  }
  root = insertRoot(root, interval, label); 
 }
 /**
  * insert the node at the correct position
  * rotate the node so that the new node will be the root 
  * while still maintaining the BST structure
  * @param node
  * @param interval
  * @param label
  * @return
  */
 private Node insertRoot(Node node, Interval interval, V label) {
  if (node == null)
   return new Node (interval, label);
  int cmp = interval.compareTo(node.interval);
  if (cmp < 0) {
   node.left = insertRoot(node.left, interval, label);
   node = rotR(node);
  }
  else {
   node.right = insertRoot(node.right, interval, label);
   node = rotL(node);
  }
  return node;
 }
 
 /***************************************
  * deletion
  * *************************************/
 public V remove(Interval interval) {
  V value = get(interval);
  root = remove(root, interval);
  return value;
 }
 private Node remove(Node node, Interval interval) {
  if (node == null)
   return null;
  int cmp = interval.compareTo(node.interval);
  if (cmp < 0)
   node.left = remove(node.left, interval);
  else if (cmp > 0)
   node.right = remove(node.right, interval);
  else
   node = join(node.left, node.right);
  fix(node);
  return node;
 }
 /**
  * join the left and right subtree of a node 
  * once the node is deleted
  * use a random number to determine whether the new node is the left child
  * or the right child
  * @param a
  * @param b
  * @return
  */
 private Node join(Node a, Node b) {
  if (a == null)
   return b;
  if (b == null)
   return a;
  //generate a number between 0.0 to 1.0
  if (Math.random() * (double)(size(a) + size(b)) < (double)size(a)) {
   a.right = join(a.right, b);
   fix(a);
   return a;
  }
  else {
   b.left = join(a, b.left);
   fix(b);
   return b;
  }
 }
 
 
 
 /******************************
  * Search the Interval tree
  ******************************/
 public Interval search(Interval interval) {
  return search(root, interval);
 }
 public Interval search(Node node, Interval interval) {
  while (node != null) {
   if (interval.intersects(node.interval))
    return node.interval;
   else if (node.left == null)
    node = node.right;
   else if (node.left.max < interval.low)
    node = node.right;
   else
    node = node.left;
  }
  return null;
 }
 /**
  * return all intervals that intersect the given interval
  * running time is proportional to RlogN, where R 
  * is the number of intersections
  * @param interval
  * @return
  */
 public Iterable searchAll (Interval interval) {
  LinkedList list = new LinkedList ();
  searchAll(root, interval, list);
  return list;
 }
 public boolean searchAll(Node node, Interval interval, LinkedList list) {
  boolean found_root = false;
  boolean found_left = false;
  boolean found_right = false;
  if (node == null)
   return false;
  if (interval.intersects(node.interval)) {
   list.add(node.interval);
   found_root = true;
  }
  if (node.left != null && node.left.max >= interval.low)
   found_left = searchAll(node.left, interval, list);
  if (node.right != null && node.right.max >= interval.high)
   found_right = searchAll(node.right, interval, list);
  return found_root || found_left || found_right;
 }
 
 
 
 /**********************************
  * useful methods
  **********************************/
 public int size() {
  return size(root);
 }
 private int size(Node node) {
  if (node == null)
   return 0;
  else
   return node.N;
 }
 public int height() {
  return height(root);
 }
 private int height(Node node) {
  if (node == null)
   return 0;
  return 1 + Math.max(height(node.left), height(node.right));
 }
 /**
  * fix auxilliar information 
  * subtree count and max fields
  * @param node
  */
 private void fix(Node node) {
  if (node == null)
   return;
  node.N = 1 + size(node.left) + size(node.right);
  node.max = max3(node.interval.high, max(node.left), max(node.right));
 }
 private int max(Node node) {
  if (node == null)
   return Integer.MIN_VALUE;
  return node.max;
 }
 
 private int max3(int a, int b, int c) {
  return Math.max(a, Math.max(b, c));
 }
 /**
  * right rotate
  *     1             2
  *    / \           / \
  *   2   3    ->   4   1
  *  / \               / \
  * 4   5             5   3
  * @param h
  * @return
  */
 private Node rotR(Node h) {
  Node l = h.left;
  h.left = l.right;
  l.right = h;
  fix(h);
  fix(l);
  return l;
 }
 /**
  * left rotate
  *     1             3
  *    / \           / \
  *   2   3    ->   1   5
  *      / \       / \
  *     4   5     2   4
  *     
  * @param h
  * @return
  */
 private Node rotL(Node h) {
  Node r = h.right;
  h.right = r.left;
  r.left = h;
  fix(h);
  fix(r);
  return r;
 }
 /********************************
  * Debugging 
  ********************************/
 public boolean check() {
  return checkCount() && checkMax();
 }
 
 private boolean checkCount() {
  return checkCount(root);
 }
 private boolean checkCount(Node node) {
  if (node == null)
   return true;
  return checkCount(node.left) && checkCount(node.right) 
    && (node.N == 1 + size(node.left) + size(node.right));
 }
 private boolean checkMax() {
  return checkMax(root);
 }
 private boolean checkMax(Node node) {
  if (node == null)
   return true;
  return node.max == max3(node.interval.high, max(node.left), max(node.right));
 }
}
public class Interval implements Comparable{
 public final int low;
 public final int high;
 Interval(int low, int high) {
  if (high < low)
   throw new IllegalArgumentException("Illegal argument");
  this.low = low;
  this.high = high;
 }
 
 public boolean contains(int x) {
  return low <= x && high >= x;
 }
 public boolean intersects (Interval interval) {
  if(high < interval.low)
   return false;
  if (low > interval.high)
   return false;
  return true;
 }
 
 public int compareTo(Interval interval) {
  if (low < interval.low)
   return -1;
  else if (low > interval.low)
   return 1;
  else if (high < interval.high)
   return -1;
  else if (high > interval.high)
   return 1;
  else
   return 0;
 }
 public String toString()
 {
  return  "[" + String.valueOf(low) + " ," + String.valueOf(high) + "]"; 
 }

}

src on Github: https://github.com/shirleyyoung0812/intervalSearchTree.git

Least moves

Given a m*n grid starting from (1, 1). At any point (x, y
   ), you has two choices for the next move: 1) move to (x+y, y); 2) move to (x, y+x); From point (1, 1), how to move to (m, n) in least moves? (or there's no such a path) 

At first I thought I should use DP, but after taking a look at other people's solutions, I realize it is not that complicated.

If m = n and both m and n are greater than 1, then there is no solution. This is because at any time we will move to x+ y, y or x, y + x then there are only two possibilities for the last move:

x + y = m
y = n

or
x = m
y + x = n

if m = n, either of these will lead to x = 0 or y = 0, which is impossible since the start point is (1, 1), thus at anytime when m = n and m > 1, there is no solution.

Then the next thing is to start from m and n, goes back to 1, 1.

public static int leastMoves(int m, int n) {
  if (m == n && m == 1)
   return 0;
  if (m == n && m > 1)
   return -1;
  int count = 0;
  while (m > 1 || n > 1) {
   if (m == n)
    return -1;
   else if (m > n) {
    m -= n;
    count++;
   }
   else {
    n -= m;
    count++;
   }
  }
  if (m != 1 || n != 1)
   return -1;
  return count;
 }

Simple polygon

"Write a function to check if polygon is simple based on given list of points"

I was stuck on the problem at first because I didn't know what is a "simple" polygon compares to what is a "complex" polygon. More information can always be found on Wikipedia, here I will just show you two figures. 

Yep, exactly what you are thinking, a simple polygon has no other intersections between two lines except for the point, a complex one involves more than one intersections. 

Then the rest of the problem becomes very easy: check every line and see if there exists another intersection. 

public static boolean isSimplePolygon(Point[] polygon) {
  if (polygon == null || polygon.length < 3)
   throw new IllegalArgumentException("invalid input!");
  Set slopes = new HashSet ();
  for (int i = 0; i < polygon.length - 1; i++) {
   slopes.clear();
   for (int j = i + 1; j < polygon.length; j++) {
    double slope;
    if (polygon[i].x == polygon[j].x) {
     slope = (double)Integer.MAX_VALUE;
    }
    else if (polygon[i].y == polygon[j].x) {
     slope = 0.0;
    }
    else {
     slope = (double) (polygon[i].y - polygon[j].y) / (double)(polygon[i].x + polygon[j].x);
    }
    if (slopes.contains(slope))
     return false;
    slopes.add(slope);
   }
  }
  return true;
 }

Running Median

"There is a stream of numbers, design an effective datastructre to store the numbers and to return the median at any point of time."


Since the number is coming from a stream, the size of the list is dynamic, so as the median. It is possible to store the numbers in a sorted list and find the middle. However, this will take O(n) to insert an element and O(1) to get the median. So the question is, can we do better?

If the total numbers are divided into two parts, the numbers in the left part are always smaller than those in the right part. If we divide the total number in such a way that the size of the left and right part will differ no larger than 1, then the median will be the smallest number in the right part if the right part has more elements, or the largest number in the left part if the left part has more elements, or the average of the minimum of the left part and maximum of the right part if two parts have equal elements. So how can we find the maximum and minimum?

Use two heaps. The left part will be a max heap and the right part will be a min heap. Though it is quite flexible, I set the rule that if two parts have equal size, then the element will be added to the right part, otherwise it will be inserted to the left part.

Here comes one more question, what if the new number is smaller (or larger) than any number in the left part when it is supposed to be added to the right (left) part? In that case, we can add the number into the left (right) part, and then poll the head, which is the maximum in the left (minimum in the right), and add that number to the right (left) part.

 

package runningMedian;
/**
 * There is a stream of numbers, design an effective data structre to store 
 * the numbers and to return the median at any point of time. 
 * @author shirleyyoung
 *
 */
import java.util.*;
public class RunningMedian {
 //max heap
 PriorityQueue leftQueue;
 //min heap
 PriorityQueue rightQueue;
 
 public RunningMedian() {
  leftQueue = new PriorityQueue (
    new Comparator () {
   public int compare(Integer a, Integer b) {
    return b - a;
   }
  }
  );
  rightQueue = new PriorityQueue ();
 }
 /**
  * the number will be added to the rightQueue if the total numbers are even
  * however, in order for all numbers in the leftQueue to be smaller than those
  * in the rightQueue, we add n to the leftQueue first, then poll out the head 
  * of the leftQueue, which is the maximum in the queue, then add it to the rightQueue
  * if the total numbers are odd, the number will be added to the leftQueue
  * @param n
  */
 public void add(int n) {
  if (leftQueue.size() == rightQueue.size()) {
   if (rightQueue.size() == 0) {
    rightQueue.add(n);
   }
   else {
    leftQueue.add(n);
    int leftMax = leftQueue.poll();
    rightQueue.add(leftMax);
   }
  }
  else {
   if (rightQueue.peek() < n) {
    rightQueue.add(n);
    int rightMin = rightQueue.poll();
    leftQueue.add(rightMin);
   }
   else {
    leftQueue.add(n);
   }
  }
 }
 
 public double getMedian() {
  if (leftQueue.size() == 0 && rightQueue.size() == 0)
   throw new IllegalArgumentException("No elements!");
  if (leftQueue.size() == rightQueue.size()) {
   return (double)(leftQueue.peek() + rightQueue.peek()) / 2.0;
  }
  return (double)rightQueue.peek();
 }
}

Sort color

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note:
You are not suppose to use the library's sort function for this problem.

I have solved this four times, but I still couldn't remember it correctly. It is similar to dual pivot quick sort.
1. We take two pivots, the left one (pl) initialized at index 0 and the right one initialized at index A.length - 1;
2. Then we loop the array, if A[index] == 0, we swap it with pl, increment pl; if A[index] == 2, we swap it with pr, decrement pr.

public void sortColors(int[] A) {
        if (A == null || A.length < 2)
            return;
        int pl = 0;
        int pr = A.length - 1;
        int index = 0;
        while (index <= pr){
            if (A[index] == 0){
                swap(A, index++, pl++);
            }
            else if (A[index] == 2)
                swap(A, index, pr--);
            else
                index++;
        }
    }
    private void swap(int[] A, int i, int j){
        int tmp = A[i];
        A[i] = A[j];
        A[j] = tmp;
    }