I have done quite a few software engineering interviews and there seems to be a trend of questions, particularly concerning the Fibonacci series. I am 100% certain if you Google it then you will find an answer. But why do interviewers ask it and what does it show?
Lets begin by just defining what the Fibonacci series actually is:
0 , 1, 1 , 2 , 3 , 5 , 8,…
Are you slowly getting the pattern? What we see is that any number in position n is the sum of the previous two numbers (well except in the case of n = 0 or n = 1)
We actually very simply write this as a triangle:
0
1 1
1 2 1
1 3 3 1
As we can see here, we add the upper right and left together to form the next row and so on.
Hence we can write the series as:
This the key here, in any interview question is firstly realising the series is Fibonacci and then more importantly that it can be dealt with in using recursion.
So why recursion? Well clearly we need to look back at previous values and build up and on, hence we split the problem to recall two functions i.e.
return fib(n-1) + fib(n-2);
public class Fibonacci {
public static long fib(int n) {
if (n <= 1)
return n;
else
return fib(n-1) + fib(n-2); // recursive call here!!!
}
public static void main(String[] args) {
int n = Integer.parseInt(args[0]);
for (int 0 = 1; i <= n; i++)
System.out.println( i + ": " + fib(i) );
}
}
Ok, so first part is done i.e. recognising it is indeed a recursive problem. Now is the trickier part, finding how we can improve upon this.
One issue with recursion is that it is expensive, requiring time 
public class FibonacciIterative {
public static int fib(int n){
int prev1 = 0, prev2 =1;
for(int i = 0; i =>< n; i++){
int savePrev1 = prev1 ;
prev1 = prev2;
prev2 = savePrev1 + prev2;
}
return prev1;
}
public static void main(String[] args) {
int n = Integer.parseInt(args[0]);
for (int 0 = 1; i <= n; i++)
System.out.println( i + ": " + fib(i) );
}
}
So now we have made our recursive solution into an iterative solution.
However here is where many interviewers may actually stop, but can we make a further improvement?
One answer is to use memorization. Memoziation, from my understanding is the ability to cache the results when calculating a fibonacci number so we don’t have to recalculate it.
So how does java lend itself to this? The use of hashmaps. This is where we can place a key and a corresponding value into a hashmap. If a key already exists in the map none is added, but the value is retrieved. If the key doesn’t exist then we add it.
Here our keys are the fib(n) etc. and the values is the result from the function. So we can write a quick checker function:
public static int improvedFibo(int number){
Integer fib = cache.get(number);
if(fib != null){
return fib; //fib number from cache
}
fib = fibonacci2(number); //fib number not in cache, calculating it
cache.put(number, fib); //putting fib number in cache for future request
return fib;
}
This is a great improvement, but really we must note this only really improves the performance if the Fibonnaci no. we are calculating is really really large.
is indeed the sum of some or all of the elements in the array. Now firstly the easiness of the answer didn’t quite click with me to the point where I was thinking of graph problems. However this is in fact a problem of subsets, where we want to collate all subsets and sum them hence obtaining if K can be made from the array. So we want (in Pseudocode):![[1,2,3], [2,1,3], [3,2,1]](http://s0.wp.com/latex.php?latex=%5B1%2C2%2C3%5D%2C+%5B2%2C1%2C3%5D%2C+%5B3%2C2%2C1%5D&bg=ffffff&fg=333333&s=0 "[1,2,3], [2,1,3], [3,2,1]")
then we can see that we have 
subsets.
, this is also handy.
then we should really stop instantly as in this case we are no where near creating the value k. We could also add an element of randomisation, whereby rather than doing a for loop across all possible subsets, we could just randomise this number 
.
