2016-07-09_order-statistic-trees.md

Tech Interview Prep

@ Hacker Dojo 7/9/2016

Algorithms

Ordered Statistic Trees

• Problem: Given a stream of integers, you should be able to provide the median at any given time..
  • Ex. input: [2, 8, 5, 3, 4, 2, .. ]
    • Output (medians at i): [2, 2, 5, 3, 4, 3, 3]
  • Assumption: if you have an even number of values, the lower value is the median
• Naive solution: use insertion sort @ complexity cost O(N^2). As every value that comes in, access input[input.length / 2]
• Heap solution (Cracking the Coding Interview):
  • Create two heaps, min and max, of the same size
    • Heaps
      • Insertion: 2O(logn) + (change for rebalancing) + C = O(logn)
      • Deletion: O(logn)
    • For this problem:
      • O(logn) + [O(logn) + O(logn) (chance for rebalancing)] + C (constant time lookups) => O(logn)
  • When the heaps are differing in size by 1, take the top value of the larger heap add add it to the smaller heap
• Ordered Statistic Tree solution:
  • "Find the kth largest element in a streaming collection"
  • Using a BST requires traversing the entire tree to find the kth element, there not suited to solve this problem
  • Create a BST with node "weights" (size of the subtree with that root) with the same structure as the value BST.
  • Finding the kth largest value

    • Start at the root, check k

    • Runtime is proportional to the height of the tree, in a balanced tree: log(n)

      func findkth(k, root) {
          if(root.left == null) {
            leftCount = 0;
          }
          else {
            leftCount = root.left.count;
          }
          
          if(leftCount == k) {
            return root.value;
          }
          else if(leftCount < k) {
            return findkth((k - leftCount - 1), root.right);
          }
          else {
            return findkth(k, root.left);
          }
      }
      

    • Can be converted into a while loop

    • Works for both balanced (preferred for optimal time complexity) and unbalanced

    • A ranking function is the inverse of the above procedure; e.g., given a value of v, tell me the rank of that number in the set

  • Weights derived through tree balancing algorithms
  • Look into deletions for trees

Solving Problems with Ordered Statistic Trees

• Class of problems involving contiguous subarrays

  • Given A = [5, 3, 8, -8, 2, -4] count how many subarrays that sum to a target range T = [7, 9]

  • Possible to solve this in O(n^3) or O(n^2)

  • How can we do better?

    • When asked to deal with contiguous subarrays, think about pairs of arrays

  • Create a cumulative array, C, wrt A:

    A = [   5, 3, 8, -8, 2, -4]
            |  |  |   |  |   |
    C = [0, 5, 8, 16, 8, 10, 6]
    

  • When T is a single number, not a range...

    • Go right-to-left on C and insert (i + T, 1) into a hash table if key i + T doesn't exist. If it does, increment the value, such as (i + T, x + 1), AND increment the global matching subarray counter

  • To use an OST...

    • Think in sets... # elements >= a and < b == (# of elements < b) - (# of elements < a)
    • Like in the single number case, instead of keeping track of subarrays in a hash table, you are using an ordered statistic tree
    • Complexity is O(nlogn)

• Handling duplicates

  • Add a weight to the node, so that it will be (value, duplicate count, cumulative weight [sum |children|, |root|])

• How to practice?

  • Start with BST, then handle duplicates, then OST

• Another class of problem to solve with OST: subsequences

  • Find the total number of increasing subsequences in A = [8, 4, 7, 3, 2, 8, 5]

  • Naive O(n^2) solution: Go left to right, create a C that memos the sum of all sequences less than the value of the current index and also to the left of the current index, thus...

    A = [8, 4, 7, 3, 2, 8, 5]
         |  |  |  |  |  |  |
    C = [1, 1, 2, 1, 1, 6, 4]
    

  • How to optimize using an OST?

    • Create an OST that's (value, C[i], total weight)

• FYI: Know how to write the code to print out all subsequences of an array. And know its complexity

Resources

• geeksforgeeks
• careercup.com