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: {((())), (()()), (())(), ()(()), ()()()}

How do we solve this problem? Let’s start with base cases.

  • 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):

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.

 Problem : 

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.

Duplicates Within K Distance in Array/Matrix/2D Array

Given an array of integer, find duplicates which are within k indices away. Find duplicates within K manhattan distance away in a matrix or 2D array. Return true or false if such elements exists.

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).

Find the Influencer or Celebrity

A celebrity/influencer is a person who doesn’t know anybody but is known to or followed by everybody. Given N peoples and a matrix for known or following information then find the celebrity or influencer among the group of N peoples.

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.