Clone Graph Part I

May 30, 2012 at 10:42 am in Uncategorized by 1337c0d3r · 59 Comments »

Clone a graph. Input is a Node pointer. Return the Node pointer of the cloned graph.

Palindrome Number

Jan 4, 2012 at 11:18 pm in Uncategorized by 1337c0d3r · 146 Comments »

Determine whether an integer is a palindrome. Do this without extra space.

Longest Palindromic Substring Part II

Nov 20, 2011 at 11:07 pm in string by 1337c0d3r · 113 Comments »

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.

Longest Palindromic Substring Part I

at 7:04 am in dynamic programming, string by 1337c0d3r · 82 Comments »

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

Regular Expression Matching

Sep 1, 2011 at 2:47 am in backtracking, string by 1337c0d3r · 99 Comments »

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

Insert into a Cyclic Sorted List

Aug 12, 2011 at 9:28 pm in linked list by 1337c0d3r · 70 Comments »

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

Aug 6, 2011 at 3:16 pm in bit operations by 1337c0d3r · 49 Comments »

Reverse bits of an unsigned integer.

Lowest Common Ancestor of a Binary Tree Part II

Jul 21, 2011 at 7:28 am in binary tree by 1337c0d3r · 27 Comments »

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

Jul 18, 2011 at 6:12 pm in binary tree by 1337c0d3r · 47 Comments »

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)

Jul 17, 2011 at 3:24 am in binary tree by 1337c0d3r · 25 Comments »

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 at 2:10 am in Uncategorized by 1337c0d3r · 115 Comments »

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 at 3:39 am in string by 1337c0d3r · 87 Comments »

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 at 2:27 am in Uncategorized by 1337c0d3r · 35 Comments »

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

Apr 20, 2011 at 4:30 am in binary tree by 1337c0d3r · 63 Comments »

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

The Painter’s Partition Problem Part II

Apr 6, 2011 at 10:19 pm in binary search by 1337c0d3r · 30 Comments »

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

The Painter’s Partition Problem Part I

Apr 5, 2011 at 3:43 am in dynamic programming by 1337c0d3r · 36 Comments »

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

Mar 28, 2011 at 2:23 am in Uncategorized by 1337c0d3r · 127 Comments »

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

Feb 9, 2011 at 3:24 am in dynamic programming by 1337c0d3r · 59 Comments »

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

Jan 27, 2011 at 2:43 am in binary search by 1337c0d3r · 116 Comments »

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

Jan 25, 2011 at 7:25 pm in Uncategorized by 1337c0d3r · 83 Comments »

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  [read more →]