Alcatel Lucent Interview Question
Java DevelopersCountry: India
Interview Type: Written Test
Yes, this is "coin change" or "change-making" problem, the only minor difference is that the given coin system is not finite.
Fibonacci is a canonical coin system, i.e., a coin system for which a greedy algorithm can give result as good as the optimal result.
Greedy algorithm for this problem is efficient enough.
Great job!
getHighestFibNumber can be optimised using binary search.
thereby reducing overall complexity to O( n log n ).
I think time complexity of this implementation is O(logN * logN), where N is the value of the desired sum, assuming adding/comparison two (big) integers is O(1). (In fact, adding/comparison of two big numbers N and M is O(max(logN, logM)).
Why it is O(logN * logN) time? Well, we have at most O(logN) number of Fibonacci numbers that are not larger than N.
The minimum number of Fibonacci needed is also of O(logN).
In the OP implementation, the split() function is called O(logN) times. For each call, the function getHighestFibNumber() takes about O(logN) to loop through the list of "cached" Fibonacci numbers. Thus, overall running time is O(logN * logN).
So, if using binary search for getHighestFibNumber(), the overall complexity can be reduced to O(logN * log(logN)).
Even better, if we process the Fibonacci list from back to front, we can get average O(1) for getHighestFibNumber(), thus improving to O(logN) overall.
Keshav's implementation below achieves O(logN) time complexity.
Note that, we can't do better than O(logN), which is= number of Fibonacci numbers less than N. Thus, O(logN) time algorithm is optimally efficient for this problem.
@Vishnu: did you mean n = number of Fibonacci numbers = log N? Then you're correct!
Following is a DP solution in O(n) using O(n) space :-
import java.util.ArrayList;
import java.util.List;
public class fibosum {
public static int minFiboSum(int n) {
List<Integer> fiboNums = new ArrayList<Integer>();
int a=1,b=1,c=1;
while(true) {
c = a+b;
if(c<=n)
fiboNums.add(c);
else break;
a = b;
b = c;
}
int minSum[] = new int[n+1];
minSum[0] = 0;
for(int i = 1;i<=n;i++) {
minSum[i] = n;
for(Integer fibo : fiboNums) {
int k = fibo;
int steps = 0;
if(k<=i) {
steps = minSum[i-k] + 1;
minSum[i] = Math.min(minSum[i], steps);
}
else break;
}
}
return minSum[n];
}
public static void main(String args[]) {
System.out.println(minFiboSum(7));
System.out.println(minFiboSum(70));
}
}
This problem is similar to that of finding prime factors of a number, only the factors considering here are different.
The Algorithm works by Stacking up the fibonacci numbers till the number crosses given "n" value.
Pop the number from the stack and compare the "sum" + the number retrieved with "n".
If the total is greater than "n" then ignore the number retrieved, iterate for next element from the stack. If the value is lesser then add up the number to sum and continue the recursion till the "sum" became equal to "n".
import java.util.Stack;
public class HelloWorld{
static Stack st = new Stack();
public static void main(String []args){
fibonacciSum(123);
}
public static void fibonacciSum(int n){
int prev = 1, cur = 2;
st.push(prev);
while(cur<n){
int temp = prev;
prev = cur;
cur = temp + prev;
st.push(prev);
}
int sum = (int)st.pop();
System.out.println(sum);
recSum(sum,n);
}
public static void recSum(int sum, int n){
if((sum+(int)st.peek())==n){
System.out.println(sum+(int)st.peek() + " - " + st.pop());
}
else if((sum+(int)st.peek())>n){
st.pop();
recSum(sum, n);
}
else if((sum+(int)st.peek())<n){
sum+=(int)st.peek();
System.out.println(sum + " - " + st.peek());
recSum(sum,n);
}
}
}
Time complexity of this algorithm is log(sqrt(n)).
Trying to implement the same algorithm to handle with duplicates will depreciate the efficiency.
We should have to mention that this greedy works fine for Fibonacci series.
Your implementation using stack is really nice!
By the way, you state that your algorithm is O(log(sqrt(N)), which indeed is = O(log N) (where N is the value of the desired sum).
The number of Fibonacci numbers that less than N is of O(log(N)) already. How did you get the sqrt()?
My dynamic programming solution, (in python because I dislike java):
First, define a fibonacci function with memoization so we can get the Nth fibonacci number in O(N).
fib = dict()
def fibonacci(i):
if not fib.get(i):
if i < 2:
fib[i] = 1
else:
fib[i] = fibonacci(i-1) + fibonacci(i-2)
return fib[i]
Now we can build up the solution from 1 -> N using DP. In general for an arbitrary array of integers, if we have an array of E elements, the DP step looks like:
DP(i) = min(1 + DP(i - ej, j-1)) for 0 < j < len(E), where ej is the jth element of E.
In this algorithm, E is just the sequence of fibonacci numbers. Since fibonacci number sequence is infinite, we only really need the numbers up to N, or up to i with each step of iteration. The repetition is tricky, since we have to test all possible multiples for ej.
def min_fib(N):
fib_index = 0
DP = dict()
E = set()
DP[0] = 0
for i in range(1, N+1):
# update the list E with all possible fib numbers that could add up to i
while fibonacci(fib_index) <= i:
E.add(fibonacci(fib_index))
fib_index += 1
min_option = None
for e in E:
multiple = e
# since reptitions are allowed, we have to test all multiples
while i-multiple >= 0:
option = multiple/e + DP[i-multiple]
if not min_option or option < min_option:
min_option = option
# extra optimization step: if there are more multiples then the min_option, it is impossible to achieve a better score and we can just break here
if min_option <= multiple/e:
break
multiple += e
DP[i] = min_option
return DP[N]
Runtime is O(N^3) I believe. Without repetitions allowed it would be O(N^2).
repetition is allowed. first fibonacci number is 1. 1+1+1... can give you any number. so 1?
Pseudo code:
_1. Generate all the Fibs that are less than or equal to the number
_2. Obtain the numbers that would be needed and count them
___1. use BST to find the largest number in the FIB that is smaller than or equal to the actual number
___2. subtract the BST result from the number
___3. if the new number is 0 return the number of times this repeated otherwise repeat at substep 1
The complexity of this approach should approximate (not sure how to make the exact logarithmic computation due not being able to convert the growth rate of Fib as compared to n so I'm replacing Log with Fib to represent a logarithmic-like Fib growth rate) O( Fib n * Log (Fib n) ) time ( it will take O( Fib n) to compute the Fib values present and O( Fib n * Log (Fib n) ) to execute the repeated BST searches) and it will take O( Fib n) memory):
public static int numFibs(int k){
ArrayList<Integer> fibs = computeFibs(k);
return searches(k, fibs);
}
private static ArrayList<Integer> computeFibs(k){
ArrayList<Integer> results = new ArrayList<Integer>();
if(k == 0){
return results;
}
results.add(1);
if(k == 1){
return results;
}
results.add(1);
int val = -1;
while( (val = results.get(results.size() - 1) + results.get(results.size() - 2) ) <= k){
results.add(val);
}
return results;
}
private static int searches(int k, int[] fibs){
int count = 1;
k -= fibs[fibs.length -1];
int maxIndex = fibs.length - 2;
while(k > 0){
int newIndex = bst(k, fibs, maxIndex);
k-= fibs[newIndex];
count++;
maxIndex = newIndex;
}
return count;
}
private static int bst(int k, int[] arr, int maxIndex){
if(maxIndex == 0){
return 0;
}
int lo = 0;
int hi = arr.length -2;
while(lo < hi){
int mid = ( lo + hi ) >>> 1;
if(arr[mid] > k ){
hi = mid -1;
}
else if(arr[mid+1] < k ){
lo = mid + 1;
}
else{
return mid;
}
}
if(lo == maxIndex){
return lo;
}
else if(arr[lo + 1] < k){
return lo + 1;
}
else{
return lo;
}
}
Thinking about this, I could probably make the code generate the fib numbers at the same time as the computation and finish it simpler in O(Fib n)...
public static int countFibFactor(int k){
ArrayList<Integer> fibs = new ArrayList<Integer>();
//build the fibs
fibs.add(0);
int fib = 1;
while(fib < k){
fibs.add(fib);
fib = fibs.get(fibs.size() -1 ) + fibs.get(fibs.size() -2);
}
//greedily remove values from the fib computation
int count = 0;
for(int i = fibs.size() - 1; i > -1; i -- ){
int num = fibs.get(i);
if(k >= num){
k -= num;
count++;
}
if(k == 0){
break;
}
}
return count;
}
WHOW, WHOW, here's the right solution:
I don't want to explain it, but you can understand that I'm calculating fibonacci sequence, till it reaches the number and then I use that array (in which I saved the fibonacci sequence) to calculate the solution for all numbers from 1 to N (by using dp).
DP[N]= Min, where Min is calculated using :for all j in fibonacci sequence such that j<N, Min= (Min,1+DP[N-j])
private static ArrayList<Integer> CalFibonacci(int N){
int Fib0=0;
int Fib1=1;
ArrayList<Integer> ret=new ArrayList<>();
ret.add(Fib0);
if (N==Fib0) return ret;
ret.add((Fib1));
if(N==Fib1) return ret;
else{
int lastAdded=Fib1;
while(lastAdded<N){
//size=ret.size();
lastAdded=ret.get(ret.size()-1)+ret.get(ret.size()-2);
ret.add(lastAdded);
}
}
return ret;
}
private static int solveMinFibSum(int N){
ArrayList<Integer> fib=CalFibonacci(N);
//return if its in the fib series
if(fib.get(fib.size()-1)==N){ return 1;}
int[] dp=new int[N];
int[] sol=new int[N];
dp[0]=1;
sol[0]=-1;
for (int i=1;i<N;i++){
//dp[i] stores the answer for number i+1
int pos=PosByBinarySearch(fib,i+1);
if(fib.get(pos)==(i+1)){
dp[i]=1;
sol[i]=-1;
}
else{
int min=Integer.MAX_VALUE;
int beforeMin=min;
for(int j=pos;j>0;j--){
min=Math.min(min,1+ dp[(i)-fib.get(j)]);
if(beforeMin!=min){
sol[i]=j;
}
beforeMin=min;
}
dp[i]=min;
}
}
//print solution
int k=sol[N-1];
int curr=N;
//this crap is just for printing solution and verifying my solution
while(k>=0){
System.out.print(fib.get(k)+" ");
curr=curr-fib.get(k);
k=sol[curr-1];
}
if (k==-1) System.out.print(curr);
System.out.println();
//
return dp[N-1];
}
private static int PosByBinarySearch(ArrayList<Integer> arr, int srch){
return BinarySearchPos(arr,srch,0,arr.size()-1);
}
private static int BinarySearchPos(ArrayList<Integer> arr, int srch, int start , int end){
if(arr.get(start)>srch) return start; //should never happen , but alas
if (start==end){return start;}
if (end-start==1)
{ //a lot of cases should never happen here, but you gotta write them up
if (arr.get(start)==srch) return start;
else if(arr.get(end)==srch) return end;
else if(arr.get(end)>srch) return start;
else return end;
}
else{
int mid=(start+end)/2;
int midvalue=arr.get(mid);
if(midvalue==srch) return mid;
else if(midvalue<srch){
return BinarySearchPos(arr,srch,mid,end);
}
else return BinarySearchPos(arr,srch,start,mid-1);
}
}
public static void main(String [] args){
//ArrayList<Integer> ans=CalFibonacci(134654897);
//for(int i=0;i<ans.size();i++){System.out.print(ans.get(i)+ " ");}
System.out.println(solveMinFibSum(110));
}
}
How about this approach ----
Need some clean up --just wrote it :)
import java.util.ArrayList;
public class FiboSum {
public ArrayList<Integer> result = new ArrayList<Integer>();
public ArrayList<Integer> fibo(int num) {
int a = 0, b = 1, c = 0, i;
ArrayList<Integer> series = new ArrayList<Integer>();
series.add(b);
for (i = 1; i <= num; i++) {
c = a + b;
if (c <= num) {
series.add(c);
a = b;
b = c;
}
}
return series;
}
public void getMinFibo(int num) {
ArrayList<Integer> series = new ArrayList<Integer>();
series = fibo(num);
result.add(series.get(series.size() - 1));
int diff = num - series.get(series.size() - 1);
if (diff >= 1) {
getMinFibo(diff);
}
System.out.print("series= " + result);
}
public static void main(String[] args) {
FiboSum ff = new FiboSum();
ff.getMinFibo(70);
}
}
It looks like the Change-making problem.
As Fibonacci is a canonical system, a solution for spliting N in a sum of fib numbers is just to get the highest fibonacci number F and then do the same with N' = N-F ...
for N= 70 instead of getting 34+34+2, I will get 55+13+2.
here is my solution
- Guillaume November 03, 2014