Epic Systems Interview Question Software Engineer / Developers
0of 0 votesGiven the start and an ending integer as user input, generate all integers with the following property.
Example : 123 , 1+2 = 3 , valid number
121224 12+12 = 24 , valid number
1235 1+2 = 3 , 2+3 = 5 , valid number
125 1+2 <5 , invalid number
Country: United States
Interview Type: Phone Interview
"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?
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);
}
}
Takes care of variable length also. Just the code to check whether a number is fib
int 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;
}
/*
* 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);
}
}
#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;
}
Here is my solution. Please let me know if I missed something:
- Sasi on March 21, 2012 Edit | Flag ReplyThe 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.