Epic Systems Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: Written Test
we can use a single iteration of for loop like this
{{
def validate_phone_number(phone_number):
if phone_number[0] == '4'
four_flag = True
is_valid = True
for i,digit in phone_number:
if digit == '7' || digit == '2' || digit == '9':
is_valid == False;
break
elif digit == '4' and four_flag == False:
is_valid == False
break
elif i != 0 and phone_number[i-1] == phone_number[i]:
is_valide == False
break
return is_valid
}}
yeah looks good....
I was thinking of something that could construct the number by using a valid digits array rather than iterating through all the pow(n,10) possibilities, atleast 3/10 of which are going to be invalid...
Nice solution, but what if we decide to add the number '0' to unallowed numbers? In that case we'd have to go back and change the code. What I would suggest is that keep a list of all the unallowed numbers in a linked list (or any other collection) add 4 if ph[0] != 4.
Anyway, your solution will work.
The question says: "Print all valid phone numbers of length n"
How are you printing all the numbers when length = 10?
What is the efficient way to keep incrementing phoneNumber value?
#include <iostream>
using namespace std;
char invalid[] = {'2', '7', '9'};
int sizeOfInvalid = 3;
bool IsValidChar(char ch)
{
for(int i=0;i<sizeOfInvalid;i++)
{
if(invalid[i]==ch)
return false;
}
return true;
}
void RecurseAndPrint(int n, char* current, int sizeOfCurrent)
{
if(sizeOfCurrent == n)
{
current[sizeOfCurrent]='\0';
cout<<current<<endl;
return;
}
for(char ch='0';ch<='9';ch++)
{
if(ch=='4' && sizeOfCurrent> 0 && current[0]!='4')
continue;
if(IsValidChar(ch) )
{
if(sizeOfCurrent>0 && ch==current[sizeOfCurrent-1])
continue;
current[sizeOfCurrent] = ch;
RecurseAndPrint(n, current, sizeOfCurrent+1);
}
}
}
char current[10];
int main()
{
int n = 7;
RecurseAndPrint(7, current, 0);
return 0;
}
May It will Help:
public boolean ValidPh(int[] ph) {
boolean invalid = false;
if (ph[0] == 4) {
for (int j = 0; j < ph.length; j++) {
if ((j + 1) != ph.length) {
if (ph[j] == ph[j + 1]) {
invalid = true;
break;
}
if (!invalid) {
if (ph[j] == 7 || ph[j] == 2 || ph[j] == 9) {
invalid = true;
break;
}
}
}
}
} else {
invalid = true;
}
return invalid;
It will be valid only for numbers starting with "4", but its not necessary that the number should start with 4.
public boolean ValidPh(int[] ph) {
boolean invalid = false;
if (ph[0] == 4) {
for (int j = 0; j < (ph.length-1); j++) {
if (ph[j] == ph[j + 1]) {
invalid = true;
break;
}
if (!invalid) {
if (ph[j+1] == 7 || ph[j+1] == 2 || ph[j+1] == 9) {
invalid = true;
break;
}
}
}
} else {
invalid = true;
}
return invalid;
void phone(char* s, int pos, int len, char bad1, char bad2, char bad3)
{
char c, tmp_c;
if (pos==len)
{
puts(s);
return;
}
tmp_c=s[pos];
for (c='0'; c<='9'; c++)
{
if (c==bad1 || c==bad2 || c==bad3 || (pos>0 && (c==s[pos-1] || c=='4')))
continue;
s[pos]=c;
phone(s,pos+1,len,bad1,bad2,bad3);
}
s[pos]=tmp_c;
return;
}
void phone_main(int len, char bad1, char bad2, char bad3)
{
char* s;
s = (char*) malloc(sizeof(char)*(len+1));
s[len]='\0';
phone(s,0,len,bad1,bad2,bad3);
free(s);
}
PrintValidPhoneNos(String Phoneno, int n,int[] invalidnos)
{
int length=Phoneno.length();
if(length==n)
{
System.out.println(Phoneno);
}
else
{
for(int i=0;i<=9;i++)
{
if(i==invalidnos[0]||i==invalidnos[1]||i==invalidnos[2])
continue;
if(Phoneno.charAt(length-1)==i)
continue;
if(i==4&&Phoneno.charAt(0)!='4')
continue;
PrintValidPhoneNos(PhoneNo+(char)i,n,invalidnos);
}
}
In perl:
sub genNumber {
my $len = shift; # length to generate
my $number = shift; # number so far
my @invalid = @_; # list of digits not allowed
return $number if $len <= 0; # we're done
my @numbers = ();
for my $digit (0 .. 9) {
# skip if not first digit of number and digit is 4
next if length($number) > 0 and $digit == 4;
# skip if digit is same as previous digit
next if length($number) > 0 and substr($number,-1,1) == $digit;
# skip if digit is in the list of not allowed
next if grep {$digit == $_} @invalid;
# recursive call
push @numbers, genNumber($len-1, $number.$digit, @invalid);
}
return @numbers;
}
# first parameter is length to generate
# second is initial value
# remainder are disallowed numbers
print join(',', genNumber(5, "", 7,2,9))."\n";
#include <string>
#include <vector>
#include <cstdio>
std::string make_decimal(const std::vector<int>& number) {
std::string str(number.size(),'x');
for (int i = 0; i < number.size(); i++) {
str[i] = '0'+number[i];
}
return str;
}
// invalid_digits acts as a bitset: Digit d is disallowed
// iff invalid_digits & (1 << d) == true
void print_valid_numbers(const int N, int invalid_digits,
int level, std::vector<int>& number) {
if (level >= N) {
printf("%s\n", make_decimal(number).c_str());
return;
}
for (int d = 0; d < 10; d++) {
if (invalid_digits & (1 << d))
continue;
// We only allow numbers to contain a 4 if they already start with 4
// Also make sure that no two neighbouring digits are the same
if (level > 0 && ((d == 4 && number[0] != 4) || number[level-1] == d))
continue;
number[level] = d;
print_valid_numbers(N, invalid_digits, level+1, number);
}
}
int main(int argc, char** argv) {
std::vector<int> number(4);
int invalid_digits = (1 << 2) | (1 << 5) | (1 << 8);
print_valid_numbers(4, invalid_digits, 0, number);
return 0;
}
public class ValidPhoneNumber {
public static void printValidPhoneNum(int n) {
if (n <= 0 || n == 7 || n == 2 || n == 9) {
System.out.println("No such phone number");
return;
}
for (int start = (int) Math.pow(10.0, (double) (n - 1)); start < (int) Math
.pow(10.0, (double) (n)); start++) {
if (checkDoesContainFour(start) && checkConsecutive(start)) {
System.out.println(start);
}
}
}
private static boolean checkConsecutive(int num) {
String str = String.valueOf(num);
for (int i = 0; i < str.length() - 1; i++) {
// 0 1 2 3 4 5 6 7 8 9
if (str.charAt(i) + 1 == str.charAt(i + 1)
|| str.charAt(i) - 1 == str.charAt(i + 1)) {
return false;
}
}
return true;
}
private static boolean checkDoesContainFour(int num) {
String str = String.valueOf(num);
if (str.contains("4")) {
if (str.charAt(0) == '4') {
return true;
}else{
return false;
}
}
return true;
}
/**
* @param args
*/
public static void main(String[] args) {
printValidPhoneNum(3);
}
}
@Lalitha, you are right. The time complexity is O(n^2).
But I think it's necessary because we need to check Consecutive Letter.
Do you have some better idea?
Python version working code. loop through all the numbers, convert to string, if validate, print.
"""
Print all valid phone numbers of length n subject to following constraints:
1.If a number contains a 4, it should start with 4
2.No two consecutive digits can be same
3.Three digits (e.g. 7,2,9) will be entirely disallowed, take as input
"""
class ValidPhone(object):
def __init__(self, n):
if n is None:
print 'Invalid length!'
raise SystemExit
self._n = n
def validate(self, number):
isValid = True
#rule 1
if '4' in number and number[0] != '4':
isValid = False
# rule 3
if ('7' in number) or ('2' in number) or ('9' in number):
isValid = False
# rule 2
for i in range(len(number)-1):
if number[i] == number[i+1]:
isValid = False
return isValid
def gen(self):
for i in range(10 ** self._n):
out = str(i)
if len(out) < self._n:
out = '0' * (self._n - len(out)) + out
if self.validate(out):
print out
if __name__ == '__main__':
phone = ValidPhone(3)
phone.gen()
public class PhoneNumbersPrinter
{
public static void printPhoneNumbers(int n, int a, int b, int c)
{
int[] digits = new int[7]; // valid digits array
// Initialize valid digits array
int j = 0;
for (int i = 0; i < 10; i++)
{
if (i != a && i != b && i != c)
digits[j++] = i;
}
String number = "";
printNumber(number, n, digits);
}
private static void printNumber(String currNum, int n, int[] digits)
{
// stopping condition is to reach an n length string
if (currNum.length() == n)
{
System.out.println(currNum);
return;
} else
{
// put all possible digits
for (int i = 0; i < digits.length; i++)
{
// check if phone number starts with 4
// check for 2 same consecutive digits
if (currNum.length() == 0
|| (char) (digits[i] + (int) '0') != currNum
.charAt(currNum.length() - 1))
{
if (!(digits[i] == 4 && (currNum.length() != 0 && currNum
.charAt(0) != '4')))
printNumber(currNum + digits[i], n, digits);
}
}
}
}
public static void main(String[] args)
{
printPhoneNumbers(3, 7, 8, 9);
}
}
Its a absolutely Correct Code...
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
void print(int *a, int size)
{
int i;
for(i=0;i<size;i++)
printf("%d",a[i]);
printf("\n");
}
void allnumprint(int *arr1,int arr[],int index,int size)
{
int i;
if(index==size)
{
print(arr1,size);
return ;
}
for(i=0;i<7;++i)
{
if(index!=0)
{
if(arr1[index-1]==arr[i])
continue;
if(i==3&&arr1[0]!=4)
continue;
}
arr1[index]=arr[i];
allnumprint(arr1,arr,index+1,size);
}
}
int main()
{
int i,n,*a;
int b[7]={0,1,3,4,5,6,8};
printf("Enter number of digits:");
scanf("%d",&n);
a=(int *)malloc(n*sizeof(int));
for(i=0;i<n;i++)
a[i]=0;
allnumprint(a,b,0,n);
getch();
}
I think I have a good solution by DFS and compiled.
public class ValidPhoneNumber {
public static void main(String[] args) {
String source = "0134568";
StringBuilder sb = new StringBuilder();
validNumber(source, sb, 4);
}
public static void validNumber(String source, StringBuilder sb, int size){
if(sb.length() == size) {
System.out.println(sb.toString());
return;
}
for(int i = 0; i < source.length(); i++){
if(sb.length() == 0 && source.charAt(i) == '4'){
continue;
}
if(sb.length() > 0){
if(sb.charAt(sb.length() - 1) == source.charAt(i) ){
continue;
}
}
sb.append(source.charAt(i));
validNumber(source, sb, size);
sb.deleteCharAt(sb.length() - 1);
}
}
}
my working code
#include <iostream>
#include <string>
using namespace std;
void phoneNum(string set, string src, int numLeft) {
if (numLeft == 0) {
cout << src ;
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) {
phoneNum("013568", "4", n - 1);
phoneNum("013568", "", n);
}
void main(){
phone(5);
cin.get();
}
public class validphone {
public static void main(String[] args)
{
int n = 3;
int start = (int)Math.pow(10,n-1);
int end = (int)Math.pow(10,n) - 1;
for(int i=start; i<=end; i++)
{
char num[] = (i+"").toCharArray();
boolean flag = true;
for(int j=0; j<num.length;j++)
{
if(num[j]=='7' || num[j]=='8' || num[j]=='9')
{
flag = false;
break;
}
}
if(flag==true)
{
for(int j=0; j<num.length;j++)
{
if(num[j]=='4' && num[0]!='4')
{
flag=false;
break;
}
}
}
if(flag==true)
{
for(int j=1; j<num.length;j++)
{
if(num[j-1]==num[j])
{
flag = false;
break;
}
}
}
if(flag==true)
System.out.println(i);
}
}
}
C# solution. any comments are welcome:
using System;
namespace Test
{
public class CareerCup
{
public static void Main(string[] args)
{
string n = Console.ReadLine().Trim();
lookAndSay(n, 10);
}
public static void lookAndSay(string n, int repetition) {
for (int i = 0; i < repetition; i++) {
if (n != "0" && n!="")
{
n = spellTheNumbers(n);
Console.WriteLine(n); ;
}
else
{
break;
}
}
}
public static string spellTheNumbers(string number) {
string result = "";
int counter = 1;
for (int i = 0; i < number.Length; i++) {
if (i > 0 && number[i] == number[i - 1])
{
counter++;
}
if (i > 0 && number[i] != number[i - 1])
{
result += Convert.ToString(counter) + Convert.ToString(number[i - 1]);
counter = 1;
}
if (i == number.Length - 1)
{
result += Convert.ToString(counter) + Convert.ToString(number[i]);
counter = 1;
}
}
return result;
}
}
}
package Epic;
/************************************************************
*
* Print all valid phone numbers of length n subject to
* following constraints:
*
* 1.If a number contains a 4, it should start with 4
* 2.No two consecutive digits can be same
* 3.Three digits (e.g. 7,2,9) will be entirely disallowed,
* take as input
*
* @author jhaxx030
*
*/
public class ValidPhoneNumber {
/**
*
* @param args
*/
public static void main(String[] args) {
//boolean isValid = validatePhone(443564828);
//boolean isValid = validatePhone(443564888);
//boolean isValid = validatePhone(943564808);
//boolean isValid = validatePhone(443564808);
boolean isValid = validatePhone(123456789);
if(isValid){
System.out.println("Valid Phone");
}else{
System.out.println("Not a Valid Phone");
}
}
/************************************************************
*
* @param number
* @return
*/
static boolean validatePhone(int number){
boolean isValid = false;
String str = String.valueOf(number);
// If not of length 9, invalid.
if(str.length() !=9){
System.out.println("InValid1");
return isValid;
}
// If contains 2, 7 or 9, invalid.
if(str.contains("2")||str.contains("7")||
str.contains("9")){
System.out.println("InValid2");
return isValid;
}
// If contains 4 and do not start with 4, invalid.
if(str.contains("4") && (str.indexOf('4') !=0)){
System.out.println("InValid3");
return isValid;
}
char previousChar = 'a';
for(int i =0; i < str.length(); i++){
if(str.charAt(i) == previousChar){
System.out.println("InValid5");
return isValid;
}
previousChar = str.charAt(i);
}
isValid = true;
return isValid;
}
}
Java Code... Any comments are welcome
i think it might be easier if we just dont include the invalid digits in the first place
someone tell me if this program is correct or not
- Paul March 04, 2013