Programming

Suppose you have a random list of people standing in a queue. Each person is described by a pair of integers (h, k), where h is the height of the person and k is the number of people in front of this person who have a height greater than or equal to h. Write an … Read more

I have written a solution for this question before: http://www.lifeincode.net/programming/leetcode-median-of-two-sorted-arrays-java/ That solution seems easy to understand. However, it turns out to be very difficult to implement. The hardest part is how we come up with a correct way to handle borders. After reading some post, I found there is another way to achieve findKth number from two … Read more

In the last post, I have mentioned that I want to write the solution for finding two missing numbers from 1 to N. It has been several months(almost half year, how time flies) and finally I have time to write it down. Problem description: Find two missing number from 1 to N Given an array of … Read more

Find one missing number from 1 to N Given an array of size N-1, containing integer numbers from 1 to N, but there is one number missing. Return the missing number. Analysis Assuming the array given is A[], it’s easy to get N since we have the size of the array: N = A.length + 1. … Read more

Palindrome Partitioning Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s. For example, given s = “aab”, Return

Palindrome Partitioning II Given a string s, partition s such that every substring of the partition is a palindrome. Return the minimum cuts needed for a palindrome partitioning of s. For example, given s = “aab”, … Read more

Say you have an array for which the ith element is the price of a given stock on day i. Design an algorithm to find the maximum profit. You may complete at most two transactions. Note: You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again). Analysis In this … Read more

Given a string S and a string T, count the number of distinct subsequences of T in S. A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, “ACE” is a subsequence of “ABCDE” while “AEC” is not). Here is an example: … Read more

Two elements of a binary search tree (BST) are swapped by mistake. Recover the tree without changing its structure. Note: A solution using O(n) space is pretty straight forward. Could you devise a constant space solution? Analysis We can use in-order traverse to find the swapped element. During the traverse, we can find the element that … Read more

Given a binary tree, determine if it is a valid binary search tree (BST). Assume a BST is defined as follows: The left subtree of a node contains only nodes with keys less than the node’s key. The right subtree of a node contains only nodes with keys greater than the node’s key. Both the left and right subtrees … Read more

Unique Binary Search Trees Given n, how many structurally unique BST’s (binary search trees) that store values 1…n? For example, Given n = 3, there are a total of 5 unique BST’s.

Unique Binary Search Trees II Given n, generate all structurally unique BST’s (binary search trees) that store values 1…n. For example, Given n = 3, your program should return all 5 unique … Read more