Remove Pattern String from Text String.

Given string input1, input2, remove wherever the occurrence of input2 in input1.
e.g: 
input1: skjthshetheshetesm
input2: she
input1 will become "skjththetesm" 


Code output:

Text: skjthshetheshetesm
Pattern: she
After removing pattern from text: skjththetesm
Text: abababa
Pattern: aba
After removing pattern from text: b

Graph to Tree Conversion and Diameter of a BinaryTree.

Given an acyclic undirected unweighted connected graph, find its representation as a tree with the least height. Brute force is O(n^2). Come up with an O(n) solution.


Approach:

1. All the edges are of weight "1" in the above graph. 
2. Pick a random Node in the above Graph, Say we pick "C", now do BFS and calculate the farthest Node from C.
2. The Farthest Node from "C" would come to be "F" and "G" - Both of them "3" units away.
3. Lets Pick one of the Nodes from "F" & "G" above, say "F".
4. Now do BFS starting from "F" and calculate the farthest node from "F" - here we are calculating the "Diameter of the Graph".
5. After we are done with BFS above, the farthest Node from  "F" would come out to be Node "B", which would be 4 units aways. - "4" is the diameter of the graph, lets call it D.
6. Now calculate d = D/2 = 4/2 = 2.
7. Find the nodes which are d (2 units) distance away from F along the route of F => B. Here we get Node "D" as the candidate which satisfies our criteria.
8.  Now "D" is the root of the tree that we set out to create, do a BFS starting from D, nodes 1 unit away are its first level children and so on..


Finally, the tree would look like:

Terminologies:
Diameter of the Graph: maximum distance between any two vertices, here the distance is the length of the shortest walk; therefore, the diameter is the longest of the shortest walks.

Diameter of a Tree

The diameter of a tree (sometimes called the width) is the number of nodes on the longest path between two leaves in the tree. The diagram below shows two trees each with diameter nine, the leaves that form the ends of a longest path are shaded (note that there is more than one path in each tree of length nine, but no path longer than nine nodes).

The diameter of a tree T is the largest of the following quantities:

* the diameter of T’s left subtree
* the diameter of T’s right subtree
* the longest path between leaves that goes through the root of T (this can be computed from the heights of the subtrees of T)

Code output:

Building binary tree with following random values:
30 38 4 32 14 9 42 2 85 6 
Inorder traversal of the binary tree:
2 4 6 9 14 30 32 38 42 85 
Diameter of BinaryTree: 8

Bloom Filter

From Wikipedia:


A Bloom filter, conceived by Burton Howard Bloom in 1970,is a space-efficient probabilistic data structure that is used to test whether an element is a member of a set. False positives are possible, but false negatives are not; i.e. a query returns either "inside set (may be wrong)" or "definitely not in set". Elements can be added to the set, but not removed (though this can be addressed with a counting filter). The more elements that are added to the set, the larger the probability of false positives.


An empty Bloom filter is a bit array of m bits, all set to 0. There must also be k different hash functions defined, each of which maps or hashes some set element to one of the m array positions with a uniform random distribution.


To add an element, feed it to each of the k hash functions to get k array positions. Set the bits at all these positions to 1


To query for an element (test whether it is in the set), feed it to each of the k hash functions to get k array positions. If any of the bits at these positions are 0, the element is definitely not in the set – if it were, then all the bits would have been set to 1 when it was inserted. If all are 1, then either the element is in the set, or the bits have by chance been set to 1 during the insertion of other elements, resulting in a false positive. In a simple bloom filter, there is no way to distinguish between the two cases, but more advanced techniques can address this problem.


read more on..
http://en.wikipedia.org/wiki/Bloom_filter


Code output:

"apple" is present in bloomfilter? true
"apples" is present in bloomfilter? false
"banana" is present in bloomfilter? true
"grapes" is present in bloomfilter? true
"grape" is present in bloomfilter? false

Search by first name, last name or both.

Create a structure that will allow you to search a person by first name or last name (or both), in better than O(N) timeframe.


Approach:
Suppose the names are:
String [] names = {
"A B",
"A C",
"A D",
"A Y",
"A Z",
"A X",
"X I",
"X Y",
"X Z",
"X B",
"X C",
"X D",
"I J",
"I L",
"I K",
"Z I"
};


Approach:
1. Create 2 HashMaps, one FMap as Map<firstName, List of FullNames> and another LMap as Map<lastName, list of FullNames>.
2. Now you can search firstname in the FMap or lastName in LMap.
3. If you want to search with fullname then split full name say "F L" into first and last name ie "F" and "L", then search F in FMap
and "L" into LMap and then take the cross of FMap and LMap results.
4. In FMap or LMap, instead of using list to store fullnames, we can use better datastructures like BST or another HashMap which gives better read complexity.


Code output:

Searching with full name ...
[A X]
Searching with first or last name ...
[X I, X Y, X Z, X B, X C, X D, A X]
Searching with first or last name ...
[I J, I L, I K, X I, Z I]

Partition an array into 2 parts with equal average.

How do you partition an array into 2 parts such that the two parts have equal average? Each partition may contain elements that are non-contiguous in the array.


We need to solve the problem of finding all possible sum for a subset of size k (for 1<=k<=n/2), where n is total number of items.


Let S1 = sum of partition 1
n1 = # of items in partition 1
S2 = sum of partition 2
n2 = # of items in partition 2
S = S1+S2
n = n1+n2
Since, S1/n1 = S2/n2, it implies S1/n1 = S2/n2, which in turn implies (S1+S2)/(n1+n2) = S/n


Now, we populate a table of size (N/2) x N x S, where each entry T[k][i][j] is 1 if we there exists some subset of size k using the set of elements {1,2,...,i} that sum to j. During the computation of this table entries, if we ever found that j/k = S/n, there exists a way to make a partition with equal average. T[k][i][j] can be generated as a recurrence like :


T[k][i][j] = T[k-1][i-1][j-item_i] || T[k][i-1][j] ;


Time complexity: O(N^2*S), 
Space complexity: O(N*S).


Input Array:
int [] A = {2, 4, 4, 5, 6, 6, 7, 8, 9, 12};
Code Output:

Partition 1: 6 1
Partition 1: 57 9

Find Index of a key

A function GetWordFromList takes an integer parameter and returns the word at the corresponding index. Now you are given a word,say "string", how do you optimally get the index of the word where it occurs. You don't know the data structure used to store the words.Assume that all the words in list/database are sorted.Also assume that the function returns null or some exception if the index which is given as input is out of bound.


Approach:
1. Suppose the list is an array (just of argument sake).
2. Let the array be 
String [] A = { "apple",
"boy",
"chair",
"dear",
"dog",
"eating",
"feature",
"great",
"heat",
"hunter",
"intelligent",
"jealous",
"joker",
"kites",
"least",
"light",
"meaning",
"money",
"name",
"neat",
"operation",
"peace",
"polite",
"quite",
"relentless",
"string",
"temperature",
"tools"
"universe",
"volvo",
"wax",
"xeon",
"year",
"zebra"
 }
Length of the array is 34.
3. Now lets start searching from 0th index and let first and lsst be variables init to 1.
4. keep doubling "last" and setting first to last, till our search key falls in the "first" and "last" range.
5. So if we try to trace "money" position in array A, we will have following values for first and last.
first = 1, last = 1;
first = 1, last = 2;
first = 2, last = 4;
first = 4, last = 8;
first = 8, last = 16;
first = 16, last = 32; -> "money" occurs in this range.


Now we we will do binary search in the range of A[16] and A[32] to locate the string "money".


Time complexity - O(logn) to find the range + O(logk) - (assuming k is the length of the range where the search key occurs).


Code output:
Length of Array: 34
Index of "money": 17
Index of "zebra": 33
Index of "boy": 1
Index of "volvo": 29
Index of "baby": -1

Algorithm to find top 10 search items.

How do you go about finding the top 10 google searches at the end of a day? In case you are storing the information about them, how and where would you store it? (like disks etc)


link: algorithm-to-find-top-10-search-terms


relevant paper: Approximate-frequency-counts-over-datastreams

Find triplet such that (a+b+c) is closest to 0

Find triplet <a,b,c> such that (a+b+c) is closest to 0.


Code output:


Array values are: 
-12 -7 -4 2 3 5 9 10 15 16 
We found a triplet that sums to zero!!
Triplet is: 
-12, -4, 16


Array values are: 
-29 -9 -4 2 3 9 10 15 16 49 
Triplet whose sum is closest to zero by: 1
Triplet is: 
-4, 2, 3


Approach:
1. For every A[i], have 2 pointers in the array say j at the A[i+1] and k at A[n-1] and a min variable which will store how far the (a+b+c) sum is from zero.
2. Check the expression (A[i]+A[j]+A[k] == 0), if false then do ++j or --k depending on (A[i] < A[j]+A[k]) or (A[i] > A[j]+A[k]).
Also check if (A[i]+A[j]+A[k]) < min, if yes then replace the min value with (A[i]+A[j]+A[k]).
3. If true, we have found an exact match for triplet that sums to zero, break the loop.
4. At (2) and (3) points we store the triplet in fa, fb, fc - ie final a, final b and final c.


total time complexity: O(n^2)

Find all triplets in an array such that "a - b = c".

Given a sorted array, output all triplets <a,b,c> such that a-b = c. Expected time is O(n^2). 


Input Array:
-12, -7, -4, 0, 3, 5, 9, 10, 15, 16


Code Output:
-12 -7 -4 0 3 5 9 10 15 16 
Number of triplets for "a-b=c":6
-7 -12 5 
-4 -7 3 
3 -12 15 
3 -7 10 
5 -4 9 
9 -7 16 


Approach:
1. For every A[i], have 2 pointers in the array say j at the A[0] and k at A[n-1].
2. Check the expression (A[i] == A[j]+A[k]), if false then do ++j or --k depending on (A[i] < A[j]+A[k]) or (A[i] > A[j]+A[k]).
3. When you are moving the pointers just make sure that (j != i) and (k != i).
4. Store the triplets in the hashMap and in the end print those triplets.

Put Spaces in a String.

Let's say you have a phrase without any spaces - eg. "thisisawesome". Given a dictionary, how would you add spaces in this string?


OR


When people search at Google, they often type two words without space. For example, instead of typing "binary tree", someone can type "binarytree". Given an input, what is a good way of finding if it is a combination of two valid words?


Input:
thisisaninterestingsentence
Output:
this is an interesting sentence


Approach for the phrase problem:
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.


Approach for the "two words wothout the space" problem.
1. Split the given string S[0..n] at the i (0<=i<n) positions. - For every split at ith index you will get 2 substrings S[left] and S[right]
2. Check if S[left] and S[right] are valid words.

Find triplets that sum to zero in an array.

Print triplets that sum to 0 in an integers array.


Approach:
1. Sort the Array say A[].
2. Keep three pointers i, j, and k. 0<=i<n-2, j=i+1 and k=n-1
3. Now for every i, check if (A[i] + A[j] + A[k]) == 0, if so we have our triplet otherwise do ++j or --k depending on whether (A[i] + A[j] + A[k]) is less than zero or greater than zero.


Time complexity: O(n^2).


Example:
int [] A = {1, 2, -5, 4, -2, 3, -19, 10, 5, 8, -25, 19, 6, 20, -10, -7, -3};


Output:
-25 -19 -10 -7 -5 -3 -2 1 2 3 4 5 6 8 10 19 20 
Number of triplets that sum to zero:13
-25 5 20 
-25 6 19 
-10 2 8 
-10 4 6 
-7 -3 10 
-7 1 6 
-7 2 5 
-7 3 4 
-5 -3 8 
-5 1 4 
-5 2 3 
-3 -2 5 
-3 1 2 

Matching cap and pens problem.

Given N pens and n caps . Sort them. you cant compare pens with other pens and caps with other caps. - Originally known as Matching Nuts and Bolts problem.


Approach:
Pens = {P3, P2, P1, P5, P4}
Caps = {C4, C1, C5, C2, C3}


We are going to use a modified version of quick sort to solve this.


Choose one of the pens as pivot say P3, find the cap for P3.


Now compare every pen with C3 (cap for P3) and divide the pen around pivot P3, 
Similarly compare every cap with P3 and divide the caps around the pivot C3, 
We now have the arrays as:
Pens = {P2, P1} +  P3 + {P5, P4} - P3 is now at its correct position if Pens array would have been sorted.
Caps = {C1, C2} +  C3 + {C4, C5} - C3 is now at its correct position if Caps array would have been sorted.


Now run the above steps recursively of the left and right subproblems.


Time complexity: T(n) = T(k) + T(n-k) + O(n)
= O(n^2)
Average case: O(nlogn) - we can use the randomized pivots to achieve O(nlogn) as expected time (averaged over all choices of pivots).


Space complexity: Quick sort is an inplace algorithm so space complexity - O(1)

Ways to choose k non-consecutive integers from n consecutive integers.

let f(n, k) be the # of ways of choosing k integers without replacement from
n consecutive integers so that no two selected are consecutive.
a. give a recurrence for f(n, k)
b. efficient implementation of f(n, k)


Recurrence:
f(n,0) = 0;
f(n,1) = n;
f(n,n) = 1;
f(n,k) = f(n-1, k) + f(n-2, k-1);


OR
f(n,k) = f(n-2, k-1) + f(n-3, k-1) ... f(2(k-1)-1, k-1);


Sample output(s):
n=4, k=2;
n: 4
k: 2
result: 3


n=5, k=3;
n: 5
k: 3
result: 1

find least common multiple of 2 numbers.

Given two numbers m and n, write a method to return the first number r that is
divisible by both (e.g., the least common multiple).


LCM (a, b) = (a x b) / GCD(a, b)


Code input:
a=12, b=18
code output:
LCM is: 36

Random Number Generator

Given a list, L, of size k. L contains elements between 1 and n. Also given a function RND() such that this function returns a number between 1 and INT_MAX.
Now generate number between 1 and n, using RND(), such that the element should not be there in the list L. All elements should have a uniform probability.
OR

k distinct integers [0, N)
Select a random no [0,N) which is not in this k distinct list.


Example:
[4, 6, 9]
Choose a random no between 0 - 9 which is not 4, or 6, or 9.


Valid output: 2
Invalid output: 6



Approach:
N = 10;
L = {1,2,3,4,5}
K = L.length;
Generate random number R = RND()%(N-K) + 1;
Let R = 2;
now iterate through L and for every number greater or equal than 2, increase R by 1,
2,3,4,5 are greater than or equal to 2. 
L[1] >= R(2) = ++R = 3
L[2] >= R(3) = ++R = 4
L[3] >= R(4) = ++R = 5
L[4] >= R(5) = ++R = 6
So now we have final random number R = 6;

Lets  see another example:



K = [2, 3, 6, 9, 12, 17, 20, 21]
N = 30
r = rand (22) = 16



Available: [1, 4, 5, 7, 8, 10, 11, 13, 14, 15, 16, 18, 19, 22, 23, 24, 24, 26, 27, 28, 29, 30]
So r = 24 in this case. 


It is important that k be in increasing order for this method to work. If you take a second look at the method, you will see that it isn't just incrementing r for each below it in k, it is incrementing based on its previous incrementend value.
So for the above situation, the iterations will be: 


k[0] -> 16 > 2, so r = 17
k[1] -> 17 > 3, so r = 18
k[3] -> 18 > 6, so r = 19
k[4] -> 19 > 9, so r = 20
k[5] -> 20 > 12, so r = 21
k[6] -> 21 > 17, so r = 22
k[7] -> 22 > 20, so r = 23
k[8] -> 23 > 21, so r = 24


So finally here we have r=24 as the answer.

Petrol Bunk in a Circle.

You have a circular track containing fuel pits at irregular intervals. The total amount of fuel available from all the pits together is just sufficient to travel round the track and finish where you started. Given the the circuit perimeter, list of each fuel pit location and the amount of fuel they contain, find the optimal start point on the track such that you never run out of fuel and complete circuit.


There are n petrol bunks arranged in circle. Each bunk is separated from the rest by a certain distance. You choose some mode of travel which needs 1litre of petrol to cover 1km distance. You can't infinitely draw any amount of petrol from each bunk as each bunk has some limited petrol only. But you know that the sum of litres of petrol in all the bunks is equal to the distance to be covered.
ie let P1, P2, ... Pn be n bunks arranged circularly. d1 is distance between p1 and p2, d2 is distance between p2 and p3. dn is distance between pn and p1.Now find out the bunk from where the travel can be started such that your mode of travel never runs out of fuel.


Approach:
Let D be the distance array.
Let P be the petrol array.
int [] D =  {4, 7, 4, 8, 4, 1};
int [] P =  {3, 5, 3, 8, 3, 6};


Now start with i=0;
D[0] = 4 > P[0] = 3; i=0 can not be starting point so we move to i=1;
D[1] = 7 > P[1] = 5; i=1 can not be starting point So we move to i=2;
D[2] = 4 > P[2] = 3; i=2 can not be starting pointso we move to i=3;
D[3] = 8 <= P[3] = 8; i=3 can be starting point, now keep on summing the D[i] and P[i] and P[i] >= D[i]
D[4] = 4 > P[4] = 3; here the P[i] is not greater or equal to D[i] so we break; and start from next i=5;


D[5]=1 < P[5] = 6; and carry over petrol is 5
now,
D[0] = 4 < P[0] + carry = 3 + 5;
D[1] = 7 < P[1] + carry = 5 + 4;
D[2] = 4 < P[2] + carry = 3 + 2;
D[3] = 8 < P[3] + carry = 8 + 1;
D[4] = 4 <= P[4] + carry = 3 + 1; // now next i = 5 is the same as the starting point ie index 5.
So the starting point is index=5;


Total time complexity: O(n)

Given an int array which might contain duplicates, find if it is a sequence.

Given an int array which might contain duplicates, find if it is a sequence. 
Eg. {45,50,47,46,49,48}
is a sequence 45, 46,47,48,49,50
Sorting is an obvious solution. Can this be done in O(n) time and O(1) space


Approach:
Example array: A = {4, 1, 3, 3, 2}
1. get the min and max.
min=1 and max=4
2. if (max - min) > A.length then "its NOT a sequence".
3. else for each element in A[i] do the following:
a. calculate A[i] - min till A[i]-min=i;
i=0; 4 - 1 = 3, swap A[0] and A[3]
Now we have A = {3, 1, 3, 4, 2}
Again, 
i=0; 3 - 1 = 2, now A[0] and A[2] are same so swap A[0] and A[length-1] and put A[length] = infinite.
A = {2, 1, 3, 4, INF}
Again,
i=0; 2 - 1 = 1, swap A[0] and A[1], 
A = {1, 2, 3, 4, INF}
i=1; 2 - 1 = 1 (which is same as i)
similarlty for i=2, i=3
finally we have A as,
A = {1, 2, 3, 4, INF}


Code output: 

Printing Original Array ...
45 50 47 45 50 46 49 48 49 
MIN:45  MAX:50
Final Array ... 
45 46 47 48 49 50 2147483647 2147483647 2147483647 
Is Sequence: true

**Integer.MAX_VALUE (

2147483647 ) 

denotes INFINITE in the array values.

Find the largest subset of numbers in an array which forms a consecutive sequence.

Given an int array which might contain duplicates, find the largest subset of it which form a sequence. 
Eg. {1,6,10,4,7,9,5}
then ans is 4,5,6,7
Sorting is an obvious solution. Can this be done in O(n) time


Approach:
A = {1,6,10,4,7,9,5}


For each number A[i], put A[i] in hashMap<Int, List>
Also check if (A[i]+1) and (A[i]-1) exists in the Map,
If hashMap.contains((A[i]+1)) is true then append A[i] to the hashMap.get((A[i]+1));
If hashMap.contains((A[i]-1)) is true then append A[i] to the hashMap.get((A[i]-1));
And Append hashMap.get(A[i]+1) and hashMap.get(A[i]-1) to hashMap.get(A[i]);


In the end the iterate through all the keys of the hashMap and the largest List of hashMap.get(A[i]) is the longest sequence that exists in the input array.


Input Array for the below code:
A = {2, 3, 9, 10, 11, 4, 13, 5, 15, 6, 17, 7};
Output:

subset which forms the longest consecutive sequence: 
2 3 4 5 6 7 

Given an array A[], find (i, j) such that A[i] < A[j] and distance (j - i) is maximum.

Approach:
Example array:
int [] A = {6,5,9,15,29,7,4};


Create another array which has all the min elements to the left of  any i (0<=i<len(A)-1)
Lets call that array as B.
for (int i=1,k=0; i<len(A); i++,k++) {
     B[k] = Math.min(A[i],A[i-1]);
}
So now B would look like:
B = {5,5,9,15,7,4}


Similarly create another array say C which has all the max elements to the right of j
for (int i=len(A)-2, k=len(A)-2; i>=0; i--,k--) {
     C[k] = Math.max(A[i], A[i+1]);
}
Now array C would look like:
C = {6,9,15,29,29,7}


Now, compare each of B with C, by keeping track of max distance of i and j seen so far.
This would be like:


maxDistance = 0;
while (i<len(B) && j<len(C)) {
      if (B[i] < C[j]) {
              maxDistance = Math.max(maxDistance, j-i);
       }
}


Output:

Max Distance: 5
i:1   j:5

Coin change problem with limit on number of coins of each denomination.

You have coins with different denominations and you have limited number of each denominations (some maybe zero), how will you determine if you can supply the given change ?


Approach:

Characterize the structure of a coin-change solution.
• Define C[j] to be the minimum number of coins we need to
make change for j cents.
• If we knew that an optimal solution for the problem of
making change for j cents used a coin of denomination di,
we would have:
C[j] = 1 + C[j - di]




C[j] = infinite if j < 0
= 0 if j == 0;
= 1 + min { C[j - D[i]] } if j >= 1;
1<=i<=k


Now here we *DO NOT* have unlimited coins, so we keep one more array of limit of each type of coin denominations.
Let coin denominations be:
int [] D = {50, 25, 10, 1};
Ex for above coin denominations
int [] limit = {2, 1, 2, 5};


Now please refer "makeChangeLimitedCoins" method implementation in the below code for more..


If we want to make change for 30, with the above coin denominations and limit then below code outputs the following:

Printing Coin Value and Change:
1:1
2:2
3:3
4:4
5:5
6: Not Possible
7: Not Possible
8: Not Possible
9: Not Possible
10:1
11:2
12:3
13:4
14:5
15:6
16: Not Possible
17: Not Possible
18: Not Possible
19: Not Possible
20:2
21:3
22:4
23:5
24:6
25:1
26:2
27:3
28:4
29:5
30:6

Print the numbers of form 2^i.5^j in increasing order.

Print the numbers of form 2^i.5^j in increasing order. For eg:
1, 2, 4, 5, 8, 10, 16, 20


Output:
1 2 4 5 8 10 16 20 25 32 40 50 64 80 100 125 128 160 200 250 


Code:

Implement a versioned stack

We need to implement a versioned stack, i.e. version of stack will increment after each push/pop. Apart from push/pop, implement a method print(n) which would print stack state corresponding to version 'n'. For example:
-> initially stack is empty.
-> Version 1: 11 is pushed
-> Version 2: 8 is pushed
-> version 3: pop. only 11 left
-> Version 4: 15 is pushed
....
And so on.
Print(n) should print state at version 'n'.
Here 1 should print 11, 2 should print 8, 11...
All methods should be as efficient as possible.


Approach:
Implement the stack as the singly link list where each node contains the data and ptr to the next node.
Create a versionHashMap<Integer, Node>, versionHashMap stores the version and points to the latest node of the stack.


Ex:
version stack-nodes
v0         => null
push 9
v1        => 9->null
push 10
v2        => 10->9->null
push 11
v3        => 11->10->9->null
pop 11
v4        => 10->9->null
push 12
v5        => 12=>10->9->null


Now at version 4 the this is how the stack would look like in memory:


v5      v3   v4,v2  v1      v0
|          |        ||        |         |
12 -> 11 -> 10 -> 9 -> null




Output for below code:

Version::0
null
Version::1
9 -> null
Version::2
10 -> 9 -> null
Version::3
11 -> 10 -> 9 -> null
Version::4
10 -> 9 -> null
Version::5
12 -> 10 -> 9 -> null
Version::6
10 -> 9 -> null
Version::7
9 -> null
Version::8
null