Given a non-empty array of integers, return the k most frequent elements.

Example:

Given [1,1,1,2,2,3] and k = 2, return [1,2].

Note:

• You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
• Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size.

Given a roman numeral, convert it to an integer.

Input is guaranteed to be within the range from 1 to 3999.

Given a binary tree, return the preorder traversal of its nodes’ values.

Example:

Given binary tree {1,#,2,3},

1
2
3
4
5

   1
    \
     2
    /
   3

return [1,2,3].

Note:

Recursive solution is trivial, could you do it iteratively?

Given an integer n, generate all structurally unique BST’s (binary search trees) that store values 1…n.

Example

Given n = 3, your program should return all 5 unique BST’s shown below.

1
2
3
4
5

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

Write a program to find the node at which the intersection of two singly linked lists begins.

Example:

The following two linked lists:

1
2
3
4
5

A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3

begin to intersect at node c1.

Notes:

• If the two linked lists have no intersection at all, return null.
• The linked lists must retain their original structure after the function returns.
• You may assume there are no cycles anywhere in the entire linked structure.
• Your code should preferably run in O(n) time and use only O(1) memory.

Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array.

Formally the function should: Return true if there exists i, j, k

such that arr[i] < arr[j] < arr[k] given 0 ≤ i < j < k ≤ n-1 else return false.

Your algorithm should run in O(n) time complexity and O(1) space complexity.

Examples

Given [1, 2, 3, 4, 5], return true.

Given [5, 4, 3, 2, 1], return false.

For a undirected graph with tree characteristics, we can choose any node as the root. The result graph is then a rooted tree. Among all possible rooted trees, those with minimum height are called minimum height trees (MHTs). Given such a graph, write a function to find all the MHTs and return a list of their root labels.

Format

The graph contains n nodes which are labeled from 0 to n - 1. You will be given the number n and a list of undirected edges (each edge is a pair of labels).

You can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.

Example 1:

Given n = 4, edges = [[1, 0], [1, 2], [1, 3]]

1
2
3
4
5

    0
    |
    1
   / \
  2   3

return [1]

Example 2:

Given n = 6, edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]

1
2
3
4
5
6
7

 0  1  2
  \ | /
    3
    |
    4
    |
    5

return [3, 4]

Hint

How many MHTs can a graph have at most?

Note

1. According to the definition of tree on Wikipedia: “a tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any connected graph without simple cycles is a tree.”

2. The height of a rooted tree is the number of edges on the longest downward path between the root and a leaf.

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

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

Note:

You may assume that duplicates do not exist in the tree.

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note

You are not suppose to use the library’s sort function for this problem.