Sunday, September 30, 2012

Nearest sibling of a node

Find the nearest sibling of a given node in a tree. Nodes on same level are siblings of each other.
_________A_________
_____B________C____
___D___E____H_____
__F_____G__I_______
Nearest sibling of G is I

Strategy:

Do breadth first traversal of a tree ..
For this, we need one FIFO queue . Starting from root of the tree, go on queuing nodes in a queue at each level, then dequeue the front node and enqueue it's children and so on ...
In above example,
1. Enqueue A - Queue = A
2. Dequeue A and Enqueue B and C - Queue = B C
3. Dequeue B and Enqueue D and E - Queue = C D E
4 .Dequeue C and Enqueue H - Queue = D E H
5. Dequeue D and Enqueue F - Queue = E H F
6. Dequeue E and Enqueue G - Queue = H F G
7. Dequeue H and Enqueue I - Queue = F G I
8. Dequeue F - Queue = G I
Hence, in the queue we can see that nearest sibling of G is I.

Reconstruct BST again !

All elements of a BST are multiplied by -1. Convert it to a BST once again.

Build the tree from ancestor matrix

A tree is represented as a matrix where a(i,j) = 1 if j is ancestor of i. Build the tree.

Highest possible sum less than number of elements

Given sorted arrays a1 and a2. find i,j such that. a1[i]+a2[j] <= n [ Number of elements] and their sum is highest possible.

Number of inversions

Given an array. Find the number of inversions (if ith element is greater than jth element where i<j)
Eg: arr = {3,5,7,2,8}
Output: 3 ( 3>2, 5>2, 7>2)

Saturday, September 29, 2012

URL Encoding / Decoding in C

Encode the url: http://foo bar/
 
Code 1: 
 
/* Converts a hex character to its integer value */
char from_hex(char ch) {
  return isdigit(ch) ? ch - '0' : tolower(ch) - 'a' + 10;
}

/* Converts an integer value to its hex character*/
char to_hex(char code) {
  static char hex[] = "0123456789abcdef";
  return hex[code & 15];
}

/* Returns a url-encoded version of str */
/* IMPORTANT: be sure to free() the returned string after use */
char *url_encode(char *str) {
  char *pstr = str, *buf = malloc(strlen(str) * 3 + 1), *pbuf = buf;
  while (*pstr) {
    if (isalnum(*pstr) || *pstr == '-' || *pstr == '_' || *pstr == '.' || *pstr == '~') 
      *pbuf++ = *pstr;
    else if (*pstr == ' ') 
      *pbuf++ = '+';
    else 
      *pbuf++ = '%', *pbuf++ = to_hex(*pstr >> 4), *pbuf++ = to_hex(*pstr & 15);
    pstr++;
  }
  *pbuf = '\0';
  return buf;
}

/* Returns a url-decoded version of str */
/* IMPORTANT: be sure to free() the returned string after use */
char *url_decode(char *str) {
  char *pstr = str, *buf = malloc(strlen(str) + 1), *pbuf = buf;
  while (*pstr) {
    if (*pstr == '%') {
      if (pstr[1] && pstr[2]) {
        *pbuf++ = from_hex(pstr[1]) << 4 | from_hex(pstr[2]);
        pstr += 2;
      }
    } else if (*pstr == '+') { 
      *pbuf++ = ' ';
    } else {
      *pbuf++ = *pstr;
    }
    pstr++;
  }
  *pbuf = '\0';
  return buf;
}
 
Code 2:
 
#include <stdio.h>
#include <ctype.h>
 
char rfc3986[256] = {0};
char html5[256] = {0};
 
/* caller responsible for memory */
void encode(unsigned char *s, char *enc, char *tb)
{
 for (; *s; s++) {
  if (tb[*s]) sprintf(enc, "%c", tb[*s]);
  else        sprintf(enc, "%%%02X", *s);
  while (*++enc);
 }
}
 
int main()
{
 unsigned char url[] = "http://foo bar/";
 char enc[sizeof(url) * 3];
 
 int i;
 for (i = 0; i < 256; i++) {
  rfc3986[i] = isalnum(i)||i == '~'||i == '-'||i == '.'||i == '_'
   ? i : 0;
  html5[i] = isalnum(i)||i == '*'||i == '-'||i == '.'||i == '_'
   ? i : (i == ' ') ? '+' : 0;
 }
 
 encode(url, enc, rfc3986);
 puts(enc);
 
 return 0;
} 

Friday, September 28, 2012

Trailing zeros in 100!

Question: How many zeros are there in 100! (100 factorial)?

Strategy:
A trailing zero is formed when a multiple of 5 is multiplied with a multiple of 2. Now all we have to do is count the number of 5′s and 2′s in the multiplication.
Let’s count the 5′s first. 5, 10, 15, 20, 25 and so on making a total of 20. However there is more to this. Since 25, 50, 75 and 100 have two 5′s in each of them (25 = 5 * 5, 50 = 2 * 5 * 5, …), you have to count them twice. This makes the grand total 24. For people who like to look at it from a formula point of view
Number of 5′s = 100/5 + 100/25 + 100/125 + … = 24 (Integer values only)
Moving on to count the number of 2′s. 2, 4, 6, 8, 10 and so on. Total of 50 multiples of 2′s, 25 multiples of 4′s (count these once more), 12 multiples of 8′s (count these once more) and so on… The grand total comes out to
Number of 2′s = 100/2 + 100/4 + 100/8 + 100/16 + 100/32 + 100/64 + 100/128 + … = 97 (Integer values only)
Each pair of 2 and 5 will cause a trailing zero. Since we have only 24 5′s, we can only make 24 pairs of 2′s and 5′s thus the number of trailing zeros in 100 factorial is 24.

Monday, September 24, 2012

Find maximum stack possible with given slabs

You are given many slabs each with a length and a breadth. A slab i can be put on slab j if both dimensions of i are less than that of j. In this similar manner, you can keep on putting slabs on each other. Find the maximum stack possible which you can create out of the given slabs.Generalize this for n dimensions.

All possible combination of digits

Find all possible combination of digits ranging 1 to 9 whose sum is 10
No digit should be repeated in any combination.

1234
127
136
145
19
235
28
37
46

Wednesday, September 19, 2012

Find Next Higher Number With Same Digits

Given a number, find the next higher number using only the digits in the given number. For example if the given number is 12543, next higher number with same digits is 13245.

Strategy:

Simple without thinking :Generate the numbers with all digit permutations and sort them. Then find the given number in the sorted sequence and return the next number in sorted order.
The complexity of this approach is pretty high though, because of the permutation step involved. A given number N has logN+1 digits, so there are O(logN!) permutations. After generating the permutations, sorting them will require O(logN!loglogN!) operations. We can simplify this further, remember that O(logN!) is equivalent to O(NlogN). And O(loglogN!) is O(logN). So, the complexity is O(N(logN)^2).

Efficient thinking:
Let’s visualize a better solution using an example, the given number is 12543 and the resulting next higher number should be 13245.
Step 1:We scan the digits of the given number starting from the tenths digit (which is 4 in our case) going towards left. At each iteration we check the right digit of the current digit we’re at, and if the value of right is greater than current we stop, otherwise we continue to left. So we start with current digit 4, right digit is 3, and 4>=3 so we continue. Now current digit is 5, right digit is 4, and 5>= 4, continue. Now current is 2, right is 5, but it’s not 2>=5, so we stop. The digit 2 is our pivot digit.

Step 2:From the digits to the right of 2, we find the smallest digit higher than 2, which is 3.We swap this digit and the pivot digit, so the number becomes 13542. Pivot digit is now 3. We sort all the digits to the right of the pivot digit in increasing order, resulting in 13245.So we got the answer!

Improvement:
We can also reverse the elements from the point we place the next highest or equal number with the current number.This way we can avoid sorting. But we should also be careful during swapping, for example if the original number is 136442. We’ll swap the pivot 3 with 4, and which 4 we swap with is important if we’re going to reverse later. We should swap with the rightmost one, otherwise we won’t get the next higher number.
Time complexity:O(n)

Note:
If the digits of the given number is monotonically increasing from right to left, like 43221 then we won’t perform any operations, which is what we want because this is the highest number obtainable from these digits.The same case occurs when the number has only a single digit, like 7. We can’t form a different number since there’s only a single digit.

Complexity: O(n)
The complexity of this algorithm also depends on the number of digits, and the sorting part dominates. A given number N has logN+1 digits and in the worst case we’ll have to sort logN digits. Which happens when all digits are increasing from right to left except the leftmost digit, for example 1987. For sorting we don’t have to use comparison based algorithms such as quicksort, mergesort, or heapsort which are O(KlogK), where K is the number of elements to sort. Since we know that digits are always between 0 and 9, we can use counting sort, radix sort, or bucket sort which can work in linear time O(K). So the overall complexity of sorting logN digits will stay linear resulting in overall complexity O(logN). This is optimal since we have to check each digit at least once.

Monday, September 17, 2012

maximum subset of Cuboid boxes that can fit into one another

Given a lot of cuboid boxes with different length, breadth and height. We need to find the maximum subset which can fit into each other. For example: If Box 1 has LBH as 7 8 9 If Box 2 has LBH as 5 6 8 If Box 3 has LBH as 5 8 7 If Box 4 has LBH as 4 4 4 then answer is 1,2,4 A box can fit into another only and only if all dimensions of that is less than the bigger box.Rotation of boxes is not possible.

Code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>


/*Struct defining cube*/
typedef struct
{
    int l;
    int b;
    int h;
}Cube;

/*Cube compare function */
int cube_compare(const void *x, const void *y)
{
    const Cube *a = x;
    const Cube *b = y;

    if(a->l == b->l)
    {
        if(a->b == b->b)
            return a->h - b->h;

        return a->b - b->b;
    }
    return a->l - b->l;

}

/*Struct to hold successor info*/
typedef struct
{
    int next;
    int chainLength;
}Successor;


/*Checks whether cube 'a' fits into cube 'b' */
inline int cube_fits(Cube *a , Cube *b)
{
    return (a->l < b-> l)  && (a->b < b->b) && (a->h < b->h);
}

/*Prints all the cubes which fits into one another */
void max_fit_cubes(Cube cubes[], int n)
{

    //Fill the chain
    Successor nextCube[n];

    memset(nextCube, 0, sizeof(nextCube));

    int i = n - 1, j;

    while(i--)
    {
        for(j = i + 1; j < n; j++)
        {
            if(cube_fits(cubes + i, cubes + j))
            {
                if((nextCube[j].chainLength + 1) > nextCube[i].chainLength)
                {
                    nextCube[i].chainLength = nextCube[j].chainLength + 1;
                    nextCube[i].next = j;
                }
            }
        }
    }

    //find the max chain
    int m = i = n - 1;

    while(i--)
    {
        if(nextCube[i].chainLength > nextCube[m].chainLength)
            m = i;
    }


    //Now print the max chain

    printf("Max Chain Length: %d, m: %d\n", nextCube[m].chainLength, m);

    do
    {
        printf("(%d,%d,%d) =>", cubes[m].l, cubes[m].b, cubes[m].h);
        m = nextCube[m].next;
    }while(m);

    printf("\n");
}

int main()
{
    int n;

    scanf("%d", &n);

    Cube cubes[n];

    int i;

    for(i = 0; i < n; ++i)
    {
        scanf("%d%d%d", &(cubes[i].l), &(cubes[i].b), &(cubes[i].h));
    }

    qsort(cubes, n, sizeof(Cube), cube_compare);

    max_fit_cubes(cubes, n);
    return 0;
}

Pending


Saturday, September 15, 2012

Find a sorted subsequence of size 3 in linear time

Given an array of n integers, find the 3 elements such that a[i] < a[j] < a[k] and i < j < k in 0(n) time. If there are multiple such triplets, then print any one of them.

Thursday, September 13, 2012

Design a Client-facing Service

Imagine you are building some sort of service that will be called by up to 1000 client applications to get simple end-of-day stock price information (open, close, high, low). You may assume that you already have the data, and you can store it in any format you wish. How would you design the client-facing service which provides the information to client applications? You are responsible for the development, rollout, and ongoing monitoring and maintenance of the feed. Describe the different methods you considered and why you would recommend your approach. Your service can use any technologies you wish, and can distribute the information to the client applications in any mechanism you choose.


Monday, September 10, 2012

Find longest interval with maximum sum

We are given with two arrays A and B. Each of size N. Elements of array contains either 1 or 0. We have to find such an interval (p,q)(inclusive) such that the sum of all the elements of A (between this interval) and sum of all elements of B (between this interval ) is equal. i.e.
a[p]+a[p+1]....+a[q]= b[p]+b[p+1]....+b[q]

Solution:

a)Calculate the prefix sum of both the arrays – value at each index represents the sum till that index
  void prefixSum(int *array, int *sum)
{
     int i;
     for(i=0;i < N;i++)
     { 
             if(i==0) 
             {
                sum[i]=array[i];
             }
             else
             {
                 sum[i]=array[i]+sum[i-1];
             }
     }
}
b)Make 4 variables:
size: to keep track of largest subset size found till now sum: sum of that subset
p: starting index of the subset
q: ending index of the subset
Initially search of there is any sub set from starting index in both the arrays that has the same sum, if found update the value of size, sum and indices p, q.
for(int i=0;i < N;i  )
    {
            if(sumA[i]==sumB[i])
            {
                          if((i 1) > size)
                          {
                                        size=i 1;
                                        p=0;
                                        q=i;
                                        sum=sumA[i];
                          }
            }
    }
c)Now search for largest subset by incrementing the starting position and continue this loop till the size of the array.
for(int i=0;i < N-1;i  )
    {
            for(int j=i 1;j < N;j  )
            {
                    if( (sumA[j]-sumA[i]) == (sumB[j]-sumB[i]) )
                    {
                          if( (j-i) > size )
                          {
                              size= j-i;
                              p=i 1;
                              q=j;
                              sum=sumA[j]-sumA[i];
                          }
                          else if( (j-i) == size )
                          {
                               if( (sumA[j]-sumA[i]) > sum )
                                   sum=(sumA[j]-sumA[i]);
                          }
                          else {}

                    }
            }
    }
Time complexity of the algorithm in O(N2) because of the double loop of i and j

Wednesday, September 5, 2012

Maximum subarray of equal number of 0s & 1s

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.

Examples

Input: arr[] = {1, 0, 1, 1, 1, 0, 0}
Output: 1 to 6 (Starting and Ending indexes of output subarray)

Input: arr[] = {1, 1, 1, 1}
Output: No such subarray

Input: arr[] = {0, 0, 1, 1, 0}
Output: 0 to 3 Or 1 to 4


Solution:
We can change 0 to -1 on the original array.
Define a sum array S[i] = a[1] + ... + a[i] (a being the input)
Now We want to find indices i and j such that a[i]+...+a[j] = 0
and that is the same as
S[j]-S[i-1] = 0
S[j] = S[i-1]
now We can hash these values (they range from -n to n, so we can do this in O(n) memory)and find the indices in O(n). We can also take an array of size 2n+1 and store the first index containing the value seen and compute difference whenever u see the value again ..


Following is a solution that uses O(n) extra space and solves the problem in O(n) time complexity.
Let input array be arr[] of size n and maxsize be the size of output subarray.
1) Consider all 0 values as -1. The problem now reduces to find out the maximum length subarray with sum = 0.
2) Create a temporary array sumleft[] of size n. Store the sum of all elements from arr[0] to arr[i] in sumleft[i]. This can be done in O(n) time.
3) There are two cases, the output subarray may start from 0th index or may start from some other index. We will return the max of the values obtained by two cases.
4) To find the maximum length subarray starting from 0th index, scan the sumleft[] and find the maximum i where sumleft[i] = 0.
5) Now, we need to find the subarray where subarray sum is 0 and start index is not 0. This problem is equivalent to finding two indexes i & j in sumleft[] such that sumleft[i] = sumleft[j] and j-i is maximum. To solve this, we can create a hash table with size = max-min+1 where min is the minimum value in the sumleft[] and max is the maximum value in the sumleft[]. The idea is to hash the leftmost occurrences of all different values in sumleft[]. The size of hash is chosen as max-min+1 because there can be these many different possible values in sumleft[]. Initialize all values in hash as -1
6) To fill and use hash[], traverse sumleft[] from 0 to n-1. If a value is not present in hash[], then store its index in hash. If the value is present, then calculate the difference of current index of sumleft[] and previously stored value in hash[]. If this difference is more than maxsize, then update the maxsize.
7) To handle corner cases (all 1s and all 0s), we initialize maxsize as -1. If the maxsize remains -1, then print there is no such subarray.


#include <stdio.h>
#include <stdlib.h>

int max(int a, int b) { return a>b? a: b; }

int findSubArray(int arr[], int n)
{
    int maxsize = -1, startindex;

    int sumleft[n];
    int min, max; // For min and max values in sumleft[]
    int i;

    // Fill sumleft array and get min and max values in it.
    // Consider 0 values in arr[] as -1
    sumleft[0] = ((arr[0] == 0)? -1: 1);
    min = arr[0]; max = arr[0];
    for (i=1; i<n; i++)
    {    
        sumleft[i] = sumleft[i-1] + ((arr[i] == 0)? -1: 1);
        if (sumleft[i] < min)
            min = sumleft[i];
        if (sumleft[i] > max)
            max = sumleft[i];
    }

    // Now calculate the max value of j - i such that sumleft[i] = sumleft[j].
    // The idea is to create a hash table to store indexes of all visited values.
    // If you see a value again, that it is a case of sumleft[i] = sumleft[j]. Check
    // if this j-i is more than maxsize.
    // The optimum size of hash will be max-min+1 as these many different values
    // of sumleft[i] are possible. Since we use optimum size, we need to shift
    // all values in sumleft[] by min before using them as an index in hash[].

    int hash[max-min+1];

    // Initialize hash table
    for (i=0; i<max-min+1; i++)
        hash[i] = -1;

    for (i=0; i<n; i++)
    {
        // Case 1: when the subarray starts from index 0
        if (sumleft[i] == 0)
        {
           maxsize = i+1;
           startindex = 0;
        }

        // Case 2: fill hash table value. If already filled, then use it
        if (hash[sumleft[i]-min] == -1)
            hash[sumleft[i]-min] = i;
        else
        {
            if ( (i - hash[sumleft[i]-min]) > maxsize )
            {
                maxsize = i - hash[sumleft[i]-min];
                startindex = hash[sumleft[i]-min] + 1;
            }
        }
    }
    if ( maxsize == -1 )
        printf("No such subarray");
    else
        printf("%d to %d", startindex, startindex+maxsize-1);

    return maxsize;
}

int main()
{
    int arr[] =  {1, 0, 0, 1, 0, 1, 1};
    int size = sizeof(arr)/sizeof(arr[0]);

    findSubArray(arr, size);
    return 0;
}

Time Complexity: O(n)
Auxiliary Space: O(n)

http://www.geeksforgeeks.org/largest-subarray-with-equal-number-of-0s-and-1s/