Programming Problems 4

1. Power of 3

Given M, find if M = 3^x for some positive integer x efficiently. DO NOT think of log, pow etc.

2. Maximum Sum path in a Matrix

Given a M*N matrix A. Find a path from the top-left element (ie A[0][0]) to the bottom right element (ie A[M-1][N-1]) such that the sum of the elements in the path is maximum.  Length of path should be M + N – 1. Moves can be made towards the right and bottom only by 1 cell i.e. from A[i][j] only two possible steps are A[i+1][j] or A[i][j+1].

3. 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 should be better than O(n^2)

4.Divide the array into groups

Divide a list of numbers into groups of consecutive numbers but their original order should be preserved.

Example:
<8,2,4,7,1,0,3,6>
Two groups:
<2,4,1,0,3> <8,7,6>

Better than O(n^2) is expected.

5. Sort on second key when array is sorted on first key

Assume that we are given as input n pairs of items, where

  1. the first item is a number
  2. the second item is one of three colors (red, blue, or yellow).

Further, assume that the items are sorted by number. Give an O(n) algorithm to sort the items by color (all reds before all blues before all yellows) such that the numbers for identical colors stay sorted.

For example: (1,blue), (3,red), (4,blue), (6,yellow), (9,red) should become (3,red), (9,red), (1,blue), (4,blue), (6,yellow).

Advertisements

About Avi Dullu
Jaako rakhe saiyan, maar sake na koi!

8 Responses to Programming Problems 4

  1. Divya says:

    5. we can solve the problem using chain hashinh. take a hash map of three and traverse the array. if element is of red colour.. append it to hash[0] if u blue then to hash[1] else to hash[2]..
    now print the result by traversing through hash . 1st print all elements of hash[0] by traversing linked list at hash[0]..when we reach null ( end of hash[0] ) then traverse hash[1] and then hash[2].
    time O(n)

    • Avi Dullu says:

      is correct 🙂

      A different approach is still possible where you can solve it in-place i.e. without using the extra space for hashing, by just re-arranging the elements in the array in O(n) time.

  2. Divya says:

    4.

    sort in nlogn and then while traversing the array put the elements in a group till they are consecutive . when a[i+1]!=a[i]+1 then put a[i+1] in different group..and maintain the index along with every element.
    now we need to rearrange elements in the group by sorting them on the basis of their index.

    time O(nlogn)

  3. Avi Dullu says:

    @divya
    5. just count the number of red, blue and greens and then figure out a way. This approach works because there are only 3 distinct values for second pair.

  4. Divya says:

    1. write number M in base-3, and check if it contains only one digit(1)

    5 I think you are refering to Dutch national flag algo for 3 elements. but that will change the order of nos. ie it will make the colour sorted but nummbers within the same colour may not remain sorted. and then we have to sort the numbers again. I think hashing technique should be apt here. Please correct me if i am wrong.

    4. pseudocode

    divideInGroups(int a[],int n) {
    int index[n];
    for(i=0;i<n;i++)
    index[i]=i;
    sort(a,n,index); //use any sorting O(nlogn) algorithm to sort the array. and while changing the position of number change its index according.. for eg if the initial array was a={ 8,2,4,7,1,0,3,6} and index[] was = {0,1,2,3,4,5,6,7} after sort function a[] will be= {0,1,2,3,4,6,7,8} and index[] will be {5,4,1,6,2,7,3,0}
    // now we have to divide into groups 🙂
    i=0;
    while(i<n)
    {
    while(a[i+1]=a[i]+1)
    {
    insert in same group (make a link list perhaps for a group)
    i++;
    }
    sort the group (linked list ) according to index[] array
    print the group
    i++;
    }
    }

  5. ANJALI says:

    #include
    using namespace std;
    void main()
    {
    int pow=1;

    cout<>M; // as m is

    for(int i=0;i<=50;i++) // 50 is arbitary limt

    {
    pow= pow* 3;
    if(M==pow)

    {
    x= i;
    break;
    }

    }
    cout<<x;
    }

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: