Problem of the day for today is Longest palindromic substring: *Given a string, find its longest palindromic substring.*. For example, given the string “ababab”, the longest palindromic substring would be “ababa”.

# Tag Archives: dynamic programming

# Segmented Least Squares Problem

The **least squares problem** is described as follows:

Given n points in the plane: (x_{1}, y_{1}), (x_{2}, y_{2}), …, (x_{n}, y_{n}), find a line y = ax + b that minimizes the sum of squared errors:

SSE = sum_{1 ≤ i ≤ n}(y_{i} – ax_{i} – b)^{2}

# 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 w_{i} and the goal is to find the maximum-weight subset of compatible requests. It degenerates to the interval scheduling problem when w_{i} = 1 ∀i.

# 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.

# 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.

# 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.