Using TreeMap - How to Succeed in Algorithms Interview


Using TreeMap - How to Succeed in Algorithms Interview

How to Succeed in Algorithms Interview Series


Application of TreeMap

  • find floor, ceiling
  • next greater, previous smaller
  • interval

Make it sorted and traverse

public int carFleet(int target, int[] position, int[] speed) {
    TreeMap<Integer, Integer> map = new TreeMap<>();
    int n = position.length;
    for(int i=0; i<n; ++i){
        map.put(target - position[i], speed[i]);
    }
    int count = 0;
    double r = -1.0;
    for(Map.Entry<Integer, Integer> entry: map.entrySet()){
        int d = entry.getKey(); // distance
        int s = entry.getValue(); // speed
        double t = 1.0*d/s; // time to target
        if(t>r){ // this car is unable to catch up previous one, form a new group and update the value
            ++count;
            r = t;
        }
    }
    return count;
}

Find floor/ceiling

  • 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 870 - Advantage Shuffle
public int[] advantageCount(int[] A, int[] B) {
    TreeMap<Integer, Integer> m = new TreeMap<>();
    for (int i : A) m.put(i, m.getOrDefault(i, 0) + 1);
    int[] res = new int[A.length];
    for (int i = 0; i < A.length; ++i) {
        Integer x = m.higherKey(B[i]);
        if (x == null) x = m.firstKey();
        m.put(x, m.get(x) - 1);
        if (m.get(x) == 0) m.remove(x);
        res[i] = x;
    }
    return res;
}
  • LeetCode 239 - Sliding Window Maximum
  • HARD LeetCode 862 - Shortest Subarray with Sum at Least K
    public int shortestSubarray(int[] A, int K) {
       if (A.length == 0) return -1;
       TreeMap<Long, Integer> map = new TreeMap();
       map.put(0L, -1); // pay attention to the initial state
       long cumSum = 0; // sum of range[0-->i]
       int minLen = Integer.MAX_VALUE;
       for (int i = 0; i < A.length; i++) {
           // get cur cumSum
           cumSum += A[i];
           // find all candidates and update res (firstKey() will throw exception if map is empty)
           Long lowestKey = map.firstKey(), floorKey = map.floorKey(cumSum - K);
           if (lowestKey != null && floorKey != null) {
               Map<Long, Integer> subMap = new HashMap(map.subMap(lowestKey, true, floorKey, true));
               for (Long key: subMap.keySet()) {
                   int curLen = i - subMap.get(key);
                   if (minLen > curLen) minLen = curLen;  // update res
                   map.remove(key);                  // prune bad candidate
               }
           }
           // put new cumSum to tree
           map.put(cumSum, i);
       }
       return minLen == Integer.MAX_VALUE ? -1 : minLen;
     }
  • LintCode 360 - Sliding Window Median
    • TreeMap as maxHeap and minHeap but Ologn for remove

Examples

  • LintCode 502 - Mini Cassandra
  • TimeTravelingHashTable: Map<String, TreeMap<Integer, String>> map
  • LeetCode 846 - Hand of Straights
    • TreeMap
    • Remainder
  • LeetCode 954 - Array of Doubled Pairs
    • starting point: min/max value
    • O(nlogk): k is the count of distinct values
    public boolean canReorderDoubled(int[] A) {
      Map<Integer, Integer> count = new TreeMap<>();
      for (int a : A)
          count.put(a, count.getOrDefault(a, 0) + 1);
      for (int x : count.keySet()) {
          if (count.get(x) == 0) continue;
          int want = x < 0 ? x / 2 : x * 2;
          if (x < 0 && x % 2 != 0 || count.get(x) > count.getOrDefault(want, 0))
              return false;
          count.put(want, count.get(want) - count.get(x));
      }
      return true;
    }
  • LeetCode 975 - Odd Even Jump
    • scan backward + use TreeMap to find floor, ceiling
    public int oddEvenJumps(int[] A) {
      int n  = A.length, res = 1;
      boolean[] higher = new boolean[n], lower = new boolean[n];
      higher[n - 1] = lower[n - 1] = true;
      TreeMap<Integer, Integer> map = new TreeMap<>();
      map.put(A[n - 1], n - 1);
      for (int i = n - 2; i >= 0; --i) {
          Map.Entry hi = map.ceilingEntry(A[i]), lo = map.floorEntry(A[i]);
          if (hi != null) higher[i] = lower[(int)hi.getValue()];
          if (lo != null) lower[i] = higher[(int)lo.getValue()];
          if (higher[i]) res++;
          map.put(A[i], i);
      }
      return res;
    }
  • LeetCode 911 - Online Election
private TreeMap<Integer, Integer> tm = new TreeMap<>(); // time and leading candidate
public TopVotedCandidate(int[] persons, int[] times) {
    int[] count = new int[persons.length]; // count[i]: count of votes for persons[i].
    for (int i = 0, max = -1; i < times.length; ++i) {
        ++count[persons[i]]; // at times[i], persons[i] got a vote.
        if (max <= count[persons[i]]) { // is persons[i] leading?
            max = count[persons[i]]; // update leading count.
            tm.put(times[i], persons[i]); // update leading candidate.
        }
    }
}
public int q(int t) {
    return tm.floorEntry(t).getValue(); // fetch the corresponding information.
}

private Map<Integer, Integer> map = new HashMap<>(); // time and leading candidate
private int[] times;
public TopVotedCandidate(int[] persons, int[] times) {
    this.times = times;
    int[] count = new int[persons.length + 1]; // count[i]: count of votes for persons[i].
    for (int i = 0, winner = -1; i < times.length; ++i) {
        ++count[persons[i]]; // at times[i], persons[i] got a vote.
        // is persons[i] leading? update winner.
        if (map.isEmpty() || count[winner] <= count[persons[i]]) { winner = persons[i]; }
        map.put(times[i], winner); // update time and winner.
    }
}
public int q(int t) {
    int idx = Arrays.binarySearch(times, t); // search for the time slot.
    return map.get(times[idx < 0 ? -idx - 2 : idx]); // fetch the corresponding information.
}

Methods of TreeMap

treeMap.subMap(column_start, true, column_end, true);
map.put(item, map.getOrDefault(item,0)+1);
map.merge(item, 1, Integer::sum)
map.merge(key, msg, String::concat)

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)