NetApp Interview Question
Member Technical StaffsCountry: India
Interview Type: In-Person
Well.. I remember the famous "Prison Break" Breakdown with the question.. ;)
Anyways.. I guess the algo Approach would be Something like this
Vector<char> words[27];
For each element1 in {abc}
For each element2 in {def}
For each element3 in {ghi}
if(dictonary(element1element2element3))
Word[index++]= element1element2element3;
end loop
end loop
end loop
Assuming dictonary is a function returning true if word exist else false.
O(n3).. time compexity.. ;(
@ Abhi : Recursive solution will also have the same complexity right O(n^5) in the example given by you. But I guess iterative solution will save the extra stack creation "time as well as space".
public class MobileNumberPadProblem {
static String[] s = new String[5];
int n = s.length - 1;
static int k = 0;
public static void main(String[] args) {
s[0] = "abcd";
s[1] = "def";
s[2] = "ghi";
s[3] = "jkl";
s[4] = "mno";
combi();
}
static void combi() {
new MobileNumberPadProblem().get(s[0], "", 0);
System.out.println("\n" + k);
}
void get(String s1, String t, int i) {
for (int j = 0; j < s1.length(); j++) {
t = t + s1.charAt(j);
if (i < n) {
i++;
get(s[i], t, i);
i--;
t = t.substring(0, t.length() - 1);
continue;
}
System.out.print(t + " ");
k++;
t = t.substring(0, t.length() - 1);
}
}
}
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
void print(string str[], int in, int l, int len, char arr[], char que[])
{
int i;
if(l==len)
{
for(i=0;i<l;i++)
{
cout<<arr[i];
}
cout<<endl;
return;
}
for(i=0;i<str[que[in]-'0'].length();i++)
{
arr[l]=str[que[in]-'0'][i];
print(str,in+1,l+1,len,arr,que);
}
}
int main()
{
char s[1001],t[1001];
string str[1001];
str[1]="abc";
str[2]="def";
str[3]="ghi";
str[4]="jkl";
str[5]="mno";
str[6]="pqr";
str[7]="stu";
str[8]="vwx";
str[9]="yz";
cout<<"Enter the string";
cin>>s;
char arr[1001];
print(str,0,0,strlen(s),arr,s);
}
void Calculate(int number){
char arr1[3]={'a','b','c' };
char arr2[3]={'d','e','f' };
char arr3[3]={'g','h','i' };
int count =0;
for(int i=0;i<sizeof(arr1);i++){
for(int j=0;j<sizeof(arr2);j++){
for(int k=0;k<sizeof(arr3);k++){
cout<<arr1[i]<<arr2[j]<<arr3[k]<<endl;
count ++;
}
}
}
cout<<count<<endl;
}
This problem is given in "Programming Interview Exposed". You can use recursion to solve it. Shamelessly copying the code :)
- Abhi January 28, 2013