Segmented Least Squares Problem

The least squares problem is described as follows:

Line of Best Fit

Line of Best Fit

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

Continue reading

Weighted Interval Scheduling Problem

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.

Continue reading

Preparing for the Coding Interview

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.

Continue reading

Kadane’s Algorithm

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.

Continue reading

Algorithms: Design and Analysis II

Recently I completed “Algorithms: Design and Analysis, Part 2” course at Coursera. It was offered by Professor Tim Roughgarden of Stanford University and was incredible, extremely informative and the professor was just too good.

Continue reading