Binary Search Tree: Any Path Sum

You are given a binary tree in which each node contains a value. Design an algorithm to print all paths which sum up to that value. Note that it can be any path in the tree - it does not have to start at the root.

Input/Output:

printing inorder: 

1 3 4 5 6 7 8 9 10 12 13 15 17 

printing preorder: 

7 5 3 1 4 6 12 9 8 10 15 13 17 

printing path(s):

7 -> 5 -> null

5 -> 3 -> 4 -> null

12 -> null

Binary Tree: Is SubTree ?

You have two very large binary trees: T1, with millions of nodes, and T2, with hundreds of nodes. Create an algorithm to decide if T2 is a subtree of T1.

Approach 1:
T1 has 10 million nodes—this means that the data alone is about 40 mb. We could create a string representing the inorder and preorder traversals. If T2’s preorder traversal is a substring of T1’s preorder traversal, and T2’s inorder traversal is a substring of T1’s inorder traversal, then T2 is a substring of T1. We can check this using a suffix tree. However, we may hit memory limitations because suffix trees are extremely memory intensive. If this become an issue, we can use an alternative approach.

Approach 2:
Find all the occurances of  T2's root node in T1 and then check recursively if the binary tree matches or not.

Binary Search Tree: Least Common Ancestor

Least common ancestor of 2 nodes in a binary search tree:

Approach:
The main idea of the solution is — While traversing Binary Search Tree from top to bottom, the first node n we encounter with value between n1 and n2, i.e., n1 < n < n2 is the Lowest or Least Common Ancestor(LCA) of n1 and n2 (where n1 < n2). 
So just traverse the BST in pre-order, if you find a node with value in between n1 and n2 then n is the LCA,
 if it's value is greater than both n1 and n2 then our LCA lies on left side of the node,
 if it's value is smaller than both n1 and n2 then LCA lies on right side.

Binary Tree: Least Common Ancestor

Design an algorithm and write code to find the first common ancestor of two nodes in a binary tree. NOTE: This is not necessarily a binary search tree.

Approach:
Do the inorder traversal and store it in an array I
Then do the preorder traversal and store it in an array P

Inorder: D B F G E A C
PreOrder: A B D E F G C


Suppose we need to find LCA for nodes D and F
mark the positions in inorder array and find first preorder ptr which seprates it into two
different parts of Inorder array

for above example first preorder ptr is "B" which seprates inorder into "D" and "F G E A C"
so "B" is first commom ancester of "D" and "F".

Binary Tree: Inorder Predecessor

Write an algorithm to find the ‘previous’ node (e.g., in-order predecessor) of a given node in a binary search tree where each node has a link to its parent.


To Find the inorder predecessor of node u:
If u has a left child, l, then pred(u) is the rightmost descendent of l
Otherwise, pred(u) is the closest ancestor, v, of u (if any) such that u is de-
scended from the right child of v.
If there is no such ancestor, then pred(u) is undefined.

The running time of TREE-SUCCESSOR on a tree of height his O(h), since we either follow a path up the tree or follow a path down the tree. The procedure TREE-PREDECESSOR, which is symmetric to TREE-SUCCESSOR, also runs in time O(h).

Taking the nodes one at a time and applying the rule:
node C: Does not have a left child. Closest ancestor such that node-C is de-
scended from the right child is node-A. Therefore, the predecessor of node-C
is node-A.
node A: Has a left child, node-B. Rightmost descendent of node-B is node-E.
node E: Has a left child, node-F. Rightmost descendent of node-F is node-G.
node G: Does not have a left child. Closest ancestor such that node-G is de-
scended from the right child is node-F.
node F: Does not have a left child. Closest ancestor such that node-F is de-
scended from the right child is node-B.
node B: Has a left child, node-D. Rightmost descendent of node-D is node-D
itself.
node D: Does not have a left child. There is no ancestor such that node-D is
descended from the right child. Therefore, the predecessor of node-D is
undefined.

BinaryTree: Inorder Successor

Write an algorithm to find the ‘next’ node (e.g., in-order successor) of a given node in a binary search tree where each node has a link to its parent.Inorder Successor

Approach:
To Find the inorder successor of node u:
If u has a right child, r, then succ(u) is the leftmost descendent of r

Otherwise, succ(u) is the closest ancestor, v, of u (if any) such that u is de-
scended from the left child of v. If there is no such ancestor, then succ(u) is
undefined.

The running time of TREE-SUCCESSOR on a tree of height his O(h), since we either follow a path up the tree or follow a path down the tree. The procedure TREE-PREDECESSOR, which is symmetric to TREE-SUCCESSOR, also runs in time O(h).

Taking the nodes one at a time and applying the rule:
node D: Does not have a right child. Its successor is the closest ancestor, v
such that node-D is descended from the left child of v. Node-D is descended
from the left child of node-B, so succ(D) is node-B.
node B: Has a right child (node-E), so successor is the leftmost descendent of
node-E, namely node-F.
node F: Has a right child (node-G), so successor is the leftmost descendent of
node-G, namely node-G itself.
node G: Does not have a right child. Its successor is the closest ancestor, v
such that node-G is descended from the left child of v. Node-G is descended
from the left child of node-E, so succ(G) is node-E.
node E: Does not have a right child. Its successor is the closest ancestor, v
such that node-E is descended from the left child of v. Node-E is descended
from the left child of node-A, so succ(E) is node-A.
node A: Has a right child (node-C), so successor is the leftmost descendent of
node-C, namely node-C itself.
node C: Does not have a right child. Its successor would be the closest ances-
tor, v such that node-C is descended from the left child of v. However,
there is no such ancestor, so succ(C) is undefined (node-C has no succes-
sor).

Code:

Binary Tree: level order linked list

Given a binary search tree, design an algorithm which creates a linked list of all the nodes at each depth (eg, if you have a tree with depth D, you’ll have D linked lists).

Approach:
We can do breadth first traversal of the tree keeping track of the levels, and create a linkedlist of all the nodes at any particular level

Input/Output:
iterative inorder:
3 7 9 15 17 21 25
printing level order:
15
7 21
3 9 17 25

Printing linked list at each level:
Level: 0
15
Level: 1
7 21
Level: 2
3 9 17 25

Binary Tree: Min Height

Given a sorted (increasing order) array, write an algorithm to create a binary tree with minimal height.

Approach:
We need to create a binary tree such that the number of nodes in left subtree and right subtree are equal if possible.

1. Pick the mid element of the array as the root of the binary tree.
2. The left part of the subarray goes into the left subtree.
3. The right part of the subarray goes into the right subtree.
4. Recurse.

Graphs: find path between 2 nodes.

Given a directed graph, design an algorithm to find out whether there is a route between two nodes.

Approach:
This problem can be solved by just simple graph traversal, such as depth first search or breadth first search. We start with one of the two nodes and, during traversal, check if the other node is found. We should mark any node found in the course of the algorithm as ‘already visited’ to avoid cycles and repetition of the nodes.

Binary Tree: Is Balanced or not.

Implement a function to check if a tree is balanced. For the purposes of this question, a balanced tree is defined to be a tree such that no two leaf nodes differ in distance from the root by more than one.

Approach:
The idea is: the difference of min depth and max depth should not exceed 1, since the difference of the min and the max depth is the maximum distance difference possible in the tree.

Input/Output:

Inorder:
3 7 9 15 17 19 21 25
is tree balanced: true
Inorder:
3 7 9 15 17 19 20 21 25
is tree balanced: false

Set of stacks

Imagine a (literal) stack of plates. If the stack gets too high, it might topple. Therefore, in real life, we would likely start a new stack when the previous stack exceeds some threshold. Implement a data structure SetOfStacks that mimics this. SetOfStacks should be composed of several stacks, and should create a new stack once the previous one exceeds capacity. SetOfStacks.push() and SetOfStacks.pop() should behave identically to a single stack (that is, pop() should return the same values as it would if there were just a single stack).
FOLLOW UP
Implement a function popAt(int index) which performs a pop operation on a specific sub-stack.

Approach:
In the first part of the question its evident that we need to maintain a list of stacks and as and when one stack exceeds its full capacity we need to switch to next stack.

What about the follow up question? This is a bit trickier to implement, but essentially we should imagine a “rollover” system. If we pop an element from stack 1, we need to remove the bottom of stack 2 and push it onto stack 1. We then need to rollover from stack 3 to stack 2, stack 4 to stack 3, etc.
We could make an argument that, rather than “rolling over,” we should be OK with some stacks not being at full capacity. This would improve the time complexity (by a fair amount, with a large number of elements), but it might get us into tricky situations later on if someone assumes that all stacks (other than the last) operate at full capacity.

Stack: Push Pop Min in O(1)

How would you design a stack which, in addition to push and pop, also has a function min which returns the minimum element? Push, pop and min should all operate in O(1) time.

Approach 1:

class Node {
Integer data;
Integer min;
}

push(4)
stack: (data:4|min:4) -> null;

push(1)
we compare top min ie 4 with value (1) and we have min so far as 1; Now our stack looks like:
stack: (data:1|min:1) -> (data:4|min:4) -> null;

push(5)
stack: (data:5|min:1) -> (data:1|min:1) -> (data:4|min:4) -> null;

Top give us 5
min gives: 1

With above approach we need additional space of size (n) where n is the size of the stack.

Approach 2:
1. We will have one normal stack S1 which supports usual operations push, pop, and peek.
2. Lets declate another stack called minStack where we will keep the min elements seen so far.

Lets trace now:
push(5)
S1: (5) -> null;
minStack: (5) -> null;

push(4)
S1: (4) -> (5) -> null;
minStack: (4) -> (5) -> null;

push(2)
S1: (2) -> (4) -> (5) -> null;
minStack: (2) -> (4) -> (5) -> null;

push(7)
S1: (7) -> (2) -> (4) -> (5) -> null;
// no change in min stack as 2 is still the min element so far.
minStack: (2) -> (4) -> (5) -> null;

push(9)
S1: (9) -> (7) -> (2) -> (4) -> (5) -> null;
// no change in min stack as 2 is still the min element so far.
minStack: (2) -> (4) -> (5) -> null;

element (2) from the minStack will only be popped out when it's popped from S1.

This approach also has additional space requirement and in worst case it will be of size (n) if all the data is unique and sorted in decreasing order.

Input/Output:

TOP: 9
null -> 4 -> 1 -> 5 -> 7 -> 9
TOP: 1
null -> 4 -> 1

Stacks: implement 2 stacks in an array.

Describe how you could use a single array to implement three stacks.

Approach 1:
Divide the array in three equal parts and allow the individual stack to grow in that limited space.
note: “[“ means inclusive, while “(“ means exclusive of the end point.
»»for stack 1, we will use [0, n/3)
»»for stack 2, we will use [n/3, 2n/3)
»»for stack 3, we will use [2n/3, n)
This solution is based on the assumption that we do not have any extra information about the usage of space by individual stacks and that we can’t either modify or use any extra space. With these constraints, we are left with no other choice but to divide equally.


Approach 2:
In this approach, any stack can grow as long as there is any free space in the array.
We sequentially allocate space to the stacks and we link new blocks to the previous block. This means any new element in a stack keeps a pointer to the previous top element of that particular stack.
In this implementation, we face a problem of unused space. For example, if a stack deletes some of its elements, the deleted elements may not necessarily appear at the end of the array. So, in that case, we would not be able to use those newly freed spaces.
To overcome this deficiency, we can maintain a free list and the whole array space would be given initially to the free list. For every insertion, we would delete an entry from the free list. In case of deletion, we would simply add the index of the free cell to the free list.
In this implementation we would be able to have flexibility in terms of variable space utilization but we would need to increase the space complexity.

Singly Linked List: loop start detection

Given a circular linked list, implement an algorithm which returns node at the beginning of the loop.
DEFINITION
Circular linked list: A (corrupt) linked list in which a node’s next pointer points to an earlier node, so as to make a loop in the linked list.
EXAMPLE
Input: A -> B -> C -> D -> E -> C [the same C as earlier]
Output: C

Approach:
If we move two pointers, one with speed "v" and another with speed "2v", they will end up meeting if the linked list has a loop. Why? Think about two cars driving on a track—the faster car will always pass the slower one!

The tricky part here is finding the start of the loop. Imagine, as an analogy, two people racing around a track, one running twice as fast as the other. If they start off at the same place, when will they next meet? They will next meet at the start of the next lap.

Now, let’s suppose Fast Runner had a head start of k meters on an n step lap. When will they next meet? They will meet k meters before the start of the next lap. (Why? Fast Runner would have made k + 2(n - k) steps, including its head start, and Slow Runner would have made n - k steps. Both will be k steps before the start of the loop.)


For the slow ptr we have:
n = v * t
for fast ptr we have
k+x = 2*v * t

now if we solve for x we have
(k+x)/2 = n
x = 2*n - k

So if fast pointer has a head start of k meters on an n step lap then both will meet k meters before the start of the next lap.

Now, going back to the problem, when Fast Runner (n2) and Slow Runner (n1) are moving around our circular linked list, n2 will have a head start on the loop when n1 enters. Specifically, it will have a head start of k, where k is the number of nodes before the loop. Since n2 has a head start of k nodes, n1 and n2 will meet k nodes before the start of the loop.

So, we now know the following:
1. Head is k nodes from LoopStart (by definition).
2. MeetingPoint for n1 and n2 is k nodes from LoopStart (as shown above).
Thus, if we move n1 back to Head and keep n2 at MeetingPoint, and move them both at the same pace, they will meet at LoopStart.

Adding 2 Singly linked lists

You have two numbers represented by a linked list, where each node contains a single digit. The digits are stored in reverse order, such that the 1’s digit is at the head of the list. Write a function that adds the two numbers and returns the sum as a linked list.
EXAMPLE
Input: (3 -> 1 -> 5), (5 -> 9 -> 2)
Output: 8 -> 0 -> 8

Approach:
We can implement this recursively by adding node by node, just as we would digit by digit.
1. result.data = (node1 + node2 + any earlier carry) % 10
2. if node1 + node2 > 10, then carry a 1 to the next addition.
3. add the tails of the two nodes, passing along the carry.


Input/Output:
A = 8 -> 7 -> 1 -> 1 -> null
B = 6 -> 3 -> 4 -> null
Adding the above linked lists:
Result: 4 -> 1 -> 6 -> 1 -> null

Singly LinkedList: Delete Node

Implement an algorithm to delete a node in the middle of a single linked list, given only access to that node.
EXAMPLE
Input: the node ‘c’ from the linked list a->b->c->d->e
Result: nothing is returned, but the new linked list looks like a->b->d->e


Approach:
Lets say the list is a->b->c->d->e
We have point p1 pointing to "c" node.
Get a pointer p2 to point to the next node of p1 ie to node "d" here.
Now copy "d" node data to node pointed by p1 and delete node pointed by p2.
new list is "a->b->d->e";

NOTE: this problem can not be solved if pointer p1 is pointing to the last node of the singly linked list.

Singly Linked List: Nth Node from end

Implement an algorithm to find the nth to last element of a singly linked list.

Approach:
lets assume n = 3;
declare 2 ptrs, prev and current which point to the head of the linked list.
advance current by n (3) positions.
then advance both prev and current pointers one at a time till current becomes null.
At this point prev is the nth node from end of the linked list.

Input/Output:
51 -> 70 -> 74 -> 32 -> 10 -> 90 -> 18 -> 21 -> 30 -> null
3 node from end: 18
7 node from end: 74
9 node from end: 51
10 node from end is null

19 -> 16 -> 15 -> null
3 node from end: 19
7 node from end is null
9 node from end is null
10 node from end is null

Time complexity: O(n) - where n is the size of the singly linked list.

Remove duplicates from singly link list.

Write code to remove duplicates from an unsorted linked list.

Approach:
Create a hashtable.
Iterate through the list and check the node if its already present in the hashtable, if present then delete it from the list.
If not then add it to the hashtable and move ahead in the list.


Input/Output:
Original linked list:
2 -> 3 -> 2 -> 5 -> 2 -> 8 -> 2 -> 3 -> 8 -> null
After deleting duplicate node:
2 -> 3 -> 5 -> 8 -> null

Time complexity: O(n) -> n is the length of the linked list.
Space complexity: O(n) -> size of the hashtable.

Is Rotation

Assume you have a method isSubstring which checks if one word is a substring of another. Given two strings, s1 and s2, write code to check if s2 is a rotation of s1 using only one call to isSubstring (i.e., “waterbottle” is a rotation of “erbottlewat”).



Approach:
Let S1 = "waterbottle";
S2 = "erbott";

concatanate S1 with itself
So we have S3 = S1 + S1 = "waterbottle" + "waterbottle" ;
S3 = "waterbottlewaterbottle";

Now we need to check if the S2 is a substring of S1.

if (s2.isSubstring(s3)) then return true;
else return false;

Set matrix rows and cols to zero

Write an algorithm such that if an element in an MxN matrix is 0, its entire row and column is set to 0.

Approach:

1. Iterate through the matrix, and where ever we encounter 0, remember the row and col in separate arrays.
2. Do the second iteration through the matrix for the rows and cols stored above and mark them zero.

Sample Input/Output:
printing original matrix..
1 2 0 
4 5 6 
0 8 9 
After removing zero rows and cols: 
0 0 0 
0 5 0 
0 0 0 
printing original matrix..
4 5 6 
7 0 8 
9 1 2 
After removing zero rows and cols: 
4 0 6 
0 0 0 
9 0 2 

Replace Spaces

Write a method to replace all spaces in a string with ‘%20’.

Sample Input/Output:


String: this is a nice world!
replaced space with %20: this%20is%20a%20nice%20world!

Is Anagram

Write a method to decide if two strings are anagrams or not.

Sample Input/Output:

first String: tea
second String: eat
Is Anagram: true

first String: teas
second String: seat
Is Anagram: true

first String: peas
second String: peat
Is Anagram: false

Remove Duplicate Characters from String

Design an algorithm and write code to remove the duplicate characters in a string without using any additional buffer.

Sample Input/Output:

String: programming

after removing duplicate chars: progamin

String: words

after removing duplicate chars: words

String: texts

after removing duplicate chars: texs

String: a

after removing duplicate chars: a

String: aa

after removing duplicate chars: a

String: ba

after removing duplicate chars: ba

Unique Characters in a String

Implement an algorithm to determine if a string has all unique characters. What if you can not use additional data structures?

SAMPLE Input/Output:

String: abcb
Has Unique chars: false
String: want
Has Unique chars: true
String: calls
Has Unique chars: false
String: x
Has Unique chars: true
String: 
Has Unique chars: true
String: aa
Has Unique chars: false
String: mn
Has Unique chars: true

Smallest positive number.

You are given an unsorted array with both positive and negative elements. You have to find the smallest positive number missing from the array in O(n) time using constant extra space.
Eg: 
Input = {2, 3, 7, 6, 8, -1, -10, 15}
Output = 1


Input = { 2, 3, -7, 6, 8, 1, -10, 15 }
Output = 4


Approach:
Put all the numbers from array in the hashmap, and then starting from 1, check all the natural numbers in the map, the first number not there is the answer.

Least natural number.

Given a set of natural numbers N = {1,2,3,4,5 ... infinity}
And another array A with random numbers, now find the least natural number which is not present in array A.


Example:
A = {9, 8, 5, 1, 15}
here least natural number which is not present in A is 2.


Example2:
A = {5, 7, 2, 1, 4}
here least natural number which is not present in A is 3.




Approach:
1. Take a bit vector propertional to the size of array A.
if we consider the first example then our bit vector would be of size 5.
A = {9, 8, 5, 1, 15}
initially bit vector would be like:
0 0 0 0 0 
2. Go through elements in array A and set the corresponding bit vector.
A[0] = 9
since bit vector size is 5, we cant set 9th bit vector so we ignore 9.
A[1] = 8
since 8 > bit_vector_size(5), we ignore it.
A[2] = 5
we set 5th bit vector.
0 0 0 0 1
A[3] = 1
we set the 1st bit vector
1 0 0 0 1
A[4] = 15
15 > bit_vector_size(5), we ignore it.


Now our bit vector looks like:
1 0 0 0 1


And our answer is the first unset bit vector, that is 2.


time complexity: O(n) where is n is the size of array A.
space complexity: O(n) where n is the size of the array A.

Design Pattern: Observer pattern.

Head First - Design Patterns: chapter 02 notes:


The Observer Pattern defines a one-to-many dependency between objects so that when one object changes state, all of its dependents are notified and updated automatically.


Design Principle
Strive for loosely coupled designs between objects that interact.


Loosely coupled designs allow us to build flexible OO systems that can handle change because they minimize the interdependency between objects.

Design Pattern: Strategy pattern.

Head First - Design Patterns: chapter 01 notes:

Design Principle
Identify the aspects of your application that vary and separate them from what stays the same.


Take what varies and “encapsulate” it so it won’t affect the rest of your code.
The result? Fewer unintended consequences from code changes and more flexibility in your systems!


Design Principle
Program to an interface, not an implementation.
“Program to an interface” really means “Program to a supertype.”


Design Principle
Favor composition over inheritance


The Strategy Pattern defines a family of algorithms, encapsulates each one, and makes them interchangeable. Strategy lets the algorithm vary independently from clients that use it.

Construct binary tree from inorder and preorder.

In Binary tree .. from the in-order traversal and pre-order travrsal .. construct the tree.


Input:
int [] inorder = {5, 9, 7, 8, 2, 10, 3};
int [] preorder = {8, 9, 5, 7, 10, 2, 3};


output:
printing inorder of the built binary tree: 
5 9 7 8 2 10 3 


Approach:
1. First data of preorder Array is 8, so it would be root of the binary tree.
2. All the elements in inorder array before 8 would be the left subtree and all the elements to the right of 8 in inorder array would be right subtree.
3. develope the recursion based on 1. and 2.

Longest Arithmetic Progression

Given an array of integers A, give an algorithm to find the longest Arithmetic progression in it, i.e find a sequence i1 < i2 < … < ik, such that 
A[i1], A[i2], …, A[ik] forms an arithmetic progression, and k is the largest possible. 
The sequence S1, S2, …, Sk is called an arithmetic progression if 
Sj+1 – Sj is a constant


{2,3,5,7,8,11}


DP solution with O(n^3). 
Assume, we've optimum solution for array a[0,1,2,....,k]. To get solution for index = k+1, we can put a[k+1] next in a sequence ending with a[j] for 0 <= j <= k. 
So, if diff = a[k+1] - a[j], we need to look up sub-problem solution for index = j to search for diff, and taking the max value to get a maximum sequence.


code input/output:
{2,3,5,7,8,11};
max seq: 2, 5, 8, 11
DP array values:

0 0 0 0 0 0 
1 0 0 0 0 0 
1 1 0 0 0 0 
1 1 2 0 0 0 
1 1 2 1 0 0 
1 1 1 2 3 0 

Valid phrases from text.

You have given a dictionary and a string, you need to separate words that are in dictionary.
ex - catsanddog (here cat and cats both can be in dictionary)
output - cats and dog


Approach:
1. Lets say the length of the string is n and init phrase String as empty.
2. Now for every substring S[i,j] (0<=i<=j<n), check if its a valid word - check against the dictionary.
3. If we get a valid word then append it to the previously calculated and running phrase with a space.


Code input/output:
Input String: catsanddog
valid phrases:
[cats and dog]

Lowest positive number.

Given an array of integers (positive or negative) find the lowest positive integer NOT present in that array.


example array A = {-2, 3, 7, 9, -4, 6, 1, 2, -5}


get the count of the positive numbers, in the above example its 6
create a bit vector of size 6, then traverse the array from left to right and toggle the bit for the number which is <= 6 in the array.
[0] [0] [0] [0] [0] [0]


first positive number 3,
[0] [0] [1] [0] [0] [0]


second positive number 7 (which is greater than the size of the array (6) so we do nothing)
[0] [0] [1] [0] [0] [0]


third +ve number is 9 and as above we do nothing.
[0] [0] [1] [0] [0] [0]


fourth is 6 so we set 6th bit to 1.
[0] [0] [1] [0] [0] [1]


then its 1 and 2 so we set 1st and 2nd bit to 1.
[1] [1] [1] [0] [0] [1]


so the lowest +ve number in the array is the first bit with 0 value which is 4.

Find top k from given array.

You are given an array A of k values which contain int values in sorted (asec) order. Find top k values (asec) which can either be the number from the array A, or sum of any two numbers from A or sum of any three numbers from A. So, if A's values are represented as : a1,a2,...,ak , the possible numbers can be: a(i), a(i)+a(j), a(i)+a(j)+a(l) for any i,j,l < k


Ex: A[7] = {3,4,5,15,19,20,25}
output B[7] = {3,4,5,(3+4),(3+5),(4+5),(3+4+5)}


create a min-heap out of array A,
now get the root, ie 3, and do min-heapify.
after that again get the root ie 4, add it to the rest of the elements seen so far and push back on min-heap.
so in output we have 3, 4
heap we have 5, 7, 15, 19, 20, 25
get the root, add it to each element of the outpu array and push the result back on heap.
also take 2 elements at a time from the array and add it to 5 and push back the result on min-heap and heapify.
output we have now, 3, 4, 5
pushing on heap - (3+5), (4+5) (3+4+5)
heap is now: 7, 8, 9, 12, 15, 19, 20, 25


again get the root and do the above steps,


finally we will have the output array as:
3, 4, 5, 7, 8, 9, 12


Total time complexity: 
klogk + k^2

Ugly Numbers

Ugly numbers are numbers whose only prime factors are 2, 3 or 5. The sequence
1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, …
shows the first 11 ugly numbers. By convention, 1 is included.
Write a program to find and print the 150'th ugly number.




Approach:
Start with num=1
now multiple 1 with 2, 3 and 5 and store the results in min heap if the result is not already there.
now remove the root of the min-heap and output it then multiply the removed root with 2, 3 and 5 and store the result in min-heap if not already present.
repeat it n number of times, in the above case 150 times.


Code output:

ugly numbers are: 
1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36 40 45 48 50 54 60 64 72 75 80 81 90 96 100 108 120 125 128 135 144 150 160 162 180 192 200 216 225 240 243 250 256 270 288 300 320 324 360 375 384 400 405 432 450 480 486 500 512 540 576 600 625 640 648 675 720 729 750 768 800 810 864 900 960 972 1000 1024 1080 1125 1152 1200 1215 1250 1280 1296 1350 1440 1458 1500 1536 1600 1620 1728 1800 1875 1920 1944 2000 2025 2048 2160 2187 2250 2304 2400 2430 2500 2560 2592 2700 2880 2916 3000 3072 3125 3200 3240 3375 3456 3600 3645 3750 3840 3888 4000 4050 4096 4320 4374 4500 4608 4800 4860 5000 5120 5184 5400 5625 5760 5832 

Roman to Decimal Conversion

Code input/output:

Roman: XCIV Decimal: 94
Roman: XXXVI Decimal: 36
Roman: XXXIV Decimal: 34
Roman: LIX Decimal: 59

String A contains a substring which is anagram of String B ?

you are given two arrays. A of size n, B of size m. m is a very very small number compared to n. find out if A contains a substring which is anagram of B.


Approach1:
1. Sort B
2. maintain a window of length m and slide it along A
3. for each window do:
3.1 Sort the window O(mlogm)
3.2 Compare the sorted window with sorted B
3.3 If equal anagram found


T(n) = O(n*mlogm) but since m<<n T(n)~O(n)




Approach 2:
A = "dropoffprogrammingisgoodforhealth"
B = "ford"


find all the indices of characters in B string in A.
f = 5,6,24
o = 2,4,9,21,22,25
r = 1,8,11,26
d = 0,23


now find the indices for "f", "o", "r" and "d" such that they are consecutive.


In the above example we have 23, 24, 25, 26 - hence A contains a substring which is anagram of B.


If we can not find consecutive indices for all the characters in B, then A does not contain substring which is anagram of B.


What if B contains duplicate characters ? ie what if B = "fordo" in the above example ?


time complexity for above solution = O(n)

Maximum submatrix

a) There is a square of nxn size which is comprised of n-square 1x1 squares. Some of these 1x1 squares are colored. Find the biggest subsquare which is not colored.

b) Also asked to extend it to find the biggest area rectangle.

OR

Given a binary matrix, find out the maximum size square sub-matrix with all 1s.

For example, consider the below binary matrix.

   0  1  1  0  1
   1  1  0  1  0
   0  1  1  1  0
   1  1  1  1  1
   1  1  1  1  1
   0  0  0  0  0
The maximum square sub-matrix with all set bits is

    1  1  1
    1  1  1
    1  1  1

Approach:
Let the given binary matrix be M[R][C]. The idea of the algorithm is to construct an auxiliary size matrix S[][] in which each entry S[i][j] represents size of the square sub-matrix with all 1s including M[i][j] and M[i][j] is the rightmost and bottommost entry in sub-matrix.

1) Construct a sum matrix S[R][C] for the given M[R][C].
     a) Copy first row and first columns as it is from M[][] to S[][]
     b) For other entries, use following expressions to construct S[][]
         If M[i][j] is 1 then
            S[i][j] = min(S[i][j-1], S[i-1][j], S[i-1][j-1]) + 1
         Else /*If M[i][j] is 0*/
            S[i][j] = 0
2) Find the maximum entry in S[R][C]
3) Using the value and coordinates of maximum entry in S[i], print
   sub-matrix of M[][]
For the given M[R][C] in above example, constructed S[R][C] would be:

   0  1  1  0  1
   1  1  0  1  0
   0  1  1  1  0
   1  1  2  2  1
   1  2  2  3  2
   0  0  0  0  0
The value of maximum entry in above matrix is 3 and coordinates of the entry are (4, 3). Using the maximum value and its coordinates, we can find out the required sub-matrix.

To find the biggest rectangle:
R0   0  1  1  0  1
R1   1  1  0  1  0
R2   0  1  1  1  1
R3   1  1  1  1  1
R4   1  1  1  1  1
R5   0  0  0  0  0

Rij denote Ri & Rj
R01 = 0 1 0 0 0 (max area of rect so far: 1*2 = 2)
R12 = 0 1 0 1 0 (max area of rect so far: 1*2 = 2)
R23 = 0 1 1 1 1 (max area of rect so far: 4*2 = 8)
R34 = 1 1 1 1 1 (max area of rect so far: 5*2 = 10)
R45 = 0 0 0 0 0  (max area of rect so far: 10)

Again lets do the same & operation between consecutive rows above.

R02 = 0 1 0 0 0 (local area: 1*3=3, max so far: 10)
R13 = 0 1 0 1 0 (local area: 1*3=3, max so far: 10)
R24 = 0 1 1 1 1 (local area: 4*3=12, new max so far: 12)
R35 = 0 0 0 0 0 (local area: 0*0=0, new max so far: 12)

R03 = 0 1 0 0 0 (max so far: 12)
R14 = 0 1 0 1 0 (max so far: 12)
R25 = 0 0 0 0 0 (max so far: 12)

again repeat
R04 = 0 1 0 0 0 (max so far: 12)
R15 = 0 0 0 0 0 (max so far: 12)

finally,
R05 = 0 0 0 0 0

And max area of rectangle so far = 12.