Things to Learn/Improve in 2018


Plan
- Think what things have to be done
- Plan them earlier and carefully, seriously

 Growth mindset

 Keep learning
& Learn quickly
& Learn more


 Don't be shy to show your stupidity
Just ask questions

- more and deeper

Social Skills
Build Connections

 Be effective
Effective time management
Use time meaningfully and wisely

 Add values
Get things done
Empower the team

Take risks
Accept criticism

Effective Communication skills
- Get work done
- Get recognition
- with colleagues, manager, senior managers
- Confirm and say thanks after someone helps you

 Technical Skills
Python
Posted by at
Labels:

Monotone Queue + Stack - How to Succeed in Algorithms Interview


Monotone Queue + Stack - How to Succeed in Algorithms Interview

How to Succeed in Algorithms Interview Series

States

  • what to store
    • element, index
    • candidates of starting index/element
    • prefix sum: not necessarily use the input data
  • running length: element(or index), count of same values

Partial Monotonic stack/queue

When to use

  • expect time complexity O(N)
  • find one range with xxx

Monotonic Queue Examples

DP - Monotone Queue

  • F[i]=min(F[j]+a[i]:j<i) a[i]是与j无关的数
  • moving interval
  • NOIP - 烽火传递
  • JZOJ 1772 - Holiday
  • bzoj 3831 - Little Bird

Examples

Monotonic Stack

Implementation
  • calculate results when pop the element from the stack
  • < or <=; > or >=
Examples
  public int sumSubarrayMins(int[] A) {
      int res = 0, n = A.length, mod = (int)1e9 + 7;
      int[] left = new int[n], right = new int[n];
      Stack<int[]> s1 = new Stack<>(), s2 = new Stack<>();
      for (int i = 0; i < n; ++i) {
          int count = 1;
          while (!s1.isEmpty() && s1.peek()[0] > A[i])
              count += s1.pop()[1];
          s1.push(new int[] {A[i], count});
          left[i] = count;
      }
      for (int i = n - 1; i >= 0; --i) {
          int count = 1;
          while (!s2.isEmpty() && s2.peek()[0] >= A[i])
              count += s2.pop()[1];
          s2.push(new int[] {A[i], count});
          right[i] = count;
      }
      for (int i = 0; i < n; ++i)
          res = (res + A[i] * left[i] * right[i]) % mod;
      return res;
  }

  public int sumSubarrayMins(int[] A) {
      Stack<Integer> stack = new Stack<>();
      int[] dp = new int[A.length + 1];
      stack.push(-1); // case when stack is empty, not really needed
      int result = 0, M = (int)1e9 + 7;
      for (int i = 0; i < A.length; i++) {
          while (stack.peek() != -1 && A[i] <= A[stack.peek()]) {
              stack.pop();
          }
          dp[i + 1] = (dp[stack.peek() + 1] + (i - stack.peek()) * A[i]) % M;
          stack.push(i);
          result += dp[i + 1];
          result %= M;
      }
      return result;
  }

  public int sumSubarrayMins(int[] A) {
      Stack<Integer> s = new Stack<>();
      int n = A.length, res = 0, mod = (int)1e9 + 7, j,k;
      for (int i = 0; i <= n; i++) {
          while (!s.isEmpty() && A[stack.peek()] > (i == n ? 0 : A[i])) {
              j = stack.pop();
              k = stack.isEmpty() ? -1 : stack.peek();
              res = (res + A[j] * (i - j) * (j - k)) % mod;
          }
          stack.push(i);
      }
      return res;
  }
public int trap(int[] A) {
    if (A==null) return 0;
    Stack<Integer> s = new Stack<Integer>();
    int i = 0, maxWater = 0, maxBotWater = 0;
    while (i < A.length){
        if (s.isEmpty() || A[i]<=A[s.peek()]){
            s.push(i++);
        }
        else {
            int bot = s.pop();
            maxBotWater = s.isEmpty()? // empty means no il
            0:(Math.min(A[s.peek()],A[i])-A[bot])*(i-s.peek()-1);
            maxWater += maxBotWater;
        }
    }
    return maxWater;
}
  • LeetCode 85 - Maximal Rectangle
    • calculate maxArea for each row
    • Separate DP functions/states
      • left(i,j) = max(left(i-1,j), cur_left), cur_left can be determined from the current row
      • right(i,j) = min(right(i-1,j), cur_right), cur_right can be determined from the current row
      • height(i,j) = height(i-1,j) + 1, if matrix[i][j]==‘1’;
  • LeetCode 402 - Remove K Digits
    public String removeKdigits(String num, int k) {
  int len = num.length();
  Stack<Character> stack = new Stack<>();
  int i =0;
  while(i<num.length()){
      //whenever meet a digit which is less than the previous digit, discard the previous one
      while(k>0 && !stack.isEmpty() && stack.peek()>num.charAt(i)){
          stack.pop();
          k--;
      }
      stack.push(num.charAt(i));
      i++;
  }
  // corner case like "1111"
  while(k>0){
      stack.pop();
      k--;            
  }
  //construct the number from the stack
  StringBuilder sb = new StringBuilder();
  while(!stack.isEmpty())
      sb.append(stack.pop());
  sb.reverse();    
  //remove all the 0 at the head
  while(sb.length()>1 && sb.charAt(0)=='0')
      sb.deleteCharAt(0);
  return sb.toString();
}
  • LintCode 126 - Max Tree
public TreeNode maxTree(int[] A) {
    if (A == null || A.length == 0) return null;
    Stack<TreeNode> stack = new Stack<>();
    for (int i = 0; i < A.length; i++) {
        //遍历A的每个元素，创造结点node
        TreeNode node = new TreeNode(A[i]);
        //将stack中小于当前结点的结点都pop出来，存为当前结点的左子树
        while (!stack.isEmpty() && node.val >= stack.peek().val) node.left = stack.pop();
        //如果stack仍非空，剩下的结点一定大于当前结点，所以将当前结点存为stack中结点的右子树；而stack中结点本来的右子树之前已经存为当前结点的左子树了
        if (!stack.isEmpty()) stack.peek().right = node;
        //stack中存放结点的顺序为：底部为完整的max tree，从下向上是下一层孩子结点的备份，顶部是当前结点的备份
        stack.push(node);
    }
    TreeNode root = stack.pop();
    while (!stack.isEmpty()) root = stack.pop();
    return root;
}
  • LeetCode 316 - Remove Duplicate Letters
    • remove duplicate letters so that every letter appear once and only once. You must make sure your result is the smallest in lexicographical order among all possible results
  • LeetCode 321 - Create Maximum Number
    • Given two arrays of length m and n with digits 0-9 representing two numbers. Create the maximum number of length k <= m + n from digits of the two. The relative order of the digits from the same array must be preserved. Return an array of the k digits. You should try to optimize your time and space complexity.
  • HARD LeetCode 654 - Maximum Binary Tree
    • decreasing stack
    • create the TreeNode while access the data, push them into monotone stack, connect TreeNodes when push or pop 
    public TreeNode constructMaximumBinaryTree(int[] nums) {
  Deque<TreeNode> stack = new LinkedList<>();
  for(int i = 0; i < nums.length; i++) {
      TreeNode curr = new TreeNode(nums[i]);
      while(!stack.isEmpty() && stack.peek().val < nums[i]) {
          curr.left = stack.pop();
      }
      if(!stack.isEmpty()) {
          stack.peek().right = curr;
      }
      stack.push(curr);
  }    
  return stack.isEmpty() ? null : stack.removeLast();
}
  • HARD LeetCode 456 - 132 Pattern - hard
public boolean find132pattern(int[] nums) {
  if (nums.length < 3)
    return false;
  Stack<Integer> stack = new Stack<>();
  int[] min = new int[nums.length];
  min[0] = nums[0];
  for (int i = 1; i < nums.length; i++)
    min[i] = Math.min(min[i - 1], nums[i]);
  for (int j = nums.length - 1; j >= 0; j--) {
    if (nums[j] > min[j]) {
      while (!stack.isEmpty() && stack.peek() <= min[j])
        stack.pop();
      if (!stack.isEmpty() && stack.peek() < nums[j])
        return true;
      stack.push(nums[j]);
    }
  }
  return false;
}

// https://www.jianshu.com/p/910fe372d9a0
public boolean find132pattern(int[] nums) {
  boolean result = false;
  int third = Integer.MIN_VALUE; // the third number, 13(2)
  Stack<Integer> stack = new Stack<Integer>(); // decreasing stack
  for (int i = nums.length - 1; i >= 0; i--) {
    if (nums[i] < third)
      return true;
    while (!stack.isEmpty() && nums[i] > stack.peek()) {
      third = Math.max(third, stack.pop());
    }
    stack.push(nums[i]);
  }
  return result;
}
Monotonic stack stores candidates then scan original data from end
int[] res, count; ArrayList<HashSet<Integer>> tree; int n;
public int[] sumOfDistancesInTree(int N, int[][] edges) {
    tree = new ArrayList<HashSet<Integer>>();
    res = new int[N];
    count = new int[N];
    n = N;
    for (int i = 0; i < N ; ++i ) tree.add(new HashSet<Integer>());
    for (int[] e : edges) {tree.get(e[0]).add(e[1]); tree.get(e[1]).add(e[0]);}
    dfs(0, new HashSet<Integer>());
    dfs2(0, new HashSet<Integer>());
    return res;
}
public void dfs(int root, HashSet<Integer> seen) {
    seen.add(root);
    for (int i : tree.get(root))
        if (!seen.contains(i)) {
            dfs(i, seen);
            count[root] += count[i];
            res[root] += res[i] + count[i];
        }
    count[root]++;
}
public void dfs2(int root, HashSet<Integer> seen) {
    seen.add(root);
    for (int i : tree.get(root))
        if (!seen.contains(i)) {
            res[i] = res[root] - count[i] + n - count[i];
            dfs2(i, seen);
        };
}
Posted by at
Labels: , , ,

Interval - How to Succeed in Algorithms Interview


Interval - How to Succeed in Algorithms Interview

How to Succeed in Algorithms Interview Series

Application of Interval

  • sort by start time or finish time
    • sort then choose greedily
    • sort then dynamic programming
    • track last max_end (or max_start)
  • Two pointers for input data: int[] start, end
  • TreeMap:
    • start -> end, start/end -> index
    • boundary count: point -> count
  • TreeSet: intervals, sort by start or end time
  • PriorityQueue
    • merge k sorted list: [outerIndex, innerIndex]
    • [point, isStart] or interval
  • Greedy
  • Boundary count: start +1, end -1;
    • with TreeMap

Implementation

  • List merged,
  • save prevInterval, lastEnd

Basic

  • LeetCode 57 - Insert Interval
    • 3 steps: add intervals before the inserted, merge, add intervals after the inserted
    public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
  List<Interval> result = new LinkedList<>();
  int i = 0;
  // add all the intervals ending before newInterval starts
  while (i < intervals.size() && intervals.get(i).end < newInterval.start)
      result.add(intervals.get(i++));
  // merge all overlapping intervals to one considering newInterval
  while (i < intervals.size() && intervals.get(i).start <= newInterval.end) {
      newInterval = new Interval( // we could mutate newInterval here also
              Math.min(newInterval.start, intervals.get(i).start),
              Math.max(newInterval.end, intervals.get(i).end));
      i++;
  }
  result.add(newInterval); // add the union of intervals we got
  // add all the rest
  while (i < intervals.size()) result.add(intervals.get(i++));
  return result;
}
  • LeetCode 56 - Merge Intervals
private class IntervalComparator implements Comparator<Interval> {
  @Override
  public int compare(Interval a, Interval b) {
    return a.start < b.start ? -1 : a.start == b.start ? 0 : 1;
  }
}
public List<Interval> merge(List<Interval> intervals) {
  Collections.sort(intervals, new IntervalComparator());
  LinkedList<Interval> merged = new LinkedList<Interval>();
  for (Interval interval : intervals) {
    if (merged.isEmpty() || merged.getLast().end < interval.start) {
      merged.add(interval);
    }
    else {
      merged.getLast().end = Math.max(merged.getLast().end, interval.end);
    }
  }
  return merged;
}
  • LeetCode 436 - Find Right Interval
    • TreeMap can simplify code related with binary search
    public int[] findRightInterval(Interval[] intervals) {
  int[] result = new int[intervals.length];
  java.util.NavigableMap<Integer, Integer> intervalMap = new TreeMap<>();
  for (int i = 0; i < intervals.length; ++i) {
      intervalMap.put(intervals[i].start, i);    
  }
  for (int i = 0; i < intervals.length; ++i) {
      Map.Entry<Integer, Integer> entry = intervalMap.ceilingEntry(intervals[i].end);
      result[i] = (entry != null) ? entry.getValue() : -1;
  }
  return result;
}
  • LeetCode 253 - Meeting Rooms II
    public int minMeetingRooms(Interval[] intervals) {
  if (intervals == null || intervals.length == 0) {
      return 0;
  }
  TreeMap<Integer, Integer> times = new TreeMap<>();
  for (Interval i : intervals) {
      times.put(i.start, times.getOrDefault(i.start, 0) + 1);
      times.put(i.end, times.getOrDefault(i.end, 0) - 1);
  }
  int count = 0, res = 0;
  for (int c : times.values()) {
      count += c;
      res = Math.max(res, count);
  }
  return res;
}

Convert events into start, end array

Sort

for (int i = 1; i < intervals.length; i++) {
  Interval a = intervals[i];
  if (a.getLow() <= high) {
    high = Math.max(a.getHigh(), high);
  } else {
    maxInterval = Math.max(maxInterval, high - low);
    maxGap = Math.max(maxGap, a.getLow() - high);
    low = a.getLow();
    high = a.getHigh();
  }
}

TreeMap

  • start -> end
  • boundary count, position -> count+1 for start, count-1 for end
Methods of TreeMap
  • floorKey, ceilingKey, lowerEntry,
LeetCode 729 - My Calendar I
List<int[]> calendar;
List<int[]> overlaps;

MyCalendarTwo() {
    calendar = new ArrayList();
}

public boolean book(int start, int end) {
    for (int[] iv: overlaps) {
        if (iv[0] < end && start < iv[1]) return false;
    }
    for (int[] iv: calendar) {
        if (iv[0] < end && start < iv[1])
            overlaps.add(new int[]{Math.max(start, iv[0]), Math.min(end, iv[1])});
    }
    calendar.add(new int[]{start, end});
    return true;
}
// -------
TreeMap<Integer, Integer> delta;

public MyCalendarTwo() {
    delta = new TreeMap();
}

public boolean book(int start, int end) {
    delta.put(start, delta.getOrDefault(start, 0) + 1);
    delta.put(end, delta.getOrDefault(end, 0) - 1);

    int active = 0;
    for (int d: delta.values()) {
        active += d;
        if (active >= 3) {
            delta.put(start, delta.get(start) - 1);
            delta.put(end, delta.get(end) + 1);
            if (delta.get(start) == 0)
                delta.remove(start);
            return false;
        }
    }
    return true;
}
LeetCode 732 - My Calendar III
  • boundary count
LeetCode 352. Data Stream as Disjoint Intervals
  • TreeMap: start -> Interval
LeetCode 715 - Range Module

Boundary count

  • boundary count, position -> count+1 for start, count-1 for end
  • critical point: cnt=0 or cnt itself
  • sort, TreeMap or PriorityQueue

PriorityQueue

public List<Interval> employeeFreeTime(List<List<Interval>> schedule) {
  List<Interval> res = new ArrayList<Interval>();
  PriorityQueue<Node> minHeap = new PriorityQueue<Node>(
      (a, b) -> schedule.get(a.employee).get(a.index).start - schedule.get(b.employee).get(b.index).start);

  int start = Integer.MAX_VALUE;
  for (int i = 0; i < schedule.size(); i++) {
    minHeap.add(new Node(i, 0));
    start = Math.min(start, schedule.get(i).get(0).start);
  }

  while (!minHeap.isEmpty()) {
    Node cur = minHeap.poll();
    if (start < schedule.get(cur.employee).get(cur.index).start) {
      res.add(new Interval(start, schedule.get(cur.employee).get(cur.index).start));
    }

    start = Math.max(start, schedule.get(cur.employee).get(cur.index).end);
    cur.index++;
    if (cur.index < schedule.get(cur.employee).size()) {
      minHeap.add(cur);
    }
  }
  return res;
}

class Node {
  int employee;
  int index;

  public Node(int employee, int index) {
    this.employee = employee;
    this.index = index;
  }
}

Greedy

Interval Tree

Posted by at
Labels: , , ,

Union Find (Disjoint Set) - How to Succeed in Algorithms Interview


Union Find - How to Succeed in Algorithms Interview

How to Succeed in Algorithms Interview Series

Applications of Union Find(Disjoint Set)

  • Connected components/groups, connections
  • Find cycle
  • useful when give edges of graph

Time complexity

  • without anything: O(N)
  • with Union by Rank: O(logN)
  • with Path Compression: O(α(N)) which is inverse Ackermann function.

Info we can get

  • find root, union
  • count of components, size of each component
  • whether two nodes are connected or in same group

Implementation Detail

  • UnionFind(int size)
  • int[] parent; int[] rank;
  • Map<String, String> parents or parent[];
  • find, union, isConnected, findCount
  • highestRank, maxUnion
  • find grouped ids

Summary

  • dummy root node

Dummy node/parent

Given a 2D board containing 'X' and 'O', capture all regions surrounded by 'X'. A region is captured by flipping all 'O's into 'X's in that surrounded region.
For example,
X X X X  
X O O X  
X X O X  
X O X X  
After running your function, the board should be:
X X X X  
X X X X  
X X X X  
X O X X
  • we connect all the ‘O’ nodes on the boundary to a dummy node, and then connect each ‘O’ node to its neighbour ‘O’ nodes
int row, col;
public void solve(char[][] board) {
    if (board == null || board.length == 0) return;
    row = board.length;
    col = board[0].length;
    UnionFind uf = new UnionFind(row*col+1);
    int dummy = row*col;
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            if (board[i][j] == 'O') {
                if (i == 0 || i == row-1 || j == 0 || j == col-1) uf.union(node(i, j), dummy);
                else {
                    if (i > 0 && board[i-1][j] == 'O') uf.union(node(i, j), node(i-1, j));
                    if (i > 0 && board[i+1][j] == 'O') uf.union(node(i, j), node(i+1, j));
                    if (j > 0 && board[i][j-1] == 'O') uf.union(node(i, j), node(i, j-1));
                    if (j > 0 && board[i][j+1] == 'O') uf.union(node(i, j), node(i, j+1));
                }
            }
        }
    }
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            if (uf.isConnected(node(i, j), dummy)) board[i][j] = 'O';
            else board[i][j] = 'X';
        }
    }
}
public int node(int i, int j) {
    return i*col+j;
}

What to Group/Union

Map<Integer, Integer> map = new HashMap<>(); // parent
Map<Integer, Integer> c = new HashMap<>(); // count
int res=1;
public int longestConsecutive(int[] a) {
    if(a.length==0) return 0;
    for(int i=0;i<a.length;i++){
        int cur = a[i];
        if(map.containsKey(cur)) continue;
        map.put(cur,cur);
        c.put(cur, 1);
        if(map.containsKey(cur-1)) union(cur-1, cur);
        if(map.containsKey(cur+1)) union(cur+1, cur);
    }
    return res;
}
int find(int x){
    if(map.get(x)==x) return x;
    int par = find(map.get(x));
    map.put(x, par); // path compression
    return par;
}
void union(int x, int y){
    int px = find(x);
    int py = find(y);
    int newCount = c.get(py)+c.get(px);
    if(c.get(px)<c.get(py)){
        map.put(px, py);    
        c.put(py, newCount);
    }else{
        map.put(py, px);    
        c.put(px, newCount);
    }
    res=Math.max(res, newCount);
}
public int largestComponentSize(int[] A) {
    int N = A.length;
    Map<Integer, Integer> map = new HashMap<>();// key is the factor, val is the node index
    UF uf = new UF(N);
    for (int i = 0; i < N; i++){
        int a = A[i];
        for (int j = 2; j * j <= a; j++){
            if (a % j == 0){
                if (!map.containsKey(j)){//this means that no index has claimed the factor yet
                    map.put(j, i);
                }else{//this means that one index already claimed, so union that one with current
                    uf.union(i, map.get(j));
                }
                if (!map.containsKey(a/j)){
                    map.put(a/j, i);
                }else{
                    uf.union(i, map.get(a/j));
                }
            }
        }
        if (!map.containsKey(a)){//a could be factor too. Don't miss this
            map.put(a, i);
        }else{
            uf.union(i, map.get(a));
        }
    }
    return uf.max;
}

Union-Find - Weight

  • Parent node contains extra info
  • HARD LeetCode 399 - Evaluate Division
    class Node {
public String parent;
public double ratio;
}
class UnionFindSet {
private Map<String, Node> parents = new HashMap<>();
public Node find(String s) {
  if (!parents.containsKey(s)) return null;
  Node n = parents.get(s);
  if (!n.parent.equals(s)) {
    Node p = find(n.parent);
    n.parent = p.parent;
    n.ratio *= p.ratio;
  }
  return n;
}
public void union(String s, String p, double ratio) {
  boolean hasS = parents.containsKey(s);
  boolean hasP = parents.containsKey(p);
  if (!hasS && !hasP) {
    parents.put(s, new Node(p, ratio));
    parents.put(p, new Node(p, 1.0));
  } else if (!hasP) {
    parents.put(p, new Node(s, 1.0 / ratio));
  } else if (!hasS) {
    parents.put(s, new Node(p, ratio));
  } else {
    Node rS = find(s);
    Node rP = find(p);
    rS.parent = rP.parent;
    rS.ratio = ratio / rS.ratio * rP.ratio;
  }
}
}
public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
UnionFindSet u = new UnionFindSet();
for (int i = 0; i < equations.length; ++i)
  u.union(equations[i][0], equations[i][1], values[i]);
double[] ans = new double[queries.length];
for (int i = 0; i < queries.length; ++i) {      
  Node rx = u.find(queries[i][0]);
  Node ry = u.find(queries[i][1]);
  if (rx == null || ry == null || !rx.parent.equals(ry.parent))
    ans[i] = -1.0;        
  else
    ans[i] = rx.ratio / ry.ratio;
}
return ans;
}

Info we can get

  • group count, max group,
// https://leetcode.com/articles/minimize-malware-spread/
for (int node: initial)
    count[dsu.find(node)]++;

Time complexity

  • without anything: O(N)
  • with Union by Rank: O(logN)
  • with union by rank + Path Compression: O(α(N)) which is inverse Ackermann function.
    • This function has a value {(n)<5} for any value of n that can be written in this physical universe.

Classic Problems

int x_set = find(parent, edge.source);
int y_set = find(parent, edge.destination);
//check if source vertex and destination vertex belongs to the same set
// if in same set then cycle has been detected else combine them into one set
if(x_set==y_set)
    return true;
else
    union(parent, x_set, y_set);
int res = Integer.MAX_VALUE;
public int minTransfers(int[][] transactions) {
   HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
   for (int[] transaction : transactions) {
       map.put(transaction[0], map.getOrDefault(transaction[0], 0)-transaction[2]);
       map.put(transaction[1], map.getOrDefault(transaction[1], 0)+transaction[2]);
   }
   ArrayList<Integer> depts = new ArrayList<Integer>();
    for (int dept : map.values()) {
        if (dept != 0) depts.add(dept);
    }
    helper(depts, 0, 0);
    return res;
}

public void helper(ArrayList<Integer> depts, int start, int count) {
  while (start<depts.size() && depts.get(start)==0) start++;
  if (start == depts.size()) {
      res = Math.min(res, count);
      return;
  }
  for (int i=start+1; i<depts.size(); i++) {
      if (depts.get(start)<0&&depts.get(i)>0 || depts.get(start)>0&&depts.get(i)<0) {
          depts.set(i, depts.get(i)+depts.get(start));
          helper(depts, start+1, count+1);
          depts.set(i, depts.get(i)-depts.get(start));
      }
  }
}

Examples

Design a data structure to support following functions:
1. setManager(A, B) sets A as a direct manager of B
2. setPeer(A, B) sets A as a colleague of B. After that, A and B will have the same direct Manager.
3. query(A, B) returns if A is in the management chain of B.
Every person only has 1 direct manager.

Union Find Implementation

  • rank is only used in union
Using Array
class UnionFind {
    int[] parent;
    int[] rank;
    int count;
    public UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        count = n;
        for (int i = 0; i < n; ++i) {
            parent[i] = i;
            rank[i] = 0;
        }
    }
    public int find(int x) { // path compression
        // only the rank of the root matters, used in union op.
        if (parent[x] != x)
            parent[x] = find(parent[x]);
        return parent[x];
    }
    public void union(int x, int y) { // union with rank
        int rootx = find(x);
        int rooty = find(y);
        if (rootx != rooty) {
            if (rank[rootx] > rank[rooty]) {
                parent[rooty] = rootx;
            } else {
                parent[rootx] = rooty;
                if (rank[rootx] == rank[rooty])
                    rank[rooty] += 1;
            }
            count--;
        }
    }
    public int getCount() {
        return count;
    }
}
Using HashMap
class UnionFind{
    //HashMap maintaining key - > value (child -> parent) relationship
    HashMap parent;
    public UnionFind(HashSet hs){
        parent = new HashMap();
        for(int i : hs){
            parent.put(i, i);
        }
    }
    public int root(int i){
        while(i != parent.get(i)){
            parent.put(i, parent.get(parent.get(i)));
            i = parent.get(i);
        }
        return i;
    }
    public void union(int i, int j){
        int p = root(i);
        int q = root(j);
        if(p != q){
            parent.put(p, q);
        }
    }
}
Posted by at
Labels: , , ,
Subscribe to: Posts (Atom)

Labels

adsense (5) Algorithm (69) Algorithm Series (35) Android (7) ANT (6) bat (8) Big Data (7) Blogger (14) Bugs (6) Cache (5) Chrome (19) Code Example (29) Code Quality (7) Coding Skills (5) Database (7) Debug (16) Design (5) Dev Tips (63) Eclipse (32) Git (5) Google (33) Guava (7) How to (9) Http Client (8) IDE (7) Interview (88) J2EE (13) J2SE (49) Java (186) JavaScript (27) JSON (7) Learning code (9) Lesson Learned (6) Linux (26) Lucene-Solr (112) Mac (10) Maven (8) Network (9) Nutch2 (18) Performance (9) PowerShell (11) Problem Solving (11) Programmer Skills (6) regex (5) Scala (6) Security (9) Soft Skills (38) Spring (22) System Design (11) Testing (7) Text Mining (14) Tips (17) Tools (24) Troubleshooting (29) UIMA (9) Web Development (19) Windows (21) xml (5)