Finding repeated elements in an array.

Design an algorithm that, given a list of n elements in an array, finds all the elements that appear more than n/3 times in the list.
The algorithm should run in linear time. (n >=0 )

You are expected to use comparisons and achieve linear time. No hashing/excessive space/ and don't use standard linear time deterministic selection algo.

Approach:

Let N = size of the input array A.

Now we need to find all the elements in the array which occur more than (N/K) times in the input Array A.

maintain a Map (Key=A[i], and value is the frequency of Key in array A so far).

as soon as the size of the Map reaches K, decrement the value of all the Keys by 1, if the value is 1, then after decrementing it will be 0 - Delete those keys from Map.

At max you will have to do (N/K) deletions. 

In the end you will be left with atmost (K-1) unique Keys - which are candidate answers.

Now again re-iterate through the array A and report the Keys whose frequency is greater than (N/K).

Time Complexity: O(nlogk).

space complexity: O(k).

Ex:

int [] A = {5, 4, 4, 3, 2, 3, 4, 5, 5, 8};

N = 10;

K = 5;

we need to find all the elements in A which occurs more than (N/K) = 2 times.

As you iterate through the Array A, the steps would be - Imagine you are playing tetris, where same keys stack upon each other and you put the different keys in the adjacent column, when you have a row of size K - you delete that row:

When 8 is coming, the tetris would look like:

5 4

5 4 3

5 4 3 2

When 8 has dropped tetris would look like:

5 4

5 4 3

5 4 3 2 8 <= This row is now full (means its size has K=5)

After deleting the tetris snapshot would be:

5 4

5 4 3

So now 3,4,5 are your candidate elements which can occur more than (N/K) = (10/5) = 2 times in A.

Again iterate through the Array A, and report elements among 3,4,5 which occur more than 2 times.

Ans is:

Key: 4 Value: 3

Key: 5 Value: 3

you can prove that in the end at most (K-1) unique values would be remaining as candidate answer.


output for the below code:

Key: 4 Value: 6
Key: 10 Value: 6
End!

Find the majority element in an array in linear time.

A Linear Time Majority Vote Algorithm:

Traverse the array starting from the first index.


As we traverse we maintain a pair consisting of a current candidate and a counter. Initially, the current candidate is unknown and the counter is 0.


When we move the pointer forward over an element X:


If the counter is 0, we set the current candidate to X and we set the counter to 1.
If the counter is not 0, we increment or decrement the counter according to whether X is the current candidate.
When we are done, the current candidate is the majority element, if there is a majority.



Input:
char [] arr = {'A', 'A', 'A', 'C', 'C', 'B', 'B', 'C', 'C', 'C', 'B', 'C', 'C'};
Output:
Majority Element: C

First non-repeated URL

Given a very long list of URLs, find the first URL which is unique ( occurred exactly once ).



Approach:
Iterate through the urls, and store them in linkedHashMap (keys are stored in doubly linklist and the insertion order is maintained).
Whenever you encounter that some key (url) already exists, delete the entry in the linkedHashMap.
In the end you will have only non-repeated urls in the linkedHashMap.
the first entry (head) of the linkedHashMap will be the first non repeated URL.
Time complexity: theta of N, space complexity: O(N)


Sample Input:

String [] str = { "http://www.google.com/",
 "http://www.yahoo.com/",
 "http://www.amazon.com/",
 "http://www.apache.com/",
 "http://www.google.com/",
 "http://www.mycar.com/",
 "http://www.microsoft.com/",
 "http://www.casandra.com/",
 "http://www.apache.com/",
 "http://www.google.com/",
 "http://www.oracle.com/",
 "http://www.yahoo.com/",
 "http://www.oracle.com/",
 "http://www.facebook.com/",
 "http://www.pandora.com/",
 "http://www.microsoft.com/",
 "http://www.google.com/",  
 "http://www.mycar.com/",
 "http://www.amazon.com/",
 "http://www.apple.com/",
};


Sample output:
1 : http://www.casandra.com/
1 : http://www.facebook.com/
1 : http://www.pandora.com/
1 : http://www.apple.com/
First Non Repeated URL: http://www.casandra.com/

Merge 2 sorted arrays, where one array has gaps between elements.

Given two sorted arrays of sizes N,M (N > M). 
N has M gaps even though it is sorted. (gaps can be in between . Not required to be at the end).
Best algorithm to merge these two arrays , with out using any extra space.


Suppose we have 2 arrays:

char [] A = {'a',' ','c','e',' ', ' ', 'g',' ','j', ' '};
char [] B  = { 'b','d','f','h','i'};


Let's space char be the gap mentioned in the above question.
Now first iterate through the Array A and shift all the non-space chars to the left.


Then merge 2 arrays A and B by comparing the elements and filling Array A from the end.


output:

Length A:10
Length B:5
Starting array A printing: 
a b c d e f g h i j 

Count of binary trees, given inorder traversal.

Given an inorder traversal only for a binary tree (not necessarily a BST), give a pseudo code to generate all possible binary trees for this traversal sequence.
Firstly, how many binary trees can be generated given an in-order traversal? I know that given 'n' nodes, number of BTs possible is (2^n)-n. But if we are given a specific in-order sequence, can we cut down on this number?


Strategy: consider that each value could be the root. Recursively find the size of the left and right subtrees.


If you need to build all those Trees, then there are 3 ways a new node N could be added to the already existing set of Tree(s) T to preserve the inorder sequence.
1. N could be added as the rightmost child of tree T.
2. N could be root and T as its left subtree.
3. The right subtree of T say R could be added as left subtree of N and then N added as the right subtree of T.

You are given a list of points in the plane, write a program that outputs each point along with the three other points that are closest to it.

You are given a list of points in the plane, write a program that
outputs each point along with the three other points that are closest
to it. These three points ordered by distance.
The order is less then O(n^2) .

For example, given a set of points where each line is of the form: 

ID x-coordinate y-coordinate

1 0.0 0.0
2 10.1 -10.1
3 -12.2 12.2
4 38.3 38.3
5 79.99 179.99

Your program should output:

1 2,3,4
2 1,3,4
3 1,2,4
4 1,2,3
5 4,3,1

Approach:

First Have all the points in an array and sort them according to their X axis, which would give:

3 -12.2 12.2 

1 0.0 0.0 

2 10.1 -10.1 

4 38.3 38.3 

5 79.99 179.99 

Then for every point P, calculate the distance from 3 points in the front and 3 point in the back:

For Ex: Point with Id=3 (-12.2, 12.2) does not have 3 points in the back.

Always store only min 3 distances and the corresponding point Ids - Max heap can help here.

Then Sort the points according to their Y Axis, which would give:

2 10.1 -10.1 

1 0.0 0.0 

3 -12.2 12.2 

4 38.3 38.3 

5 79.99 179.99 

Again calculate for every point p, distances from 3 points in the front and 3 points in the back - Always maintaining the Max heap of size 3.

Total complexity: 2nlogn + 4kn + klogk = O(nlogn)

k = 3 here.

Bit counting - Expected order is the number of bits set.

Count number of set bits in a number.

output:

Bit Count: 6
1100110101

Dutch National Flag Problem.

Re-arrange an array containing only 0s,1s and 2s, so that all 1s follow all 0s and all 2s follow 1s. e.g. 00000011111111222222. Linear time algorithm.


Input: {0,0,1,1,2,2,0,0,2,0,1,1,1,0,1};
Output: (0 0 0 0 0 0 1 1 1 1 1 2 2 2 }

Count words in a sentence. Words can be separated by more than one space.

Count words in a sentence. Words can be separated by more than one space.


Input: "  an b  c   d";
output: 4

Remove Duplicate slashes

Remove Duplicate slashes

"/root//foo/bar"=> "/root/foo/bar"

Water Cup Pyramid Problem.

There is a pyramid with 1 cup at level , 2 at level 2 , 3 at level 3 and so on..
It looks something like this 
    1
   2 3
 4 5 6
every cup has capacity C. you pour L liters of water from top . when cup 1 gets filled , it overflows to cup 2,3 equally, and when they get filled , Cup 4 and 6 get water only from 2 and 3 resp but 5 gets water from both the cups and so on.
Now given C and L .Find the amount of water in kth cup.


Idea:
Pour L into coup 1. Divide into its children if overflows. Do this for subsequent elements, until find k.
LeftChildIndex = index + height[index] + 1 for the first child,
RightchildIndex = LeftChildIndex  + 1 for the next.


Suppose C=3.0 and L=23.0 then lets find out the amount of water in 8th Cup.
OutPut:

CUP: 1 :H: 0 :W: 3.0
CUP: 2 :H: 1 :W: 3.0
CUP: 3 :H: 1 :W: 3.0
CUP: 4 :H: 2 :W: 3.0
CUP: 5 :H: 2 :W: 3.0
CUP: 6 :H: 2 :W: 3.0
CUP: 7 :H: 3 :W: 0.25
CUP: 8 :H: 3 :W: 2.25
Water Amount in 8th cup: 2.25

find all the possible subset of the array of size k

Given an array of size n, find all the possible sub set of the array of size k(all the subsets must be of size k).


Algorithm:
Suppose array size is of length 5 ie A = {1,2,3,4,5};
and we need all the subsets of size k=3.


If we were supposed to find all the subsets then we would have taken all the binary representations of numbers from 1 to (2^5 - 1) and then according to the bits set, we would have chosen the corresp. number from Array A.


Now the idea is get the minimum number where all "k" lower bits are set.
In our case that would be = "00111" => 7 in decimal
Now find the next decimal number > 7 where 3 bits are set.
Keep on finding the next numbers till you hit "11100" = 28 since that is the largest binary number with 3 bits set of length 5.


Given an integer, method to find the next smallest number that have the same numbers of bits set:
1. Traverse from right to left, Once we have passed a 1, turn on the next 0. 
ex: 101110 becomes 111110
2. Turn off the one that's just to the right side of that (where you switched on '0' to '1').
now 111110 becomes 110110.
3. Make the number as small as possible by rearranging all the 1's to be as far as right as possible.
ex: 110110 becomes 110011.


Sample output of below code:

Subsets of size 3 are: 
3 4 5 
2 4 5 
2 3 5 
2 3 4 
1 4 5 
1 3 5 
1 3 4 
1 2 5 
1 2 4 
1 2 3 

Subset of Size K from Array of size n

Given an array of size n, find all the possible sub set of the array of size k(all the subsets must be of size k).

Binary Tree Operations.

Code for following problems:


1. Given a binary tree, count the number of nodes in the tree.
2. Given a binary tree, compute its "maxDepth" -- the number of nodes along the longest path from the root node down to the farthest leaf node. The maxDepth of the empty tree is 0.
3. Given a non-empty binary search tree (an ordered binary tree), return the minimum data value found in that tree. Note that it is not necessary to search the entire tree. A maxValue() function is structurally very similar to this function.
4. Given a binary search tree (aka an "ordered binary tree"), iterate over the nodes to print them out in increasing order.
5. Given a binary tree and a sum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum. Return false if no such path can be found.
6. Given a binary tree, print out all of its root-to-leaf paths, one per line.
7. Change a tree so that the roles of the left and right pointers are swapped at every node.
8. Given two binary trees, return true if they are structurally identical -- they are made of nodes with the same values arranged in the same way.
9. Suppose you are building an N node binary search tree with the values 1..N. How many structurally different
binary search trees are there that store those values? Write a recursive function that, given the number of distinct values, computes the number of structurally unique binary search trees that store those values. For example, countTrees(4) should return 14, since there are 14 structurally unique binary search trees that store 1, 2, 3, and 4. The base case is easy, and the recursion is short but dense. Your code should not construct any actual trees; it's just a
counting problem.
10. Write an isBST() function that returns true if a tree is a binary search tree
and false otherwise.

Code:

First Non-Repeated Character in the String.

Given a String, find the first non-repeated character in the string.


Input:
abcdeecbkbala
Output:
Input String:
abcdeecbkbala
First non-repeated char in the string: d


Code:

Fibonacci Numbers

Recursive definition:
Fn = 0 if n= 0;
= 1 if n= 1;
= F(n-1) + F(n-2) if n>=2
0 1 1 2 3 5 8 13 21 34 ...

Output:

Printing fibonacci sequence till 9:
0 1 1 2 3 5 8 13 21 
Calculating fibonacci sequence iteratively till 9: 
0 1 1 2 3 5 8 13 21 

Powering a Number in O(logn) Time.

Problem:Compute a^n, where n is a natural number.
Naive algorithm:Θ(n).
a^n = a^(n/2) * a^(n/2) if n is even;
= a^((n–1)/2) * a^((n–1)/2) * a if n is odd;


Divide-and-conquer algorithm:
T(n) = T(n/2) + Θ(1) ⇒T(n) = Θ(lgn).


Input:
15
7
Output:
15^7 = 170859375


Code:

Multiply long numbers.

Write a function to take two arbitrarily long numbers in the form of Strings and multiply them, returning another String with the product.
Input:
2839745624
8769342123
Output:
2839745624 x 8769342123 = 24902700919148119752


Code:

Kth Smallest element in Binary Search Tree in O(N) - Recursive and Iterative.

Write a function to take a BST and a value k as input and have it print the kth smallest element in the BST.
Write a function that takes a binary tree as input, and have it perform In order traversal - recursive and then iterative

Output:
97 92 3 10 87 6 46
Printing inorder:
3 6 10 46 87 92 97
K value: 3
Kth Smallest Node Value: 10
Kth Node :10

Retrieving an element with a given rank from a Binary Search Tree in O(logN) time.

The given Binary Search Tree has an extra information in each of its node.
Each node of the BST contains a field called "size", which is the number of internal nodes in
the subtree rooted at node (including node itself).

Find Minimum element in sorted but rotated array

Input:
6 5 4 2 3
Output:
Elements in the array:
6 5 4 2 3
Min:2


Code:

Maximum sum submatrix of a given Matrix.

Approach:

Median of Numbers, which is distributed across N machines.

Approach (Based upon quick sort):

1. Designate one computer as the master and others as slave.
2. Let the Master choose one random number, say X from its array of numbers and ask all the other slave nodes to partition their arrays based on Pivot X.
3. Then Slave nodes report back the count of numbers less than X and count of numbers more than X (can be done in parallel).
4. The Master node then add all the numbers received less than X and more than X and checks if the median is less than or greater than X.
5. Now choose X2 based upon the partition data depending upon where the median might be ie in the left partition or the right partition.
6. Continue till we get median.