Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.

Note:

You may assume k is always valid, 1 ≤ k ≤ BST’s total elements.

Follow up:

What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?

• Try to utilize the property of a BST.
• What if you could modify the BST node’s structure?
• The optimal runtime complexity is O(height of BST).

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Example

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)

Output: 7 -> 0 -> 8

Given a set of distinct integers, nums, return all possible subsets.

Note:

The solution set must not contain duplicate subsets.

Example:

If nums = [1,2,3], a solution is:

1
2
3
4
5
6
7
8
9
10

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

Example

Given 1->2->3->3->4->4->5, return 1->2->5.

Given 1->1->1->2->3, return 2->3.

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

Example

Given input array nums = [1,1,2],

Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn’t matter what you leave beyond the new length.

Given a list of airline tickets represented by pairs of departure and arrival airports [from, to], reconstruct the itinerary in order. All of the tickets belong to a man who departs from JFK. Thus, the itinerary must begin with JFK.

Note:

• If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string. For example, The itinerary [“JFK”, “LGA”] has a smaller lexical order than [“JFK”, “LGB”].

• All airports are represented by three capital letters (IATA code).

• You may assume all tickets form at least one valid itinerary.

Example 1:

tickets = [[“MUC”, “LHR”], [“JFK”, “MUC”], [“SFO”, “SJC”], [“LHR”, “SFO”]]

Return [“JFK”, “MUC”, “LHR”, “SFO”, “SJC”].

Example 2:

tickets = [[“JFK”,“SFO”],[“JFK”,“ATL”],[“SFO”,“ATL”],[“ATL”,“JFK”],[“ATL”,“SFO”]]

Return [“JFK”,“ATL”,“JFK”,“SFO”,“ATL”,“SFO”].

Another possible reconstruction is [“JFK”,“SFO”,“ATL”,“JFK”,“ATL”,“SFO”]. But it is larger in lexical order.

Given an integer, write a function to determine if it is a power of three.

Follow up:

Could you do it without using any loop / recursion?

Given a complete binary tree, count the number of nodes.

A Complete binary tree: is a binary tree in which all interior nodes have two children and all leaves have the same depth or same level

In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

Calling next() will return the next smallest number in the BST.

Note:

next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.

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

Example

Given the array [2,3,-2,4], The contiguous subarray [2,3] has the largest product = 6.