Coders Stop

Count the number of subsequence divisible by 6

2015-06-28T12:57:00.000+05:30

You are provided a string with only digits [0 - 9], your task is to count the number of subsequences of string divisible by 6.

For e.g. The given string is 1234566
The subsequences divisible by 6 are 12, 24, 36, 6, 6, 66
Hence the answer should be 6

The most obvious approach which comes is to generate all the subsequences and do a divisibility check and return the count satisfying the condition.
But it is too expensive and overall complexity is 2^n (where n is the size of the string)

Can we make it better?

Obviously the units places has to be even i.e among 2, 4, 6, 8, 0.
So the questions boils down finding the number of subsequences divisible by 3 and units digits as even.

So how can we find the number of subsequences divisible by 3?
Or when does the adding of a number at units place makes it divisible by 3 ?

Lets assume you have a subsequence in hand
a(1) a(2) a(3) ... a(n) % 3 = x (0 <=x <= 2)
so what if add another digit in front of it making it
a(1) a(2) a(3) ... a(n) a(n + 1) % 3 = y (0 <= y <= 2)
Now if you work out few examples we would get the following table

x	a(n+1)% 3	y
0	0	0
0	1	1
0	2	2
1	0	1
1	1	2
1	2	0
2	0	2
2	1	0
2	2	1

So by looking at the following table we can easily work out the code

#define MOD 1000000007

long long count(char * s) {
 long long len = strlen (s);
 long long ones = 0, twos = 0, threes = 0, ans = 0, t_ones, t_twos, t_threes, sum = 0;
 for (int  i = 0; i < len; i++) {
  int rm = (s[i] - '0') % 3;
  switch (rm) {
   case 0:
    t_ones = (ones + ones) % MOD;
    t_twos = (twos + twos) % MOD;
    t_threes = (threes + threes) % MOD;
    sum = threes + 1;
    ones = t_ones, twos = t_twos, threes = t_threes;
    threes++;
    break;
   case 1:
    t_ones = (ones + threes) % MOD;
    t_twos = (twos + ones) % MOD;
    t_threes = (threes + twos) % MOD;
    sum = twos;
    ones = t_ones, twos = t_twos, threes = t_threes;
    ones++;
    break;
   case 2:
    t_ones = (ones + twos) % MOD;
    t_twos = (twos + threes) % MOD;
    t_threes = (threes + ones) % MOD;
    sum = ones;
    ones = t_ones, twos = t_twos, threes = t_threes;
    twos++;
    break;
  }
  if ((s[i] - '0') % 2 == 0)
   ans = (ans + sum) % MOD;
 }
 return ans;
}

Overall complexity of the algorithm is O(n)

Searching words in a dictionary [Tries]

2015-03-13T02:37:00.001+05:30

Given a dictionary, on which the below operations are required

1. Update the dictionary
2. Find a word in a dictionary.

What are the possible options?
One of the most intuitive approach is to store the strings in a sorted manner.
Lets have a look at the complexity of the operations

If average length of the string in the dictionary is m and the number of entries in dictionary is n,
To build the sorted set of entries is O(m * n * log n)
and the complexity to find a word will be O(m * logn)

For large number of queries the algorithm is pathetically slow.

How can we improve this?

Can we have a deterministic algorithm, with the maximum complexity being dependent on the number of characters in the word and not on the number of entries.

Lets try to visualize how we search in the dictionary for a particular word.
Assuming the word to searched is 'program'
We first search if the word exist p, then inside p if r exists and so on...

So irrespective of the thickness of the dictionary we just searched based on some predefined marking of the characters which helps to search in the order of the length of the string.

Can we use the same concept in the programming?

If we build a tree of which each node has 26 child, each representing one of the characters, then we can uniquely identify each of the string starting from the root and following each of the characters.
The below figure speaks more than the thousand words,

Dont fall into the trap that only leaf nodes are the terminal nodes, infact each node can act as a terminal node.

So essentially the complexity to add a word or to query a word takes O(m), where m is the length of the string and is independent on the number of entries in the set!

[Flipkart Interview] Compress the string

2015-03-12T23:20:00.001+05:30

Given a string you are provided with the possible operations.
We can group the adjacent substrings, for e.g ABCABCBC can be compressed as
2ABC1BC or 1ABCA2BC

Among all the possible options, task is to find the resultant string with the minimum length.

In case if there are multiple solutions return the lexicographically smallest string.
So for the above example the solution would be 2ABC1BC

Another example would be
FLFLAFLAFLAF
Solution: 1FLF3LAF

Approach:

One obvious approach is to find all the possible compressions of the string and then find the one with the minimum length.

So how do you achieve this? We need to find the repetitive substrings in sequence and perform it recursively. Well it is an awful exponential algorithm.

So how do we improve this ?

Find the pivot element in the rotated sorted array

2014-03-02T20:48:00.000+05:30

A sorted array is rotated around a pivot element. Find the pivot element in the rotated sorted array.

Analysis

Lets start with an example
Original array:           2, 4, 6, 8, 9, 10, 12, 15
Rotated array:           10, 12, 15, 2, 4, 6, 8, 9
Output:    3

One important observation is that the pivot element lies between two elements i, j iff i > j and a[i] < a[j]
The ith element is the pivot element iff a[i-1] > a[i] < a[i+1]

With the above two observations we can modify the basic binary search technique to find the pivot element

Below piece of code returns the pivot element

int pivot(int * a, int len) {
    int l = 0, r = len - 1;
    if(a[l] < a[r])
        return 0;
    while (true) {
        if(l == r) return l;
        int m = (l + r)/2;
        if(a[m] < a[m-1] && a[m] < a[m+1])
            return m;
        if (a[m] > a[r])
            l = m + 1;
        else r = m;
    }
}

Remove the duplicate elements in the string

2014-02-23T00:34:00.000+05:30

Given a string, inplace remove the duplicate elements form the string.
For e.g. the given string is "codersstop is a programming blog"
Result: "coderstp iagmnbl"

Approach:

Maintain a lookup table of the 256 entries to mark the occurrence of each of the characters, and only copy the elements which are occurring for the first time.
Below snippet of code removes the duplicate elements from the string

void removeDuplicate(char * s) {
    char a[256] = {0}, c = 0;
    int len = strlen(s);
    for(int i = 0; i < len; i++) {
        if(a[s[i]] == 0) s[c++] = s[i];
        a[s[i]] = 1;
    }
    s[c] = '\0';
}

Overall time complexity is O(n) and space complexity O(1)

Minimum distance between the two nodes of tree

2014-02-03T00:37:00.005+05:30

Given a binary tree(not BST) and two nodes in the tree(not necessarily leaf nodes), find the minimum distance between them.

Approach:

The minimum distance can be computed by first finding the LCA of the two nodes, and then finding the heights of the all the three nodes(2 nodes + 1 LCA) from the root.
(For finding the LCA in the binary tree refer to the previous post
and finding the height of the element in the binary tree is self explanatory.)

Then the total distance can be computed as
height(root, p) + height(root, q) - 2 * height (root, r) + 1;

int lca(struct tree * root, struct tree * p, struct tree * q, struct tree  *& res) {
    if(root == NULL || res != NULL)
        return 0;
    int found = 0;
    if(root == p || root == q)
        found = 1;
    found += lca(root->left, p, q, res);
    found += lca(root->right, p, q, res);
    if(res == NULL && found == 2)
        res = root;
    return found;
}

int height(struct tree * root, struct tree * p) {
    if (root == NULL)
        return -1;
    if(root == p)
        return 0;
    int r = max(height(root->left, p), height(root->right, p));
    return r >= 0 ? r + 1 : r;    
}

int minDist(struct tree * root, struct tree * p, struct tree * q) {
    struct tree * r = NULL;
    lca(root, p, q, r);
    if(r == NULL)
        return -1;
    cout<< r->data << endl;
    return height(root, p) + height(root, q) - 2 * height (root, r) + 1;
}

LCA for a binary tree

2013-10-19T21:37:00.002+05:30

Given a binary tree(not a binary search tree) find the LCA of the 2 given nodes.

The lowest common ancestor(LCA) for the nodes u and v is defined as the lowest node w in tree that has both u and v as the descendants (where a node can be a descendant of itself).

Approach:

Lets consider the below tree

LCA of node 30, 5 is 100
LCA of node 15, 50 is 50
and so on

Its easy to visualize that the bottom up approach is the way to go.
Populate from the bottom to up the number of nodes matched with the target nodes and the first level to find both the nodes is the required LCA.

The short code snippet which finds the LCA of the two nodes is given below

int lca(struct tree * root, struct tree * p, struct tree * q, struct tree  *& res) {
    if(root == NULL || res != NULL)
        return 0;
    int found = 0;
    if(root == p || root == q)
        found = 1;
    found += lca(root->left, p, q, res);
    found += lca(root->right, p, q, res);
    if(res == NULL && found == 2)
        res = root;
    return found;
}

A closer look at Coin Change

2013-10-16T17:26:00.000+05:30

Coin change has been a very famous computing problem which can be easily solved by Dynamic programming.

So what is coin change ?
If we want to make change for

N

cents, and we have infinite supply of each of valued coins, how many ways can we make the change? (The order does not matter.)

For example, for

N = 4, S = {1,2,3}

, there are 7 possible solutions:

{1,1,1,1},{1,1,2}, {1, 2, 1}, {2, 1, 1}, {2,2},{1,3}, {3, 1}

.

So how to compute the number of ways efficiently?

Lets assume you know the number of ways to generate the sum 1, 2, 3 , can you find the number of ways to generate 4?

Yes, you can, indeed you have just broken the problem into the subproblems, a basic paradigm of the dynamic programming.

Let assume F(n) denotes the number of solutions possible.
So F(4) = F(3) + F(2) + F(1)

In general if S[i] denotes the denominations of the coins then

The below piece of code generates the number of combinations for a particular sum.

int coin_change_infinite(int s[], int n, int val) {
    int * a = (int *) calloc(1, sizeof(int) * (val + 1));
    int res;
    sort(s, s + n);
    a[0] = 1;
    for(int i = 1; i <= val; i++)
         for(int j = 0; s[j] <= i && j < n; j++)
                 a[i] += a[i - s[j]];
    res = a[val];
    free(a);
    return res;
}

Overall running time for the algorithm is O(n*c) (n is the value for which the denominations needs to be made and c is the types of denominations available.) and space complexity is O(n)

Largest area in a Histogram

2013-07-05T01:10:00.003+05:30

Find the maximum area of a rectangle that fits entirely in the Histogram.

For e.g in the below histogram the maximum area of the rectangle is 2 * 80 = 160

The length of each bar will be the input, and the width of each bar is same, 1

Approach:

The naive approach can be to select one histogram at a time, find the maximum area which can be formed with this, finally return the maximum value over all the histogram.

Time Complexity O(n^2), Space Complexity O(1)

Can we do better. Lets have a look if we are computing some of the results over and over or if any of the computations are unnecessary.

Some of the key observations are:
The area of the neighbouring groups is equal to (min height of the bar in group * width of the group)

This means that we need to calculate the area formed by each minimum bar encountered so far, calculating the max of all such areas will give us the desired result.

So if we have the bars in the order given as
9, 4, 10, 12, 16, 14, 8, 5, 1

So we need to calculate the area at the points, 4, 14, 8, 5, 1
for the ith bar which has the height h
max area = (h)*(number of contiguous bar to the left and right which has height <= h)

and the max of this is 8*5 = 40 (which is the max area of the rectangle completely inside the histogram)

So what is the data structure we can employ,
Stack seems to be an obvious choice since we are always concerned with the element just pushed(which is the top of the stack)
Below is the piece of code which calculates the max area

int maxArea(int a[], int n ) {
    stack<int> s;
    int max = 0;
    for(int i = 0; i < n;i++) {
        while(!s.empty() && (a[i] <= a[s.top()])) {
            int h = s.top();
            s.pop();
            int l = s.empty() ? 0 : s.top() + 1;
            int m = (i - l) * a[h];
            if(m > max) max = m;
        }
        s.push(i);
    }
    while(!s.empty()) {
        int h = s.top();
        s.pop();
        int l = s.empty() ? 0 : s.top() + 1;
        int m = (n - l) * a[h];
        if(m > max) max = m;
    }
    return max;
}

Since every bar is inserted and removed only once, time complexity O(n).

[Amazon Online test] Sort an array containing 0, 1 & 2

2013-06-02T17:36:00.001+05:30

Given that an array consists of only 0s 1s and 2s sort the array in one pass.

Approach:

Lets view the problem if the constraint of one pass wouldn't have been there
Scan over the array and count the number of 0, 1, and 2.
Now initialise the array with the 0, 1, 2 with the number of elements, the idea is similar to the counting sort.

To solve the above problem in one pass we can use the famous Dutch national flag algorithm.
The basic idea is to traverse over the array and keep track of the current 0s and 2s and the read pointers(initialised with -1, n and 0). Now traverse the array and keep swapping the current element in the respective buckets of interest.

The implementation is given by

void sort(int a[], int n)
{
   int zero = -1;
   int two = n;
   int current = 0;
 
   while(current < two) {
      switch(a[current]) {
         case 0:
           swap(&a[zero++], &a[current++]);
           break;
         case 1:
           current++;
           break;
         case 2:
           swap(&a[current], &a[two--]);
           break;
      }
   }
}

[Expedia Interview] Intersection of two link list

2013-06-02T10:29:00.001+05:30

Given two link lists intersecting in the following manner

check whether the two list intersect or not, if it does find the point of intersection.

Approach:
First gotcha in the problem is that such a linked list cannot exist. Since it is a singly linked list hence a node cannot have 2 next pointers.
So the problem reduces to the Y shaped linked list.

Now we observe that the pointer D is common to both the list and to find if the list intersect or not it is sufficient to find if both the list have a common pointer among their start or end pointers.
Finding the point of intersection is now trivial and left to the reader.

Cumulative Sums of elements in an array[Binary Indexed Tree]

2013-06-01T12:23:00.001+05:30

Given a array and with below possible operations
Update: Add a value to a index a
Query: Get a cumulative sum from a range a to b
What is the data structure you would employ and what will be the time complexity of the update and query operations.

Approach:
The basic idea of any of the algorithm is to store/update the sum of the subparts and compute the sum in a range by adding up the relevant subparts.So for e.g a common data structure Segment tree creates a tree where the parent stores the sum of the child elements.

So each node in the tree takes care of the sum in a particular range.

Once you create a static Segment tree the update and the query operation should be easy.

Can we avoid the extra space incurred and rather use the given array elements as the nodes to hold the sum in a range.
Infact a famous data structure Binary Index Tree(also known as Fenwick tree) works on the same principle and is relatively simple to code and debug.

So how do one assign the parent child relationship in the tree. Since now there are no internal node to hold the sum of a range like (0,4) we can infact use the 4th index to hold the sum of (0, 4), the same is true for the
3 holding the sum of (3,3)
10 holding the sum of (9,10)
12 holding the sum of (9,12)
16 holding the sum of (0,16)
So to generalize each index index holds the sum of elements in range
((index - 2^r + 1) , index) where r is the right most bit postion set in index.

I would strongly suggest to go over the above logic once more and write a pseudo code for the update query.

Kudos if you were successful to write the working piece of the code.

So how do we add a delta to a index, we need to update all the elements which are using its value.
Also to extract the rightmost bit we can use
n & -(n) //Proof is left to reader :)
Below is the terse piece of code which updates the delta at a particular index

void update(int index ,int delta){
   while (index <= N){             // N is the total number of elements in the array
       A[index] += delta;
       index += (index & -index);
   }
}

To initialize the array we can intialize all the array elements to 0 and iteratively call the update function for each of the index.

To find the sum of elements in the range (0, index), the below function can be used

int query(int index){
 int sum = 0;
 while (index > 0){
  sum += A[index];
  index -= (index & -index);
 }
 return sum;
}

To find the sum in a given range (a,b), we can compute it by

int sum = query(b) - query(a-1);

Finally the time complexity of each of the update, query is O(log2(N))

Fibonacci Series Part II

2013-02-23T16:53:00.005+05:30

In the last post we discussed about evaluating the nth Fibonacci number in logarithmic time O(logn).

Lets us look at another problem on the similar lines.
Given a series
F(n) = F(n-1) + 2*F(n-2) + 3*F(n-3) + F(n-4)

Lets try to solve the problem in the similar fashion,

The matrix multiplication looks like below,

The running time to compute the nth term of the series will be

(sizeof(M) ^3) * log(n) = 64*log(n)

Can we optimize it further ?

Lets again go over the series once more
F(n) = F(n-1) + 2*F(n-2) + 3*F(n-3) + F(n-4)
F(n-1) = F(n-2) + 2*F(n-3) + 3*F(n-4) + F(n-5)
F(n) - F(n-1) = F(n-1) + F(n-2) + F(n-3) - 2*F(n-4) - F(n-5)
After some more rearrangement it reduces to
F(n) = 2* F(n-1) + F(n-2)
Some of you must have recognized it as Pell's number.

So the matrix multiplication reduces to

So the final runtime reduces to O(8* log(n))

Fibonacci numbers [Matrix exponentiation]

2013-02-23T01:58:00.003+05:30

Fibonacci numbers has been a very famous sequence represented as:

F(n) = F(n-1) + F(n-2)
with F(0) = 0, F(1) =1
So what if you need to find the nth term of the series. Its easy to view the recursive nature of the problem.

The code snippet would look something like

int fib(int n) {
    if(n<1) return 0;
    if(n == 1) return 1;
    return fib(n-1) + fib(n-2);
}

Lets try to analyse the sequence of calls for calculating the F(4)

Clearly we are computing the same value over and over, and the size of computations will grow exponentially with the increasing value of n. Can we reuse the same value computed before ?

Yes, infact we term this as a technique called memorization or Dynamic programming.
The trick is to store the values as you compute and look up the value before computing it.

The iterative solution to compute the nth Fibonacci is as follows

int fib(int n) {
    if(n < 1)
        return 0;
    int *a = malloc(sizeof(int) * (n+1));
    a[0] = 0; a[1] = 1;
    for(int i = 2; i <= n; i++)
        a[i] = a[i-1] + a[i-2];

    return a[n];      
}

The above implementation reduces the time complexity to O(n) with a overhead of the O(n) space.

Can we still do better ?
Is it necessary to generate all the previous Fibonacci numbers ?
Let's try to rearrange the formulas to generate the series
F(2) = F(1) + F(0)
F(3) = F(2) + F(1) = 2*F(1) + F(0)
F(4) = F(3) + F(2) = 3*F(1) + 2*F(0)

It appears that every term in the series can be broken down to a form of
F(n) = p*F(1) + q*F(0)

So the task boils down to find the p & q for a particular given 'n'.

Its easy to realize that the subsequent terms can be generated using the matrix multiplication.

So we can calculate the nth Fibonacci number as

Can we evaluate the power(a,b) in sub-linear time ?
The answer is yes, we will be using the same technique again of reusing the old values computed before.
May be the old computed values concept may not be straightforward.
Lets take a closer look on how to calculate power(a,.b)
power(a, b) = a*a*a*a*.........*a (b times)
can you figure out the overlapping solutions.

We can rewrite the above equation as
power(a,b) = power(a,b/2) * power(a, b/2) If b is even
power(a,b) = power(a,b/2) * power(a,b/2) * a If b is odd

By now you would have realized that the number of multiplications required will be ceil(log(b))
(where log is evaluated in base 2)

Using the same approach we can evaluate the power(matrix M, n) and number of operations needed will be
(sizeof(M) ^3) * log(n)

In our case it will be 8* log(n)

Hence the nth Fibonacci number can be calculated in O(log(n)). Writing the code snippet for the same is left as an exercise to the reader.
Comments invited :)

[Google Interview] Query the most frequent element

2013-01-14T13:20:00.002+05:30

Design a data structure which supports the below operation
Insertion of an integer
Deletion removes the element with highest frequency at that instant. In case of tie, go by the FIFO startegy.

For e.g

Insert 5,6,5,7,5,7
1st removal -- 5,6,5.7,7
2nd removal -- 5,6,5,7,
3rd removal -- 5,6,7
and so on

Perform both the operations in O(1).

[Amazon Online test] Number of swaps required

2012-09-23T23:18:00.003+05:30

Given an array containing 0 & 1 only, You have only 1 operation i.e. you can swap theadjacent elements in the array. Find the minimum number of operationsrequired to sort the given input array.

A = (0,0,1,0,1,0,1,1)

Min Operations: 3.

Approach:
Let's start with some of the trivial test cases.
(1,0) -- Number of swaps = 1
(1,1,0) -- Number of swaps = 2
(1,1,0,0) -- Number of swaps = 4
So an important observation comes that given an array of the type
(1, 1, 1, ... n times, 0, 0, 0, .. m times)
Number of swaps = n*m (This is based on the fact that each 0 has to be pushed(swapped) back m number of time)

So iterate over the array and keep track of the 1's encountered, whenever we hit a 0 we add the result(number of swaps) with the number of 1's encountered so far(as 0 has to be swapped with each of them order to reach a configuration like (0,0,..., 1, 1, 1...))

Now the piece of code will look like

int swapSort(int *a, int n) {
  int swaps = 0;
  int noOfOne = 0;
  for (i =0;i<n;i++) {
    if (a[i] == 1) 
      noOfOne++;
    else
      swaps += noOfOne;
  }
  return swaps;
}

[DirectI Online test] Number of substrings containing atmost 2 different characters

2012-09-23T23:14:00.002+05:30

Given an input string, find the number of substrings which contains atmost two different characters.
E.g - aabc Ans: 8

Approach:

Lets start with a simple approach,

The most naive solution would be to iterate over all the possible substrings of the array
(~ n ^ 2) and then validate if the substrings have atmost two unique characters.
The complexity will go over to O(n^3), proof is left to the reader.

Can we do it better, indeed yes,

An important observation is that we should break when we have the distinct characters greater than 2 and we should not be computing the further substrings with the same prefix.
Also we need not find the distinct characters in each substring, rather we can just compute the largest length substring with a starting index with atmost 2 different characters, and length of the substring found is number of substrings which can be formed staring for a given index.
For e.g. aabbac
For the 0th index the aabba is the longest substring with atmost 2 different characters,
and indeed the number of strings which can be formed starting with 0th index is 5

which are a, aa, aab, aabb, aabba.

The above approach can be implemented by summation of the largest substrings of atmost 2 characters possible with each index element

The complexity boils down to O(n^2)

Can we still do better ?

A little pen and paper work will make us realize that there are lot of computations which are done repeatedly.

Once we know that the largest substring starting at index i is substring (i,j) that contains at most 2 elements.

Now to figure out the largest substring for the index i+1, should we again compute from i + 1 to j, but infact we just computed in previous iteration so why not store the result and use it back. This technique is often termed as memorisation in the computing terms.

So the algorithm looks like

Keep track of the characters and their count till the distinct characters are less than 2

At each successive iteration we need to remove the last previous index from the tracking list.

Return the result as the sum of the largest substrings formed at each index.

The running time complexity reduces to O(n)

Below is a implementation of the above logic in C

int isInArray(int a[2][2], int n, int k) {
   if(n > 2) return -1;
   if(n == 1) {
        if(a[0][0] == k) {
           a[0][1]++;     
           return 1;

        } else {
           a[1][0] = k;
           a[1][1] = 1;
           return 2;
        }
   } else if(n == 2) {
       if(a[0][0] == k) {a[0][1]++; return 2;}
       if(a[1][0] == k) {a[1][1]++; return 2;}

       return -1;
   }
   return -1;
}
int removeFromArray(int a[2][2], int k) {
    if(a[0][0] == k) {
        a[0][1]--;
        if(a[0][1] <= 0) {
           a[0][0] = a[1][0];
           a[0][1] = a[1][1];

           return 1;
        }
        return 2;
    } else if(a[1][0] == k) {
        a[1][1]--;
        if(a[1][1] <= 0) {
           return 1;
        }
        return 2;
    }
    return 2;        

}
int numberOfSubstrings ( string A ) {
    int len = A.length();
    int res = 0, j = 1, c = 1, a[2][2];
    a[0][0] = A[0]; a[0][1] = 1; 
    for(int i=0;i<len;i++) {
        for (;j<len; j++) {

           c = isInArray(a, c, A[j]);
           if(c == -1) break;  
        }
        c = removeFromArray(a,A[i]);
        res = (res + j-i);
    }
    return res;
}

[Amazon Interview] Compare the BSTs

2012-03-22T12:16:00.005+05:30

Given two unsorted integer arrays, your task is to compare the BST formed by both the arrays.

e.g [3 2 1 4 5] & [3 4 2 5 1]
when the BST is formed by taking the elements from the left, both BST turn out to be same.

         3
        / \
      2 4
   /         \
1           5

Expected time complexity O(n).

Approach:
First observation is that the first element of the array forms the root of the BST.
So the first element needs to be equal of both the arrays.
Now the next left element which gets added to the BST is the next smaller element in the array, and same is true for the next right element in the BST.

So the sequence of the elements of the less than the the first element should be same in both arrays

And the same is true for the elements greater than the root element

So if the first array contains elements {9, 14, 8, 11, 4, 7, 15, 10, 6}
so any array which forms the same BST should have the elements of the sort
{9, ., 14, ..,11, .., 15, .., 10} & {9, .., 8, .., 4, .., 7, .., 6}

Both the preconditions can be verified trivially by two scans over the arrays.

[Amazon Online Test] : Finding the inorder successor

2012-02-08T11:49:00.000+05:30

Given a binary search tree with the following node structure

struct tree {
    int data;
    struct tree *left;
    struct tree *right;
    struct tree *next;
};
The next pointer of each node is pointing to null.
Write a code to initialize the next pointer of each node to its inorder successor.

Approach:

Traverse in the BST in reverse inorder manner(i.e. postorder) and initialize the inorder successor as the last element visted.

Below piece of code initializes the next element to the inorder successor.

void inorder_successor(struct node * root) {
     static struct node * current = NULL;
     if(root == NULL)
         return;
     inorder(root->right);
     root->next = current;
     current = root;
     inorder(root->left);
     return;
}

Euler problem : Finding the minimum sum

2012-02-02T00:06:00.000+05:30

In the 5 by 5 matrix below, the minimal path sum from the top left to the bottom right, by only moving to the right and down, is indicated in bold red and is equal to 2427.

131	673	234	103	18
201	96	342	965	150
630	803	746	422	111
537	699	497	121	956
805	732	524	37	331

This can be solved by an easy application of the DP.
A nice variation of the above problem is to find the minimal path sum from the top left to the bottom right, by moving left, right, up, and down, is indicated in bold red and is equal to 2297.

131	673	234	103	18
201	96	342	965	150
630	803	746	422	111
537	699	497	121	956
805	732	524	37	331

Euler Problem: Pandigital number

2012-01-24T23:57:00.002+05:30

Multiplying 9 by 1, 2, 3, 4, and 5, gives the pandigital, 918273645, which is the concatenated product of 9 and (1,2,3,4,5).

What is the largest 1 to 9 pandigital 9-digit number that can be formed as the concatenated product of an integer with (1,2, ... , n) where n >1?

Its fun to solve the problem without the use of code :)

[Amazon Online Test] Find the nodes at k distance.

2012-01-21T13:21:00.001+05:30

Given a tree with the root and a particular node, find the nodes which are atmost at a distance of k from the particular node and print them in sorted order.

Approach:

Lets say the given tree is

And the given node is of the value 50, and distance k = 3
Then the desired result is 5, 30, 50, 70, 90

The task can be broken down to below sub tasks
1.To find the desired node
2. Find and store all the elements in its vicinity of distance k
3. Sort the nodes by value and print the same.

Obviously the recursion is the key, we recursively iterate over the nodes of the tree and as soon as the target node is found, we publish this result to the calling function so that all the nodes can be stored

The below code snippet prints the nodes at a distance of atmost k.

int printNodeAtKrec(struct tree * root, struct tree * target, int k, vector <int> &v, int n) {
    if(root == NULL)
        return 0;
    int left = 0, right = 0, level = n;
    if(root == target)
        level = k;
    left = printNodeAtKrec(root->left, target, k, v, level - 1);
    level = max(level, left);
    right = printNodeAtKrec(root->right, target, k, v, level - 1);
    if(right > 0 && level < 0) {
        level = right;
        printNodeAtKrec(root->left, target, k, v, level - 1);
    }
    if(level > 0)
        v.push_back(root->data);
    return level - 1;
}

void printNodeAtK(struct tree * t, struct tree * r, int k) {
    vector <int> v;
    printNodeAtKrec(t, r, k + 1, v, 0);
    sort(v.begin(), v.end());
    for(int i = 0; i < v.size(); i++)
        cout<<v[i]<<endl;
}

Calculating the multiplicative inverse

2011-12-20T09:56:00.000+05:30

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

long long res = 1;
for(int i = 0; i < n; i++)
    res *= a[i];
for (int i = 0; i < n; i++)
    res /= b[i];
res %= MOD;

But, wait there is a catch, what if a1* a2 * .... overflows the long long range or the datatype under use?

So what are the possible options. Some people might fall into the trap

res = (res * a[i]) % MOD;
res = (res /a[i]) % MOD;

While first statement is perfectly correct, but the subsequent divisions operations are incorrect.
You can pick some of the examples to reason it out!

So moving ahead, one most common 'trick' which would hit us would be, how we used to perform these operations in our early school days.

Get the prime factorizations of a1, a2, a3...., b1, b2, b3,
And then cancel out the common factors,
Then the problem reduces to find the multiplication of the left out factors(lets say c[]) which can be done by

for(int i = 0; i < n; i++)
    res = (res * c[i]) % MOD;

But sooner or later you would realise, this easy looking task is actually quite expensive. Infact the good methods would take around O(sqrt(n)) per number to factorize itself.
So for (n + n) numbers with average value of x the overall complexity would be

n * O(sqrt(x))

With this approach as the average value x increases the code would timeout for most of the cases.

So whats next? Most of us who are familiar with the set theory would be thinking about the possibility of computing the multiplicative inverse.
So formally, for a number x, a number y is a multiplicative inverse if
(x * y) % N = 1 or
(x * y) == 1(MOD N)

A naive implementation to compute the inverse would be to try y for all the numbers between 1 to N - 1 and find the suitable match.

Well, there is a Fermat's Little theorem which could help us here, if MOD is prime number then the inverse can be given by

The a ^ n can be calculated in O(log n) time, for details you can refer here

So the overall complexity boils down to n * O(log M)

So what do we do if the MOD value is not a prime number? Can we solution this based on Fermat's theorem? This is left as an exercise to the reader :)

Sidenote, there are several other methods to achieve in a more optimised way.

[Amazon Interview] Finding the shortest path

2011-12-10T17:29:00.001+05:30

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 ?

Maximising the duration

2011-10-21T06:18:00.000+05:30

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.