The least squares problem is described as follows:
Given n points in the plane: (x1, y1), (x2, y2), …, (xn, yn), find a line y = ax + b that minimizes the sum of squared errors:
SSE = sum1 ≤ i ≤ n(yi – axi – b)2
Unlike the Interval Scheduling Problem where we sought to maximize the number of requests that could be accommodated simultaneously, in the Weighted Interval Scheduling Problem, each request i has an associated value or weight wi and the goal is to find the maximum-weight subset of compatible requests. It degenerates to the interval scheduling problem when wi = 1 ∀i.
I recently got interviewed for a position at Microsoft and I think I owe acknowledgement to the various interview resources I used to prepare for it. Further, it should be helpful to many others like me who will be facing technical interviews this interview season.
Here, I describe variants of Kadane’s algorithm to solve the maximum subarray and the minimum subarray problems. The maximum subarray problem is to find the contiguous subarray having the largest sum. Likewise, the minimum subarray problem is to find the contiguous subarray having the smallest sum. Variants of Kadane’s algorithm can solve these problems in O(N) time.