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)