Least Number of Perfect Squares that Sums to n

Given a number “n”, find the least number of perfect square numbers that sum to n

For Example:
n=12, return 3 (4 + 4 + 4) = (2^2 + 2^2 + 2^2) NOT (3^2 + 1 + 1 + 1)
n = 6, return 3 (4 + 1 + 1) = (2^2 + 1^2 + 1^2)

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.

Wildcard or Regex Matching

Implement wildcard pattern matching with support for ‘.’ and ‘*’.

‘.’ Matches any single character.
‘*’ Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

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.

Quicksort – inplace O(nlgn) sorting

From wiki, Quicksort (sometimes called partition-exchange sort) is an efficient sorting algorithm, serving as a systematic method for placing the elements of an array in order. Developed by Tony Hoare in 1959, with his work published in 1961, it is still a commonly used algorithm for sorting. When implemented well, it can be about two or three times faster than its main competitors, merge sort and heapsort.

C++ Class Hierarchy Pointer Assigments

Implicit Conversion of Classes: The address of an object of a derived class can be assigned to a pointer declared to the base class, but the base class pointer can be used only to invoke member functions of the base class

Profit Maximization – Maximum Single-Sell Profit problem

Given an array of stock prices, where the increasing indexes of the array signify the increase in time. Return a good time to buy and sell such that profit is maximized.

Reverse Linked List – single pointer – in group of K

Reverse a link list using one/single pointer.

We first try to device straightforward solution to reverse a linked list recursively. For example, given a linked list 1->2->3->4->5->null, how we can reverse this? Let’s start with straightforward solution using two temp pointers. We will basically keep a new pointer to append nodes from the list into the front of new pointer. Below is both recursive and iterative solution in O(n) time.

Merge Sort

Merge sort is based on the divide-and-conquer paradigm. Its worst-case running time has a lower order of growth than insertion sort. Since we are dealing with subproblems, we state each subproblem as sorting a subarray A[p .. r]. Initially, p = 1 and r = n, but these values change as we recurse through subproblems.

Split The Linked List

Given a linked list and a number n. Split the link list into two based on the following pattern

input: 1->2->3->4->5->6->7->8->null and n=2
output: 1-2->3->4->null and 5->6->7->8->null

input: 2->3->1->4->6->7->7->6->null and n=4
output: 2-3->null and 1->4->6->7->7->6->null

return the right partition pointer.