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

# Serialize and Deserialize Binary Tree

Design an algorithm to serialize and deserialize a binary tree.

There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

# Topological Sort

Given a graph G(V,E), find the topological sorted list of vertices.

First of , what is topological sorting?

From wikipedia, topological sort (sometimes abbreviated toposort) or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering.

# Rearrange Characters in String With No Adjacent Duplicate Characters

Given a string, rearrange characters of the string such that no duplicate characters are adjacent to each other.

For example,

Input: aaabc
Output: abaca

Input: aa
Output: No valid output

Input: aaaabc
Output: No valid output

# Wiggle Sort

Given an unsorted array nums, reorder it in-place such that nums[0] <= nums[1] >= nums[2] <= nums[3]....

For example, given nums = [3, 5, 2, 1, 6, 4], one possible answer is [1, 6, 2, 5, 3, 4], another could be [3, 5, 1, 6, 2, 4].

Basically, A[0] <= A[1] >= A[2] <= A[3] >= A[4] <= A[5] Let's look into the problem closely. We can see if two consecutive elements are in wiggle sort order i.e. A[i-1]<=A[i]>=A[i+1] then it’s neighbors are also in wiggle order. So we could actually check by even and odd positions –

# Longest Valid Parenthesis

Given a string containing just the characters ‘(‘ and ‘)’, find the length of the longest valid (well-formed) parentheses substring.

For “(()”, the longest valid parentheses substring is “()”, which has length = 2.
Another example is “)()())”, where the longest valid parentheses substring is “()()”, which has length = 4.

# Moving Average of Last N numbers in a Stream

Design a class to calculate moving average of last N numbers in a stream of real numbers

For example, if N=3 and the stream S=[2,3,4,1,2,-3,0,…] then moving averages at each each streamed number are = [2.0, 2.5, 3.0, 2.66, 2.33, 0, -0.33,…].

# Rotate an Array

Given an array of integers. Rotate the array by k position to right (or left).

For example, given array A=[1,2,3,4,5,6] then rotateRight(A, 2) will return [5, 6, 1, 2, 3, 4] and rotateLeft(A,2) will return [3, 4, 5, 6, 1, 2]. Also, otateRight(A, 8) will return [5, 6, 1, 2, 3, 4] because after k=length of array(=6) the rotated array will be same as original array.

# Inorder traversal using constant space – Morris Traversal

Usual approach using linear space (stack)
We can easily do the traversal by using a stack where we keep pushing left. If no left is there then we pop an element to print it and then push its right. This is O(n) time and O(n) space algorithm.

# Transformation between Binary Tree and Linked Lists

Given a Binary Tree (or BST).
1. Flatten the BT into a single link in the order of inorder traversal.
2. Flatten the BT into a single link in the order of preorder traversal.
3. Flatten the BST to sorted single linked list.
4. Flatten a BST to Double Linked List
5. Flatten a BST to Circular Double Linked List
6. Convert Sorted Linked List to BST.
7. Convert heap ordered Linked List to BT.