Imagine you’re sitting by the window, coding. Suddenly, your attention is drawn to a little girl outside, playing hopscotch. She carefully jumps across the drawn tiles—sometimes skipping one and sometimes making a big leap over two. For a moment, you get distracted and pause your work.
At that moment, your logical mind becomes curious: If the hopscotch tiles are lined up in a row and the girl only jumps one or two steps, how many different ways are there to reach the last tile?
Combinatorics Solution
Someone asked me this question in an algorithmic interview, and the first solution that came to mind was using combinatorics. First, we need to determine how many single jumps and how many double jumps are required to reach the last square.
For example, if there are four squares, there are three different ways to reach the end:
- Four single jumps
- Two single jumps and one double jump
- Two consecutive double jumps
Then I realized that the order of jumps also affects the total number of possibilities. A formula from combinatorics came to mind which could be used to calculate the number of possible arrangements:
Total arrangements = Factorial of total jumps divided by the factorial of repeated jumps
Finally, I computed the total number of possibilities for all possible ways. At first glance, the code I wrote seemed to have a time complexity of O(N²) due to two loops, but since these loops were independent of each other, the actual complexity was O(N).
Recursion Solution
After solving the problem, I analyzed the results and noticed a pattern: The solution for a given number of squares was equal to the sum of the solutions for the previous two numbers. That rings a bell, The famous Fibonacci sequence! So, I decided to use this approach to solve the problem:
Memoized Recursion Solution
When testing my code, I realized that, for large inputs, my implementation was extremely slow. I knew that the time complexity of the Fibonacci function is O(2ⁿ). The first improvement that came to mind was using memoization: defining a cache to store function inputs and outputs. If the function was called with the same input, instead of calculating the result, get the output directly from the cache.
This code was faster than the combinatorics solution for small inputs, but for large inputs, such as calculating the solution for 30 hopscotch tiles, it was much slower. Also, for inputs greater than 1000, I ran into a RecursionError.
For Loop Solution
It was obvious that, to determine the solution for any given input, I only needed the previous two results. This meant that I could solve the problem with a simple loop.
This simple loop was able to outperform the combinatorics solution across all inputs by a constant factor. Additionally, its time complexity was O(N), and its space complexity was O(1).
Memoized Combinatorics Solution
At this point, I was wondering why the combinatorics approach was slower. After a bit of research, I found that in Python, factorial calculations are performed using a for loop, meaning that what I initially thought was O(N) was actually O(N²). I also noticed that many factorials were being recalculated unnecessarily, so I considered memoizing them.
Surprisingly, this did not improve performance. In fact, it made the algorithm slower due to the increased space complexity. At this point, I stopped optimizing further and submitted the simple loop solution as my final answer.
Results
What do you think? If you were asked this question, how would you approach it? Do you think this algorithm can be optimized further? Let me know in the comments!
P.S. 1: I used the richbench library to test the speed of the algorithms. These are the specifications of the hardware I was testing on:
CPU: 11th Gen Intel i5-11400H
Memory: 15694 MiB
GPU: Intel TigerLake-H GT1 [UHD Graphics]
OS: Zorin OS 17.2 x86_64
PYTHON_VERSION: 3.12.7
P.S. 2: In Python, @functools.cache is typically used for memoization, but in an algorithmic interview, you should implement it yourself.
Top comments (0)