## Longest Palindromic Substring Part II

November 20, 2011 in string

Given a string S, find the longest palindromic substring in S.

Note:
This is Part II of the article: Longest Palindromic Substring. Here, we describe an algorithm (Manacher’s algorithm) which finds the longest palindromic substring in linear time. Please read Part I for more background information.
Read the rest of this entry →

## Longest Palindromic Substring Part I

November 20, 2011

Given a string S, find the longest palindromic substring in S.

## Regular Expression Matching

September 1, 2011

Implement regular expression matching with support for ‘.’ and ‘*’.

## Insert into a Cyclic Sorted List

August 12, 2011

Given a node from a cyclic linked list which has been sorted, write a function to insert a value into the list such that it remains a cyclic sorted list. The given node can be any single node in the list.

## Reverse Bits

August 6, 2011

Reverse bits of an unsigned integer.

## Lowest Common Ancestor of a Binary Tree Part II

July 21, 2011

Given a binary tree, find the lowest common ancestor of two given nodes in the tree. Each node contains a parent pointer which links to its parent.

## Lowest Common Ancestor of a Binary Tree Part I

July 18, 2011

Given a binary tree, find the lowest common ancestor of two given nodes in the tree.

## Lowest Common Ancestor of a Binary Search Tree (BST)

July 17, 2011

Given a binary search tree (BST), find the lowest common ancestor of two given nodes in the BST.

## A Distance Maximizing Problem

May 19, 2011

Given an array A of integers, find the maximum of j-i subjected to the constraint of A[i] < A[j].

## Longest Substring Without Repeating Characters

May 16, 2011 in string

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for “abcabcbb” is “abc”, which the length is 3. For “bbbbb” the longest substring is “b”, with the length of 1.

## Determine If Two Rectangles Overlap

May 12, 2011

Given two axis-aligned rectangles A and B. Write a function to determine if the two rectangles overlap.

## Construct Binary Tree From Inorder and Preorder/Postorder Traversal

April 20, 2011

Given preorder and inorder traversal of a tree, construct the binary tree.

## The Painter’s Partition Problem Part II

April 6, 2011

Note:
This is Part II of the article: The Painter’s Partition Problem. Please read Part I for more background information.
Read the rest of this entry →

## The Painter’s Partition Problem Part I

April 5, 2011

You have to paint N boards of length {A0, A1, A2 … AN-1}. There are K painters available and you are also given how much time a painter takes to paint 1 unit of board. You have to get this job done as soon as possible under the constraints that any painter will only paint continuous sections of board, say board {2, 3, 4} or only board {1} or nothing but not board {2, 4, 5}.

## Median of Two Sorted Arrays

March 28, 2011

There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

## Coins in a Line

February 9, 2011

There are n coins in a line. (Assume n is even). Two players take turns to take a coin from one of the ends of the line until there are no more coins left. The player with the larger amount of money wins.

1. Would you rather go first or second? Does it matter?
2. Assume that you go first, describe an algorithm to compute the maximum amount of money you can win.

## Find the k-th Smallest Element in the Union of Two Sorted Arrays

January 27, 2011

Given two sorted arrays A, B of size m and n respectively. Find the k-th smallest element in the union of A and B. You can assume that there are no duplicate elements.

## Sliding Window Maximum

January 25, 2011

A long array A[] is given to you. There is a sliding window of size w which is moving from the very left of the array to the very right. You can only see the w numbers in the window. Each time the sliding window moves rightwards by one position. Following is an example:
The array is [1 3 -1 -3 5 3 6 7], and w is 3.

```Window position                Max
---------------               -----
[1  3  -1] -3  5  3  6  7       3
1 [3  -1  -3] 5  3  6  7       3
1  3 [-1  -3  5] 3  6  7       5
1  3  -1 [-3  5  3] 6  7       5
1  3  -1  -3 [5  3  6] 7       6
1  3  -1  -3  5 [3  6  7]      7```

Input: A long array A[], and a window width w
Output: An array B[], B[i] is the maximum value of from A[i] to A[i+w-1]
Requirement: Find a good optimal way to get B[i]

## Nuts in an Oasis

January 20, 2011

A pile of nuts is in an oasis, across a desert from a town. The pile contains ‘N’ kg of nuts, and the town is ‘D’ kilometers away from the pile.

The goal of this problem is to write a program that will compute ‘X’, the maximum amount of nuts that can be transported to the town.

The nuts are transported by a horse drawn cart that is initially next to the pile of nuts. The cart can carry at most ‘C’ kilograms of nuts at any one time. The horse uses the nuts that it is carrying as fuel. It consumes ‘F’ kilograms of nuts per kilometer traveled regardless of how much weight it is carrying in the cart. The horse can load and unload the cart without using up any nuts.

Your program should have a function that takes as input 4 real numbers D,N,F,C and returns one real number: ‘X’

## Studious Student Problem Analysis

January 10, 2011

You’ve been given a list of words to study and memorize. Being a diligent student of language and the arts, you’ve decided to not study them at all and instead make up pointless games based on them. One game you’ve come up with is to see how you can concatenate the words to generate the lexicographically lowest possible string. Read the rest of this entry →