# Simplicity and Memorization – Fibonnaci Series Broken Down

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:

$F(n) = F(n-1) + F(n-2)$

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 $O(2^n)$. So lets look at how we can do this iteratively which will be linear 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.

# Finding if the Sum k exists in an Array and Finding Subsets of an Array- JAVA

Today I was asked an interesting question which I thought I would share here. So lets say we have an int array, let this be called nums. We want to see if an integer K exists in this array, but not just directly but by the summation of any elements of an array.

For example.

nums = [1, 3, -5, 10]
k = 11 => true
(1 + 10 == 1) k = 6 => true
(1 – 5 + 10 == 6) k = 20 => false

So here we want our function to return true, if $k$ 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. Calculate all subsets of nums
2. Sum the subsets to check if they equal to k

Just briefly how many subsets do we have? Lets say order really doesn’t matter i.e. we don’t care if its $[1,2,3], [2,1,3], [3,2,1]$ then we can see that we have $2^n$ subsets.

Here is my solution in Java:

```
import java.util.ArrayList;

public class Subset {

public static void main(String[] args){

// let final args be the k value

// checks args are given
if(args != null){

int[] nums = new int[args.length - 1];

for(int current = 0; current &lt; args.length - 1; current++ ){
nums[current] = Integer.parseInt(args[current]);
}

if( subsets(nums, Integer.parseInt(args[args.length-1]) ) ){
System.out.println("k does exits in nums");
}
else
System.out.println("k does not exist in nums");

}
}

// this gets us all subsets

public static boolean subsets(int[] nums , int k){

int length = nums.length;
int totalSubsets = (int) Math.pow(2,length);

ArrayList subsets = new ArrayList();

for(int i = 0; i &lt; totalSubsets; i++){

int position = length - 1;

// we can actually directly calculate the sum, and check when a  subset is created if this equals k

int sum = 0;

ArrayList currentSubset = new ArrayList();

sum += nums[position];

}

position--;
}

System.out.println(currentSubset);
System.out.println("k "+ k);
System.out.println("sum "+ sum);

if(sum == k)
return true;

}

return false;
}
}

```

Now reflecting on this.. how to improve….

Well firstly in the pseudocode, I had assumed we would calculate the subsets first then check the sum of each one. What is better to keep the running total of each subset and return when equal to $k$, as I did above. This leads me to question, why even keep the array list of every subset or all subsets at all. The only advantage of this is for our own sanity to print these out and ensure there is no repetition of subsets. Also lets say if we were relying on knowing what elements when summed together produce $K$, this is also handy.

With regards to returning true, the second we find k equal to the sum of some elements, prevents any excess computation after as opposed to keeping a flag.

Ok so these are small things, but what about more advanced improvements. Well firstly a very simply one would be checking that k is not equal to any of the elements i.e. is k present in the array. Also we should really check the boundaries and whether the sum can even reach k. This is where we would sum all elements instantly, before any subset is made and simply check that we could ‘realistically’ make k, i.e. If we have $a + b + c = d < k$ 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 $i$.

Anyway I wanted to reflect on this, mainly as I never fully considered how to produce subsets of a given list. I find with Python one can become rather lax with using itertools permutations functions and such. It is interesting to see how usig a bitmask can work.

# Kids Koding

Today I am coming to the end of a week of teaching some kids to code.

Me taking the kids to the science museum

If I’m honest I expected this week to be some fun, but mainly a job. I have never really worked with children and it actually turns out to be fairly rewarding (when they are behaving themselves!), but I never expected it to feel so rewarding. Its great when they get a concept and simply get excited to start doing some Javascript etc.

Their eyes light up to doing something more interactive and see their hard work in action. I could really feel how they loved how these lines of code became transformed.

So anyway, this is a new scheme in London, called Fire Tech Camp, which was co-founded by Jill Hodges with the intention of getting children into tech at an early age (something which rarely happens)

In recent months there has been a huge campaign by Code.org. video

Many schools in the UK simply don’t teach kids to code. Instead they are often stuck with an hour a week of lessons in Word and PowerPoint (possibly the worst and most user unfriendly software out there). As much as an introduction to these packages are needed, now that children are exposed so heavily to tech anyway we have to ask if its neccessairy to teach them basic I.T. in school or if we need to break it down further into the code which creates these programmes.

As much as the curriculum is now looking at change towards CS, the issue is whether it can stay relevant and up-to-date.

That is exactly where Fire Tech Camp comes into force.

Fire Tech Camp has 3 areas: Robotics, Apps and Games. These are taught alongside learning applications and tools such as GameSalad, AppShed and Enchanting. What’s key is the tutors, often people either in a form of CS education or experienced developers who know about current tech trends and know how far they can take the children’s learning.

Beyond this seeing the kids code is fascinating. I have previously coded with others and seen how older people learn. The children win on the experimental and creative side. The app ideas really tend to push boundaries, beyond anything I’ve seen fellow programmers. I even think some have picked things up quicker than me!

Anyway reflecting on this, maybe this is the way we really change the shape of the technology industry in the future. By getting children into this when they are younger hopefully in the future they will continue on to be programmers, filling the gap and demand in the market.

Clearly getting the kids generally interested in tech at a young age, should not only deal with the need for more programmers but also even out any gender differences.

But all of this made me question, what stops many from questioning in the first place?

At a young age kids question, experiment with things, often leading to something breaking etc. but as we grow up we often stop this all. Many of us question, yes, but our passion and questions of a science nature often disappear. Its as if the current education system drums this out of us.

So how can we change this?

Well I am not quite a parent yet (at least for a good 7+ years) but parents do really need to encourage kids to experiment and play around. I think there almost needs to be a little less of ‘don’t do that’ which we often say as a kid does something leading to disaster. But instead if we encourage them to explore science then maybe this passion will never die and we could have more scientists in our wake.

# Contents

## Why JavaScript Isn't Enough?

This article assumes that the reader has a good knowledge of JavaScript and has done at least some development in it, but if this is not about you, you can just first refer to one of the beginner's JavaScript books like…