# Programming Problems 6

November 5, 2009 12 Comments

**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.

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);

}

}

}

the above code will not work.

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)

How many loops

this question is not clear to me.. please clarify..

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

Minimum positive-sum subarray

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

-1 2 3

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

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

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..

@divya

write a

compilableC/C++/Java/Python code, then u’ll realize the flaw.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);

}

}

}

Your

sanitizedcode 🙂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

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