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 must also be binary search trees.

Invert a binary tree.

Example

1
2
3
4
5

     4
   /   \
  2     7
 / \   / \
1   3 6   9

to

1
2
3
4
5

     4
   /   \
  7     2
 / \   / \
9   6 3   1

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [−2,1,−3,4,−1,2,1,−5,4], the contiguous subarray [4,−1,2,1] has the largest sum = 6.

Practice:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

You are playing the following Nim Game with your friend: There is a heap of stones on the table, each time one of you take turns to remove 1 to 3 stones. The one who removes the last stone will be the winner. You will take the first turn to remove the stones.

Both of you are very clever and have optimal strategies for the game. Write a function to determine whether you can win the game given the number of stones in the heap.

Example

if there are 4 stones in the heap, then you will never win the game: no matter 1, 2, or 3 stones you remove, the last stone will always be removed by your friend.

Hint

If there are 5 stones in the heap, could you figure out a way to remove the stones such that you will always be the winner?

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

OJ’s undirected graph serialization: Nodes are labeled uniquely.

We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.

Example

consider the serialized graph {0,1,2#1,2#2,2}.

The graph has a total of three nodes, and therefore contains three parts as separated by #.

• First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
• Second node is labeled as 1. Connect node 1 to node 2.
• Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle. Visually, the graph looks like the following:

1
2
3
4
5
6

   1
  / \
 /   \
0 --- 2
     / \
     \_/

Given an absolute path for a file (Unix-style), simplify it.

Example

• path = “/home/”, => “/home”
• path = “/a/./b/../../c/”, => “/c”

Corner Cases

• Did you consider the case where path = “/../”? In this case, you should return “/”.
• Another corner case is the path might contain multiple slashes ‘/’ together, such as “/home//foo/”. In this case, you should ignore redundant slashes and return “/home/foo”.

The count-and-say sequence is the sequence of integers beginning as follows: 1, 11, 21, 1211, 111221, …

Example

• 1 is read off as “one 1” or 11.
• 11 is read off as “two 1s” or 21.
• 21 is read off as “one 2, then one 1” or 1211.
• Given an integer n, generate the nth sequence.

Note

The sequence of integers will be represented as a string.

Given an unsorted array of integers, find the length of longest increasing subsequence.

Example

Given [10, 9, 2, 5, 3, 7, 101, 18], The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.

Your algorithm should run in O(n2) complexity.

Follow up: Could you improve it to O(n log n) time complexity?

Given a set of candidate numbers © and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note

All numbers (including target) will be positive integers.

Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).

The solution set must not contain duplicate combinations.

Example

given candidate set 2,3,6,7 and target 7,

A solution set is:

1
2

[7] 
[2, 2, 3]