Largest 100

There is a big file containing 10^8 integers, one per line. Devise an algorithm to find the largest 100 integers among them. Remember you cannot read all of them into memory at once.

Solution :

We simply use Min-Heap data structure to keep list of top 100 numbers replacing next with lowest if greater.

Code :

/**
 *  Assume standard heap ADT operations : heap_min(), heap_remove() and heap_insert()
**/

void top_100(FILE *fp, int output[]){

int num, count=0;

while(fscanf(fp, "%d\n", &num)){

if(++count > 100 && num > heap_min(output)){

heap_remove(output);

}
heap_insert(output, num);

}

}

Complexity :

• Time : O(N log N)
• Space : O(1)

Bitonic array

Given an array of N distinct integers with the property that there exists an index K (0 <= K <= N-1) such that input[0], ..., input[K] is and increasing sequence and input[K], ..., input[N-1] is a decreasing sequence. Devise and algorithm to find K.

Ex [1 2 4 7 10 15 13 11 5 0 -5]
Answer: K=5 (input[K]=15)

Solution :

Use binary search with the following conditions :

input[mid-1] < input[mid] > input[mid+1] for mid != 0 and mid != N-1
input[mid] > input[mid+1]  for mid == 0
input[mid-1] < input[mid] for mid == N-1

with initial low = 0, high = N-1, mid = (high + low)/2

Code :

int bitonic_pivot(int input[], int N)
{

    int low=0, high=N-1, mid;

    while(low < high)
    {

        mid=(low+high)/2;

        if((!mid || (input[mid-1] < input[mid])) && (mid != N-1 || (input[mid] > input[mid+1])))

            return mid;

        else if((!mid || (input[mid-1] < input[mid])) && (mid != N-1 || (input[mid] < input[mid+1])))

            low=mid+1;

        else if((!mid || (input[mid-1] > input[mid])) && (mid != N-1 || (input[mid] > input[mid+1])))

            high=mid;

    }

    return -1;

}

Complexity :

• Time : O(log N)
• Space : O(1)

Largest Non Consecutive Subsequence

Given a sequence of N integers, devise an algorithm to find a sub-sequence S[] for which sum of its elements is maximum and such that S contains no two consecutive elements from input sequence.

Ex. input[] = [1 5 3 7 -2 -4 2]
Answer [5 7 2] Sum=14

Solution :

This requires Dynamic Programming formulation :
Let sum[i] represent maximum non-consecutive subsequence sum till ith element of input[], then
sum[i] = max(sum[i-1], input[i] + sum[i-2])

which says that new sum would either be obtained by not including ith element i.e previous sum, or by including it with last to previous sum i.e input[i-2]. The new sum would be maximum of these two possibilities.

Code :

int largest_non_consecutive(int input[], int N, int output[]){

int sum[N], jump[N], k=0, i;

sum[0] = input[0];
jump[0] = -2

if(input[1] > input[0]){

sum[1] =  input[1];
jump[1] = -1;

}
else {

sum[1] =  input[0];
jump[1] = 0;

}

for(i=2; i<N; i++){

if(sum[i-1] > input[i] + sum[i-2])){

sum[i] =  sum[i-1];
jump[i] = i-1;

}
else {

sum[i] = input[i] + sum[i-2];
// input[i] is included in resulting sequence when jump[i] is i-2
jump[i] = i-2;

}

}

// fill output according to jumps -- resulting sequence is in reverse order
for(i=N-1; i; i++){

if(jump[i] == i-2){

output[k++] = input[i];

}

}

return sum[N-1];

}

Complexity :

• Time : O(N)
• Space : O(1)

Adjacent removal

Given a string. Write an algorithm to remove adjacent characters if they are same.

Ex. Input = abccbcba
remove cc => abbcba
remove bb => acba (final result)

Solution :

We just compare the last element with next and if equal remove both.
[In implementation we may also use stack]

Code :

// M = output size

void adjacent_removal(int input[], int N, int output[], int *M){

int i=1;
*M = 0

while(i < N){

while(input[i] == input[*M] && (i < N) && (*M >= 0)){

i++;
(*M)--;

}
output[++(*M)] = input[i];

}

}

Complexity :

• Time : O(N)
• Space : O(1)

Lonely element

Given an array of integers with size 2N+1 such that N elements appear twice in arbitrary positions and 1 element appears only once.
Devise an algorithm to find the lonely element.

Ex : {1 2 4 5 1 4 2}
Answer : 5

Solution :

Note the properties of XOR :

1. A ^ A = 0
2. 0 ^ A = A
3. A ^ (B ^ C) = (A ^ B) ^ C

Thus we just XOR all integers to finally get the lonely element since all others will be made 0 for repeating twice.

Complexity :

• Time : O(N)
• Space : O(1)

Code :

int lonely_element(int input[], int N){

int result=0, i=0;

for(i=0; i<N; i++)

result ^= input[i];

return result;

}

Check range

Write a function that takes an int array of size M, and returns (true/false) if the array consists of the numbers only within the range [N, N+M-1]. The array is not guaranteed to be sorted.
For instance, {2,3,4} would return true. {1,3,1} would return true, {1,2,4} would return false.

Solution :

Simply find out the maximum and minimum in one pass and check if N == (max - min + 1)

Complexity :

• Time : O(N)
• Space : O(1)

Code :

int check_range(int input[], int N){

int max = input[0], min = input[0], i;

for(i=1; i<N; i++){

if(input[i] < min) min=input[i];
if(input[i] > max) max=input[i];

}

return (max - min + 1) == N;

}

Find repeated element

Given an array of size N which contains all the numbers from 1 to N-1. Find the number which is repeated in O(N) time.
How do you proceed with the same with floating numbers from 0 to 1 instead of 1 to N-1 ?

Solution :

For integers use sum to find the repeated number.
For floating numbers, use Hash tables.

Complexity :

• Time : O(N)
• Space : O(1) [O(K), K >> N for hash table]

Code :

int repetition_int(int input[], int N){

int i=0, sum=0;

for(i=0; i<N; i++)

sum += input[i];

return sum - (N*(N-1)/2);

}

float repetition_float(float input[], int N){

int i;

for(i=0; i<N; i++){

if(hash_table_exists(input[i]))

return input[i];

hash_table_insert(input[i]);

}

return -1.0;

}

Tricky addition

Write a function to add to integers without using mathematical operators (+, -, *, /, ^).

Solution :

We use the logic used in digital circuits where sum = A XOR B and carry = A AND B. We simply add the carry again after shifting it 1 left till it become zero.

Complexity :

• Time : O(1)
• Space : O(1)

Code :

int add(int a, int b){

int carry = 0;
while(b){

carry = a & b;
a = a ^ b;
b = carry << 1;

}
return a;

}

Largest subsequence in terms of absolute sum

Given an array of N integers (both positive and negative), find the sub-sequence with largest absolute sum.
For ex: Let A = {1 2 -5 4 5 -1 2 -11} then largest absolute sum is 11 with sub-sequence {-11}.

Solution :

A simpler variant was previously discussed [Largest consecutive sum], here the difference being absolute sum.
We use the same algorithm of O(N) here too first to get highest positive sum and then highest negative sum and find the one with higher absolute value as the answer.

Complexity :

• Time : O(N)
• Space : O(1)

Code :

void largest_consecutive_sum(int input[], int N, int *start, int *end, int *max){

*start = *end = *max = -1;
int current = -1;
int sum = 0;

for(int i=0; i<N; i++){

sum += input[i];

if(sum < 0){

sum = 0;
current = i+1;

}

if(sum > *max){

*max = sum;
*start = current;
*end = i;

}

}

}

void largest_consecutive_absolute_

sum(int input[], int N, int *start, int *end, int *max){

int pos_start, pos_end, pos_max, neg_start, neg_end, neg_max;
int i;

largest_consecutive_sum(input, N, &pos_start, &pos_end, &pos_max);

for(i=0; i<N; i++){

input[i] = -1*input[i];

}

largest_consecutive_sum(input, N, &neg_start, &neg_end, &neg_max);

if(pos_max > neg_max){

*start = pos_start;
*end = pos_end;
*max = pos_max;

}
else {

*start = neg_start;
*end = neg_end;
*max = neg_max;

}

}

Modified 2-color sort

Given an array of integers containing only 0s and 1s.You have to place all the 0s in even position and 1s in odd position. And if suppose, no. of 0s exceed no. of 1s or vice versa then keep the exceeding integers untouched. Do that in ONE PASS and without taking extra memory (modify the array in-place).

For Example :
Input Array:    [0,1,1,0,1,0,1,0,1,1,1,0,0,1,0,1,1]

Output Array: [0,1,0,1,0,1,0,1,0,1,0,1,0,1,1,1,1]

Solution :

Find the wrong positions for 0 and 1 and swap them

Complexity :

• Time : O(N)
• Space : O(1)

Code :

void interleave_0_1(int input[], int N){

int i=0, j=1;

while(1){

while(i < N && input[i] == 0)

i += 2;

while(j < N && input[j] == 1)

j += 2;

if(i < N && j < N){

input[i] ^= input[j];
input[j] ^= input[i];
input[i] ^= input[j];

}
else

break;

}

}

Reversing linked list

Devise an algorithm to print elements of linked list in reverse without reversing the linked list. State the time and space complexities.

Solution :

Use recursion

Complexity :

• Time : O(N)
• Space : O(N)

Code :

void display_reverse(node *list){

       if(list){

              display_reverse(list->next);

              printf("%d\n", list->info);

       }

}

Largest sum of elements with no three consecutive

Given a sequence of  positive numbers, find the maximum sum that can be formed which has no 3 consecutive elements present.

For example: consider the sequence 3000 2000 1000 3 10  Here,  the answer would be 5013, by taking 3000, 2000, 3 & 10. Note that we can't form a sequence that takes 3000, 2000 & 1000 together because they are the consecutive elements of the array.

Sample cases 1 2 3                            ans=5 

100 1000 100 1000 1                        ans=2101 

1 1 1 1 1                                            ans=4 

1 2 3 4 5 6 7 8                                   ans=27

Try to find an O(N) solution. N is the number of elements in the array. 

Solution :

The solution for this problem is by dynamic programing as given below in code.

Complexity :

• Time : O(N)
• Space : O(N)

Code :

int max_three(int[] input, int N){

int sum[] = new int[N+2];

sum[0] = 0;

sum[1] = input[0];

sum[2] = input[0] + input[1];

for (int i=2; i<N ;++i){

    sum[i+1] = max(input[i] + sum[i-1], input[i] + input[i-1] + sum[i-2]);

    sum[i+1] = max(sum[i+1], sum[i]);

}

return sum[N];

}

Zero the matrix

Given a N x N matrix with 0s and 1s. Devise an algorithm such that whenever you encounter a 0 make the corresponding row and column elements 0.

Eg.
Input  
1 0 1 1 0
1 1 1 1 1
1 1 1 1 0
1 1 1 1 1
0 0 1 1 0

Output
0 0 0 0 0
0 0 1 1 0
0 0 0 0 0
0 0 1 1 0
0 0 0 0 0

Solution :

We keep two arrays for rows and columns with 0 indicating the corresponding row/column contains at least one 0.
Finally we use these arrays to set the required cells to 0.

Complexity :

• Time : O(N^2)
• Space : O(N)

Code :

void matrix_set_zero(int *input, int N){

int *row = new int[N];
int *col = new int[N];

for(int i=0; i<N; i++){

row[i] = col[i] = 1;

}

for(int i=0; i<N; i++){

for(int j=0; j<N; j++){

row[i] &= input[i][j];
col[j] &= input[i][j];

}

}

for(int i=0; i<N; i++){

for(int j=0; j<N; j++){

input[i][j] = row[i] & col[j];

}

}

}

Kth smallest in union of arrays

Given two sorted arrays of size M and N. Find Kth smallest element in the union of the two arrays in constant space. (i.e. without using additional space).

Solution :

The Kth element will be found within first K elements of both arrays, so we consider only these elements or whole array if size is less than K
We use recursive procedure. We compare (K/2)th element in arrays A(0 K) and B(0 K)
if A(K/2) < B(K/2) we recursively find (K-K/2)th smallest element in A(K/2+1 K) and B(0 K/2) eliminating first K/2 elements from A
else if A(K/2) > B(K/2) we recursively find (K-K/2)th smallest element in B(K/2+1 K) and A(0 K/2) eliminating first K/2 elements from B
if A(K/2) == B(K/2) return A(K/2) as answer

Boundaries must be checked in the procedure

Complexity :

• Time : log N + log M (Please check if its min(log N, log M) rather than this)
• Space : O(1)

Code :

void kth_smallest(int[] A, int M, int[] B, int N, int K, int &result){

int a_high = (M < K) ? M : K;
int b_high = (N < K) ? N : K;

result = find_kth(A, 0, a_high, B, 0, b_high, K);

}

int find_kth(int[] A, int a_low, int a_high, int[] B, int b_low, int b_high, int K){

// boundary cases
if(a_low > a_high)

return B[b_low + K - 1];

if(b_low > b_high)

return A[a_low + K - 1];

int mid = (K+1)/2;  // finding ceiling of K/2

if(A[mid] == B[mid])

return A[mid];

else if(A[mid] < B[mid])

return find_kth(A, a_low + mid+1, a_high, B, b_low, b_low + mid, mid);

else if(A[mid] > B[mid])

return find_kth(A, a_low, a_low + mid, B, b_low + mid + 1, b_high, mid);

}

void kth_smallest_linear(int[] A, int M, int[] B, int N, int K, int &result){

int i=0, j=0;
for( ; K; K--){

if(i >= M){

result = B[j + K - 1];
break;

}
if(j >= N){

result = A[i + K - 1];
break;

}
if(A[i] == B[j]){

result = A[i++];
j++;

}
else

result = (A[i] < B[j]) ? A[i++] : B[j++];

}

}

Last non-zero digit of N!

Find the last non-zero digit of N!. Assume N! to be extremely large.

Solution : 

Please refer the following link for an in-depth analysis of solutions to this problem :
http://comeoncodeon.wordpress.com/2009/06/20/lastnon-zero-digit-of-factorial/