# Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is: {((())), (()()), (())(), ()(()), ()()()}

• n=0 : result set is empty (no solution)

# K-th permutation sequence

Given n and k, return the k-th permutation sequence of permutations of numbers {1,2,..,n}.

Note: Given n will be between 1 and 9 inclusive.

By listing and labeling all of the permutations in order, we get the following sequence (ie, for n = 3):
“123”
“132”
“213”
“231”
“312”
“321”

# Print All Factors Of a Number

Given a positive number. Find all unique combinations of factors that constitute the number.

Note that we are not asking for only prime factors but any factors including primes. For example, given number n=12 can be factorize into 12 * 1, 6 * 2, 4 * 3, 3 * 2 * 2.

# The  Maximum  Gap  Problem :  Pigeonhole  Principle

Given a unsorted array with n elements. How can we find the largest gap between consecutive numbers of sorted version in O(n)?

For example, we have a unsorted array, a=[5, 3, 1, 8, 9, 2, 4] of size n=7 then the sorted version is
[1, 2, 3, 4, 5, 8, 9]. The output of the algorithm should be 8-5 = 3.

# Check Postordered Array Forms a BST

Given an array that contains a Post order traversal of a Binary Tree. Check if a possible Binary Tree formed from the postorder traversal is a Binary Search Tree.

For example, a1=[1, 3, 4, 2, 7, 6, 5] is a BST but a2=[1, 3, 4, 6, 7, 2, 5] is not a BST.

# The Skyline Problem

A city’s skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Now suppose you are given the locations and height of all the buildings as shown on a cityscape photo (Figure A), write a program to output the skyline formed by these buildings collectively (Figure B).

# nth Ugly Number

Write a program to find the n-th ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.

Note that 1 is typically treated as an ugly number.

# Convert to Reverse Polish Notation and Evaluate the Expression – Shunting-yard Algorithm

Given an infix expression with binary operators convert it to reverse polish notation (RPN) and evaluate the expression.

For example, the RPN form of the expression 3+2 is 32+. Similarly RPN for 3+4*2/(1-5)*2/3 is 342*15-/2*3/+ and the value of the expression is 1.66.