Month: July 2014

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

A message containing letters from A-Z is being encoded to numbers using the following mapping:

Given an encoded message containing digits, determine the total number of ways to decode it. For example, Given encoded message “12”, it could be decoded as “AB” (1 2) or “L” (12). The number of ways decoding “12” is 2. Analysis We can solve this problem recursively. But … Read more

The gray code is a binary numeral system where two successive values differ in only one bit. Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0. For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:

Note: … Read more

Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively. Below is one possible representation of s1 = “great”:

To scramble the string, we may choose any non-leaf node and swap its two children. For example, if we choose the node “gr” and swap its two children, it produces a … Read more

Follow up for “Search in Rotated Sorted Array”: What if duplicates are allowed? Would this affect the run-time complexity? How and why? Write a function to determine if a given target is in the array. Analysis This problem is similar to “Search in Rotated Sorted Array”. But there could be duplicates. In problem “Search in Rotated Sorted … Read more

Given a 2D board and a word, find if the word exists in the grid. The word can be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once. For example, Given board =

word = “ABCCED”, -> returns true, word = “SEE”, -> … Read more

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n). For example, S = “ADOBECODEBANC” T = “ABC” Minimum window is “BANC”. Note: If there is no such window in S that covers all characters in T, return the emtpy string “”. If there are multiple … Read more

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place. Follow up: Did you use extra space? A straight forward solution using O(mn) space is probably a bad idea. A simple improvement uses O(m + n) space, but still not the best solution. Could you devise a constant … Read more

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.) You have the following 3 operations permitted on a word: a) Insert a character b) Delete a character c) Replace a character Analysis This is a DP problem. We will use a two dimensional array distance[][] … Read more

Implement int sqrt(int x). Compute and return the square root of x. Analysis We can use binary search for this problem. It could be pretty easy to implement. It’s possible that integer overflows. So in the following code I use long type. There is another way, which is Newton’s Method. You can check the code here. Code … Read more