Credit Suisse Interview Question
Software Engineer / DevelopersThe first design choice is that you'll need some sort of a map somewhere that informs you which characters are associated with which number. A 2d array of characters is good enough in this case, because: 1) Its hardcoded, so you know exactly how much space you'll need. 2) Although the distribution of characters is uneven, (i.e. 2 -> ABC, but 7-> PQRS), you'll only end up wasting 6 bytes overall, which should be acceptable to any sensible interviewer. If you want even greater space efficiency, try a hash map where each number maps to a linked list of characters. But again, but 6 bytes, it isn't worth the trouble, especially when 2d char arrays afford you the luxury of random access.
The second design choice is in what format you receive the input. I'd say a string of numbers is a pretty good option. You could be clever and just use ints or longs or long longs, but then you're limiting yourself.
Ok, onto the algo. Have to point out that the example provided is wrong. So I'll use my own, say 234. Possible permutations are: ADG, ADH, ADI, AEG, AEH, AEI, AFG....
So the way I'm looking at it, it seems like I can fix a letter in the first position, move to the second position, fix a letter there, move to the third position, etc. Eventually I fix a letter at each position. When I've reached the end of the number, I print the string I've just built.
Now, instead of starting over, its easier to just move back one position, iterate over all the possible characters for that number, and print every string. So once I'm done with iterating over the last position, I move back to the second last. Then I continue iterating over the rest of the chars in the second last position and when I'm done, move back to the third last. Hey, what do you know, sounds like recursion!
int main()
{
char zero[]="0";
char one[]="1";
char two[]="abc";
char three[]="def";
char four[]="ghi";
char five[]="jkl";
char six[]="mno";
char seven[]="pqrs";
char eight[]="tuv";
char nine[]="wxyz";
map<int, char*> table2;
table2.insert ( pair<int,char*>(0, zero));
table2.insert ( pair<int,char*>(1, one));
table2.insert ( pair<int,char*>(2, two));
table2.insert ( pair<int,char*>(3, three));
table2.insert ( pair<int,char*>(4, four));
table2.insert ( pair<int,char*>(5, five));
table2.insert ( pair<int,char*>(6, six));
table2.insert ( pair<int,char*>(7, seven));
table2.insert ( pair<int,char*>(8, eight));
table2.insert ( pair<int,char*>(9, nine));
cout<<"Input Telphone Num: (xxx-xxx-xxxx)"<<endl;
string telStr;
cin>>telStr;
string::iterator it;
for(it=telStr.begin(); it<telStr.end(); it++ )
{
if(*it=='-')
telStr.erase(it);
}
printTelString(telStr, 0 , "", table2);
return 0;
}
void printTelString(string s, int i, string outStr, map<int, char*>table)
{
if (i == s.size()) //go to the last element, there is no permutation
cout << outStr << endl;
else
{
char curChar=s[i];
int curNum=atoi(&curChar);
map<int, char*>::iterator test=table.find(curNum);
char* cur=table.find(curNum)->second ;
int j=0;
while(*(cur+j)!='\0')
{
string old=outStr;
outStr=outStr+cur[j];
printTelString(s, i + 1, outStr, table);
outStr=old;
++j;
}
}
}
void printcombos(int digs, int count, String a, String temp)
{
for (i=0;i<a[digs[count-1].length();i++)
printcombos(digs,count-1,a, temp+a[digs[count-1][i]);
}
void printstrings (int number)
{
if (number <=0) {cout << "No combinations";return ();}
int digs[10];int count=0;
String a[][]={{},{},{ABC},{DEF},{GHI},{JKL},{MNO},{PQRS},{TUV},{WXYZ}};
while (number > 0)
{
digs[count++]=number%10;number/=10;
}
String temp="";
printcombos(digs,count,a,temp);
}
hey can i get the ans
- iDevloper October 21, 2009