Tuesday, December 20, 2011

Calculating the multiplicative inverse

Given a number x, find its multiplicative inverse y for a given modulo N
i.e. (x*y) == 1(MOD N)

Where the multiplicative inverse is useful?

Lets assume we need to compute ((a1 * a2 *....)/(b1 * b2 * .....)) mod N
1 simple way is to compute the above expression as

Saturday, December 10, 2011

[Amazon Interview] Finding the shortest path

Given a matrix having non negative integers you have to find the shortest path from one point to another within the matrix. The cost of path is all the matrix entries on the way. You can move in any direction (up, down, left, right, diagonally)
e.g.
5 9 10 1
3 7 4 4
8 2 1 9
So shortest path from (0,0) to (2,2) - 5+3+2+1 = 11

Approach:

The matrix can be easily converted to a graph with each element having its neighbors as the up, down, left, right and diagonal elements.
Just pass this graph into any one of the Single source shortest path algorithm and you will find the minimum distance between the two elements 

Can we do better ?

Friday, October 21, 2011

Maximising the duration

There is a TV avid person, who wants to spend his maximum time on TV. There are N channels that telecast programs of different length at different timings. Find the program and channel number so that the person can spend his max time on TV. If the person watches a program, he watches it completely.

For e.g
Channel1:
prg1: 8:00 am - 9:00am
prg2: 9:30 am - 12:00 am

Channel2:
prg1: 8:15 am - 9:30am
prg2: 9:30 am - 11:45 am

In this case, between 8:00 AM to 12:00 noon, the answer is:

ch2/prg1 + ch1/prg2

Approach:

Sort the programs with the end times. And then apply the greedy algorithm to find the maximum duration.

Saturday, August 27, 2011

Find a element in an 2D array

Given a 2D array of size NxN, whose rows and columns are sorted individually in ascending order from the top left corner.
Now given a number X you need to find the position of the number in the array.


Now lets say the element X(INT_MAX) in the array signifies the empty space in the array and lies always at the bottom right. How would insert an element by replacing this space in such a place so that the property of the array is maintained. (The only operation allowed is to swap two adjacent elements which share an edge.)

Similarly how would you delete an element from the array and replace it with the X

Friday, April 1, 2011

Largest elements in the array to its right

Given an array of n elements find all the elements in the array such that it is greater than all the elements to its right. For e.g
array is {4,8,9,5,1,2,3}, numbers are 9,5 and 3

Approach:

The trivial implementation would scan the integers from index 0 to n - 1 and for each index x we can compute if it is maximum among all the elements with index > x.

This implementation is pretty slow, with overall complexity O(n^2)


Monday, March 28, 2011

Find the absolute value of an integer

Given an integer find the absolute value without using conditional statements

Approach:
The last bit (31st bit in case of 4 byte variable) contains the sign information. If you update the value of the 31st bit, the job is done.

Saturday, January 29, 2011

Lexicographically smallest string

Given a group of strings, find a string by concatenating all the strings in any order which produces the lexicographically smallest string.
For e.g strings are acc bcc abb
So the string formed should be abbaccbcc

Approach:

By looking at the problem the most quick and easy solution seems to sort the strings and concat them.
But wait, will it really work?
Lets say, strings are aba and ab 
With the above approach the solution would be ababa
But infact there exists a lexicographically smaller string and that is abaab.

So what went really wrong? Take a minute to think it through and how to overcome it.

Sunday, January 23, 2011

Google Interview Questions

You are provided with four possible operations that can be done on the editor(each operation requires 1 keyboard hit)

1. A
2. Ctrl+A
3. Ctrl+C
4. Ctrl+V
Now you can hit the keyboard N times and you need to find the maximum number of A's that can be printed. Also print the sequence of keyboard hits.

Approach:

Lets start with the base cases, 
Its trivial to have the observation for n <= 6, the max number of A's = n
How about n = 7? If you computed the answer as 8 or 9, open an editor and type the sequence and validate the answer. This is a common gotcha thinking that Ctrl + A, Ctrl + C, Ctrl + V would double the characters but it doesn't :). Infact the characters remains intact while the next Ctrl + V would infact copy the same sequence.


Further thoughts, can you arrive at an optimal number which you can go ahead and copy over and over, or you need a calculated strategy where you refresh your clipboard with current contents. Once you are able to identify this, you should be able to arrive at a proper formative answer

Saturday, January 22, 2011

Merge two sorted arrays

Given two sorted arrays A and B with X and Y elements. The array A has X+Y space. Now merge array A and B in the array A with minimum number of steps and without using any auxiliary array space.

Approach:

Lets start with an example with array
A = {7, 9, 14, 19, _ , _, _, _, _}
B = {4, 12, 17, 18, 23}

So, the final configuration should be
A = {4, 7, 9, 12, 14, 17, 19, 23}

The simplest naive approach comes from the concept of the insertion sort, compare iteratively successive elements of array B to the elements in array A and if it is greater, then move all the elements in A by one position forward from that index and insert the element B in the current position. Code is left as an exercise to the reader.

Friday, January 21, 2011

Find the second largest number in an array

Given an array of integers find the value of 2nd largest element in minimum number of comparisons.

Approach

Well its trivial to prove that the lower bound of the algorithm will be O(n) (Since the array is unordered so we need to scan the values atleast once to figure out the solution)

What can be the possible solutions?


Number of digits

Given a positive number n find the number of digits in factorial n. 'n' can be very large (may be 10^4) so consider the case of the overflow.

Approach: 
Lets analyse how we can find the number of digits in any give number
If the given number is x = 10^y (x being an integer and y being a float)
The number of digits = floor(y) + 1
So y = log10(x)

Now to find the number of digits in n!, we need to find the
y = log(n!) = log(1*2*3*4.......*n) = log(1) + log(2) + log(3) + ......+ log(n)

Sunday, January 16, 2011

Number of pairs whose sum equals k

You have an integer array and a number k, find all the pairs of numbers from the array whose sum is equal to k.
What will be the approach if the numbers in the given array are sorted and unsorted?



Approach: 
There are myraid number of approaches to attack this problem.
Lets take the case when the array is already sorted.
One of the approaches can be to iterate over each element let say a[i] = x, then we need to figure out if a number k - x exists or not in the array

We can very well search for the element in the array in O(n) making the overall complexity O(n^2).
But wait, since the array is already sorted we could have just performed a binary search over the array to search a given element.
This reduces the overall complexity to O(n*logn)

Can we improve the approach?
Well, there is an important observation that if we pick the two extreme indexes of the array and sum it up, there are 3 possibilities

1. Sum is equal, bingo :)
2. Sum is less than the target k, 
3. Sum is greater than target k

For the case 2, if there exists a pair, it has to be achieved by increasing the sum, i.e by moving the left index ahead.
For the case 3,  if there exists a pair, it has to achieved by decreasing the sum, i.e by moving the right index behind.
For the case 1, you can move any index.
Following the above approach you can figure out all the possible combinations.

So how about the time complexity?
Each element is accessed only once, hence the overall complexity turns out to be linear O(n)
Below piece of code just does the job


void printPairs(int *arr, int n, int k) {
    if (n < 2)
       return;
    int front = 0, back = n - 1;
    while (front < back) {
        if (arr[front] + arr[back] == k) {
           cout << front << " " << back << endl;
           if (back > 0 && arr[back - 1] == arr[back]) back--;
           else front++;
        } else if (arr[front] + arr[back] < k) {
            front++;
        } else {
            back--;
       }
    }
}


In case the array is not sorted?
Well we can sort the array in O(nlogn) and then apply one of the above approaches, the overall complexity would be O(nlogn)

But is it necessary to sort?
If you have the luxury, you can easily push the elements in the hash, and then look for each element x, if there exists an element k - x?
Safely assuming the Insertion and lookup complexity of the hash implemention to be O(1), the overall complexity of the algorithm would be O(n)

Tuesday, January 11, 2011

Binary array !!!

Given an array of 0's and 1's. only, find the maximum length of the subarray such that the number of 0's and 1's in that subarray are equal.

Sunday, January 2, 2011

Maximum sub array revisited !!!

Given an array of positive numbers, find the maximum sum of a subsequence such that no 2 elements in the sequence should be adjacent in the array.
For e.g
For an array  3 2 5 10 7 function should return 15

Approach:

If we figure out all the combinations in which no two elements are adjacent and pick the maximum sum, our job would be done.
A simple recursive algorithm would perform the job



int maxSum(int *a, int size, int idx, int sum) {
    if (idx >= size)
        return 0;
    return max (maxSum(a, n, idx + 1), a[idx] + maxSum(a, n, idx + 2));
}

But wait how about the complexity? The order would be equal to number of combination processed, which would be exponential in nature.

So how do we reduce it? If we observe carefully many of the subproblems are repeated and computed over and over (To gain more insight on the repeating subproblems refer this link). 
Indeed it is a dynamic programming problem and storing the results of the subproblems would improve the complexity considerably. 

Below is short snippet code for the same

int maxSum(int *a, int size, int idx, int sum) {
    if (idx >= size)
        return 0;
    if (mem[idx + 1] == 0)
        mem[idx + 1] = maxSum(a, n, idx + 1);
    if (mem[idx + 2] == 0)
        mem[idx + 2] = maxSum(a, n, idx + 2);

    return max (mem[idx + 1], a[idx] + mem[idx + 2]);
}