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.

Largest monotonically increasing contiguous sequence

Write code for finding length of largest monotonically increasing contiguous sequence in an array of integers. Optimize it (not the usual O(n) in worst case, but a better approach in average case).


Approach:
Keep a HashMap of <A[i], length of the largest contiguous sequence of which A[i] is part of>
for each of A[i] in the array of numbers [] A.
Check if A[i]-1 is in HashMap H, if so increase its count L by 1.
check if A[i]+1 is in H, if so increase its count R by 1.
Then put A[i] in HashMap H, with count = L+R.


In the end the key with the largest count is the answer.




Code input/output:
int [] A = {2, 3, 9, 10, 11, 4, 13, 5, 15, 6, 17, 7};
largestContiguousSeq(A);
Max length of congiuous elements: 6


int [] B = {1,6,10,4,7,9,5};
largestContiguousSeq(B);
Max length of congiuous elements: 4

Merge N Sorted Lists/Arrays.

Design and implement an algorithm to merge N sorted arrays.


Approach:
1. Take the head of all the N sorted arrays in a min-heap.
2. Get the min element from the min-heap and output/store it.
3. now pull out another element from the array to which the min-element in 2. belonged and add it to the heap and heapify it.
4. now repeat 2. & 3. till all the elements in N sorted arrays are exhausted.




Number of arrays: 7
48 52 202 459 589 647 700 794 
72 227 257 513 545 
151 327 361 691 821 
29 30 363 753 938 
120 178 314 364 409 662 695 
181 240 378 472 556 584 756 760 871 
87 111 242 275 368 376 815 944 966 
Final merged lists data: 
29 30 48 52 72 87 111 120 151 178 181 202 227 240 242 257 275 314 327 361 363 364 368 376 378 409 459 472 513 545 556 584 589 647 662 691 695 700 753 756 760 794 815 821 871 938 944 966 

Pairs of integers that sum to a given value.

Given an array with integers and a number n, design an algorithm and write code to print all pairs of integers that sum up to this number.


Code input/output:
int [] A = {5, 9, 2, 11, 3, 8, 15, 7, 4, 12, 1};


Pairs that sum up to 12
5:7
9:3
11:1
8:4

Merge 2 Sorted Arrays, such that integer in both array is copied once.

Write code to merge two arrays in sorted order such that if an integer is in both arrays, it only gets put into the new array once. 
What if you knew that one array was much longer than the other? Could you optimize it?


Input Arrays with repeated elements:
int [] A = {1, 1, 2, 2, 3};
int [] B = {2, 3, 3, 4};
Output:
Merged Array: 
1 1 2 2 3 3 4 


Input Arrays with unique elements:
int [] C = {2, 5, 7, 9, 10, 11};
int [] D = {1, 3, 5, 7, 8, 9, 11, 13};
Merged Array: 
1 2 3 5 7 8 9 10 11 13 


time complexity: O(lenA+lenB) = O(m+n).
space complexity: O(m+n);


Suppose array A is much larger than array B.
Now, take B[0] and do binary search in A for B[0].
If we find it at index i, then copy the data A[0]..A[i] to C;
Otherwise find index i in A, such that A[i] is less than B[0] and A[i+1] is greater than B[0].
Copy A[0]..A[i] to C and then copy B[0] to C at k=i+1;


Now, lets take B[1] and again do binary search for B[1] in A.
if we find it at index j, then copy A[i+1]..A[j] to C.
Otherwise find index j in A, such that A[j] < B[1] and A[i+1] > B[0].
Copy A[i+1]...A[j] to C and then copy B[1] to C at k=j+1;


So on...
suppose n = A.length; and m = B.length;
time complexity: O(m log n)
space complexity: O(m+n)

Number of connections on web server in last 1 minute.

Write a data structure to count number of connections on web server in last 1 minute.

Approach:

Use a circular array of size say 60 with cumulative connections stored in indices. 

To calculate how many connections are on web server in last minute, just take difference between the current index and the previous one.

At any point, suppose you are storing the connections at index i, then reset i+1 to 0. 

Code output:

Server Connections in last 1 min: 3

3 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 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 0 

Server Connections in last 1 min: 2500473

4042037 8366214 12750825 17069356 21435609 25818813 30193316 34585084 38981930 43362517 47729398 51954656 56319336 60718454 65115406 69495682 73891294 78291081 82663083 85163556 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 0 0 0 0 0 0 0 0 0 0 0 

Server Connections in last 1 min: 1673643

4042037 8366214 12750825 17069356 21435609 25818813 30193316 34585084 38981930 43362517 47729398 51954656 56319336 60718454 65115406 69495682 73891294 78291081 82663083 86993284 91375051 95752355 100071358 104330554 108415170 112538285 116863280 121258700 125587403 129942011 134230253 138600661 142938928 147332572 151699763 156056115 160386707 164517422 168667052 170340695 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 

Server Connections in last 1 min: 1937344

0 8366214 12750825 17069356 21435609 25818813 30193316 34585084 38981930 43362517 47729398 51954656 56319336 60718454 65115406 69495682 73891294 78291081 82663083 86993284 91375051 95752355 100071358 104330554 108415170 112538285 116863280 121258700 125587403 129942011 134230253 138600661 142938928 147332572 151699763 156056115 160386707 164517422 168667052 172844039 177046285 181257855 185477645 189761265 193999235 198216330 202498034 206710346 210913720 215265043 219554608 223756476 228036400 232286104 236596081 240862590 245114846 249370034 253580282 255517626 

Server Connections in last 1 min: 1165884

261960600 266156936 270515554 274897599 279280497 283664192 288055183 292439077 296814993 301208147 305548693 309453194 313561569 317817387 322058006 326376381 330750504 335138909 339517887 340683771 0 95752355 100071358 104330554 108415170 112538285 116863280 121258700 125587403 129942011 134230253 138600661 142938928 147332572 151699763 156056115 160386707 164517422 168667052 172844039 177046285 181257855 185477645 189761265 193999235 198216330 202498034 206710346 210913720 215265043 219554608 223756476 228036400 232286104 236596081 240862590 245114846 249370034 253580282 257793064 

Server Connections in last 1 min: 3375382

261960600 266156936 270515554 274897599 279280497 283664192 288055183 292439077 296814993 301208147 305548693 309453194 313561569 317817387 322058006 326376381 330750504 335138909 339517887 343893181 348271766 352634531 356957672 361256457 365595987 369933329 374262314 378625770 382977564 387371854 391741255 396148986 400533862 404908812 409300391 413695463 418093979 422477882 425853264 0 177046285 181257855 185477645 189761265 193999235 198216330 202498034 206710346 210913720 215265043 219554608 223756476 228036400 232286104 236596081 240862590 245114846 249370034 253580282 257793064 

Server Connections in last 1 min: 902289

261960600 266156936 270515554 274897599 279280497 283664192 288055183 292439077 296814993 301208147 305548693 309453194 313561569 317817387 322058006 326376381 330750504 335138909 339517887 343893181 348271766 352634531 356957672 361256457 365595987 369933329 374262314 378625770 382977564 387371854 391741255 396148986 400533862 404908812 409300391 413695463 418093979 422477882 426851222 431242526 435636157 440017329 444408215 448769117 453168222 457561690 461906594 466303078 470703003 475091017 479476932 483871156 488262033 492585214 496985526 501373444 505753642 510117476 511019765 0 

Server Connections in last 1 min: 2864165

523295700 527683139 532078847 536464008 540855095 545243156 549635094 554029949 558416866 562810843 567209609 571430001 575788814 580182347 584562119 588946702 593321752 596185917 0 343893181 348271766 352634531 356957672 361256457 365595987 369933329 374262314 378625770 382977564 387371854 391741255 396148986 400533862 404908812 409300391 413695463 418093979 422477882 426851222 431242526 435636157 440017329 444408215 448769117 453168222 457561690 461906594 466303078 470703003 475091017 479476932 483871156 488262033 492585214 496985526 501373444 505753642 510117476 514504603 518899160 

1D Array into 2D table.

You are given a 1D array of integers, such as:
int[] array = [3,4,7,2,2,6,0,9];
Suppose you need to treat this array as a 2D table with a given number of rows.
You want to sum the columns of the table.
One value of numRows is 4..in that case the resultant array would look like
3 4
7 2
2 6
0 9
—-
12 21

Minimum distance between 2 elements in an array with duplicates.

Consider there is an array with duplicates and u r given two numbers as input and u have to return the minimum distance between the two in the array with minimum complexity.

Input Array:

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

 minDist = minDistance(A, 9, 3);

System.out.println("Min Distance (9, 3): " + minDist);

minDist = minDistance(A, 3, 9);

System.out.println("Min Distance (3, 9): " + minDist);

minDist = minDistance(A, 4, 7);

System.out.println("Min Distance (4, 7): " + minDist);

minDist = minDistance(A, 9, 9);

System.out.println("Min Distance (9, 9): " + minDist);

minDist = minDistance(A, 3, 3);

System.out.println("Min Distance (3, 3): " + minDist);

minDist = calcMinDistance(A, 5, 8);

System.out.println("Min Distance (5, 8): " + (minDist-1));

minDist = calcMinDistance(A, 5, 9);

System.out.println("Min Distance (5, 9): " + (minDist-1));

Output:

Min Distance (9, 3): 0

Min Distance (3, 9): 0

Min Distance (4, 7): 3

Min Distance (9, 9): 0

Min Distance (3, 3): 1

Min Distance (5, 8): 2

Min Distance (5, 9): 0

Dynamic Programming: Maximum Contiguous Subsequence Sum of At Least Length L.

Given a sequence of n real numbers A(1) ... A(n), determine a contiguous subsequence A(i) ... A(j) of length atleast L for which the sum of elements in the subsequence is maximized.


For the following array, where L = 3.
A = {-5, -1, 2, -3, 0, -3, 3,}
The best possible sum of at least length 3 would be 0, where the subsequence is the last three elements (0, -3, 3)


Another Array with L = 2;
A = {0, 5, -3, -1, 2, -4, -1, 7, 8}
Output = 15;


Set sumL to the sum of the first L array elements.
Set runningSum = sumL.
Set maxSum = sumL
For k = L + 1 up to n, the length of the array:
Set sumL = sumL + A(k) - A(k - L)
Set runningSum = max(runningSum + A(k), sumL)
Set maxSum = max(maxSum, runningSum)
Output maxSum


Inputs:
int  [] A = {0, 5, -3, -1, 2, -4, -1, 7, 8};
int L = 2;
int [] B = {-5, -1, 2, -3, 0, -3, 3,};
L = 3;


Output:
Max sum: 15
Indices: i=7 : j=8
Max sum: 0
Indices: i=4 : j=6

Dynamic Programming: Maximum Value Contiguous Subsequence.

Given a sequence of n real numbers A(1) ... A(n), determine a contiguous subsequence A(i) ... A(j) for which the sum of elements in the subsequence is maximized.


Recurrence Equations:
For any i and j where (1 <= i < j <= n)
M(j) = Max sum over all windows ending at j.


M(j) = Max { M(j-1) + A[j], A[j] } ie either we extend the optimal window ending at j or start a fresh window with A[j].


Total time complexity: O(n) as there are n sub problems, each of size O(1).


Input Arrays:

int [] A = { -2, 11, -4, 13, -5, 2 };
int [] B = {-15, 29, -36, 3, -22, 11, 19, -5};


Output:

Max Sum: 20
Indices: i=1: j=3
Max Sum: 30
Indices: i=5: j=6

Biggest rectangle in a histogram.

Given an array of positive integers that represent the bars in a histogram,
find the rectangle with the largest area under the curve and above the axis.


Approach:
Let the array be A = {4, 1, 6, 3, 4, 7, 5, 2}, maxArea=0 and area=0;
Now for each A[i], traverse forward till A[j] >= A[i] (j > i). - say we found n such numbers.
Calculate the area as area = A[i] * (n).
Now for A[i], traverse backwards till A[j] <= A[i], - say we found m such numbers.
area += (A[i] * m);
if (area > maxArea) then maxArea <= area.
In the end return the maxArea.


Code output:
reactange with largest area under the curve and above the axis: 12

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.

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 

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.

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

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

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

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