Epic Systems Interview Question Software Engineer / Developers
Country: United States
Interview Type: Phone Interview
this solution might have a problem. How do you deal with 1235, say 2 + 3 = 5, since every time, num1 starts from '0' position of num, which means you can only consider 12, could not consider 2 separately.
Yeah, it still exists problem. The modification is easy. Just save the num1 in the second for iteration, and use a temp_num1 in the inner while iteration. Since in while{}, the num1 has been changed, but when we're out of the while{} and in the second for{} again, we need recover the num1 to the original one (front 1st for{}). Codes are shown as fellows.
public static boolean check(String num){
for(int i = 1; i<num.length();i++){
int num1 = Integer.parseInt(num.substring(0,i));
for(int j = i+1; j<num.length();j++){
int temp_num1 = num1;
int num2 = Integer.parseInt(num.substring(i,j));
int thirdIndex = j;
int rest = Integer.parseInt(num.substring(thirdIndex,num.length()));
while(temp_num1+num2<=rest){
int num3 = temp_num1+num2;
String newNum = (new Integer(num3)).toString();
int length = newNum.length();
if(thirdIndex+length > num.length()){
break;
}
if(num.substring(thirdIndex,thirdIndex+length).equals(newNum)){
thirdIndex += length;
if(thirdIndex == num.length()){
return true;
}
temp_num1 = num2;
num2= num3;
rest = Integer.parseInt(num.substring(thirdIndex,num.length()));
}else{
break;
}
}
}
}
return false;
}
Here is my solution. Please let me know if I missed something:
The minimum number of digits needed is 3.
So now consider a 'n' digit number.
1. Find all ways of generating 'n-1' number of digits as a sum of 2 numbers until n/2 if even , (n/2) + 1 if odd.
For Example:
For 121224:
1. It is a 6 digit number.
2. We can find 5 as 3+2, 2+3,1+4, 4+1.
3+2 : Form a number using first 3 digits : 121 and next 2 digits: 22 and add then to find if it equal the remaining digits.
Similarly for 1+4 and others.
3. Now for 4 : 2+2 , 1+3 , 3+1
For 2+2 : We get 12 , 12 ,their sum is 24 and check with the remaining digits i.e 24.
If it is true we return the result.
4. We do this until n/2 ie till 3 digits . as maximum is (1)(99)(100) or( 99)(1)(100).
NOTE: We always consider n as 1+1+..n. So that is the operation we definitely perform.
"Given the start and an ending integer as user input, generate all integers with the following property. "....
What property? Did you forget to write the second half of this question?
Can you please explain how this approach works for 1235 where we need to check if 1+2=3 as well as 2+3=5?
Additive or not additive? Brute force method should be easy to come up with. But as said in other posts, we have the following optimizations and assumptions:
1. Number must have at least 3 digits.
2. Negative numbers? Negative numbers are not ok.
3. Ill-formed numbers such as 10102? 1 + 01 = 02, but we prefer not to consider this case now.
At the cost of string conversion, I found it easier to code after the number is converted to string. In C++, string to integer is stoi(), while integer to string is std::to_string(). Ill formed case is easier to check when string is used too.
Playable code at
ideone.com/kRN4IN
bool verify(string s1, string s2, string s3) {
// verify that s3 is the fibbonaci sequence of s1 and s2
while(s3.size()) {
string res = to_string(stoi(s1) + stoi(s2));
if (res.size() > s3.size() || s3.substr(0, res.size()) != res)
return false;
s1 = s2;
s2 = res;
s3 = s3.substr(res.size(), s3.size() - res.size());
}
return true;
}
bool additive(int num) {
if (num <= 100) return false;
string str = to_string(num);
for (int st1len = 1; st1len <= str.size() - 2; ++st1len) {
for (int st2len = 1; st2len <= str.size() - st1len - 1; ++st2len) {
string s1 = str.substr(0, st1len);
string s2 = str.substr(st1len, st2len);
if (s1.front() == '0' || s2.front() == '0') continue;
string s3 = str.substr(st1len + st2len, \
str.size() - st1len - st2len);
if (s3.front() == '0') continue;
if (verify(s1, s2, s3)) return true;
}
}
return false;
}
When you see my logic
1910 is a 4 digit number we find how many ways 3, 2 is formed
3 is generated as 1+2 , 2+1
2 is generated as 1+1. So, in this case we have 1+ 9 and the remaining two digits form 10.
This case is definitely considered.
would it work for this case 191019, 1+9 = 10, 9+10 = 19 ? I haven't tested your code myself yet!
I am not sure, i think with variable length , it may be ill formed problem. when i say variable length case i meant like 1910 , 1+9 = 10. 1, 9 being length 1 and 10 being length two. I felt like the best i one could do is solve it for fixed length like 12122436 or 1235 , but not 1910. but i am not certain of my assertion!
import java.util.LinkedList;
import java.util.Scanner;
public class Algorithms{
public int calls;
//Finds numbers that match the following pattern , 12122436 , 12+12=24 24+12=36
public LinkedList<Long> problem1(long start,long end){
LinkedList<Long> numbers=new LinkedList<Long>();
while(start<=end){
class RecFind{
public int calls=0;
private int mincalls;
public LinkedList<Long> toDigits(long num){
LinkedList<Long> list =new LinkedList<Long>();
while(num>0){
list.offerFirst(num%10);
num/=10;
}
return list;
}
public boolean find(int split,String number){
if (split*3 <= number.length()){
long header=Long.parseLong(number.substring(0, split));
number=number.substring(split);
header+=Long.parseLong(number.substring(0, split));
long check=Long.parseLong(number.substring(split,2* split));
if (number.length()==2*split){
if (header==check)
return true;
this.calls= this.mincalls>this.calls ? this.mincalls : this.calls;
}
else if (header==check)
return find(split,number);
this.mincalls++;
}
return false;
}
}
boolean found=false;
RecFind rec=new RecFind();
String number=String.valueOf(start);
int split=1;
while(!found){
if (split*3 > number.length()){
found=true;
}else if (rec.find(split,number)){
numbers.add(start);
found=true;
}
split++;
}
start++;
this.calls=rec.calls;
System.out.println(start);
}
return numbers;
}
public static void main(String[] args){
Algorithms al=new Algorithms();
Scanner sc=new Scanner(System.in);
System.out.println("Type two numbers:");
LinkedList<Long> list;
list=al.problem1(sc.nextLong(),sc.nextLong());
int cnt=0;
for(long i: list){
System.out.println(i);
cnt++;
}
System.out.println("NUMBERS FOUND:"+cnt);
System.out.println("MAX:"+al.calls);
}
}
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
package findvalidnumber;
import java.util.ArrayList;
import java.util.Scanner;
/**
*
* @author Sompa
*/
public class FindValidNumber {
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
FindValidNumber fvn = new FindValidNumber();
Scanner scr = new Scanner(System.in);
String beg = scr.next();
String end = scr.next();
int first = Integer.parseInt(beg);
int last = Integer.parseInt(end);
int num;
while(first <= last)
{
ArrayList<Integer> digits = new ArrayList<>();
num = first;
while(num > 0)
{
digits.add(num%10);
num = num/10;
}
int[] arrDigits = new int[digits.size()];
for(int k = 0;k<arrDigits.length;k++)
arrDigits[k]= digits.get(digits.size()-1-k);
if(fvn.pattern1Match(arrDigits)||fvn.pattern2Match(arrDigits))
{
for(int n = 0;n<arrDigits.length;n++)
System.out.print(arrDigits[n]);
System.out.println();
}
first++;
}
}
private boolean pattern1Match(int[] digits){
int i;
for(i=2;i<digits.length;i++)
{
if(digits[i] == digits[i-1]+digits[i-2])
continue;
else
break;
}
if(i==digits.length)
return true;
else
return false;
}
private boolean pattern2Match(int[] digits){
int i;
if(digits.length%2==0)
{
for(i=5;i<digits.length;i++)
{
if(((digits[i-5]*10+digits[i-4])+(digits[i-3]*10+digits[i-2]))==(digits[i-1]*10+digits[i]))
continue;
else
break;
}
if(i==digits.length)
return true;
}
return false;
}
}
public class Solution {
// finds numbers that match the following pattern
public static boolean validity(String num){
int leng = num.length();
//( for example) leng = 6 ) 121224
// + is 1~leng/2
// = is +~leng-1
// . is =~leng
for( int a = 0; a<leng/2; a++){
for( int i = a+1; i<leng/2 ; i++){
for(int j= i+1; j< leng -1; j++){
for( int k=j+1; k<=leng; k++){
int x = Integer.parseInt(num.substring(a, i));
int y = Integer.parseInt(num.substring(i, j));
int z = Integer.parseInt(num.substring(j, k));
System.out.println( x+","+y+","+z);
if(x+y==z){
System.out.println( "------up-------");
if(k==leng){
return true;
}else{
continue;
}
}
}
}
}
}
return false;
}
public static void main(String[] args){
System.out.println(validity("191019"));
}
}
#include<iostream>
using namespace std;
bool property(int n1, int p)
{
int n=n1;
int target=n%p;
n=n/p;
int t1=n%p;
n=n/p;
int t2=n%p;
if (t2==0 && n==0){return true;}
if ((t1+t2)==target)
{
return true & property(n1/10,p);
}
else {return false;}
}
bool property_helper(int n)
{
int temp=n;
int count=0;
while (temp>0)
{temp=temp/10;
count++;
}
// cout<<count;
if (count<3) {cout<<"not applicable"; return false;}
else
{
int prod=10;
for (int i=1;i<=count/3;i++)
{
bool k=property(n,prod);
// cout<<"=="<<k<<"==\n";
if (k){return true;}
prod=prod*10;
}
return false;
}
}
int main()
{
cout<<"Enter the number";
int n;
cin>>n;
cout<<property_helper(n);
}
public class PerfectValidNumber {
public static void generateNum(int start, int end) {
for (int num = start; num <= end; num++) {
printValidNum(String.valueOf(num));
}
}
private static void printValidNum(String num) {
if (num == null || num.length() < 3) {
return;
}
for (int init_size = 1; init_size <= num.length() / 2; init_size++) {
if (isValid(num, init_size,
Integer.parseInt(num.substring(0, init_size)),
Integer.parseInt(num.substring(init_size, 2 * init_size)))) {
System.out.println(num);
break;
}
}
}
private static boolean isValid(String num, int init_size, int n1, int n2) {
int n3 = n1 + n2;
if (num.length() == String.valueOf(n1).length()
+ String.valueOf(n2).length() + String.valueOf(n3).length()) {
if (num.substring(
String.valueOf(n1).length() + String.valueOf(n2).length())
.equals(String.valueOf(n3))) {
return true;
} else {
return false;
}
} else if (num.length() < String.valueOf(n1).length()
+ String.valueOf(n2).length() + String.valueOf(n3).length()) {
return false;
}else{
if (num.substring(String.valueOf(n1).length() + String.valueOf(n2).length(),String.valueOf(n1).length() + String.valueOf(n2).length()+String.valueOf(n3).length())
.equals(String.valueOf(n3))) {
return isValid(num.substring(String.valueOf(n1).length()),init_size,n2,n3);
} else {
return false;
}
}
}
public static void main(String[] args) {
generateNum(123,123);
}
}
Do not understand what the input and output is, but this method checks whether a method is valid based on the rules.
static boolean isValid(int[] num, int start, int end) {
if (start > end) {
return false;
}
if (start == end) {
return true;
}
for (int i = start; i <= end - 2; i++) {
for (int j = i + 1; j <=end - 1; j++) {
for (int k = j + 1; k <=end; k++) {
int a=createNum(num, start, i);
int b=createNum(num, i + 1, j);
int c=createNum(num, j + 1, k);
if (a + b ==c) {
if(k==end)return true;
else if (isValid(num, j, end))
return true;
}
}
}
}
return false;
}
static int createNum(int[] num, int start, int end) {
if (start == end) {
return num[start];
}
String s = "";
for (int i = start; i <= end; i++) {
s += num[i];
}
return Integer.parseInt(s);
}
#! /usr/bin/env python2.7
import sys
def solution(num, tmp):
print num, tmp
if len(tmp) >= 3:
if tmp[0] + tmp[1] == tmp[2]:
if num == '':
return True
else:
num1 = ''
for a in tmp:
num1 += str(a)
new_num = num[len(num1) + 1:]
tmp.pop(0)
solution(''.join(new_num), tmp[:])
else:
return False
for i in xrange(1, len(num) + 1):
numX = num[:i]
tmp.append(int(numX))
if solution(num[i:], tmp[:]):
return True
tmp.pop()
return False
if __name__ == "__main__":
print solution(sys.argv[1], [])
My solution. It is really lengthy, but works fine.
The basic idea is:
1. We start from the right(end digit position of the number).
2. Each possible length is between 1 ~ number.length.
e.g. 9817 -> 9 + 8 = 17 (when length = (4 / 2 = 2))
3. If length is k, the possible combination is
(1). num1(1~k) + num2(k) = num3(k)
(2). num1(k) + num2(1~k) = num3(k)
(3). num1(1~k-1) + num2(k-1) = num3(k)
(4). num1(k-1) + num2(1~k-1) = num3(k)
here, num1(1~k) means the length of num1 could be from 1 to k.
Test Cases:
123 -> true
125 -> false
1235 -> true
121224 -> true
1910 -> true
37239 -> true
370239 -> false (02 is ill-formated)
2353355 -> true
bool isValidHelper(const string& num_str, int i, int k) {
for (int j = k; j >= k - 1; j--) {
for (int t = 1; t <= j; t++) {
int sub1 = -1, sub2 = -1, sub3 = -1;
if (i - (t + j + k - 1) >= 0) {
if (t > 1 && num_str[i - (t + j + k - 1)] - '0' == 0)
break;
else
sub1 = stoi(num_str.substr(i - (t + j + k - 1), t));
} else
break;
if (i - (j + k - 1) >= 0) {
if (j > 1 && num_str[i - (j + k - 1)] - '0' == 0)
break;
else
sub2 = stoi(num_str.substr(i - (j + k - 1), j));
} else
break;
if (i - (k - 1) >= 0) {
if (k > 1 && num_str[i - (k - 1)] - '0' == 0)
break;
else
sub3 = stoi(num_str.substr(i - (k - 1), k));
} else
break;
if (sub1 + sub2 == sub3) {
if (i - k - j - t < 0) {
cout << sub1 << "," << sub2 << "," << sub3 << endl;
return true;
}
else {
cout << sub1 << "," << sub2 << "," << sub3 << endl;
return isValidHelper(num_str, i - k, j);
}
}
}
}
for (int t = k; t >= k - 1; t--) {
for (int j = 1; j <= t; j++) {
int sub1 = -1, sub2 = -1, sub3 = -1;
if (i - (t + j + k - 1) >= 0) {
if (t > 1 && num_str[i - (t + j + k - 1)] - '0' == 0)
break;
else
sub1 = stoi(num_str.substr(i - (t + j + k - 1), t));
} else
break;
if (i - (j + k - 1) >= 0) {
if (j > 1 && num_str[i - (j + k - 1)] - '0' == 0)
break;
else
sub2 = stoi(num_str.substr(i - (j + k - 1), j));
} else
break;
if (i - (k - 1) >= 0) {
if (k > 1 && num_str[i - (k - 1)] - '0' == 0)
break;
else
sub3 = stoi(num_str.substr(i - (k - 1), k));
} else
break;
if (sub1 + sub2 == sub3) {
if (i - k - j - t < 0) {
cout << sub1 << "," << sub2 << "," << sub3 << endl;
return true;
}
else {
cout << sub1 << "," << sub2 << "," << sub3 << endl;
return isValidHelper(num_str, i - k, j);
}
}
}
}
return false;
}
bool isValid(int num) {
string num_str = to_string(num);
int i = (int)num_str.size() - 1;
int len = (int)num_str.size() / 2;
bool ret = false;
for (int k = len; k > 0; k--) {
ret |= isValidHelper(num_str, i, k);
}
return ret;
}
vector<int> generateValidNum(int start, int end) {
vector<int> ret;
for (int i = start; i <= end; i++) {
if (isValid(i))
ret.emplace_back(i);
}
return ret;
}
My solution. first + second = rest of the number.Can handle different lengths in rest of the number
public class Increasing_Number {
public static boolean checkNumber(int number) {
String num = number + "";
int l, j, length;
int n = num.length();
int first, second, rest;
// length of number to check
length = n / 2;
// Checking all possible lengths
for(l = 1; l <= length; ++l) {
// get all substrings
for(j = 0; j <= n - 3 * l; ++j) {
first = Integer.parseInt(num.substring(j, j+l));
second = Integer.parseInt(num.substring(j + l, j + l * 2));
// Rest of the substring is iterated for all lengths
for(int i = j + 2*l + 1; i <= n ; ++i) {
rest = Integer.parseInt(num.substring(j + 2* l, i));
if((first + second) == rest) {
if(i == n) {
return true;
}
}
}
}
}
return false;
}
public static void main(String args[]) {
int start = 101020;
int end = 101020;
boolean result = false;
for(int i = start; i <= end; ) {
result = checkNumber(i);
System.out.println(i + " : " + result);
// i = i * 10 - 18;
}
}
}
#include<iostream>
#include<string>
#include<sstream>
using namespace std;
string ConvertToString( int n )
{
stringstream st;
st << n;
return st.str();
}
int FormNumber( string s , int start , int length )
{
int result=0,i=0,j=start;
while( i < length)
{
result = result*10 +(s[j]-'0' );
j++;
i++;
}
return result;
}
void Find( int start , int end )
{
if( end <= 99 )
return;
if( start <= 99 )
start = 100;
for( int num = start ; num<=end ; num++ )
{
string s = ConvertToString(num);
for( int digit = s.length()-1 ; digit>=s.length()/2 ; digit-- )
{
for( int i=1;i<digit;i++ )
{
for( int j=1 ; j<digit ; j++ )
{
if( i+j == digit )
{
if( FormNumber(s,0,i) + FormNumber(s , i , j ) == FormNumber(s , i+j , s.length()-(i+j) ) )
cout << s;
}
}
}
}
}
}
int main()
{
Find(101 , 123 );
return 0;
}
import java.util.ArrayList;
import java.util.Collections;
public class digitAddition{
public static void main(String args[]){
int start = 100;
int end = 1000;
for(int i = start; i<= end; i++){
if(checkDigitAddProperty(i)){
System.out.println(i);
}
}
}
public static boolean checkDigitAddProperty(int num){
ArrayList<Integer> arraylist = new ArrayList<>();
while(num!=0){
arraylist.add(num%10);
num = num/10;
}
Collections.reverse(arraylist);
for(int i = 2; i<arraylist.size();i++){
if(arraylist.get(i) != arraylist.get(i-1) + arraylist.get(i -2)){
return false;
}
}
return true;
}
}
Takes care of variable length also. Just the code to check whether a number is fib
- Anonymous April 18, 2012int num1; int num2 = Integer.parseInt(num.substring(0,1)); int num3 = Integer.parseInt(num.substring(1,2)); for(int i = 1; i<num.length();i++) { num1 = Integer.parseInt(num.substring(0,i)); for(int j = i+1; j<num.length();j++) { num2 = Integer.parseInt(num.substring(i,j)); int thirdIndex = j; int rest = Integer.parseInt(num.substring(thirdIndex,num.length())); while(num1+num2<=rest) { num3 = num1+num2; String newNum = (new Integer(num3)).toString(); int length = newNum.length(); if(thirdIndex+length > num.length()) { break; } if(num.substring(thirdIndex,thirdIndex+length).equals(newNum)) { thirdIndex += length; if(thirdIndex == num.length()) { return true; } num1 = num2; num2= num3; rest = Integer.parseInt(num.substring(thirdIndex,num.length())); } else { break; } } //if(isfine) break; } //i } return false; }