## Alcatel Lucent Interview Question for Java Developers

• 0
of 0 votes

Country: India
Interview Type: Written Test

Comment hidden because of low score. Click to expand.
2
of 2 vote

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

``````public class FibSplitter {

private List<Integer> cache = new ArrayList<Integer>();

public FibSplitter() {
cache.add(0);
cache.add(1);
}

/**
* Returns the highest Fibonacci number lower than n.
* @param n
* @return
*/
private int getHighestFibNumber(int n) {
int index = 0;
int f1 = cache.get(index);
int f2 = cache.get(index + 1);
int temp;
while (f2 <= n) {
if (index < cache.size() - 2) {
f1 = f2;
f2 = cache.get(index + 2);
} else {
temp = f1;
f1 = f2;
f2 = temp + f1;
cache.add(f2);
}
index++;
}
return f1;
}

public List<Integer> split(int n) {
if (n == 0) return new LinkedList<Integer>();
int f = getHighestFibNumber(n);
List<Integer> result = split(n-f);
result.add(f);
return result;
}

public static void main(String[] args) {
FibSplitter fib = new FibSplitter();
System.out.println(fib.split(7)); // [2, 5]
System.out.println(fib.split(70)); // [2, 13, 55]
System.out.println(fib.split(2583)); // [2, 5, 13, 34, 89, 233, 610, 1597]
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 votes

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!

Comment hidden because of low score. Click to expand.
1
of 1 vote

getHighestFibNumber can be optimised using binary search.

thereby reducing overall complexity to O( n log n ).

Comment hidden because of low score. Click to expand.
0
of 0 votes

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!

Comment hidden because of low score. Click to expand.
2
of 2 vote

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;
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));
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 votes

Please, coult you explain your solution?

Comment hidden because of low score. Click to expand.
0
of 0 votes

Also how to restore numbers, that were used to make a solution.

Comment hidden because of low score. Click to expand.
2
of 2 vote

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.

Comment hidden because of low score. Click to expand.
1
of 1 vote

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()?

Comment hidden because of low score. Click to expand.
0
of 0 votes

You should pop out the element in the last block..i.e.,

else if((sum+(int)st.peek())<n){
sum+=(int)st.peek();
st.pop();
System.out.println(sum + " - " + st.peek());
recSum(sum,n);
}

Comment hidden because of low score. Click to expand.
1
of 1 vote

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

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).

Comment hidden because of low score. Click to expand.
0
of 0 votes

You're biased DP over greedy. You're biased Python over Java :))
Nice try anyway!

Comment hidden because of low score. Click to expand.
1
of 1 vote

repetition is allowed. first fibonacci number is 1. 1+1+1... can give you any number. so 1?

Comment hidden because of low score. Click to expand.
0
of 0 votes

Had the same doubt initially.
We need to find number of numbers...not the minimum number which we pick

Comment hidden because of low score. Click to expand.
0
of 0 vote

can you give me some more test cases.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 votes

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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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=1;
sol=-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));
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

int solve(int N)
{
if(N==0 || N==1)
return N;
int prev = 1,curr=2;
while(curr<=N)
{
int temp = prev;
prev= curr;
curr = temp+curr;
}
return solve(N-prev)+1;
}
int Solution::fibsum(int A) {
return solve(A);
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}

}

Comment hidden because of low score. Click to expand.
-1
of 1 vote

can you give me some more test cases.

Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

### Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

### Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More