Epic Systems Interview Question Software Engineer / Developers
public class combunationOfInputKeys {
/**
* @param args
*/
public static Map<Integer,String> inputKeys = new HashMap<Integer,String>();
public static void main(String[] args) {
// TODO Auto-generated method stub
inputKeys.put(2, "ABC");
inputKeys.put(3, "DEF");
inputKeys.put(4, "GHI");
inputKeys.put(5, "JKL");
inputKeys.put(6, "MNO");
inputKeys.put(7, "PQRS");
inputKeys.put(8, "TUV");
inputKeys.put(9, "WXYZ");
inputKeys.put(1, "");
inputKeys.put(0, "");
Scanner scan = new Scanner(System.in);
System.out.println("Please enter the input");
int input=0;
try{
input=scan.nextInt();
}
catch(InputMismatchException ime){
System.out.println("Invalid Input detected ...System exiting Next time Please enter only valid integer value ");
System.exit(0);
}
print("",input);
}
public static void print(String str,int i){
String input = i+"";
if(input.length() == 1){
String temp =inputKeys.get(Integer.parseInt(""+input.charAt(0)));
if(temp.length() == 0){
System.out.println(str);
}
else {
for(int j=0;j<temp.length();j++){
System.out.println(str+temp.charAt(j));
}
}
}
else {
String temp =inputKeys.get(Integer.parseInt(""+input.charAt(0)));
if(temp.length() == 0){
print(str,Integer.parseInt(input.substring(1)));
}
else {
for(int j=0;j<temp.length();j++){
print(str+temp.charAt(j),Integer.parseInt(input.substring(1)));
}
}
}
}
}
<pre lang="" line="1" title="CodeMonkey82170" class="run-this">#include<stdio.h>
void print(char *str, char *pattern[], int index)
{
if(index == 3)
{
printf("%s\n",str);
//*(str+index) = '\0';
}
else
{ int i=0;
while(*(pattern[index]+i))
{
*(str+index) = *(pattern[index]+i);
print(str,pattern,index+1);
i++;
}
}
}
int main()
{
char *str = (char*)malloc(sizeof(char)*4);
*(str+3)='\0';
char *pattern[3] = {"abc","def","ghi"};
print(str,pattern,0);
getchar();
return 0;
}
</pre><pre title="CodeMonkey82170" input="yes">
</pre>
import java.util.*;
import java.io.*;
class Keypad
{
public static final int[] keypadint= {0, 1, 65, 68, 71, 74,77,80,84,87};
public static void main (String arg[])
{
System.out.println("************************");
printRecursiveAlphabet ("",430017814);
}
public static void printRecursiveAlphabet (String string,int num)
{
int len,mod=0,count=0;
String newstr;
if (num==0)
{
System.out.println(string);
return;
}
mod=num%10;
num = num/10;
while (mod==0||mod==1)
{
mod=num%10;
num = num/10;
//System.out.println("mod : "+mod+" num : "+num);
if (count==10)
break;
count++;
}
if (mod==9 || mod==7)
{
len=4;
}
else
{
len = 3;
}
for (int i=0;i<len;i++)
{
newstr = string;
string =string+ (char)(keypadint[mod]+i);
//System.out.println("String : "+string+" num : "+num);
printRecursiveAlphabet(string, num);
string = newstr;
}
}
}
The correct recursive solution is
#include<stdlib.h>
#include<stdio.h>
#include<string.h>
void print_string(int cur_indx, int tot_len, char* input, char** patterns, char* out_str)
{
int i;
char indx_char = input[cur_indx];
int len = strlen(patterns[atoi(&indx_char)]);
if ((cur_indx + 1) < tot_len)
{
for (i=0; i < len; i++)
{
char* new_out_str = (char*)malloc(strlen(out_str)+2);
strcpy(new_out_str, out_str);
new_out_str[strlen(out_str)]=patterns[atoi(&indx_char)][i];
new_out_str[strlen(out_str)+1]='\0';
print_string(cur_indx+1, tot_len, input, patterns, new_out_str);
}
}
else
{
for (i=0; i < len; i++)
{
char* new_out_str = (char*)malloc(strlen(out_str)+2);
strcpy(new_out_str, out_str);
new_out_str[strlen(out_str)]=patterns[atoi(&indx_char)][i];
new_out_str[strlen(out_str)+1]='\0';
printf("%s\t", new_out_str);
}
}
}
int main (int argc, char* argv[])
{
char** out_str = NULL;
char first_arg;
int i, len, len_start, first_indx;
char* patterns[] = {"", "ABC", "DEF", "GHI", "JKL", "MNO", "PQRS", "TUV", "WXYZ"};
len = strlen(argv[1]);
printf("input length %i\n", len);
first_arg = argv[1][0];
first_indx = atoi(&first_arg);
len_start = strlen(patterns[first_indx]);
out_str = (char**)malloc(len_start);
printf("length of first pattern line:%i\n", len_start);
for (i = 0; i < len_start; i++)
{
out_str[i]=(char*)malloc(2);
out_str[i][0]=patterns[first_indx][i];
out_str[i][1]='\0';
print_string(1, len, argv[1], patterns, out_str[i]);
printf("\n");
}
return 0;
}
static void test(String []a, String value)
{
String a1 = a[Int16.Parse(value.Substring(0,1).ToString())-1];
String a2 = a[Int16.Parse(value.Substring(1, 1).ToString())-1];
String a3 = a[Int16.Parse(value.Substring(2,1).ToString())-1];
for (int i = 0; i < a1.Length; i++)
{
for (int j = 0; j < a2.Length; j++)
{
for (int k = 0; k < a3.Length;k++ )
{
String temp=a1.Substring(i,1)+""+a2.Substring(j,1)+""+a3.Substring(k,1);
Console.Write(temp+ " ");
}
}
Console.WriteLine();
}
This solution is hard coded but it work fine in C#
import java.io.*;
public class keypad_comb {
static String pattern[]={"ABC","DEF","GHI","JKL","MNO","PQRS","TUV","WXYZ"};
static char[] patt;
int size;
public static void main(String[] args) throws IOException {
// TODO Auto-generated method stub
System.out.println("Enter the input string\n");
BufferedReader br = new BufferedReader ( new InputStreamReader(System.in));
String in = br.readLine();
char[] input = in.toCharArray();
patt=new char[input.length];
print(input,0,patt,0);
}
static void print(char[] str,int k,char[] patt,int i)
{
if(k==str.length)
{
System.out.println(patt);
return;
}
int x=str[k]-'0';
x=x-2;
int la;
if ((x == 5) || (x == 7))
la=4;
else
la=3;
for(int l=0;l<la;l++)
{
patt[i]=pattern[x].charAt(l);
print(str,k+1,patt,i+1);
}
}
}
package coding;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
public class PhoneCombine {
Map inputKeys=new HashMap();
public PhoneCombine(){
inputKeys.put('2', "ABC");
inputKeys.put('3', "DEF");
inputKeys.put('4', "GHI");
}
public void findCombine(String input,String store){
if(input.length()==0)
{System.out.println(store);
store="";
return;}
for(int i=0;i<3;i++){
store+=((String) inputKeys.get(input.charAt(0))).charAt(i);
findCombine(input.substring(1),store);
store=store.substring(0,store.length()-1);
}
}
public String execute() {
String line = null;
int val = 0;
try {
BufferedReader is = new BufferedReader(new InputStreamReader(
System.in));
line = is.readLine();
// val = Integer.parseInt(line);
} catch (NumberFormatException ex) {
System.err.println("Not a valid number: " + line);
} catch (IOException e) {
System.err.println("Unexpected IO ERROR: " + e);
}
// System.out.println("I read this number: " + val);
return line;
}
public static void main(String[] args){
PhoneCombine a=new PhoneCombine();
String input=a.execute();
//a.findCombine("23", "");
a.findCombine(input, "");
}
}
I followed this approach:
I used SET data structure to hold all the result strings.
Initially, the set will be empty. For every digit in the input, i pass the set as input to a function.
The function uses Switch case and has cases for all digits. Inside each case, i read the set elements, append all the characters (specific to the case) to the string and then put them back into the set. (The previous set elements will be cleared.) Eg: if the set has ab,ac,ad and the new set of chars is f,h then the set will have abf, abh, acf, ach, adh, adf. The updated set will be returned by the function.
Is this approach ok?? I don;t use recursion and also memory to store mappings.
Comments are welcome.
I have used a very simple approach, wherein every combination is put in a vector first character by character and once the input size is reached(say 3, for 234)...i print the vector...the vector and other elements have to be global since I am using recursion...its a very easy code to understadn if u know the basics of vectors and deque.
#include <iostream>
#include <deque>
#include <vector>
#include <string>
using namespace std;
int Get_combo(int);
char **ptr;
int typed;
int count = 65;
deque<int> mydeque;
vector<char> myvector(10);
int r;
int main() {
int result;
ptr = new char *[10];
for(int i=0;i<10;i++) {
ptr[i] = new char[4];
}
for(int i=0;i<2;i++)
for(int j=0;j<4;j++)
ptr[i][j] = '0';
ptr[2][3] = '0';
ptr[3][3] = '0';
ptr[4][3] = '0';
ptr[5][3] = '0';
ptr[6][3] = '0';
ptr[8][3] = '0';
for(int i=2;i<10;i++) {
for(int j=0;j<4;j++) {
if(ptr[i][j] != '0') {
ptr[i][j] = char(count);
count++;
}
}
}
cout<<"enter the combonation needed: ";
cin>>typed;
while(typed) {
r = typed%10;
typed = typed/10;
mydeque.push_front(r);
}
result = Get_combo(0);
return 0;
}
int Get_combo(int index)
{
int cur;
if(index >= (mydeque.size())) {
for(int j=0;j<mydeque.size();j++)
cout<<myvector[j];
cout<<"\n";
return (index-1);
}
else {
cur = mydeque[index];
for(int i=0;i<4;i++) {
if(ptr[cur][i] != '0') {
myvector[index] = ptr[cur][i];
index = Get_combo(index+1);
}
else;
}
return (index-1);
}
}
static final int PHONE_NUMBER_LENGTH = 7;
void printTelephoneWords( int[] phoneNum ){
char[] result = new char[ PHONE_NUMBER_LENGTH ];
doPrintTelephoneWords( phoneNum, 0, result );
}
void doPrintTelephoneWords( int[] phoneNum, int curDigit,
char[] result ){
if( curDigit == PHONE_NUMBER_LENGTH ){
System.out.println( new String( result ) );
return;
}
for( int i = 1; i <= 3; i++ ){
result[ curDigit ] = getCharKey( phoneNum[curDigit], i );
doPrintTelephoneWords( phoneNum, curDigit + 1, result );
if( phoneNum[curDigit] == 0 ||
phoneNum[curDigit] == 1) return;
}
}
and
#include <iostream>
#include <vector>
using namespace std;
string map[10];
void seq();
void seq(int pos, string result, vector<int> data);
int main(){
map[0]= "ABC";
map[1] = "DEF";
map[2]= "GHI";
map[4] = "JKL";
map[5]= "";
map[6] = "PQR";
map[7]= "STU";
map[8] = "VWX";
seq();
return 0;
}
void seq(){
vector<int> data;
data.push_back(5), data.push_back(2), data.push_back(0);
seq(0, "", data);
}
void seq(int pos, string result, vector<int> data){
if(pos == data.size()){
cout<<result<<endl;
return;
}
string options = map[data[pos]];
if(options.length() == 0){
seq(pos+1, result, data);
}
for(int x = 0; x < options.length(); x++){
string temp = result;
temp.push_back(options[x]);
seq(pos+1, temp, data);
}
return;
}
and
static ArrayList<String> printAllCombination(
HashMap<Character, String> map, String input) {
ArrayList<String> result = new ArrayList<String>();
if (input.length() == 0) {
return result;
}
char first = input.charAt(0);
ArrayList<String> list = printAllCombination(map, input.substring(1));
for (int i = 0; i < map.get(first).length(); i++) {
if (list.size() == 0) {
String t=""+map.get(first).charAt(i);
result.add(t);
} else {
for (String s : list) {
s = map.get(first).charAt(i) + s;
result.add(s);
}
}
}
return result;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
HashMap<Character, String> list = new HashMap<Character, String>();
list.put('1', "NULL");
list.put('2', "ABC");
list.put('3', "DEF");
list.put('4', "GHI");
list.put('5', "JKL");
list.put('6', "MON");
list.put('7', "PORS");
list.put('8', "TUV");
list.put('9', "WXYZ");
System.out.println(printAllCombination(list, "2345"));
}
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
void permute(char str[], char res[], char alphabet[], int start, int end) {
int i = 0;
if(start > end) {
printf("%s\n", res);
return;
}
for(i = 3*(str[start]-'0')-6 ; i <= 3*(str[start]-'0')-4 ; i++) {
if(i < 0) {
res[start] = str[start];
i = -1;
}
else
res[start] = alphabet[i];
permute(str, res, alphabet, start+1, end);
}
}
int main() {
char alphabet[]={'A', 'B', 'C', 'D','E','F','G','H','I','J','K','L',
'M','N','O','P','R','S','T','U','V','W','X','Y'};
char str[]="234";
char *res = (char *)malloc(strlen(str)*sizeof(char));
permute(str, res, alphabet, 0, strlen(str)-1);
return 0;
}
This can be easily done with recursion as below.
static char *charMapping[] = {"", "", "ABC", "DEF", "GHI", "JKL", "MNO", "PQRS", "TUV", "WXYZ"};
void AllPossibleStringForPhoneNumber()
{
int number = 4567;
int num = number;
int numLen = 0;
while(num != 0)
{
num = num/10;
++numLen;
}
char *str = new char[numLen+1];
str[numLen] = '\0';
FindCombination(number, str, numLen-1);
delete [] str;
}
void FindCombination(int num, char *str, int index)
{
static int counter = 0; // Just to check number of string printed
if (num == 0)
cout << ++counter << ", " << str << endl;
else
{
char *mapping = charMapping[num % 10];
int mapLen = strlen(mapping);
for (int i = 0; i < mapLen; ++i)
{
str[index] = mapping[i];
FindCombination(num / 10, str, index - 1);
}
}
}
I was giving an interview today and asked this question. I struggled during an interview but after that I gave it a try and did implement it. here is the Solution in Java.
public static List<String> deriveWordCombinations(String number){
List<String> finalWord = new ArrayList<String>();
List<String> iterative = new ArrayList<String>();
finalWord.add("");
for(int i=0;i<number.length();i++){
char c = number.charAt(i);
String stringForNumber = map.get(c);
for(String s:finalWord){
for(char cs: stringForNumber.toCharArray()){
iterative.add(s+cs);
}
}
finalWord = iterative;
iterative = new ArrayList<String>();
}
return finalWord;
}
static final HashMap<Character,String> map = new HashMap<Character,String>(){
{
put('2',"abc");
put('3',"def");
put('4',"ghi");
put('5',"jkl");
put('6',"mno");
put('7',"pqrs");
put('8',"tuv");
put('9',"wxyz");
}
};
char keyvalue[][]={"","","ABC","DEF","GHI","JKL","MNO","PQR","STUV","WXYZ"};
void permutations(char * dial,int dial_len, int index)
{
if(dial_len==index)
printf("%s",dial);
for(int i=0;i<dial_len;i++)
{
for(j=0;j<strlen(keyvalue[i])-1;j++)
{
swap (dial[i], keyvalue[i][j]);
permutations( dial,dial_len, index+1);
swap (dial[i], keyvalue[i][j]);
}
}
}
the working code is
- faker September 12, 2011//consider the cell phone keypad. No 234 is given it shud print all combinations of ADG,ADH,ADI,AEG,etc
using namespace std;
#include<stdio.h>
#include<iostream>
char* pattern[]={"ABC","DEF","GHI","JKL","MNO","PQRS","TUV","WXYZ"};
char* input;
char* patt;
int size;
void print(char* str,int k,char* patt,int i)
{
if(str[k]!='\0')
{
int x=str[k]-'0';
x=x-2;
for(int l=0;l<3;l++)
{
patt[i]=pattern[k][l];
print(str,k+1,patt,i+1);
}
cout<<endl;
}
else if(i==k)
{
printf("%s\n",patt);
return;
}
}
int main()
{
input=new char[25];
cout<<"Enter the input string\n";
cin>>input;
size=sizeof(input);
patt=new char[size];
print(input,0,patt,0);
return 0;
}