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)
Monthly Archives: October 2015
Search in a 2D Array or Matrix
Write an efficient algorithm that searches for a value in an m x n matrix.
Matrix can have two forms. Solve it for each form of the matrix. This matrix has the following properties:
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.
Word Break Problem
Given an input string and a dictionary of words, find out if the input string can be segmented into a space-separated sequence of dictionary words.
For example, Given a dictionary { i, like, ili, kesa, msun, sam, sung, mobile} then
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.
Number of Unique Binary Search Trees
Given two integers m and n , n>=m. Find total number of structurally correct BSTs possible with all numbers between m and n (inclusive).
For example, m=3, n=5 then answer is 5.
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->nullinput: 2->3->1->4->6->7->7->6->null and n=4
output: 2-3->null and 1->4->6->7->7->6->nullreturn the right partition pointer.