Epic Systems Interview Question Software Engineer / Developers
0,1 are not mapped to any alphabets, hence they are left unchanged. The remaining digits are 2(A,B,C),7(P,Q,R),9(V,W,X,Y,Z). So, 279 can be replaced by their respective alphabets.
2(A)7(P)9(W)and so on.
Can you explain how to use dynamic programming? Since the result is to output all the numbers, no optimal and no cache is needed to solve temporary data. So I think this problem should not use dynamic programming , but just use recursive call to solve this problem. If I misunderstand, please tell me the reason.
// read string, input
// delete all 0's and 1's from the string
// find the length of the string, L
// find the number of strings generated, G
// create G character arrays,List each with length, L
// loop over the character arrays and
// insert the correct code at each index for each character array or string
// read string, input
String input = scanner.next();
// delete all 0's and 1's from the string
input.replace('0','/0'); => this will replace all 0's with a space
input.replace('1','/0');
input.trim() => this will delete all spaces!
// find the length of the string, L
L = input.length();
// find the number of strings generated, G
for( int i = 0; i < input.length; i++ )
{
// Since all numbers except 9 has 4 choices
if( input.charAt(i) == 9
G += 4;
else
G += 3;
}
// create G character arrays,List each with length, L
Char[][] List = new char[G][L];
// loop over the character arrays and insert the codes
If the problem is to produce mobile pad like sequence when numbers are pressed then following is code for it.
#include <stdlib.h> // for itoa() call
#include <stdio.h> // for printf() call
#include <string.h>
#include <conio.h>
int main() {
int i=-1;
int rep = 0, rep_f = 1;
char curr_val = '1', prev_val = '0';
char mobile_pad[50];
//get input char using getch() in while loop
printf("Enter the sequence\n");
while((curr_val=getchar())!='\n'){ //read input as char stream
if(curr_val > '1' && curr_val <= '9'){ //useful value?
if(curr_val == '9') rep_f = 4; //account for 4 letters for 9
else rep_f = 3;
if(prev_val == curr_val){
rep++; //repeating values
if(!(rep%rep_f)) i++; //moving to next element in array mobile_pad
}
else{
rep = 0;
i++;
}
if(!(rep%rep_f)){ //assign first time or after all rep.
switch (curr_val){
case '2': mobile_pad[i] = 'A';
break;
case '3': mobile_pad[i] = 'D';
break;
case '4': mobile_pad[i] = 'G';
break;
case '5': mobile_pad[i] = 'J';
break;
case '6': mobile_pad[i] = 'M';
break;
case '7': mobile_pad[i] = 'P';
break;
case '8': mobile_pad[i] = 'S';
break;
case '9': mobile_pad[i] = 'V';
break;
}
}
else mobile_pad[i]++; //increments ASCII value and points to next alphabet
}
prev_val = curr_val;
}
mobile_pad[++i] = '\0';
printf("\nThe alphabets corresponding to sequence you entered are:\n%s",mobile_pad);
return 0;
}
#include<iostream>
#include<string>
#include<vector>
using namespace std;
vector<std::string> strValue(10);
void doNumPrint(string prefix, string str, int startIndex)
{
//cout<<prefix;
int len = str.length() - startIndex;
if(len == 0)
{
cout<<prefix<<"\n"<<endl;
return;
}
int value = (str[startIndex] - 48);
int stringLen = strValue[value].length();
if(stringLen == 0)
doNumPrint(prefix,str,startIndex+1);
else
{
for(int i = 0; i < stringLen;i++)
{
prefix += strValue[value][i];
doNumPrint(prefix, str,startIndex+1);
prefix = prefix.substr(0,prefix.length()-1);
}
}
}
void NumPrint(string str)
{
doNumPrint("",str,0);
}
int main()
{
strValue[0] = "";
strValue[1] = "";
strValue[2] = "ABC";
strValue[3] = "DEF";
strValue[4] = "GHI";
strValue[5] = "JKL";
strValue[6] = "MNO";
strValue[7] = "PQR";
strValue[8] = "STU";
strValue[9] = "VWXYZ";
string str = "27190000";
NumPrint(str);
return 0;
}
This was nearly my exact response to this question. Although this problem is solvable in several different ways, a recursive function call is clearly the cleanest and most efficient. Took me about 25 minutes to figure this one out :S.
you may try this...
#include<stdio.h>
#include<string.h>
#include<malloc.h>
char *map[] = {"0","1","ABC","DEF","GHI","JKL","MNO","PQR","STU","VWXYZ"};
char n[20];//={"2345"};
char a[20]={0};
void parse(int index)
{
int i =0;
if(index < strlen(n))
{
for(i=0;i<strlen(map[n[index]-48]);i++)
{
a[index]=(char)(map[n[index]-48][i]);
//a[index] = 'a';
parse(index+1);
}
}
else {
a[index] = '\0';printf("\n %s",a);
}
}
int main()
{
printf("\n Enter a number ");
scanf("%s",n);
parse(0);
return 0;
}
Good thinking but this solution will also print 0 and 1 so small correction -
char *map[] = {" "," ","ABC","DEF","GHI","JKL","MNO","PQR","STU","VWXYZ"};
char n[20];//={"2345"};
char a[20]={0};
void parse(int index, int index2)
{
int i =0;
if(index < strlen(n))
{
for(i=0;i<strlen(map[n[index]-48]);i++)
{
char c=(char)(map[n[index]-48][i]);
if(c!= ' ') { a[index2] = c; parse(index+1,index2+1);}
else parse(index+1,index2);
}
}
else {
a[index2] = '\0';printf("\n %s",a);
}
}
#include<stdio.h>
#include<string.h>
void func(int *a, char *val){
int k;
if(*a=='\0'){
*val='\0';
for(int i=0; i<strlen(val); i++){
printf("%c", val[i]);
}
printf("\n");
}
else{
if(*a==9){
k=5;
}
else{
k=3;
}
for(int j=0; j<k; j++){
*val='A'+3*(*a-2)+j;
func(a+1, val+1);
}
}
return;
}
int main(){
int a[]={3, 4, 6, 2};//assume no 0,1 as of now(can be done)
char val[100];
func(a, val);
return 1;
}
somebody comment if something is wrong above.
<pre lang="" line="1" title="CodeMonkey45809" class="run-this">
ArrayList tele_pad = {"","","ABC","DEF","GHI","JKL","MNO","PQR","STU","VWXYZ"};
public void numbers_letters (int num) {
String numStr = Integer.toString(num);
parse("",numStr, 0);
}
public void parse(String prefix, String str, int index) {
if (str.length - index == 0) {
System.out.println(prefix);
return;
}
int v = str[index] -48;
int len = tele_pad[v].length;
if (len == 0) parse(prefix, str, index+1);
else {
for (int i=0; i<len; i++) {
prefix += tele_pad[v][i];
parse(prefix, str, index+1);
prefix = prefix.subString(0, prefix.length - 1);
}
}
}
}
</pre><pre title="CodeMonkey45809" input="yes">
</pre>
<pre lang="" line="1" title="CodeMonkey34253" class="run-this">package keypad;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
public class KeyPad {
private ArrayList<String> telKeys;
public KeyPad()
{
this.telKeys = new ArrayList<String>();
telKeys.add(0,"0");
telKeys.add(1,"1");
telKeys.add(2,"ABC");
telKeys.add(3,"DEF");
telKeys.add(4,"GHI");
telKeys.add(5,"JKL");
telKeys.add(6,"MNO");
telKeys.add(7,"PQR");
telKeys.add(8,"STU");
telKeys.add(9,"VWXYZ");
}
public char getCharKey( int teleKey , int place)
{
char out;
String str = this.telKeys.get(teleKey);
out = str.charAt(place);
return out;
}
public static void main(String[] args) {
InputStreamReader input = new InputStreamReader(System.in);
BufferedReader reader = new BufferedReader(input);
String phoneNum = "";
String zeroOne;
//StringBuilder out = new StringBuilder();
char [] out;
char [] in;
int length = 0,i,telKey,j;//count=0;
char letterKey;
System.out.println("Enter a phone Number : ");
try
{
phoneNum = reader.readLine();
length = phoneNum.length();
}
catch (Exception ee)
{
System.out.println("Error in reading Phone Num " + ee.getMessage());
}
KeyPad kpd = new KeyPad();
in = phoneNum.toCharArray();
out = new char[length];
//Printing the combination with the very first letter corresponding to each digit
//in the phoneNum input
for ( i = 0; i < length; i++ )
{
telKey = (in[i]) - '0';
letterKey = kpd.getCharKey(telKey , 0);
out[i] = letterKey;
}
zeroOne = new String(out);
if ( phoneNum.equalsIgnoreCase(zeroOne))
{
System.out.println("You have only one Possible Combination : " + zeroOne) ;
System.exit(0);
}
//Main loop to print the combination of letters for each didgit in phone Num
while(true)
{
//Printing the combination with the first letters
System.out.println(out);
//System.out.println("Total Combinations = " + count);
//Start at the right most end of the input and then change to the left
for ( j = length-1; j >=-1; j--)
{
/* You are done because you tried to carry the left most digit
*
*/
if ( j == -1)
return;
/*otherwise we'r not done we must continue
*
*/
telKey = (in[j]) - '0';
//Exceptional condition for input 9 and for rest of others
if ( telKey == 9)
{
//System.out.println("This case is not coded :");
//System.exit(0);
if ( in[j] == '0' ||
in[j] == '1' ||
kpd.getCharKey((in[j] - '0'),4) == out[j])
{
out[j] = (kpd.getCharKey( in[j] - '0', 0));
}
else if ( kpd.getCharKey((in[j] - '0'), 0) == out[j])
{
out[j] = (kpd.getCharKey( in[j] - '0', 1));
break;
}
else if ( kpd.getCharKey((in[j] - '0'), 1) == out[j])
{
out[j] = (kpd.getCharKey( in[j] - '0', 2));
break;
}
else if ( kpd.getCharKey((in[j] - '0'), 2) == out[j])
{
out[j] = (kpd.getCharKey( in[j] - '0', 3));
break;
}
else if ( kpd.getCharKey((in[j] - '0'), 3) == out[j])
{
out[j] = (kpd.getCharKey( in[j] - '0', 4));
break;
}
}
else
{
if ( in[j] == '0' ||
in[j] == '1' ||
kpd.getCharKey((in[j] - '0'),2) == out[j])
{
out[j] = (kpd.getCharKey( in[j] - '0', 0));
}
else if ( kpd.getCharKey((in[j] - '0'), 0) == out[j])
{
out[j] = (kpd.getCharKey( in[j] - '0', 1));
break;
}
else if ( kpd.getCharKey((in[j] - '0'), 1) == out[j])
{
out[j] = (kpd.getCharKey( in[j] - '0', 2));
break;
}
}
}//End of for loop
}//End of while loop
//System.out.println("Total Combinations = " + count);
}//End of main
}//End of Class
</pre><pre title="CodeMonkey34253" input="yes">
</pre>
<pre lang="" line="1" title="CodeMonkey51500" class="run-this">/* The class name doesn't have to be Main, as long as the class is not public. */
#include "stdafx.h"
#include "stdafx.h"
#include "stdio.h"
#include "conio.h"
#include "iostream"
#include "fstream"
#include "string"
#include "list"
#include "vector"
#include "map"
#include "string"
using namespace std;
vector<string> padrows(3);
void main()
{
bool allow = false;
int index = 0;
padrows[0]="123";
padrows[1]="456";
padrows[2]="789";
vector<string> code(3);
code[2] = "0000";//Result
cout<<"\n4 digit : ";
cin>> code[0];
cout<<"\n match : ";
cin>> code[1];
for(int i = 0; i < 4; i++)//check for each of the four digits
{
for(int tc1=0;tc1<=2;tc1++)//traverse row
{
for(int tc2=0;tc2<=2;tc2++)//traverse col
{
//int SR,SC,DR,DC;
vector<string> allowed(6);
if(code[1][i] == padrows[tc1][tc2])//get the row and col of to match code
{
//get every element of tc1 and tc2 in allowed vector
allowed[0]= padrows[tc1][0];
allowed[1]= padrows[tc1][1];
allowed[2]= padrows[tc1][2];
allowed[3]=padrows[0][tc2];
allowed[4]=padrows[1][tc2];
allowed[5]=padrows[2][tc2];
//cout<"\nFound in row number: "<<tc1+1;
//cout<<"\nFound in col number: "<<tc2+1;
//match code[0][i] with every element inside allowed
for (int e1=0; e1<=5; e1++)
{
if (code[0][i] ==allowed[e1][0])
{
code[2][i] ='1';
}
}
}
//if(code[0][i] == padrows[tc1][tc2])//get the row and col to the input code
//{
// DR=tc1;
// DC=tc2;
// //cout<<"\nFound in row number: "<<tc1+1;
// //cout<<"\nFound in col number: "<<tc2+1;
//}
}
}
}
if (code[2]=="1111")
cout <<"\nAllow";
else
cout <<"\nDo not allow";
}
</pre><pre title="CodeMonkey51500" input="yes">
1123
1126</pre>
<pre lang="" line="1" title="CodeMonkey34755" class="run-this">#include "stdafx.h"
#include "stdafx.h"
#include "stdio.h"
#include "conio.h"
#include "iostream"
#include "fstream"
#include "string"
#include "list"
#include "vector"
#include "map"
#include "string"
using namespace std;
vector<string> padrows(3);
void main()
{
bool allow = false;
int index = 0;
padrows[0]="123";
padrows[1]="456";
padrows[2]="789";
vector<string> code(3);
code[2] = "0000";//Result
cout<<"\n4 digit : ";
cin>> code[0];
cout<<"\n match : ";
cin>> code[1];
for(int i = 0; i < 4; i++)//check for each of the four digits
{
for(int tc1=0;tc1<=2;tc1++)//traverse row
{
for(int tc2=0;tc2<=2;tc2++)//traverse col
{
//int SR,SC,DR,DC;
vector<string> allowed(6);
if(code[1][i] == padrows[tc1][tc2])//get the row and col of to match code
{
//get every element of tc1 and tc2 in allowed vector
allowed[0]= padrows[tc1][0];
allowed[1]= padrows[tc1][1];
allowed[2]= padrows[tc1][2];
allowed[3]=padrows[0][tc2];
allowed[4]=padrows[1][tc2];
allowed[5]=padrows[2][tc2];
//cout<"\nFound in row number: "<<tc1+1;
//cout<<"\nFound in col number: "<<tc2+1;
//match code[0][i] with every element inside allowed
for (int e1=0; e1<=5; e1++)
{
if (code[0][i] ==allowed[e1][0])
{
code[2][i] ='1';
}
}
}
//if(code[0][i] == padrows[tc1][tc2])//get the row and col to the input code
//{
// DR=tc1;
// DC=tc2;
// //cout<<"\nFound in row number: "<<tc1+1;
// //cout<<"\nFound in col number: "<<tc2+1;
//}
}
}
}
if (code[2]=="1111")
cout <<"\nAllow";
else
cout <<"\nDo not allow";
}
</pre><pre title="CodeMonkey34755" input="yes">You can give whatever you want. This code is working. I compiled it.
Entered digit:1123
Match with digit: 1126</pre>
In this type of question(ex. permutation/combination), I prefer using string to hold and pass intermediate data through recursive function.
static void printKeypad(int number){
String numbers = String.valueOf(number);
String eff_numbers = new String();
String combo = new String();
for(int i=0;i<numbers.length();i++){
if(numbers.charAt(i) != '0' && numbers.charAt(i) != '1'){
eff_numbers += numbers.charAt(i);
}
}
printKeypad(eff_numbers, combo);
}
static void printKeypad(String eff_numbers, String combo) {
if(eff_numbers.length() == 0){
System.out.println(combo);
return;
}
int index = (int)(eff_numbers.charAt(0) - '0');
eff_numbers = eff_numbers.substring(1);
String pad = keypad[index];
for(int i=0;i<pad.length();i++){
printKeypad(eff_numbers, combo+pad.charAt(i));
}
}
Provide a python solution, just for you consideration
keys = {'0':'0',
'1':'1',
'2':'ABC2',
'3':'DEF3',
'4':'GHI4',
'5':'JKL5',
'6':'MNO6',
'7':'PQRS7',
'8':'TUV8',
'9':'WXYZ9',
'*':' '}
def split(inp):
result = []
result = inp.split('#')
return result
def decode(num):
i=0
result = []
while i< len(num):
if num[i]!=num[0]:
result.append(num[:i])
num = num[i:]
i = 0
i+=1
result.append(num)
return result
def translate(inp):
splt = split(inp)
char = ''
result = ''
for i in range(len(splt)):
inner_splt = decode(splt[i])
for j in range(len(inner_splt)):
if len(inner_splt[j]) == 1:
result+= keys[inner_splt[j]][0]
else:
char = str(inner_splt[j])
k = len(inner_splt[j])%len(keys[char[0]])
result+= keys[char[0]][k-1]
return result
print translate('23#2*2')
Can u please explain how 27190000 outputs APV
- K May 25, 2010APW
APX
APY
APZ ?
thanks,