Microsoft Interview Question
Software Engineer / DevelopersCountry: India
Initially the tillnow array should be initialised to spaces, *A is array of number given, mrt is 2-D array
containing the structure of keypad.
void print_word(char **mtr,int *A,char *tillnow,index)
{
int i;
for(i=0;i<3;i++)
{
tillnow[index]=mtr[A[index]][i];
if(index==10)
printf("%s\n",str);
else
print_word(mtr,A,tillnow,index+1);
}
}
Recursive solution(C#) using backtracking
public void FindWords(int n)
{
string s="";
BackTrack(int n,1,ref s);
}
private void BackTrack(int n,int t,ref string s)
{
if(t>n)
{
Output(s);
return;
}
char[] a=GetChars((n/t)%10);
for(int i=0;i<a.Length;i++)
{
s=a[i]+s;
BackTrack(n,t*10,ref s);
s=s.Substring(1);
}
}
Method Output(string s) is used to print string while method GetChars(int n) is used to get all chars that are corresponding to int n.
It's a classic -> "Programming interviews exposed" question.
Here is C# code for it.
public static void PrintTelephoneWords(int[] phoneNumber)
{
Dictionary<int, string> dict = new Dictionary<int, string>();
dict.Add(2, "ABC");
dict.Add(3, "DEF");
dict.Add(4, "GHI");
dict.Add(5, "JKL");
dict.Add(6, "MNO");
dict.Add(7, "PRS");
dict.Add(8, "TUV");
dict.Add(9, "WXY");
char[] result = new char[phoneNumber.Length];
DoPrintTelephoneWords(phoneNumber, 0, result, dict);
//foreach (char r in result)
//{
// Console.WriteLine(r);
//}
}
private static void DoPrintTelephoneWords(int[] phoneNumber, int currentDigit, char[] result, Dictionary<int, string> dict)
{
if (currentDigit >= phoneNumber.Length)
{
Console.WriteLine(result);
return;
}
for (int i = 0; i < 3; i++)
{
if (phoneNumber[currentDigit] == 0 || phoneNumber[currentDigit] == 1)
result[currentDigit] = phoneNumber[currentDigit] == 0? '0' : '1';
else
result[currentDigit] = dict[phoneNumber[currentDigit]][i];
DoPrintTelephoneWords(phoneNumber, currentDigit + 1, result, dict);
}
}
#include<iostream>
using namespace std;
#define max_digit 5
#define alpha 3 //this is maxmum alpahbets per digit, in our case its 3 alphates per digits
void print_word(char a[max_digit][alpha], int l, char result[max_digit+1]){
static int count=1;
//at last level print the whole string
if(l == max_digit){
cout<<result<<"\t"<<count++<<endl;
return;
}
//call the above function 3 times for each alpabet/digit, add the result before calling
for (int i=0; i<alpha; i++){
char new_res[max_digit+1];
result[l]=a[l][i];
result[l+1]=0;
print_word(a,l+1,result);
}
}
int main(){
char data[5][3]={{'a','b','c'}, {'d','e','f'}, {'g','h','i'},{'j','k','l'},{'m','n','o'}};
char res[max_digit+1]={' '};
print_word(data,0,res);
return 0;
}
#---Print all word to generate -----
# Mobile NUmver genarator====
# Author : Dipankar
#-----------------------------------
key={0:[''],
1:[''],
2:list('abc'),
3:list('def'),
4:list('ghi'),
5:list('jkl'),
6:list('mno'),
7:list('pqrs'),
8:list('tuv'),
9:list('wxyz')
}
def getAllWord(num):
if(len(num)==0):
return [''];
else:
return [ i + j for i in key[int(num[0])] for j in getAllWord(num[1:])]
res=getAllWord('9920')
print res, len(res)
- dutta.dipankar08 March 24, 2012