Epic Systems Interview Question Software Engineer / Developers
Country: United States
Interview Type: Written Test
my working code. please correct me if something is wrong.
#include <iostream>
#include <string>
#include <vector>
using namespace std;
void phoneNum(string set, string src, int numLeft) {
if (numLeft == 0) {
cout << src << endl;
return;
}
for (int i = 0; i < set.length(); ++i){
if (src.length() == 0) {
phoneNum(set, src + set[i], numLeft - 1);
} else {
if (set[i] != src[src.length() - 1]) {
phoneNum(set, src + set[i], numLeft - 1);
}
}
}
}
void phone(int n, vector<char> disAllowed) {
string tmp = "0123456789";
for (int i = 0; i < tmp.length(); ++i){
for (int j = 0; j < disAllowed.size(); ++j) {
if (tmp[i] == disAllowed[j]) {
tmp = tmp.substr(0, i) + tmp.substr(i + 1, tmp.length() - i - 1);
}
}
}
bool hasFour = false;
string tmpNoFour = "";
for (int i = 0; i < tmp.length(); ++i) {
if(tmp[i] == '4') {
hasFour = true;
tmpNoFour = tmp.substr(0, i) + tmp.substr(i + 1, tmp.length() - i - 1);
}
}
if (hasFour) {
phoneNum(tmp, "4", n - 1);
phoneNum(tmpNoFour, "", n);
} else {
phoneNum(tmp, "", n);
}
}
void main(){
char a[] = {'1','2','3'};
vector<char> b(&a[0], &a[0] + 3);
phone(3, b);
cin.get();
}
package epic;
import java.util.Vector;
public class phone {
public static void main(String argv []){
int n1=3,n2=7,n3=5;
int i;
Vector v1 = new Vector<Integer>();
for(i=0; i<10; i++){
v1.add(i);
}
System.out.println(v1);
v1.removeElement(Integer.valueOf(n1));
v1.removeElement(Integer.valueOf(n2));
v1.removeElement(Integer.valueOf(n3));
System.out.println(v1);
for(i=0; i<v1.size(); i++){
addPhoneNumber(String.valueOf(v1.get(i)), v1,3);
}
}
public static void addPhoneNumber(String src,Vector<Integer> allowed,int rem){
int i,k;
if(rem == 0){
/*
* check for 4
*/
}
else{
k=0;
String org = src;
int temp = rem;
while(k<allowed.size()){
src = org;
rem = temp;
for(i=k; i<k+rem; i++){
if(!src.equals("4") && allowed.get(i%allowed.size())==4){
src = "4" + src;
rem--;
}
else if(Integer.parseInt(src) == allowed.get(i%allowed.size())){
rem++;
}
else{
src = src + String.valueOf(allowed.get(i%allowed.size()));
rem--;
}
}
System.out.println(src);
k++;
}
}
}
}
# -*- coding: utf-8 -*-
"""
Created on Thu Dec 25 21:05:03 2014
@author: praneethpuligundla
"""
import math
def valid_phone_number(num,dis_list):
num=num-1
startnum=int(math.pow(10,num))
lastnum=int(math.pow(10,num+1))
for i in range(startnum,lastnum):
if check_valid_phone(i,num,dis_list):
print i
def check_valid_phone(phno,num,dis_list):
firstdigit=phno/(10**num-1)
fourflag=False
if firstdigit==4:
fourflag==True
count_four=0
previous=None
current=None
while phno > 0:
digit=phno%10
current=digit
phno=phno/10
if current == previous:
return False
if digit in dis_list:
return False
if digit==4:
count_four+=1
previous=current
if count_four >= 1 and fourflag == False:
return False
return True
valid_phone_number(4,[2,7,9])
import java.util.*;
class PhoneNum {
public static void generatePhoneNumber(String s,ArrayList<Integer> l,int len,int k)
{
if (len==0&&s.length()>1) {System.out.println(s);return;}
for (int i=0;i<l.size();i++)
if (l.get(i)==4) {if (s.length()==0) generatePhoneNumber("4",l,len-1,k+1);}
else if(s.length()==0||(s.charAt(s.length()-1)-'0')!=l.get(i))generatePhoneNumber(s+l.get(i),l,len-1,k+1);
}
public static void main(String args []){
int n1=9,n2=7,n3=5;
ArrayList<Integer> v1 = new ArrayList<Integer>();
for(int i=0; i<10; i++) v1.add(i);
System.out.println(v1);
v1.remove(Integer.valueOf(n1));
v1.remove(Integer.valueOf(n2));
v1.remove(Integer.valueOf(n3));
System.out.println(v1);
generatePhoneNumber("",v1,4,0);
}
}
class solution
{
vector<string> PhoneNumber(int n,vector<char>& notAllowed)
{
vector<char> option_has4={0,1,2,3,4,5,6,7,8,9};
vector<char> option_not4={0,1,2,3,5,6,7,8,9};
vector<string> result_not4=findPhoneNumber(n,option_not4,0,notAllowed,"");
vector<string> result_has4=findPhoneNumber(n-1,option_has4,0,notAllowed,"");
for(int i=0;i<result_has4.size();i++)
{
result_not4.push_back("4"+result.has4[i]);
}
return result_not4;
}
vector<string> findPhoneNumber(int n,vector<char> option,int usedNotAllowed,vector<char>& notAllowed,char last)
{
if(n==0)
{
return vector<string>(1,"");
}
for(int i=0;i<option.size();i++ )
{
if(option[i]==last) continue;
vector<string> temp_result;
if(find(notAllowed.begin(),notAllowed.end(),option[i])==notAllowed.end())
{
temp_result=findPhoneNumber(n-1,option,usedNotAllowed,notAllowed,option[i]);
}
else
{
if(usedNotAllowed==3)
{
continue;
}
temp_result=findPhoneNumber(n-1,option,usedNotAllowed-1,notAllowed,option[i]);
}
for(int j=0;j<temp_result.size();j++)
{
temp_result[j]=string(1,option[i])+temp_result[j];
}
}
return temp_result;
}
}
class solution
{
vector<string> PhoneNumber(int n,vector<char>& notAllowed)
{
vector<char> option_has4={0,1,2,3,4,5,6,7,8,9};
vector<char> option_not4={0,1,2,3,5,6,7,8,9};
vector<string> result_not4=findPhoneNumber(n,option_not4,0,notAllowed,"");
vector<string> result_has4=findPhoneNumber(n-1,option_has4,0,notAllowed,"");
for(int i=0;i<result_has4.size();i++)
{
result_not4.push_back("4"+result.has4[i]);
}
return result_not4;
}
vector<string> findPhoneNumber(int n,vector<char> option,int usedNotAllowed,vector<char>& notAllowed,char last)
{
if(n==0)
{
return vector<string>(1,"");
}
for(int i=0;i<option.size();i++ )
{
if(option[i]==last) continue;
vector<string> temp_result;
if(find(notAllowed.begin(),notAllowed.end(),option[i])==notAllowed.end())
{
temp_result=findPhoneNumber(n-1,option,usedNotAllowed,notAllowed,option[i]);
}
else
{
if(usedNotAllowed==3)
{
continue;
}
temp_result=findPhoneNumber(n-1,option,usedNotAllowed-1,notAllowed,option[i]);
}
for(int j=0;j<temp_result.size();j++)
{
temp_result[j]=string(1,option[i])+temp_result[j];
}
}
return temp_result;
}
}
class solution
{
vector<string> PhoneNumber(int n,vector<char>& notAllowed)
{
vector<char> option_has4={0,1,2,3,4,5,6,7,8,9};
vector<char> option_not4={0,1,2,3,5,6,7,8,9};
vector<string> result_not4=findPhoneNumber(n,option_not4,0,notAllowed,"");
vector<string> result_has4=findPhoneNumber(n-1,option_has4,0,notAllowed,"");
for(int i=0;i<result_has4.size();i++)
{
result_not4.push_back("4"+result.has4[i]);
}
return result_not4;
}
vector<string> findPhoneNumber(int n,vector<char> option,int usedNotAllowed,vector<char>& notAllowed,char last)
{
if(n==0)
{
return vector<string>(1,"");
}
for(int i=0;i<option.size();i++ )
{
if(option[i]==last) continue;
vector<string> temp_result;
if(find(notAllowed.begin(),notAllowed.end(),option[i])==notAllowed.end())
{
temp_result=findPhoneNumber(n-1,option,usedNotAllowed,notAllowed,option[i]);
}
else
{
if(usedNotAllowed==3)
{
continue;
}
temp_result=findPhoneNumber(n-1,option,usedNotAllowed-1,notAllowed,option[i]);
}
for(int j=0;j<temp_result.size();j++)
{
temp_result[j]=string(1,option[i])+temp_result[j];
}
}
return temp_result;
}
}
class solution
{
vector<string> PhoneNumber(int n,vector<char>& notAllowed)
{
vector<char> option_has4={0,1,2,3,4,5,6,7,8,9};
vector<char> option_not4={0,1,2,3,5,6,7,8,9};
vector<string> result_not4=findPhoneNumber(n,option_not4,0,notAllowed,"");
vector<string> result_has4=findPhoneNumber(n-1,option_has4,0,notAllowed,"");
for(int i=0;i<result_has4.size();i++)
{
result_not4.push_back("4"+result.has4[i]);
}
return result_not4;
}
vector<string> findPhoneNumber(int n,vector<char> option,int usedNotAllowed,vector<char>& notAllowed,char last)
{
if(n==0)
{
return vector<string>(1,"");
}
for(int i=0;i<option.size();i++ )
{
if(option[i]==last) continue;
vector<string> temp_result;
if(find(notAllowed.begin(),notAllowed.end(),option[i])==notAllowed.end())
{
temp_result=findPhoneNumber(n-1,option,usedNotAllowed,notAllowed,option[i]);
}
else
{
if(usedNotAllowed==3)
{
continue;
}
temp_result=findPhoneNumber(n-1,option,usedNotAllowed-1,notAllowed,option[i]);
}
for(int j=0;j<temp_result.size();j++)
{
temp_result[j]=string(1,option[i])+temp_result[j];
}
}
return temp_result;
}
}
import java.util.Stack;
public class LRevaluationNoparanthesis
{
public static int evaluate(String expression)
{
char[] tokens = expression.toCharArray();
// Stack for numbers: 'values'
Stack<Integer> values = new Stack<Integer>();
// Stack for Operators: 'ops'
Stack<Character> ops = new Stack<Character>();
for (int i = 0; i < tokens.length; i++)
{
// Current token is a whitespace, skip it
if (tokens[i] == ' ')
continue;
// Current token is a number, push it to stack for numbers
else if (tokens[i] >= '0' && tokens[i] <= '9')
{
StringBuffer sbuf = new StringBuffer();
// There may be more than one digits in number
while (i < tokens.length && tokens[i] >= '0' && tokens[i] <= '9')
sbuf.append(tokens[i++]);
values.push(Integer.parseInt(sbuf.toString()));
}
// Current token is an opening brace, push it to 'ops'
else if (tokens[i] == '(')
{
//not required
}
// Closing brace encountered, solve entire brace
else if (tokens[i] == ')')
{
//not required
}
// Current token is an operator.
else if (tokens[i] == '+' || tokens[i] == '-' ||
tokens[i] == '*' || tokens[i] == '/')
{
// While top of 'ops' has same or greater precedence to current
// token, which is an operator. Apply operator on top of 'ops'
// to top two elements in values stack
while (!ops.empty() && hasPrecedence(tokens[i], ops.peek()))
values.push(applyOp(ops.pop(), values.pop(), values.pop()));
// Push current token to 'ops'.
ops.push(tokens[i]);
}
}
// Entire expression has been parsed at this point, apply remaining
// ops to remaining values
while (!ops.empty())
values.push(applyOp(ops.pop(), values.pop(), values.pop()));
// Top of 'values' contains result, return it
return values.pop();
}
// Returns true if 'op2' has higher or same precedence as 'op1',
// otherwise returns false.
public static boolean hasPrecedence(char op1, char op2)
{
if (op2 == '(' || op2 == ')')
return false;
if ((op1 == '*' || op1 == '/') && (op2 == '+' || op2 == '-'))
return false;
else
return true;
}
// A utility method to apply an operator 'op' on operands 'a'
// and 'b'. Return the result.
public static int applyOp(char op, int b, int a)
{
switch (op)
{
case '+':
return a + b;
case '-':
return a - b;
case '*':
return a * b;
case '/':
if (b == 0)
throw new
UnsupportedOperationException("Cannot divide by zero");
return a / b;
}
return 0;
}
// Driver method to test above methods
public static void main(String[] args)
{
System.out.println(LRevaluationNoparanthesis.evaluate("10 + 2 * 6"));
System.out.println(LRevaluationNoparanthesis.evaluate("100 * 2 + 12"));
//System.out.println(EvaluatePostfixString.evaluate("100 * ( 2 + 12 )"));
//System.out.println(EvaluatePostfixString.evaluate("100 * ( 2 + 12 ) / 14"));
}
}
import java.util.Stack;
public class LRevaluationNoparanthesis
{
public static int evaluate(String expression)
{
char[] tokens = expression.toCharArray();
// Stack for numbers: 'values'
Stack<Integer> values = new Stack<Integer>();
// Stack for Operators: 'ops'
Stack<Character> ops = new Stack<Character>();
for (int i = 0; i < tokens.length; i++)
{
// Current token is a whitespace, skip it
if (tokens[i] == ' ')
continue;
// Current token is a number, push it to stack for numbers
else if (tokens[i] >= '0' && tokens[i] <= '9')
{
StringBuffer sbuf = new StringBuffer();
// There may be more than one digits in number
while (i < tokens.length && tokens[i] >= '0' && tokens[i] <= '9')
sbuf.append(tokens[i++]);
values.push(Integer.parseInt(sbuf.toString()));
}
// Current token is an opening brace, push it to 'ops'
else if (tokens[i] == '(')
{
//not required
}
// Closing brace encountered, solve entire brace
else if (tokens[i] == ')')
{
//not required
}
// Current token is an operator.
else if (tokens[i] == '+' || tokens[i] == '-' ||
tokens[i] == '*' || tokens[i] == '/')
{
// While top of 'ops' has same or greater precedence to current
// token, which is an operator. Apply operator on top of 'ops'
// to top two elements in values stack
while (!ops.empty() && hasPrecedence(tokens[i], ops.peek()))
values.push(applyOp(ops.pop(), values.pop(), values.pop()));
// Push current token to 'ops'.
ops.push(tokens[i]);
}
}
// Entire expression has been parsed at this point, apply remaining
// ops to remaining values
while (!ops.empty())
values.push(applyOp(ops.pop(), values.pop(), values.pop()));
// Top of 'values' contains result, return it
return values.pop();
}
// Returns true if 'op2' has higher or same precedence as 'op1',
// otherwise returns false.
public static boolean hasPrecedence(char op1, char op2)
{
if (op2 == '(' || op2 == ')')
return false;
if ((op1 == '*' || op1 == '/') && (op2 == '+' || op2 == '-'))
return false;
else
return true;
}
// A utility method to apply an operator 'op' on operands 'a'
// and 'b'. Return the result.
public static int applyOp(char op, int b, int a)
{
switch (op)
{
case '+':
return a + b;
case '-':
return a - b;
case '*':
return a * b;
case '/':
if (b == 0)
throw new
UnsupportedOperationException("Cannot divide by zero");
return a / b;
}
return 0;
}
// Driver method to test above methods
public static void main(String[] args)
{
System.out.println(LRevaluationNoparanthesis.evaluate("10 + 2 * 6"));
System.out.println(LRevaluationNoparanthesis.evaluate("100 * 2 + 12"));
//System.out.println(EvaluatePostfixString.evaluate("100 * ( 2 + 12 )"));
//System.out.println(EvaluatePostfixString.evaluate("100 * ( 2 + 12 ) / 14"));
}
}
import java.util.Stack;
public class LRevaluationNoparanthesis
{
public static int evaluate(String expression)
{
char[] tokens = expression.toCharArray();
// Stack for numbers: 'values'
Stack<Integer> values = new Stack<Integer>();
// Stack for Operators: 'ops'
Stack<Character> ops = new Stack<Character>();
for (int i = 0; i < tokens.length; i++)
{
// Current token is a whitespace, skip it
if (tokens[i] == ' ')
continue;
// Current token is a number, push it to stack for numbers
else if (tokens[i] >= '0' && tokens[i] <= '9')
{
StringBuffer sbuf = new StringBuffer();
// There may be more than one digits in number
while (i < tokens.length && tokens[i] >= '0' && tokens[i] <= '9')
sbuf.append(tokens[i++]);
values.push(Integer.parseInt(sbuf.toString()));
}
// Current token is an opening brace, push it to 'ops'
else if (tokens[i] == '(')
{
//not required
}
// Closing brace encountered, solve entire brace
else if (tokens[i] == ')')
{
//not required
}
// Current token is an operator.
else if (tokens[i] == '+' || tokens[i] == '-' ||
tokens[i] == '*' || tokens[i] == '/')
{
// While top of 'ops' has same or greater precedence to current
// token, which is an operator. Apply operator on top of 'ops'
// to top two elements in values stack
while (!ops.empty() && hasPrecedence(tokens[i], ops.peek()))
values.push(applyOp(ops.pop(), values.pop(), values.pop()));
// Push current token to 'ops'.
ops.push(tokens[i]);
}
}
// Entire expression has been parsed at this point, apply remaining
// ops to remaining values
while (!ops.empty())
values.push(applyOp(ops.pop(), values.pop(), values.pop()));
// Top of 'values' contains result, return it
return values.pop();
}
// Returns true if 'op2' has higher or same precedence as 'op1',
// otherwise returns false.
public static boolean hasPrecedence(char op1, char op2)
{
if (op2 == '(' || op2 == ')')
return false;
if ((op1 == '*' || op1 == '/') && (op2 == '+' || op2 == '-'))
return false;
else
return true;
}
// A utility method to apply an operator 'op' on operands 'a'
// and 'b'. Return the result.
public static int applyOp(char op, int b, int a)
{
switch (op)
{
case '+':
return a + b;
case '-':
return a - b;
case '*':
return a * b;
case '/':
if (b == 0)
throw new
UnsupportedOperationException("Cannot divide by zero");
return a / b;
}
return 0;
}
// Driver method to test above methods
public static void main(String[] args)
{
System.out.println(LRevaluationNoparanthesis.evaluate("10 + 2 * 6"));
System.out.println(LRevaluationNoparanthesis.evaluate("100 * 2 + 12"));
//System.out.println(EvaluatePostfixString.evaluate("100 * ( 2 + 12 )"));
//System.out.println(EvaluatePostfixString.evaluate("100 * ( 2 + 12 ) / 14"));
}
}
Just want to make sure, "Disallowed digits can be up to 3, and can be included along with the phone number." You mean disallowed digits cannot be included along with the phone number, right?
* Phone number can start with 0.
* An allowed number can appear multiple times as long as they are not right next to each other.
* If there are multiple 4s, the resulting number must starts with 4. Other 4s follow the above rule.
Algorithm: DFS + pruning.
void helper(int i, int numdigits, set<int>& disallowed, vector<int>& pre, vector<vector<int>>& ret) {
if (i >= numdigits) {
ret.push_back(pre);
return;
}
for (int cand = 0; cand <= 9; ++cand) {
if (disallowed.count(cand)) continue;
if (pre.size() && pre.back() == cand) continue;
if (pre.size() && cand == 4 && pre.front() != 4) continue;
pre.push_back(cand);
helper(i + 1, numdigits, disallowed, pre, ret);
pre.pop_back();
}
}
vector<vector<int>> generate(int numdigits, set<int> disallowed) {
vector<vector<int>> ret;
if (numdigits == 0) return ret;
vector<int> pre;
helper(0, numdigits, disallowed, pre, ret);
return ret;
}
My simple code.. Check mine too..
#include <iostream>
using namespace std;
int n1,n2,n3;
void generate(int A[],int pos,int len)
{
if(pos==len)
{
for(int j=0;j<len;j++)
cout<<A[j];
cout<<"\n";
return;
}
for(int i=0;i<=9;i++)
{
while((i==n1 || i==n2 || i==n3) || (pos>0 && A[pos-1]==i) || (pos>0 && A[0]!=4 && i==4))
i++;
if(i>9)
continue;
A[pos]=i;
generate(A,pos+1,len);
}
}
int main()
{
n1=2,n2=3,n3=5;
int len=3;
int A[len];
generate(A,0,len);
return 0;
}
- Anonymous October 31, 2014package epic; import java.util.Vector; public class phone { public static void main(String argv []){ int n1=3,n2=7,n3=5; int i; Vector v1 = new Vector<Integer>(); for(i=0; i<10; i++){ v1.add(i); } System.out.println(v1); v1.removeElement(Integer.valueOf(n1)); v1.removeElement(Integer.valueOf(n2)); v1.removeElement(Integer.valueOf(n3)); System.out.println(v1); for(i=0; i<v1.size(); i++){ addPhoneNumber(String.valueOf(v1.get(i)), v1,3); } } public static void addPhoneNumber(String src,Vector<Integer> allowed,int rem){ int i,k; if(rem == 0){ /* * check for 4 */ } else{ k=0; String org = src; int temp = rem; while(k<allowed.size()){ src = org; rem = temp; for(i=k; i<k+rem; i++){ if(!src.equals("4") && allowed.get(i%allowed.size())==4){ src = "4" + src; rem--; } else if(Integer.parseInt(src) == allowed.get(i%allowed.size())){ rem++; } else{ src = src + String.valueOf(allowed.get(i%allowed.size())); rem--; } } System.out.println(src); k++; } } } }