Programming Problems 6

Mapping a Phone Number

Map a phone number (such as 023-254435-13) into all the strings which can be potentially generated with a phone keyboard. Please remeber that 1 has no mapping, 2 can be mapped into ‘a’ or ‘b’ or ‘c’, 3 can be mapped into ‘d’, or ‘e’, or ‘f’ and so on. Note that 7 can be mapped into ‘p’, ‘q’, ‘r’, ‘s’, while 9 can be mapped into ‘w’, ‘x’, ‘y’, ‘z’.

Top Search Queries
Magy! receives a huge amount of queries everyday. They don’t want to store all of them, since many of the queries are unique (submitted just one time by just one user). Anyway, for caching reason they want to understand what are the queries whose frequency exceed s=0.1%. How do you solve the problem? Remember we don’t want to store all the queries.
Hint: split the stream into windows and accept some error in estimation.

First Not present
You are given a sequence of m distinct numbers extracted by a set of 1…n numbers, with m < n. Can you give an efficient algorithm for identifying a number not in the sequence.

How many loops
You are given n segments. In turn, you take each one of them and join it with one among those already selected, creating either a loop or a longer segment. How many loops there are in average, at every instant of time?

Finding elements near the median
Given an unsorted array A of n distinct numbers and an integer k where 1 <= k <= n, design an algorithm that finds the k numbers in A that are closest in value to the median of A in O(n) time.

Minimum positive-sum subarray
In this variation of the Maximum-Sum Subarray Problem, you are given a one-dimensional array A[1 : n] of positive or negative numbers, and you are asked to find a subarray A[i : j] such that the sum of its elements is (1) strictly greater than zero, and (2) minimum. In other words, you want to find a subarray of smallest positive sum. Give an O(nlog^2n) Divide and Conquer algorithm and a O(nlogn) Dynamic Programming Algorithm.

Number of Inversions
Find the number of inversions in an array in O(nlogn) time.

Advertisements

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

12 Responses to Programming Problems 6

  1. Divya says:

    1
    let ph is a character string which contains phone number. we have to print all strings for this number.
    len=strlen(ph);
    map[10][5]={1, 0,,,,
    1, 1,,,,
    3, a,b,c,,
    3, d,e,f,,
    3,g,h,i,,
    3,j,k,l,,
    3,m,n,o,,
    4,p,q,r,s,,
    3,t,u,v,,
    4,w,x,y,z};
    // map[i][0] contains number of character that map for i map[i][1]-map[i][4] conatins the charaters for which // i cn be replaced.
    void printallstring(char * ph,int start,char * output)
    {
    if(start==len)
    print output;
    else
    {
    for(i=1;i<map[i][0];i++)
    {
    output[start]=map[ph[start]][i];
    printallstring(ph,start+1,output);
    }
    }
    }

    • Avi Dullu says:

      the above code will not work.

      • Divya says:

        my logic

        i have taken a 2 d array ith rows has following information
        1. in column 0 i store no. of characters by which no. i can be replaced ( for eg. 0 can be replaced by 1 character which is 0 itself, 9 can be replaced by 4 characters which are w,x,y,z)
        2 column 1 to 4 contains the characters with which this number can be replaced. in case number can be replaced by only 3 charcters like 4 can be replaced by only 3 which are g h and i then i store null character at row[i][4]..

        now i have to find all the combinations that i can get…
        so i take the number at all the index of phonenumber string and replace it with all the characters that are possible for it..

        is there any problem with the logic also?
        i m unable to figure out my error in the code…please tell me why my code doest work?
        one thing i forgot to mention is i call the function with
        printallstring(ph,0,output)

  2. Divya says:

    How many loops
    this question is not clear to me.. please clarify..

    • Avi Dullu says:

      Its a probability based problem, any 2 line segments can either be joined to make a longer segment, or joined end to end and made into a loop. You are asked to find the average number of loops if u are doing this operation for n line segments

  3. Divya says:

    Minimum positive-sum subarray

    I think returning min element ( provided it is not zero) will solve the problem.. or m i missing something?

    • Avi Dullu says:

      -1 2 3

      your algorithm will return ‘2’ whereas the solution is ‘-1, 2’.

      • Divya says:

        ya sorry… i misread the question .i thought array has only positive elements..

      • Divya says:

        minimum sum subarray

        Given Input Array A

        form the prefix sum array P of A.

        i.e P[i] = A[1] + A[2] + … + A[i]

        Now create another array Q of pairs (Value, Index)

        such that

        Q[i].Value = P[i].
        Q[i].Index = i

        Now sort that array Q, considering only Q[i].Value for comparison.

        We get a new sorted array Q’ such that Q'[i].Value Q'[i].Index

        Time complexity o( nlogn)

        does there exist O(n) solution for it also.. i had tried a lot but could not figure out. but i think it should exist as there is for the other variation..

  4. Avi Dullu says:

    @divya
    write a compilable C/C++/Java/Python code, then u’ll realize the flaw.

    • Divya says:

      my working c code 🙂

      #include
      #include
      char map[10][5]={ {‘1′,’0’,”,”,”},
      {‘1′,’1’,”,”,”},
      {‘3′,’a’,’b’,’c’,”},
      {‘3′,’d’,’e’,’f’,”},
      {‘3′,’g’,’h’,’i’,”},
      {‘3′,’j’,’k’,’l’,”},
      {‘3′,’m’,’n’,’o’,”},
      {‘4′,’p’,’q’,’r’,’s’},
      {‘3′,’t’,’u’,’v’,”},
      {‘4′,’w’,’x’,’y’,’z’} };
      void printallstrings(char * phone,int start, char * string);
      void main()
      { clrscr();
      char phone[11],string[11];
      printf(“enter the phone number : “);
      scanf(“%s”,phone);
      printf(“the corresponding mapping strings are : \n”);
      getch();
      printallstrings(phone,0,string);
      getch();

      }

      void printallstrings(char * phone,int start, char * string)
      { int i,k;
      if(start==10)
      { string[10]=”;
      printf(“%s \n”,string);
      getch();
      return;
      }

      else{
      k=phone[start]-‘0’;
      for(i=1;i<=((map[k][0])-'0');i++){
      string[start]=map[k][i];
      printallstrings(phone,start+1,string);
      }

      }

      }

      • Avi Dullu says:

        Your sanitized code 🙂
        PS: which compiler do you use? It will not compile on GCC. I have updated it to work on GCC.
        Now probably you know why I said that the code won’t work. You can compare this with the pseudo code you gave in the first comment. The line

        for(i=1;i<map[i][0];i++)
        

        was what I was referring to. Details matter a lot and thanx for sharing the code 🙂

        #include<stdio.h>
        
        char map[10][5] = {
          {'1','0',' ',' ',' '},
          {'1','1',' ',' ',' '},
          {'3','a','b','c',' '},
          {'3','d','e','f',' '},
          {'3','g','h','i',' '},
          {'3','j','k','l',' '},
          {'3','m','n','o',' '},
          {'4','p','q','r','s'},
          {'3','t','u','v',' '},
          {'4','w','x','y','z'}
        };
        
        void printallstrings(char * phone,int start, char * string);
        
        int main() {
          char phone[11],string[11];
          printf("enter the phone number : ");
          scanf("%s",phone);
          printf("the corresponding mapping strings are : \n");
          printallstrings(phone, 0, string);
          return 0;
        }
        
        void printallstrings(char * phone,int start, char * string){
          int i,k;
          if(start == 10) {
            string[10]=0;
            printf("%s \n",string);
            return;
          } else{
            k = phone[start] - '0';
            for(i=1; i <= (map[k][0] - '0'); i++) {
              string[start]=map[k][i];
              printallstrings(phone, start+1, string);
            }
          }
        }
        

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: