by 1337c0d3r
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 →
by 1337c0d3r
November 20, 2011 in dynamic programming, string
Given a string S, find the longest palindromic substring in S.
by 1337c0d3r
September 1, 2011 in backtracking, string
Implement regular expression matching with support for ‘.’ and ‘*’.
by 1337c0d3r
August 12, 2011 in linked list
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.
by 1337c0d3r
by 1337c0d3r
July 21, 2011 in binary tree
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.
by 1337c0d3r
July 18, 2011 in binary tree
Given a binary tree, find the lowest common ancestor of two given nodes in the tree.
by 1337c0d3r
July 17, 2011 in binary tree
Given a binary search tree (BST), find the lowest common ancestor of two given nodes in the BST.
by 1337c0d3r
May 19, 2011 in Uncategorized
Given an array A of integers, find the maximum of j-i subjected to the constraint of A[i] < A[j].
by 1337c0d3r
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.
by 1337c0d3r
May 12, 2011 in Uncategorized
Given two axis-aligned rectangles A and B. Write a function to determine if the two rectangles overlap.
by 1337c0d3r
April 20, 2011 in binary tree
Given preorder and inorder traversal of a tree, construct the binary tree.
by 1337c0d3r
April 6, 2011 in binary search
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 →
by 1337c0d3r
April 5, 2011 in dynamic programming
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}.
by 1337c0d3r
March 28, 2011 in Uncategorized
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)).
by 1337c0d3r
February 9, 2011 in dynamic programming
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.
- Would you rather go first or second? Does it matter?
- Assume that you go first, describe an algorithm to compute the maximum amount of money you can win.
by 1337c0d3r
January 27, 2011 in binary search
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.
by 1337c0d3r
January 25, 2011 in Uncategorized
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] 7Input: 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]
by 1337c0d3r
January 20, 2011 in Uncategorized
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’
by 1337c0d3r
January 10, 2011 in Uncategorized
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 →