Software Engineer Interview Questions to Know (Entry Level) — Fibonacci & Garbage Collection

If you’ve just stumbled onto this series, make sure to check out the introduction here.

Question 1: Write a method to determine the nᵗʰ Fibonacci number.

Variants

• Count the number of ways to reach the nᵗʰ stair if you can only climb one stair at a time.
• Count the number of ways to reach the nᵗʰ stair if you can climb m steps at a time. This is also known as the nᵗʰ stair, m steps problem.

What They’re Really Asking

• This problem can be very easily solved using recursion. However, the solution is ridiculously inefficient compared to the solution using dynamic programming. Are you familiar with dynamic programming? Can you apply it to a given problem?
• Are you comfortable implementing recursive algorithms? Can you identify when a recursive algorithm has overlapping subproblems and when dynamic programming may be a stronger option?
• In the case of the nᵗʰ stair, m steps problem, can you recognize the underlying problem (i.e. the Fibonacci sequence)? Can you apply other problems (like the Fibonacci sequence) to solve novel problems?

Tools for Our Answer

• The Fibonacci Sequence is named after Fibonacci (1170). It is a series defined with the first two terms being 1 and each subsequent term being equal to the sum of the two previous terms. The sequence is 1, 1, (1+1) = 2, (1+2) = 3, 5, 8, 13, 21, 34, 55,…

First 13 Terms in the Fibonacci Sequence

• This problem naturally lends itself to a recursive solution as the sequence is defined recursively. We can set base cases for n=0 and n=1 as both equal to 1 and return fib(n-1)+fib(n-2) for fib(n). This is implemented below.

Recursive Solution for Fibonacci Sequence. Code source here.

• This method requires 2 lines of code. But the short length is deceptive. This is an incredibly inefficient algorithm. To see why let’s consider fib(4) and track the recursive calls that are made. This is shown below.

Visualization of the expansion for fib(4)

• We see this runs in exponential time for any given n. We also see we are repeating much of the same work — we have many overlapping subproblems. For example, we call fib(2) twice and we call fib(1) three separate times.
• If we can store these values in a clever way, we may be able to avoid redoing a solid amount of work. This is precisely the motivation for dynamic programming.
• Dynamic Programming is a problem-solving technique for dealing with problems that have many overlapping subproblems, just like as above. Dynamic Programming uses memoization — the process of storing (usually expensive) function calls in memory and retrieving these values whenever that function is called again to avoid recomputation.
• In our problem, we will use dynamic programming and memoization to compute and store all n Fibonacci numbers once. We will populate an array of size n with these values. This is shown in the code below.

Fibonacci Sequence using Dynamic Programming. Code source here.

• However, we can still do better. We turn to the French mathematician Jacques Philippe Marie Binet (1786) who developed a formula for calculating the nᵗʰ Fibonacci number. For the derivation and proof, see the Art of Problem Solving’s article here. The formula is below where Fn represents the (n-1) Fibonacci number.

Binet’s Formula. Image source here.

• We can implement the above formula in Java, as shown below. We can reasonably assume that Math.sqrt(n) and Math.pow(n) are constant time operations, meaning that the algorithm below runs in constant time.

Implementation of Binet’s Formula for the Fibonacci Sequence. Code source here.

My Answer

A simple and easy-to-write implement would be to solve this problem recursively. We can define base cases for n=0 and n=1 and return the summation of the Fibonacci value for (n-1) and (n-2). This is shown in the code below.

However, this recursive solution is very inefficient as it repeatedly calculates the same subproblems and runs in exponential time. We can use the strategy of dynamic programming and memoization to store and calculate Fibonacci values in an array once, as shown below. This decreases our runtime to O(N).

However, we can go one step further. We can use Binet’s formula for calculating the nᵗʰ Fibonacci number. All calculations required here run in constant time so this algorithm will run in constant time as well. The implementation is shown below.

Closing Note

One interesting application of the Fibonacci Sequence is in Scrum. Scrum is an Agile software development framework that software teams often use to develop their products. One key component of Scrum is stories. Stories are short requirements or small features of an application. For example, a story for a web design project may be “Add a Contact Us form”.

Stories are assigned points to give an estimate for completion time. For example, a 3 point story likely takes a couple of days to complete. These point estimates are usually the first few terms of the Fibonacci Sequence — 1, 1, 2, 3, 5, 8, 13, 21. This is because a 21-point story is often decomposed into an 8 point story and 13 point story. The 13-point story is decomposed into an 8-point story and a 5-point story, and so on. The Fibonacci sequence is an excellent way for project teams to take large stories and make them more manageable. For those interested more in Scrum, see here.

The beginning of this problem mentioned the nᵗʰ stair, m steps problem. If you count the values for climbing the first, second, third, and fourth steps, you’ll see they mirror the Fibonacci values. This pattern holds and so algorithms that work for the Fibonacci sequence can be used to solve these problems. For those interested, GeeksForGeeks’ contributor, Abhishek, has an article here detailing more.

Question 2: What is garbage collection in Java?

Variants

• What are the four ways an object can be made eligible for garbage collection in Java?
• If I am writing code for high-speed algorithmic trading, what is one potential risk of using Java?

What They’re Really Asking

• Do you understand memory management of variables? Have you worked in languages without automatic memory management?
• Can you explain when variables in memory become unreachable?
• Do you understand the Java Virtual Machine (JVM)? Do you understand how it helps compile and run Java code?
• Do you understand the possible performance effects of automatic memory management? Do you understand how this could make Java ineffective for certain programs and algorithms?

Tools for Our Answer

• Java uses automatic memory management. This is when an operating system, compiler, or interpreter manages memory allocation and deallocation. The Java Virtual Machine (JVM) manages memory for Java programs.
• In a language without automatic memory management (like C), the programmer is responsible for allocating and deallocating memory using methods like malloc() and free(). The JVM allocates memory whenever the new keyword is used, as shown below.

Memory Allocation in Java

• Java deallocates memory (the analog of free()) using garbage collection. When an object is unreachable in memory, garbage collection is the automated process that deallocates the memory that was initially allocated for this object.
• There are four ways to make an object unreachable in Java. The first way is to nullify the reference variable, which is shown below. Note that myList now points to null so the original reference is lost forever.

Nullifying the Reference Variable

• The second occurs when an object is created inside a method and that method terminates. Suppose we make an object myObj inside a method. A reference to myObj is kept in the Call Stack while myObj typically lives in the Heap. When this method terminates, the method is popped from the Call Stack. And the reference to myObj no longer exists. However, myObj still exists in the Heap but it can no longer be reached. This is similar to nullifying a reference variable.
• The third way is to reassign the reference variable. Similarly to the above, the original reference is lost permanently. So, there is no way to access the initially allocated memory. This is shown below.

Reassigning the Reference Variable

• The fourth and final way is referred to as the island of isolation. This is most easily explained through an example. Suppose we have two instantiations of the Node Class, as below.

Two Node Objects

• We can visualize this in memory as below.

Visualization of Nodes a and b in memory

• Now suppose we nullify both a and b. Then Node a and Node b will reference each other but there is no way to reach Node a or Node b. Node a and Node b are on the island of isolation.
• If an object fits any of the above four conditions, it is eligible for garbage collection and the relevant memory will be deallocated.
• Garbage collection in the JVM is a daemon thread. A daemon is a low priority thread that runs as a background process. It is created by the JVM and terminates when the program terminates.
• You can use System.gc() to manually call garbage collection but this does not guarantee an actual garbage collection. For example, the system may be in the middle of allocating memory, in which case garbage collection would be unsafe.

Calling System.gc() in Java

• Garbage collection certainly makes things easier for programmers but there is a lack of control with garbage collection. For example, I do not know exactly when my code will pause to deallocate or allocate memory. This could change due to many factors.
• To get back to the original question, garbage collection may pose an unacceptable risk if we are executing high-speed trades or launching space shuttles. This is not the same as saying Java is slow. Java is fast and only getting faster. But the level of control and speed is not comparable to C.

My Answer

Garbage collection is how the Java Virtual Machine (JVM) deallocates memory. Java manages memory automatically so this means it must have some way to free up Heap space that is no longer in use. Garbage collection is a background thread (a daemon thread) that deallocates heap space for objects that can no longer be accessed.

There are four situations in which an object is eligible for garbage collection. The first is when the original reference variable is nullified. The second occurs when there is a reference variable defined inside a method and that method finishes executing. All the variables and information in that method no longer exist and so the referencing variable is effectively nullified.

The third occurs when the reference variable is reassigned. The last situation is known as the island of isolation. Suppose we have a generic Node class. Suppose we have two instantiations of this class that point to each other. Suppose we nullifying the original reference variables. Then technically our Node objects are referenced by something but that something is inaccessible. These Nodes are on the island of isolation. They are eligible for garbage collection.

Garbage collection is certainly useful as it automates a usually difficult part of software engineering — memory management. However, the programmer loses a degree of control as garbage collection is handled by the JVM. The programmer can call garbage collection using System.gc() but this does not guarantee a garbage collection. For programs where speed is critical and where an intermittent System pause is unacceptable, Java is not the programming language to use.

Closing Note

This is an excellent question that covers the JVM, automatic memory allocation, background processes, and how references and memory objects are managed in Java. Knowing this question can help you answer similar questions about what the JVM does, how variables are stored in memory, and automatic memory management.

In my experience, this is a common question for financial institutions. If you are building tech for a Sales & Trading team looking to execute high-frequency trades with precision, it may be unacceptable to have your code delayed by garbage collection. I’m unsure if this is merely a toy example or if it is applied. But in either case, the background and motivation for this question are certainly relevant.

Check out Part 6 here!

Questions? Comments? Send me an email at andrew.oliver.medium@gmail.com! I’d love to hear from you.