Epic Systems Interview Question Software Engineer / Developers
Country: United States
Interview Type: Written Test
Every thing works fine except a small change.
temp=s[x-1] because the strings are stored in an array.
What about the time complexity? This is the brute force way i guess..Is there any better way to achieve better time complexity?
i think temp=s[x] is correct.. since if the integer has 9 as one of its digits, then the string corresponding to 9 can be accessed by s[9] and not s[8]..
I failed to answer this at the time of the test. Below is the solution that I worked out later.
#include <iostream>
#include <string>
using namespace std;
string pattern[] = {"","vtfrq","ftk","wzbg","rs","","fir","p","lo","p"};
void Generate (const string& keystroke, int curr, int size) {
static string str; /* The output string */
if (str.length() == size) {
cout << str << endl;
return;
}
int digit = keystroke[curr] - '0';
/* This if-conditional passes when the key is
* zero or five, which are NULLs. In that case,
* proceed to the next digit. Hence curr + 1.
*/
if (pattern[digit].empty() == true) {
Generate (keystroke, curr + 1, size);
return;
}
/* Loop through the characters for the current keystroke.
* Add that character to the output string and proceed to
* the next key. When you return (i.e., backtrack), pop the
* last character.
*/
for (int i = 0; i < pattern[digit].length(); i++) {
str.push_back (pattern[digit][i]);
Generate (keystroke, curr + 1, size);
str.erase (str.end() - 1); /* Pop now, since you are backtracking */
}
}
int main ( ) {
string keystroke;
/* count is the number of characters in each output string */
int count = 0;
cout << "Enter your keystroke: ";
cin >> keystroke;
for (int i = 0; i < keystroke.length(); i++) {
int digit = keystroke[i] - '0';
if (digit < 0 || digit > 9) {
cout << "Only numericals allowed." << endl;
return 1;
}
if (pattern[digit].empty() == false) count++;
}
/* The function that generates the sequences. Is recursive.
* The second parameter is a count of how many characters
* have been generated so far. The third parameters gives
* the maximum number of characters each sequence contains.
*/
Generate (keystroke, 0, count);
return 0;
}
Not very sure. Probably, the complexity should be the product of the cardinality of each keystroke, since that is the total number of outputs we are generating. To put it another way, that is number of times we're iterating the for loop. So for 9801, the number of times the for loop is iterating is |9| * |8| * |1| = 1 * 2 * 5 = 10.
For a keystroke (n1)(n2)(n3).., the runtime should be |n1| * |n2| * |n3| *.... (where only non empty keys are considered)
I assumed that the sequence of digit has given.
#include <stdio.h>
#include <string.h>
void findCombination(char (*key)[6], char *toFind, char *temp, int start, int len)
{
if(!(*toFind))
{
temp[start]='\0';
printf("%s\n ",temp);
}
else{
int i=0,j=0;
i=*toFind-'0';
if( !strcmp("NULL", key[i]) )
findCombination(key, toFind+1, temp, start,len);
else{
for(;key[i][j]; j++)
{
temp[start]= key[i][j];
findCombination(key, toFind+1, temp, start+1,len);
}
}
}
}
int main()
{
char key[][6]={"NULL", "vtfrq", "ftk", "wzbg", "rs", "NULL", "fir", "p", "io", "p"};
char toFind[]="9801";
char temp[strlen(toFind)+1];
findCombination(key, toFind, temp, 0, strlen(toFind));
return 0;
}
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<conio.h>
#include<math.h>
using namespace std;
char str[11];
void permut(int pos,int dig,int l,int n[],char a[][10])
{ if(pos!=dig-1)
{ str[pos]=a[n[pos]][l];
permut(pos+1,dig,0,n,a);
}
else
{ for(int i=0;i<strlen(a[n[pos]]);i++)
{ str[pos]=a[n[pos]][i];
puts(str);
}
return;
}
if(l<strlen(a[n[pos]]))
permut(pos,dig,l+1,n,a);
}
int main()
{ char a[10][10];
int i,n,num[11];
for(i=0;i<10;i++)
gets(a[i]);
cin>>n;
int k=n,dig=0;
while(k>0)
{ k/=10;
dig++;
}
int l=dig-1;
k=n;
while(l>=0)
{ num[l]=k%10;
k/=10;
l--;
}
permut(0,dig,0,num,a);
getch();
return 0;
}
#include<iostream>
using namespace std;
string values[]={"NULL","vtfrq","ftk","wzbg","rs","NULL","fir","p","lo","p"};
void words(int len, string str,string temp, int index)
{
if (len==0)
{
cout<<temp<<endl;
}
else
{
char t=str[index];
int k=t-'0';
string l=values[k];
if (l!="NULL")
{
for (int i=0;i<l.length();i++)
{
temp=temp+l[i];
words(len-1,str,temp,index+1);
temp=temp.substr(0,temp.length()-1);
}
}
else {words(len-1,str,temp,index+1);}
}
}
int words_helper(string st)
{
words(st.length(),st,"",0);
}
int main ()
{
words_helper("01253");
}
#include <stdio.h>
#include <string.h>
const char array[][6] = {"", "vtfrq", "ftk", "wzbg", "rs", "", "fir", "p", "lo", "p"
};
void formation (const char* input_digits, int index, char* out_str) {
if (index > strlen (input_digits)-1) {
printf ("%s\n", out_str);
} else {
int array_index = input_digits[index]-'0';
const char *array_string = array[array_index];
if (strlen (array_string) == 0) { //NULL is represented as "" in the array
formation (input_digits, index+1, out_str);
} else {
char buff[6] = {0};
int i;
for (i = 0; i < strlen (array_string); i++) {
snprintf (buff, sizeof (buff), "%s%c", out_str, array_string[i]);
formation (input_digits, index+1, buff);
}
}
}
}
int validate_input (short input_length, const char *input) {
short index;
for (index = 0; index < input_length; index++) {
if (input[index] < '0' || input[index] > '9')
return 1;
}
return 0;
}
int main(int args, char* argv[])
{
if (args != 2) {
printf("Usage: %s <input>\n", argv[0]);
return 1;
}
short input_length = strlen(argv[1]);
const char* input = argv[1];
if ( input_length < 1) {
printf("Usage: %s <series of digits>\n", argv[0]);
return 1;
}
if ( validate_input(input_length, input) ) {
printf("Usage: %s <series of digits> ex: %s 1234\n", argv[0], argv[0]);
return 1;
}
formation (input, 0, "");
return 0;
}
#include<iostream>
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
typedef vector<string> sv;
void printA(string str)
{
for(int i=0;i<str.length();i++)
cout<<str[i];
cout<<endl;
}
void all_number(string str,string given,int i,int len,sv myvector)
{
if(i==len)
printA(str);
else
{
int temp=given[i]-'0';
if(temp!=0 && temp!=5)
{
//cout<<temp<<"-this is given string";
for(int j=0;j<myvector[temp].length();j++)
{
//cout<<myvector[temp][j]<<"--this is"<<endl;
string s=myvector[temp];
str.push_back(s[j]);
all_number(str,given,i+1,len,myvector);
str.erase(str.end()-1);
}
}
else
{
all_number(str,given,i+1,len,myvector);
}
}
}
int main()
{
sv myvector;
myvector.push_back("");
myvector.push_back("vtfrq");
myvector.push_back("ftk");
myvector.push_back("wzbg");
myvector.push_back("rs");
myvector.push_back("");
myvector.push_back("fir");
myvector.push_back("p");
myvector.push_back("lo");
myvector.push_back("p");
char p[10];
scanf("%s",p);
string s(p);
//cout<<s[0]-'0'<<endl;
string str;
all_number(str,s,0,s.length(),myvector);
}
import java.util.Scanner;
public class keystroke {
public static void main(String[] args) {
@SuppressWarnings("resource")
Scanner sc=new Scanner(System.in);System.out.println("input some numbers");
StringBuffer sb=new StringBuffer();
String in="";
while(!in.equals("exit")){
if(sc.hasNext()){
sb.append(in);
in=sc.next();
}
}
String innum=sb.toString();
String num1=innum.replace("0", "");
String num=num1.replace("5", "");
System.out.println("your input number exclude 0 and 5 is :"+num);
String[] seqs=allseqs(num);
for(String s:seqs){
System.out.println(s);
}
}
private static String[] allseqs(String num) {
String[] result=null;
String[] str={null,"vtfrq","ftk","wzbg","rs",null,"fir","p","lo","p"};
if(num.length()>1){
int index=num.charAt(0)-48;
String str1=str[index];
char[] s=str1.toCharArray();
String nextnum=num.substring(1);
String[] nexnums=allseqs(nextnum);
StringBuffer sb=new StringBuffer();
for(int i=0;i<s.length;i++){
for(int j=0;j<nexnums.length;j++){
sb.append(s[i]);
sb.append(nexnums[j]);
sb.append(",");
}
}
result=sb.toString().split(",");
}
if(num.length()==1){
int index=num.charAt(0)-48;
String str1=str[index];
char[] s=str1.toCharArray();
String[] r=new String[s.length];
for(int i=0;i<s.length;i++){
r[i]=Character.toString(s[i]);
}
result=r ;
}
return result;
}
}
Python working code.
Modification from string permutation question.
"""
2:48
@Python 2.7
User inputs a sequence of digits. Every digit is a keystroke, that is equivalent to some character out of a sequence of characters. Digit zero and five mean NULL. The table is given below
0 - NULL
1 - v, t, f, r, q
2 - f, t, k
3 - w, z, b, g
4 - r, s
5 - NULL
6 - f, i, r
7 - p
8 - l, o
9 - p
Generate all possible character sequence for a given sequence of digits.
Ex - If the user input 9801, your program should generate
{plv, plt, plf, plr, plq, pov, pot, pof, por, poq} (not necessarily in this order).
This problem is somewhat similar to the SMS problem. It basically boils down to generating a cartesian product of the character sets corresponding to keys.
"""
class InputsToChar(object):
def __init__(self, inputs):
if inputs is None:
print 'Invalid Inputs!'
raise SystemExit
inputs = str(inputs)
inputs = inputs.replace('0', '')
inputs = inputs.replace('5', '')
self._inputs = inputs
self._charArray = [None, 'vtfrq', 'ftk', 'wzbg', 'rs', None, 'fir', 'p', 'lo', 'p']
self._result = []
def printAll(self, pos = 0):
if pos > len(self._inputs) - 1:
print ''.join(self._result)
return
for c in self._charArray[int(self._inputs[pos])]:
self._result.append(c)
self.printAll(pos + 1)
self._result.pop()
if __name__ == '__main__':
input = InputsToChar(9801)
input.printAll()
This is an odometer problem. Skip over the null digits (0 and 5). For the rest of the digits, populate the odometer with the first character for each digit. Then start rolling the odometer. Start with the digit on the end and go to its next character. If you reach the end of that digit's list, go back to the first character for that digit (and all previous digits) and roll the next digit's character. When you overflow the last digit's character, you are done.
#include<stdio.h>
#include<string.h>
void func(char *str, char *seq,int dig);
int main()
{
int n;
func(" ","123",0);
scanf("%d",&n);
}
void func(char str[], char seq[], int dig)
{
static char a[][4]={"abc","defk","ghi","jkl","nmo","pqr","rst","uvw","xyz"};
static int b[]={3,4,3,3,3,3,3,3};
char s[10],s2[100],s3[100];
int temp,i;
if(strlen(seq)==0)
{printf("%s",str);
return;
}
strncpy(s,seq,1);
s[1]='\0';
temp=atoi(s);
for(i=0;i<b[temp];i++)
{
s[0]=a[temp][i];
strcpy(s2,str);
strcat(s2,s);
s2[strlen(s2)]='\0';
strncpy(s3,seq+1,strlen(seq)-1);
s3[strlen(s3)]='\0';
func(s2,s3,dig+1);
}
}
#include<stdio.h>
#include<string.h>
void func(char *str, char *seq,int dig);
int main()
{
int n;
func(" ","123",0);
scanf("%d",&n);
}
void func(char str[], char seq[], int dig)
{
static char a[][4]={"abc","defk","ghi","jkl","nmo","pqr","rst","uvw","xyz"};
static int b[]={3,4,3,3,3,3,3,3};
char s[10],s2[100],s3[100];
int temp,i;
if(strlen(seq)==0)
{printf("%s",str);
return;
}
strncpy(s,seq,1);
s[1]='\0';
temp=atoi(s);
for(i=0;i<b[temp];i++)
{
s[0]=a[temp][i];
strcpy(s2,str);
strcat(s2,s);
s2[strlen(s2)]='\0';
strncpy(s3,seq+1,strlen(seq)-1);
s3[strlen(s3)]='\0';
func(s2,s3,dig+1);
}
}
public static void allString(String s1,String arr[],String path,int len){
if(len == 0){
System.out.println(path);
return;
}
String str = arr[Character.getNumericValue(s1.charAt(0))];
if(str != null){
for (char c : str.toCharArray()){
allString(s1.substring(1),arr,path+c,len-1);
}
}
else{
allString(s1.substring(1),arr,path,len-1);
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
//int a[] = {3, 7, 12, 2, 25, 8, 9, 13, 10, 0 };
//System.out.println(avg(a));
String [] s = {null,"vtfrq","ftk","wzbg","rs",null,"fir","p","lo","p"};
allString("9801",s,"",4);
- Biswajit Sinha August 23, 2012package programs; import java.util.Scanner; public class program4 { public static String [] s = {null,"vtfrq","ftk","wzbg","rs",null,"fir","p","lo","p"}; public static void Combination(String prefix, String num ) { if(num.length()==0) System.out.println(prefix); else { int x = Integer.parseInt(num.charAt(0)+""); String temp = new String(); temp = s[x]; if(temp!=null) { for(int j=0;j<temp.length();j++) { Combination(prefix+temp.charAt(j),num.substring(1,num.length())); } } else Combination(prefix,num.substring(1, num.length())); } } public static void main(String args[]) { Scanner in = new Scanner(System.in); int num; System.out.print("Enter a number: "); num = in.nextInt(); Combination("",Integer.toString(num)); } }