All pair shortest paths - Repeated Squaring.

Given a matrix which represents 1/0 representing a direct flight between two places in a 2D array, find the number of hops required to reach from one place to another place. In other words, find if it is bi-hop, tri-hop etc.


Approach: 

A dynamic-programming algorithm.

Assume input graph is given by an adjacency matrix.

W = (wij)

Let dij(m)  = minimum weight of any path from vertex i to vertex j,

                  containing at most m edges.

dij(0) =   0   if i = j

         =     (infinite)  if i != j

dij(m) = min(dij(m-1), min{dik(m-1) + wkj})

        = min1 <= k <= n{dik(m-1) + wkj}, since wjj = 0.

So, given W, we can simply compute a series of matrices D(1), D(2), …,

D(n-1) where:

D(1) = W

D(m) = (dij(m))

SP algorithm computes the

following matrix “products”:

D(1) = D(0)*W = W1

D(2) = D(1)*W = W2

D(3) = D(2)*W = W3

...

D(n-1) = D(n-2)*W = Wn-1

n := rows[W];

D(1) := W;

m := 1;

while n – 1 > m do

D(2m) := Extend-SP(D(m), D(m));

       m := 2m

od;

return D(m) 

Extend-SP(D, W)

n := rows[D];

for i := 1 to n do

for j :=1 to n do

d´ij := ;

for k := 1 to n do

d´ij := min(d´ij, dik + wkj)

od

od

od;

return D´  

Code:

Find all the conflicting appointments from a given list of n appointments.

You are given 'n' appointments. Each appointment contains startime and endtime. You have to return all conflicting appointments efficiently starttime and endtime can range from a few min to few years.


Approach:

Suppose there are 5 events:

E1 => 13 : 15

E2 => 18 : 20

E3 => 11 : 24

E4 => 19 : 27

E5 =>  4  : 12

Now sort the events with start time:

E5: 4 : 12
E3: 11 : 24
E1: 13 : 15
E2: 18 : 20
E4: 19: 27


Now take the end time of first Event (E5) ie 12 and check in the start time the first event whose start time is greater than 12, in the above example E1 - with start time 13 is the event.
Now we can safely say that all the events less than E1 and greater than E5 are conflicting with E5 - which is E3 in our case.
With the same above logic, E3 is conflicting with E1, E2 and E4.
Time complexity = O(nlogn) for sorting the events on start time + O(nlogn) for searching a all the conflicting events for a given event Ei (1 <= i <= n).
So total time complexity: O(nlogn)


Output of the below code:

Events sorted with start time:
5: 4:12
3: 11:24
1: 13:15
2: 18:20
4: 19:27
Conflicts are: 
1 <> 3 
2 <> 3 4 
3 <> 5 1 2 4 
4 <> 3 2 
5 <> 3 

In a collection of 'M' elements, some elements are repeated. Find the element which occurred at least M/2 times.

Algorithm to output for a length m of a number stream, the value of the element j appearing in the stream for which freq[j]>m/2 with space complexity O(1) and time complexity O(m). Dont need to worry about the case when there are no elements with freq > m/2.
The question in simpler terms: 
In a collection of 'M' elements, some elements are repeated. Find the element which occurred at least M/2 times.


Approach:
Initialize an array B[] of size 32 for storing bit counts.
Iterate through all the elements in the given array A[] of length m.
for each A[i] (0 <= i <= m-1), get all the positions where the bit is set and increment the corresponding positions in Array B.
Suppose Array A = {3,5,7,5};
Then after we have seen all the elements of A, Array B would look like:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 2 4


Now iterate through B and set "1" if B[i] > (m/2) else set 0. - Above m=4 so m/2 = 2;
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 => 5


So the element >= m/2 is 5 in array A.


Code:
Input:
int [] A = {7,11,8,11,9,11,7,11,8,11,9,11};


Output:

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10 2 8 10 
Majority: 11

Given a set of numbers [1-N]. Subsets such that the sum of numbers in the subset is a prime number.

Given a set of numbers [1-N] . Find the number of subsets such that the sum of numbers in the subset is a prime number.
Approach:
For each number in the Sum S, check if there is subset of numbers from 1 to N that sum up to S - Yes that you can do with Subset Sum problem. Recurrence for the same is:

Sum[0,0]=True
For S=1 to L do Sum[0, S]= False
For k=1 to n do
     For S = 0 to L do
           Sum[k, S] = Sum[k-1, S] or Sum[k-1, S - x(k)]

Then for all the subsets Sum Si which can be generated with numbers from 1 to N, check if those are Prime.

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/