Range Search

Given an sorted array of integers, perform binary search to find the index of the range in which the number lies. A range is specified by index of its lower bound.

Example :

array 12 20 32 40 52

          ^   ^   ^   ^   ^

index  0   1   2   3   4

Given the number -> 19 (It lies between index 0 and 1), return 0
Given the number -> 22 (It lies between index 1 and 2), return 1
Given the number -> 40 (It lies between index 3 and 4), return 3

Solution
Use binary search.

Suppose we are at index i , then there are two possibilities:

A[i] < N , this implies that we need to check in (i+1, N)
• A[i] >= N   this implies that we need to check in (0, i)

Code

int range_search(int array[], int N, int begin, int end){

if(begin > end)

return -1;

     
int mid=(begin + end)/2;
     
if(array[mid] > N){

if(array[mid-1] <= N)

return mid-1;

else

return range_search(array, N, begin, mid-1);

}
else if(array[mid] <= N){

if(array[mid+1] > N)

return mid;

else

return range_search(array, N, mid+1, end);

} 

}

Complexity

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

Fixed Point

Given an array of N distinct integers sorted in ascending order, write a function that returns a Fixed Point in the array, if there is any Fixed Point present in array, else returns -1. Fixed Point in an array is an index i such that arr[i] is equal to i. Note that integers in array can be negative.

Examples :

Input: arr[] = {-10, -5, 0, 3, 7}
Output: 3 // arr[3] == 3

Input: arr[] = {0, 2, 5, 8, 17}
Output: 0 // arr[0] == 0

Input: arr[] = {-10, -5, 3, 4, 7, 9}
Output: -1 // No Fixed Point

Solution

Use binary search to find out such an element where array[i] == i.

Suppose we are at index i , then there are three possibilities:

• A[i] < i , this implies that all the numbers at index less than i cannot be fixed, so we need to check in the interval (i+1, N)
• A[i] > i this implies that all the numbers at index greater than i cannot be fixed, so we need to check in the interval (0, i - 1) 
• A[i] == i this implies that the number is fixed , so output it.

Code
int fixed_point(int array[], int begin, int end){

if(begin > end)

return -1;

int mid = (begin + end)/2;

if(array[mid] > mid)

return fixed_point(array, begin, mid-1);

else if(array[mid]<mid)

return fixed_point(array, mid+1, end);

else

return mid;

}

Complexity

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

Subarray with Specific Sum

Given an unsorted array of nonnegative integers, find a continuous subarray which adds to a given number.

Examples:

Input: arr[] = {1, 4, 20, 3, 10, 5}, sum = 33
Output: Sum found between indexes 2 and 4

Input: arr[] = {1, 4, 0, 0, 3, 10, 5}, sum = 7
Output: Sum found between indexes 1 and 4

Input: arr[] = {1, 4}, sum = 0
Output: No subarray found

There may be more than one subarrays with sum as the given sum. Print first such subarray.

Solution

1. Take two indices start and end denoting the starting and ending index.,which initially point to first element A[0] and a variable sum which stored the current sum (=A[0]).
2. Now increase end until and unless sum becomes greater than required sum S. This is done because we cannot find S in a subarray whose maximum sum is less than S.
3. Now once sum becomes greater than S, we have chance to find a subarray with ending point as end. Therefore we can increase start until it is not greater than sum . Once it becomes smaller ,we are back to step 2. Now if no subarray exists for which sum is S, start will be eventually equal to end, so now the new problem will be array starting at start+1 and ending at end+1.

Code

int subarray_sum(int array[], int N, int S, int &start, int &end){

start = end = 0;
while(end < N && start < N){

while(current_sum < sum && end < N)

current_sum += array[end++];

while(current_sum > sum && start < N){

current_sum -= array[start++];

if(current_sum == sum)

return 1;

}

}
return 0;

}

Complexity

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

Constant Boundary Separation

Given an integer k and an sorted array A (can consist of both positive and negative numbers), output 2 integers from A such that a-b=k in O(n) time and O(1) space.

Solution

Idea is to take two indices i and j which initially point to the last element.Then

• If their difference is equal to K ,then output the required answer.
• If it is less than K , then only possible way is decreasing i , 
• If it is greater than K , then only possible way is decreasing j.

Code
int boundary(int array[], int N, int K, int *a, int *b){

int i = j = N -1;
while(i >= 0 && j < N && i <= j){

if(array[j] - array[i] == K){

*a = array[j];
*b = array[i];

return 1;

}
else if(array[j] = array[i] > K)

j--;

else

i--;

}
return 0;

}

Complexity

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

Circular Swap

Given three numbers a, b and c. Write a program to swap them circularly (as per following example) using only one single statement in any programming language.

Ex. a=10 b=20 c=30
Answer a=20 b=30 c=10

Solution :

a = a^b^c^(b=c)^(c=a);
This is equivalent to a = (a^b^c^c^a) = b along with the values of b and c being changed by b=c and c=a assignments.
This is an excellent answer and defeats the proposed ones in the reference.

Reference :
http://stackoverflow.com/questions/8635686/swap-three-numbers-in-single-statement

Integer Binary Roots

An integer obtained by reversing the bits of a given integer A is denoted as bit-rev(A). For example, bit-rev(25) = 19, because the binary represenation of 25 is 11001 and after reversing it becomes 10011, i.e. 19. Furthermore, bit-rev(26) = 11 and bit-rev(11) = 13.

A symmetric binary root of a given positive integer N is a positive integer A such that N = A * bit-rev(A). For example, a symmetric binary root of 50 is 10, because 10 * bit-rev(10) = 10 * 5 = 50. Note that 5 is not a symmetric binary root of 50. The number 286 has two symmetric binary roots: 22 and 26.

Write a function int symmetric_binary_root_count(N)

; that, given a positive integer N, returns the smallest symmetric binary root of N. The function should return −1 if N doesn't have any symmetric binary root. Assume that N is an integer within the range [1 ... 2,147,483,647].

For example, given N = 3245 the function should return 55.

Expected Complexities:

• worst-case time complexity is O(sqrt(N));
• worst-case space complexity is O(1).

Solution :

This problem is just integer factorization made more complicated. For a given natural number N, the problem is to determine the set of pairs of divisors (A, N / A) satisfying the predicate bit-rev(A) = N / A or bit-rev(N / A) = A.

The simplest algorithm of calculating pairs of divisors (A, N / A) is to begin with 1 and trial divide N by the counter value, up to floor(sqrt(N)). Calculating the bit-rev is O(1) because there are a finite number of bits in an integer represented on a computer. So, the process is O(sqrt(N)).

Code :

unsigned bit_rev(unsigned N){

unsigned result=0, i;
int max = sizeof(unsigned) * CHAR_BIT;

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

result |= (((N >> i) & 0x1) << (max - i - 1));

}

return result;

}

unsigned smallest_integer_binary_root(unsigned N){

unsigned result = 0, i;
unsigned sq = ceil(sqrt(N));

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

if(N%i == 0){

if(bit_rev(i) == N/i)

return i;

elseif(bit_rev(N/i) == i)

result = N/i;

}

}

return result;

}

Complexity :

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

Reference :http://stackoverflow.com/questions/8465519/binary-roots-of-an-integer

Random Pointer Reversal

Consider a Linked List with each Node, in addition to having a 'next' pointer also has a 'random' pointer. The 'random' pointer points to some random other Node on the linked list. It may also point to NULL. To simplify things, no two 'random' pointers will point to the same node, but more than 1 Node's random pointer can point to NULL.
Now we are required to reverse the direction of all the pointers (both the 'next' and 'random') of the Linked list. The constraint is the solution MUST be O(1) space complexity (A constant number of new nodes can be created but not proportional to the length of the list)

Solution :

Please refer to the following link for suitable answer :
http://stackoverflow.com/questions/8410714/reversing-a-linkedlist-with-nodes-having-a-random-pointer

Occurrence Count

Given a sorted array input[] of size N with possible duplicate integer elements. Devise an algorithm to find out the count of occurrences of a given number K.
Expected time complexity : O(log N)

Ex [1 3 3 4 4 4 4 4 5 5 6 6 7] K=4
Answer = 5

Solution :

We find first occurrence and last occurrence using binary search.
Then occurrence count would be the difference plus one.

Code :

int bin_search_first_occur(int *a,int low,int high,int data)
{
    int mid;
    while(high>=low)
    {
        mid=(low+high)/2;
        if((a[mid]==data && mid==low) || (a[mid]==data && a[mid-1]<data))
            return mid;
        else if(a[mid]>=data)
            high=mid-1;
        else
            low=mid+1;
    }
    return -1;
}
int bin_search_last_occur(int *a,int low,int high,int data)
{
    int mid;
    while(high>=low)
    {
        mid=(low+high)/2;
        if((a[mid]==data && mid==high) || (a[mid]==data && a[mid+1]>data))
            return mid;
        else if(a[mid]<=data)
            low=mid+1;
        else
            high=mid-1;
    }
    return -1;
}

int occurrence_count(int []input, int N, int K){

return bin_search_last_occur(input, 0, N-1, K) - bin_search_first_occur(input, 0, N-1, K) + 1;

}

Complexity :

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

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;

}