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