Epic Systems Interview Question Software Engineer / Developers
@ibnipun10
I think we have to prove that only some combinations are valid
for odd digit two combinations need to be considered and checked
25126 = 25,1,26 or 2,51,26
For even digit only one combination need to be considered
121224 = 12,12,24
if I try another combinations it seems not possible.
If we are only considering two number combinations i.e. lets say the range is 12 to 40 12+13=25 but not 12+13+14=39. The algorithm is as follows
public void printCombinations(int num1,int num2)
{
for(int i=num1;i<num2;i++)
{
int range=num2=num1;
for(int j=num1+1; j<=range;j++)
{
System.out.println(num1+""+j+num1+"j"+(num1+j));//this could not compile but //idea is to get tostring of all the numbers excpet the last expression
}
}
}
The only idea I can think of to include more than 2 numbers is to do some kind of meta programming and including another level of for loop based on 3num1+3<num2. But in java I wont bother doing it.
Given 2 numbers, print fibonacci in that range.
let the numbers be a and b
void fibonacci(int a, int b)
{
int min, max;
if(a==b)
{
print("%d, %d",a,b);
return;
}
else if(a<b)
{
min = a;
max = b;
}
else
{
min = b;
max = a;
}
int i=min, j=min;
print("%d",min);
while(1)
{
if((i+j)<max)
{
print("%d",j);
i=j;
temp = j;
j = i+j;
i = temp;
}
else
{
print("%d",max);// considering max input is given correct and is in series other wise eliminate printing max.
break;
}
}// end of while
}// end of function
<pre lang="java" line="1" title="CodeMonkey68384" class="run-this"> class Fibonacci{
public void printFib(int num1, int num2){
int currentNum=num1;
int nextNum=num1;
int printNum=0;
System.out.println(currentNum);
System.out.println(nextNum);
while((nextNum+currentNum)<=num2){
printNum=nextNum+currentNum;
System.out.println(printNum);
currentNum=nextNum;
nextNum=printNum;
}
}
public static void main(String[] args){
Fibonacci fi=new Fibonacci();
fi.printFib(10,890);
}
}</pre><pre title="CodeMonkey68384" input="yes">
</pre>
#include <stdlib.h> // for itoa() call
#include <stdio.h> // for printf() call
#include <string.h> // string functions
int main() {
int pass;
char lower_fib[25];
char higher_fib[50];
char fibStr[50] = "0";
int lower_len, start_len;
char start_str[10];
char last_str[10];
int start_num, last_num;
//enter a range of numbers
printf("Enter the lower range to generate fibonacci numbers\n");
scanf("%s",lower_fib);
printf("Enter the upper range to generate fibonacci numbers\n");
scanf("%s",higher_fib);
//convert to string find length/3
lower_len = strlen(lower_fib);
start_len = (lower_len > 3)?(lower_len/3):1;
//find l/3 most significant digits and form first fibo num
strncpy(start_str,lower_fib,start_len);
start_num = (lower_len >= 3)?atoi(start_str):1;
//increment l/3+1 form new number until final limit reached
pass=0;
do{
//compare with lower range; if smaller discard
if (pass > 1)
printf("%s ",fibStr);
else
if(pass == 1 && strcmp(fibStr,lower_fib) >= 0) printf("%s ",fibStr);
last_num = 2*start_num;
itoa(last_num,last_str,10);
itoa(start_num,start_str,10);
//build the fibo num
strcpy(fibStr,start_str);
strcat(fibStr,start_str);
strcat(fibStr,last_str);
start_num++; pass++;
}while(atoi(fibStr) < atoi(higher_fib));
return 0;
}
Is this correct ?
void printFibCombinations (int lower, int higher)
{
for (int i = lower ; i <=higher ; i++)
{
for (int j = i ; j <=higher ; j++)
if (i + j >=lower && i+j <= higher)
printf ("%d %d %d\n",i,j,i+j);
else
break;
}
}
For each number within the range:
1. Get all subsequence index of the number. Example: 01234 are the indexes of five digit number, the subsequences will be: 1,2,3,4,5,12,23 etc.
2. int index = 0; ArrayList candidates;
3. For each subsequence starting with index:
candidates.add(subsequence);
index = index + lastindex(subsequence) + 1;
if(index >= size_of_number)
checksum(candidates) and return true if true.
This one works fine, please post your comments if you see anything wrong .. (code in C#):
static void Main(string[] args)
{
String num1, num2;
Console.WriteLine("please enter the first number: ");
num1 = Console.ReadLine();
Console.WriteLine("Please enter the second number: ");
num2 = Console.ReadLine();
if ((num2.Length >= 3) &&(num1.Length>=3) && (Int32.Parse(num2) > Int32.Parse(num1)))
findFibnacci(num1, num2); //("12526", "12527");
else
Console.WriteLine("ERRROR!!!");
Console.ReadLine();
}
public static int getNumbers(char[] c, int nums, int currentPos)
{
String temp = "" ;
int part;
for (int i = currentPos; i < currentPos+nums; i++)
{
temp = temp + c[i];
}
part = Int32.Parse(temp);
return part;
}
public static void findFibnacci(string num1, string num2)
{
int n1 = Int32.Parse(num1);
int n2 = Int32.Parse(num2);
int nextNum = n1;
int lengthOfnextNum= 0;
int[] fibonacciNums = new int[0];
int findCount = 0;
while (nextNum <= n2)
{
char[] charNums = nextNum.ToString().ToCharArray();
lengthOfnextNum = charNums.Length;
int q = lengthOfnextNum / 3;
int r = lengthOfnextNum % 3;
int currentPos = 0;
int part1, part2, part3;
if ((r == 0) || (r==1))
{
part1 = getNumbers(charNums, q, currentPos);
currentPos = q;
part2 = getNumbers(charNums, q, currentPos);
currentPos = 2*q;
part3 = getNumbers(charNums, charNums.Length-currentPos, currentPos);
if (part1 + part2 == part3)
{
Array.Resize(ref fibonacciNums, fibonacciNums.Length + 1);
fibonacciNums[fibonacciNums.Length-1] = nextNum;
findCount++;
}
}
else if (r==2){ //0,1 or 2 that can be the only possible values of r
part1 = getNumbers(charNums, q, currentPos);
currentPos = q;
part2 = getNumbers(charNums, q+1, currentPos);
currentPos = 2*q + 1;
part3 = getNumbers(charNums, charNums.Length - currentPos, currentPos);
if (part1 + part2 == part3)
{
Array.Resize(ref fibonacciNums, fibonacciNums.Length + 1);
fibonacciNums[fibonacciNums.Length - 1] = nextNum;
findCount++;
}
else
{
currentPos = 0;
//Console.WriteLine("check begins");
part1 = getNumbers(charNums, q+1, currentPos);
currentPos = q+1;
part2 = getNumbers(charNums, q, currentPos);
currentPos = 2*q+1;
part3 = getNumbers(charNums, charNums.Length - currentPos, currentPos);
if (part1 + part2 == part3)
{
Array.Resize(ref fibonacciNums, fibonacciNums.Length + 1);
fibonacciNums[fibonacciNums.Length - 1] = nextNum;
findCount++;
}
}
}
nextNum++;
lengthOfnextNum = nextNum.ToString().Length;
}
Console.WriteLine("The custom defined fibonacci numbers between " + n1 + " and " + n2 + " are: ");
for (int k = 0; k < fibonacciNums.Length; k++)
Console.WriteLine("("+k+1 + ")" + fibonacciNums[k]);
}
A recursive solution is much simpler conceptually. I did this in less than 10 lines in Java. Also many posting here are over-looking the assumption given in the question i.e. it is safe to assume as indeed is the case for the Fibonacci series that the 1st two entries are the same number i.e. 25, 25 followed by 50 or 1, 1, followed by 2 or 12, 12, then followed by ... you know that already don't you? yeah 24
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
/**
*
* @author DIMENSION
*/
public class fibonacci_number {
public static int count = 0;
public static int check(int n1,int n2,int n3)
{
count++;
if(n1+n2==n3)
{
//System.out.println(n1+"+"+n2+"="+n3);
System.out.println(n1+""+n2+""+n3);
return 1;
}
else
return 0;
}
public static void main(String args[])
{
int range1=123;
int range2=819;
for(int k=range1;k<=range2;k++)
{
String f = Integer.toString(k);
int n = f.length()/2;
for(int i=0;i<n;i++)
{
for(int j=i+1;j<n+i+1;j++)
{
int num1 = Integer.parseInt(f.substring(0, i+1));
int num2 = Integer.parseInt(f.substring(i+1, j+1));
int num3 = Integer.parseInt(f.substring(j+1,f.length()));
int temp = check(num1,num2,num3);
if(temp == 0)
continue;
else
break;
}
}
}
}
}
Well I have used a nested loop. I keep taking 1 digit then 2 digit and so on from the start of the number and within it I keep extracting another set of numbers. Now I add the two digits from the two level of extraction and check if its equal to what is left of the number. Here is a working C++ code. It is not a very efficient code but works fine.
#include <cstdio>
#include <iostream>
#include <math.h>
using namespace std;
int func(long num);
int func(long num)
{
long int num1, n1, flag=0, n2, n3, i, j, dig, ct=0;
dig=num;
while (dig!=0)
{
dig/=10;
ct++;
}
for (i=ct-1; i>=2; i--)
{
n1=num/pow(10, i);
num1=fmod(num, pow(10, i));
for (j=i-1; j>=1; j--)
{
n2=num1/pow(10, j);
n3=fmod(num1, pow(10, j));
if (n1+n2==n3)
{
cout<<num<<endl;
cout<<n1<<"+"<<n2<<"="<<n3<<endl;
flag=1;
break;
}
}
if (flag==1)
{
break;
}
}
return 0;
}
int main()
{
long int x, y, i;
cin>>x>>y;
for (i=x; i<=y; i++)
{
func(i);
}
return 0;
}
Python working code:
def main():
num = ''
in_range = 123333
out_range = 12333333
t1 = 1
t2 = 0
i=1
while len(str(t1)) <= len(str(out_range))/2:
while len(str(t2)) <= len(str(out_range))/2:
while True:
value = fib(i,t1,t2)
num = num + str(value)
if i>=3:
if in_range < int(num) and int(num) < out_range:
print num
elif int(num)>out_range:
num = ''
i=1
break
i = i+1
t2 = t2 + 1
t2=0
t1 = t1 + 1
def fib(n,t1,t2):
#print "num", n
if n==0:
return 0
elif n==1:
return t1
elif n==2:
return t2
else:
return fib(n-1,t1,t2) + fib(n-2,t1,t2)
if __name__ == '__main__':
main()
to understand this question you need to know Fibonacci Math. Search wikipedia Fibonacci math
this means a Fibonacci math is 0,1,1,2,3,5,8... 0+1=1, 1+1=2, 1+2=3 and so on so if you have a number 242448 then it would be a true Fibonacci number because 24+24=48 a number 132134 is a true Fibonacci because 13+21=34 (and 13 is 5+8=13 from the above string) so to answer the question about 5 digit number only if it were true i.e. 12358 = 1,2,3,5,8 but not 12,35,8 because 12+35 do not equal 8 but 123547 is true. once you have this concept down then you can develop what ever to mimic this.
Good Luck Everyone
Unable to understand the question...
- DashDash July 31, 2010What do we have to say for 5 digit number
Let say we have
25125, Now this we can be taken as
25,1,25 or 25,12,5 or 2,5,1,2,5 or 251,25.. many combinations
Which combination to take?