Epic Systems Interview Question Jr. Software Engineers
Country: United States
Interview Type: Written Test
I think this should serve as a valid solution.
#include <iostream>
#include <vector>
using namespace std;
bool checkForFour(int array[], int length)
{
for(int i=0; i<length; i++)
{
if(array[i]==4)
return true;
}
return false;
}
void recurse(int array[],int next1, int next2, vector<int> excludedDigits, int length, int pos)
{
if(pos==length)
{
bool is4 = checkForFour(array,length);
if(is4)
cout<<"4";
else
cout<<array[0];
for(int i=1; i<length; i++)
cout<<array[i];
cout<<endl;
return;
}
for(int i=0;i<10; i++)
{
int prev=array[pos-1];
if((prev==next1 && i==next2) || (prev==next2 && i==next1))
continue;
vector<int>::iterator it;
it=find(excludedDigits.begin(),excludedDigits.end(),i);
if(it!=excludedDigits.end())
continue;
array[pos]=i;
recurse(array, next1, next2, excludedDigits, length, pos+1);
}
}
int main(int argc, const char * argv[])
{
int length;
cout<<"Enter the length of the phone number\n";
cin>>length;
cout<<"Enter the two digits that cannot be next to each other\n";
int next1,next2;
cin>>next1>>next2;
cout<<"Enter the number of digits to be excluded\n";
int excludedLength;
cin>>excludedLength;
vector<int> excludedDigits;
for(int i=0; i<excludedLength; i++)
{
int temp;
cin>>temp;
excludedDigits.push_back(temp);
}
int* array = new int[length];
recurse(array, next1, next2, excludedDigits, length, 0);
return 0;
}
Let n be the length of the phone number.
Let d be the amount of digits to work with after the exclusion list.
case a) 2 digits cannot be next to each other:
Start by supposing 2 digits can be next to each other and our length is 4 (n = 4)
Our amount of permutations would be d*d*d*d or d^4
Since no 2 digits can be next to each other the following digits must be 1 less, so our amount of permutations would be
d(d-1)(d-1)(d-1) or d(d-1)^3 = d(d-1)^(n-1)
That solves the problem if 4 is in the exclusion list.
If 4 is not in the exclusion list we must subtract all possible phone numbers that are not allowed. These phone numbers are c) if the number contains 4 it must start with 4 as well.
So again assuming n = 4, all possible combinations would be:
cddf + cdfc + cfcc or generally c * summation from i = 1 to n of d^(n-i)*c^(i-1)
(where f = 1 representing the single possible digit '4' and c = (d-1) representing all possible digits except '4').
Finally, for an exclusion list that does not contain 4 we have:
dc^(n-1) - c * summation from i = 1 to n of d^(n-i)*(d-1)^(i-1)
The set of all numbers that start with a four where no two adjacent numbers are the same UNION with the set of all numbers that have no fours where no two adjacent numbers are the same.
The first set contains for example [ 401, 412, 414, ... ]
The second set contains for example [ 123, 232, ... ]
The size of the first set is 1 * (D-1)^(n-1)
The size of the second set is (D-1)*(D-2)^(n-1)
Since the intersection of these sets is empty, we can simply add the sizes to get our answer: (D-1)^(n-1) + (D-1)(D-2)^(n-1)
public class PermutePhoneNumber {
public static void main(String args[]) {
permute("", null, 0);
}
public static void permute(String temp, List<Integer> exclusionList, int level) {
if(level == 9) {
System.out.println(temp);
} else {
for(int i = 3; i < 10; i++) {
if(exclusionList != null && exclusionList.contains(i)) {
continue;
}
if(!temp.endsWith(String.valueOf(i))) {
if(i != 4) {
permute(temp + i, exclusionList, level + 1);
} else {
if((temp + i).startsWith(String.valueOf(i))) {
permute(temp + i, exclusionList, level + 1);
}
}
}
}
}
}
}
public class PermutePhoneNumber {
public static void main(String args[]) {
permute("", null, 0);
}
public static void permute(String temp, List<Integer> exclusionList, int level) {
if(level == 9) {
System.out.println(temp);
} else {
for(int i = 3; i < 10; i++) {
if(exclusionList != null && exclusionList.contains(i)) {
continue;
}
if(!temp.endsWith(String.valueOf(i))) {
if(i != 4) {
permute(temp + i, exclusionList, level + 1);
} else {
if((temp + i).startsWith(String.valueOf(i))) {
permute(temp + i, exclusionList, level + 1);
}
}
}
}
}
}
}
public class PermutePhoneNumber {
public static void main(String args[]) {
permute("", null, 0);
}
public static void permute(String temp, List<Integer> exclusionList, int level) {
if(level == 9) {
System.out.println(temp);
} else {
for(int i = 3; i < 10; i++) {
if(exclusionList != null && exclusionList.contains(i)) {
continue;
}
if(!temp.endsWith(String.valueOf(i))) {
if(i != 4) {
permute(temp + i, exclusionList, level + 1);
} else {
if((temp + i).startsWith(String.valueOf(i))) {
permute(temp + i, exclusionList, level + 1);
}
}
}
}
}
}
}
public class PermutePhoneNumber {
public static void main(String args[]) {
permute("", null, 0);
}
public static void permute(String temp, List<Integer> exclusionList, int level) {
if(level == 9) {
System.out.println(temp);
} else {
for(int i = 3; i < 10; i++) {
if(exclusionList != null && exclusionList.contains(i)) {
continue;
}
if(!temp.endsWith(String.valueOf(i))) {
if(i != 4) {
permute(temp + i, exclusionList, level + 1);
} else {
if((temp + i).startsWith(String.valueOf(i))) {
permute(temp + i, exclusionList, level + 1);
}
}
}
}
}
}
}
- saran1191 April 14, 2015public class PermutePhoneNumber { public static void main(String args[]) { permute("", null, 0); } public static void permute(String temp, List<Integer> exclusionList, int level) { if(level == 9) { System.out.println(temp); } else { for(int i = 3; i < 10; i++) { if(exclusionList != null && exclusionList.contains(i)) { continue; } if(!temp.endsWith(String.valueOf(i))) { if(i != 4) { permute(temp + i, exclusionList, level + 1); } else { if((temp + i).startsWith(String.valueOf(i))) { permute(temp + i, exclusionList, level + 1); } } } } } } }