Data Structure Design - How to Succeed in Algorithms Interview


Data Structure Design - How to Succeed in Algorithms Interview

How to Succeed in Algorithms Interview Series


Implementation Detail

  • DoubleLinkedList + Map/TreeMap
  • Use DoubleLinkedList class to wrap the logic of maintain head tail nodes.
  • use version to track valid element in map

DoubleLinkedList + Map/TreeMap

Freq Buckets

  • freq increases from 1 to n continuously
  • LeetCode 895 - Maximum Frequency Stack: popMax
    class FreqStack {
      List<Stack<Integer>> bucket;
      HashMap<Integer, Integer> map;
      public FreqStack() {
          bucket = new ArrayList<>();
          map = new HashMap<>();
      }
      public void push(int x) {
          map.put(x, map.getOrDefault(x, 0) + 1);
          int freq = map.get(x);
          if (freq - 1 >= bucket.size()) {
              bucket.add(new Stack<Integer>());
          }
          bucket.get(freq - 1).add(x);
      }
      public int pop() {
          int freq = bucket.size();
          int x = bucket.get(freq - 1).pop();
          if (bucket.get(freq - 1).isEmpty()) bucket.remove(bucket.size() - 1);
          map.put(x, map.get(x) - 1);
          if (map.get(x) == 0) map.remove(x);
          return x;
      }
    }
    class FreqStack {
      class Pair{
          int num;
          int count;
          int time;
          Pair(int num, int count, int time){
              this.num = num;
              this.count = count;
              this.time = time;
          }
      }
      private PriorityQueue<Pair> queue;
      private HashMap<Integer,Integer> map;
      private int clock = 0;
      public FreqStack() {
          queue = new PriorityQueue<Pair>((a,b) -> (a.count == b.count?b.time-a.time:b.count-a.count));
          map = new HashMap();
      }
      public void push(int x) {
          Pair pair = new Pair(x,map.getOrDefault(x,0)+1,clock++);
          map.put(x,map.getOrDefault(x,0)+1);
          queue.offer(pair);
      }
      public int pop() {
          Pair cur = queue.poll();
          // update
          map.put(cur.num,map.getOrDefault(cur.num,0)-1);
          return cur.num;
      }   
    }
  • Design a Data Structure with Insert & Delete & GetMostFrequent of O(1) - LRU
    • HashMap<Integer, Node> map: Node contains all values with same frequency
  • LeetCode 432 - All O`one Data Structure
    // maintain a doubly linked list of Buckets
    private Bucket head;
    private Bucket tail;
    // for accessing a specific Bucket among the Bucket list in O(1) time
    private Map<Integer, Bucket> countBucketMap;
    // keep track of count of keys
    private Map<String, Integer> keyCountMap;
    // each Bucket contains all the keys with the same count
    // sorted linked
    private class Bucket {
      int count;
      Set<String> keySet;
      Bucket next;
      Bucket pre;
      public Bucket(int cnt) {
          count = cnt;
          keySet = new HashSet<>();
      }
    }

Custom LinkedList + HashMap

  • LeetCode 146 - Least Recently Used (LRU) Cache
    • Linkedlist + HashMap
  • [LeetCode 460 - LFU Cache][keyValueMap, freqMap, Map<Integer, LinkedHashSet> sameFreqMap, minFreq](https://leetcode.com/problems/lfu-cache/discuss/94521/java-o1-very-easy-solution-using-3-hashmaps-and-linkedhashset)
    private Node head = null;
    private int cap = 0;
    private HashMap<Integer, Integer> valueHash = null;
    private HashMap<Integer, Node> nodeHash = null;
    public LFUCache(int capacity) {
      this.cap = capacity;
      valueHash = new HashMap<Integer, Integer>();
      nodeHash = new HashMap<Integer, Node>();
    }
    public int get(int key) {
      if (valueHash.containsKey(key)) {
          increaseCount(key);
          return valueHash.get(key);
      }
      return -1;
    }
    public void set(int key, int value) {
      if ( cap == 0 ) return;
      if (valueHash.containsKey(key)) {
          valueHash.put(key, value);
      } else {
          if (valueHash.size() < cap) {
              valueHash.put(key, value);
          } else {
              removeOld();
              valueHash.put(key, value);
          }
          addToHead(key);
      }
      increaseCount(key);
    }
    private void addToHead(int key) {
      if (head == null) {
          head = new Node(0);
          head.keys.add(key);
      } else if (head.count > 0) {
          Node node = new Node(0);
          node.keys.add(key);
          node.next = head;
          head.prev = node;
          head = node;
      } else {
          head.keys.add(key);
      }
      nodeHash.put(key, head);      
    }
    private void increaseCount(int key) {
      Node node = nodeHash.get(key);
      node.keys.remove(key);
      if (node.next == null) {
          node.next = new Node(node.count+1);
          node.next.prev = node;
          node.next.keys.add(key);
      } else if (node.next.count == node.count+1) {
          node.next.keys.add(key);
      } else {
          Node tmp = new Node(node.count+1);
          tmp.keys.add(key);
          tmp.prev = node;
          tmp.next = node.next;
          node.next.prev = tmp;
          node.next = tmp;
      }
      nodeHash.put(key, node.next);
      if (node.keys.size() == 0) remove(node);
    }
    private void removeOld() {
      if (head == null) return;
      int old = 0;
      for (int n: head.keys) {
          old = n;
          break;
      }
      head.keys.remove(old);
      if (head.keys.size() == 0) remove(head);
      nodeHash.remove(old);
      valueHash.remove(old);
    }
    private void remove(Node node) {
      if (node.prev == null) {
          head = node.next;
      } else {
          node.prev.next = node.next;
      }
      if (node.next != null) {
          node.next.prev = node.prev;
      }
    }
    class Node {
      public int count = 0;
      public LinkedHashSet<Integer> keys = null;
      public Node prev = null, next = null;
    }

N Queens

Map<Integer, Integer> row = new HashMap();       // row number to count of lamps
Map<Integer, Integer> col = new HashMap();       // col number to count of lamps
Map<Integer, Integer> diag = new HashMap();       // diagonal x-y to count of lamps
Map<Integer, Integer> diag2 = new HashMap();       // diagonal x+y to count of lamps
Map<Integer, Boolean> lamps = new HashMap();       // whether lamp is  ON|OFF

Examples

Binary Tree

  • [Google – Manager Peer Problem]
  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.
  • Map<Integer, TNode> nodeMap
  • union find: int[] parent

Binary Search - How to Succeed in Algorithms Interview


Binary Search - How to Succeed in Algorithms Interview
Application

Types

  1. Compare left, right, mid
  2. compare mid, mid-1, mid+1
public List<Integer> findClosestElements(List<Integer> arr, int k, int x) {
    int lo = 0, hi = arr.size() - k;
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        if (x - arr.get(mid) > arr.get(mid+k) - x)
            lo = mid + 1;
        else
            hi = mid;
    }
    return arr.subList(lo, lo + k);
}
  • TreeSet, TreeMap
int ret = Arrays.binarySearch(arr, value);
if(ret < 0) ret = -ret - 1

Implementation - Different

  • Mistakes: deadlock,
  • invariants
  • Prefer []
  • int mid = left + (right - left) / 2; then left=mid+1
  • or mid = low + ((high - low + 1) / 2); then left=mid ### Possible Bugs | | | | | |-|-|-|-| low|high|mid|while(?) mid + 1 | mid - 1|low + ((high - low) / 2)|low <= high mid + 1 | mid |low + ((high - low) / 2) | low < high mid | mid - 1 | low + ((high - low + 1) / 2) | low < high mid | mid | X(infinite loop) | X(invalid)
  • loop not exit
  • test with cases: left=2, right=3; mid=2
private static int binarySearch0(int[] a, int fromIndex, int toIndex,
                                 int key) {
    int low = fromIndex;
    int high = toIndex - 1;

    while (low <= high) {
        int mid = (low + high) >>> 1;
        int midVal = a[mid];

        if (midVal < key)
            low = mid + 1;
        else if (midVal > key)
            high = mid - 1;
        else
            return mid; // key found
    }
    return -(low + 1);  // key not found.
}
public int searchRightIndex(int[] nums, int left, int right, int target) {  
    while (left <= right) {  
        int mid = (left + right) / 2;  
        if (nums[mid] > target) right = mid - 1;  
        else left = mid + 1;  
    }  
    return right;  
}  
public int searchLeftIndex(int[] nums, int left, int right, int target) {  
    while (left <= right) {  
        int mid = (left + right) / 2;  
        if (nums[mid] < target) left = mid + 1;  
        else right = mid - 1;  
    }  
    return left;  
}  
public int mySqrt(int x) {
    long l=0,r=x; //in case of overflow
    while(l<r){
        long mid=l+(r-l+1)/2;
        if(mid*mid>x) r=mid-1;
        else l=mid;
    }
    return (int)l;
}
int mySqrt(int x) {
    if (x <= 1) return x;
    int left = 0, right = x;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (x / mid >= mid) left = mid + 1;
        else right = mid;
    }
    return right - 1;
}
int maxElementLesser(int[] array, int key) {
  int length = array.length;
  int low = 0;
  int high = length - 1;
  while (low < high) {
    int mid = low + ((high - low + 1) / 2);//\\
    int current = array[mid];
    if (current == key) {
      return array[mid];
    } else if (current < key) {
      low = mid;
    } else {
      high = mid - 1;
    }
  }
  return array[low];
}

Search in rotated sort array

public int search(int[] nums, int target) {
    int start = 0, end = nums.length - 1;
    while (start <= end) {
        int mid = ( start + end) / 2;
        if (nums[mid] == target) {
            return mid;
        }
        if (nums[start] <= nums[mid]) {
            if (nums[start] <= target && target < nums[mid]) {
                end = mid -1;
            }
            else {
                start = mid + 1;
            }
        }
        else{
            if (nums[mid] < target && target <= nums[end]) {
                start = mid + 1;
            }
            else {
                end = mid -1;
            }
        }
    }
    return -1;
}
  • LeetCode 81 - Search in Rotated Sorted Array II
  • LeetCode 154 - Find Minimum in Rotated Sorted Array II

Examples

int findPeakElement(const vector<int> &num)
{
    int low = 0;
    int high = num.size()-1;
    while(low < high)
    {
        int mid1 = low + (high-low)/2;
        int mid2 = mid1+1;
        if(num[mid1] < num[mid2])
            low = mid2;
        else
            high = mid1;
    }
    return low;
}

Duplicates

int magicHelper(int arr[],int n,int l,int r)
{
    if(l>r||l<0||r>=n)
        return -1;
    int mid=(l+r)/2;
    if(mid==arr[mid])
        return mid;
    int rightindex=min(mid-1,arr[mid]);
    int left=magicHelper(arr,n,l,rightindex);
    if(left>=0)
        return left;
    int leftindex=max(mid+1,arr[mid]);
    int right=magicHelper(arr,n,leftindex,r);
    return right;
}
int magicFast(int arr[],int n)
{
    if(n==0)
        return -1;
    return magicHelper(arr,n,0,n-1);
}
  • [Smallest Rectangle Enclosing Black Pixels]
public int minArea(char[][] image, int x, int y) {
 int m = image.length, n = image[0].length;
 int colMin = binarySearch(image, true, 0, y, 0, m, true);
 int colMax = binarySearch(image, true, y + 1, n, 0, m, false);
 int rowMin = binarySearch(image, false, 0, x, colMin, colMax, true);
 int rowMax = binarySearch(image, false, x + 1, m, colMin, colMax, false);
 return (rowMax - rowMin) * (colMax - colMin);
}

public int binarySearch(char[][] image, boolean horizontal, int lower, int upper, int min, int max, boolean goLower) {
 while(lower < upper) {
  int mid = lower + (upper - lower) / 2;
  boolean inside = false;
     for(int i = min; i < max; i++) {
      if((horizontal ? image[i][mid] : image[mid][i]) == '1') {
       inside = true;
       break;
      }
     }
  if(inside == goLower) {
   upper = mid;
  } else {
   lower = mid + 1;
  }
 }
 return lower;
}

Resources

Binary Search Tree - How to Succeed in Algorithms Interview


Binary Search Tree - How to Succeed in Algorithms Interview

How to Succeed in Algorithms Interview Series


Implementation Detail of Binary Search Tree

  • track and update [minVal, maxVal], or just min, max
  • in-order traverse
  • convert bst to linkedlist
  • track prev node
  • if (root.val > k1) go left otherwise go right
Range value [minVal, maxVal]
public void deleteEdge(TreeNode root) {
    if(root == null) return;
    root = dfs(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
}
private TreeNode dfs(TreeNode root, int left, int right) {
    if(root == null) return null;
    if(root.val <= left || root.val >= right) return null;
    root.left = dfs(root.left, left, root.val);
    root.right = dfs(root.right, root.val, right);
    return root;
}
Examples
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || p == null || q == null) return null;
    if(root.val<Math.min(p.val,q.val)) return lowestCommonAncestor(root.right,p,q);
    if(root.val>Math.max(p.val,q.val)) return lowestCommonAncestor(root.left,p,q);
    return root;
}

In-order traverse

Node prev = null;
public Node treeToDoublyList(Node root) {
    if (root == null){
        return null;
    }
    Node dummy = new Node(0, null, null);
    prev = dummy;
    helper(root);
    //connect tail with head;
    prev.right = dummy.right;
    dummy.right.left = prev;
    return dummy.right;
}
private void helper(Node cur){
    if (cur == null){
        return;
    }
    helper(cur.left);
    prev.right = cur;
    cur.left = prev;
    prev = cur;
    helper(cur.right);
}

Postorder

  • left, right, root
  • scan backward from root to right then left
  • HARD Construct a Binary Search Tree from given postorder
    Node constructTreeUtil(int post[], int n)
    {
      Node root = new Node(post[n - 1]);
      Stack<Node> s = new Stack<>();
      s.push(root);
      for (int i = n - 2; i >= 0; --i) {
          Node x = new Node(post[i]);
          Node temp = null;
          while (!s.isEmpty() && post[i] < s.peek().data)  
              temp = s.pop();       
          // Make x as left child of temp    
          if (temp != null)  
              temp.left = x;       
          // Else make x as right of top       
          else
              s.peek().right = x;
          s.push(x);
      }
      return root;
    }

Bisection (Binary Search) - How to Succeed in Algorithms Interview


Bisection (Binary Search) - How to Succeed in Algorithms Interview

Applications of Bisection

  • O(n) optimize to logn, o(n^2) to O(nlog$the_range)
  • Know the search Space: range(min, max), index
  • calculation error(tolerance) should be less than
  • Suppose we know the value, we can easily determine whether the value is true/possible
    • With O(n) time
    • Use greedy to to check, time complexity: O(n) or less
    • Sliding window
    • Two Pointers
  • isPossible(*, int curValue)
  • minimum is maximized

Detail

  • error (tolerance) as part of the API
Search space
  • range: smallest to largest
  • index
validate the answer is right
public int woodCut(int[] L, int k) {
  int lo = 1;
  int hi = 0;
  for (int i = 0; i < L.length; i++) {
    hi = Math.max(hi, L[i]);
  }
  while (lo < hi) {
    int mid = lo + (hi - lo + 1) / 2;
    int pieces = getPieces(mid, L);
    if (pieces < k) {
      hi = mid - 1;
    } else {
      lo = mid;
    }
  }
  if (getPieces(lo, L) >= k) {
    return lo;
  } else {
    return 0;
  }
}
private int getPieces(int len, int[] L) {
  int ans = 0;
  for (int l : L) {
    ans += l / len;
  }
  return ans;
}

Find kth in sorted matrix

Examples

public int findDuplicate(int[] nums) {
    int n = nums.length-1;
    int low = 1, high= n;
    int mid = 0;
    while(low<high) {
        mid = low + (high-low)/2;
        int c= count(nums, mid); //count #numbers less than mid.
        if(c<=mid) {
            low = mid+1;
        } else {
            high = mid;
        }
    }
    return low;
}

private int count(int[] nums, int mid) {
    int c =0;
    for(int i=0; i<nums.length; i++) {
        if(nums[i]<=mid) c++;
    }
    return c;
}
  • POJ 2976 Dropping tests
    • Convert r = max(∑a[i] / ∑b[i]) -> ∑a[i] - ∑b[i] * r = 0
  • LeetCode 410 - Split Array Largest Sum
    • split the array into m non-empty continuous subarrays and minimize the largest sum among these m subarrays
    • f[i][j] = min(max(f[i - 1][k] + nums[k] + nums[k + 1] + … + nums[j]))
    • f[1][i] = prefix sum of nums[i]
    • bisection
  • LeetCode 718 - Maximum Length of Repeated Subarray
    1. dp[i][j] = 1 + dp[i - 1][j - 1];
    2. prefix rolling hash + bisection
  • HARD LeetCode 862 - Shortest Subarray with Sum at Least K
    public int shortestSubarray(int[] A, int K) {
      int N = A.length;
      // Compute cumulative sum
      int[] cumSum = new int[N];
      for (int i = 0; i < N; ++i) {
          cumSum[i] = i > 0 ? cumSum[i-1] + A[i] : A[i];
      }
      if (!existsSolution(cumSum, K, N)) return -1;
      // Binary search over all possible lengths
      int l = 1, r = N;
      while (l < r) {
          int m = l + (r-l) / 2;
          if (existsSolution(cumSum, K, m)) {
              r = m;
          } else {
              l = m+1;
          }
      }
      return l;
    }
    boolean existsSolution(int[] cumSum, int K, int len) {
      // Priority queue that maintains minimal value within the window of size 'len'
      PriorityQueue<VI> pq = new PriorityQueue<>((a, b) -> Integer.compare(a.val, b.val));
      pq.add(new VI(0, -1));
      for (int i = 0; i < cumSum.length; ++i) {
          // Clean up minimal elements that are outside of the window
          while (!pq.isEmpty() && pq.peek().pos < i-len) {
              pq.poll();
          }
          int windowMin = !pq.isEmpty() ? pq.peek().val : 0;
          if (cumSum[i] - windowMin >= K) {
              return true;
          }
          pq.add(new VI(cumSum[i], i));
      }
      return false;
    }
    public static class VI {public int val, pos;}

Return not mid

private long search(int[] nums, int k, long left, long right) {
    if (left >= right) {
        return left;
    }
    long res = left;
    long guess = left + (right - left) / 2;
    int count = 0;
    for (int num : nums) {
        if (num <= guess) {
            count++;
            res = Math.max(res, num);
        }
    }
    if (count == k) {
        return res;
    } else if (count < k) {
        return search(nums, k, Math.max(res + 1, guess), right);
    } else {
        return search(nums, k, left, res);
    }
}
public double findMedian(int[] nums) {
    int len = 0;
    for (int num : nums) {
        len++;
    }
    if (len % 2 == 1) {
        return (double) search(nums, len / 2 + 1, Integer.MIN_VALUE, Integer.MAX_VALUE);
    } else {
        return (double) (search(nums, len / 2, Integer.MIN_VALUE, Integer.MAX_VALUE) +
                search(nums, len / 2 + 1, Integer.MIN_VALUE, Integer.MAX_VALUE)) / 2;
    }
}

Resources

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)