Coding Interviews and Snake (the game) Have This One Thing in Common

If you were born in the 80s, 90s, you’ve probably heard of Snake. And by heard we mean that you’re likely to have spent an insane amount of time on your Nokia 3310, growing a giant stupid snake on your tiny little screen. What’s the other thing you remember about the Nokia phones?

Their ever lasting battery, right?
How did such a ‘primitive’ phone handle its owner spending hours on the Snake game without draining the battery?

Well it’s mostly thanks to great, sturdy components. But also, to a lesser extent, due to something less talked about: the sliding window technique.

As much as we’d love to write a full article on Snake, this post is actually covering the latter, less glamorous, yet very important, sliding window technique, and answers questions like:

• Why do we, and other programmers, consider it a fundamental algorithm?
• Why does it comes up so often in coding interviews?
• How was it used in Snake, or other ‘real life’ applications?
• What are some common coding interview questions that can be answered (better) using the sliding window technique?

Whether you’re prepping for an upcoming interview, reading for fun, or trying to learn something new, keep reading. And please: feel free to jump to the sections you’re most interested in, share your thoughts in the comments , and clap + share if you’ve enjoyed this article.

NB: If you only care about Snake (no worries, we understand), you can scroll down directly to the end of the post.
NB2: if you are prepping for coding interviews, checkout Pramp: free mock interviews, with peers.

Let’s get started.

Despite the complexities of algorithmic programming, there is only a short list of essential principles used to solve problems. One of them is the sliding window technique.

The Windowing Paradigm

The sliding window technique comes from an even more general principle, windowing.

Windowing consists of taking the system state and constraining the view to a part of it, called a window. It creates a separation between the windowing algorithm and the algorithm that would apply to what is visible through the window, simplifying both of them.

A special case occurs when the state is a sequence of objects, e.g. an array or a string. Define a window, and you will see a subsequence. Now you can apply whatever processing there is to this limited range as if there were no other values in the sequence. Limiting the range we have to process makes entire problems smaller. Moving on to the sliding property of the technique: Move the window by one position to the right and it will show another subsequence to which the processing can be applied.

That is where the journey begins. If you apply an algorithm to each window separately, then you would settle down with the brute force tactic.
The beauty of the sliding window technique though is that it helps restructure the algorithm to take advantage of the very process of sliding the window. And all with the goal of constructing better, faster algorithms.

We can improve the running speed of virtually any algorithm applied to a sliding window — at least in theory. When a window slides, only two elements change. The oldest one drops off, and the newest one comes into the frame.

If brute force required k steps to process one window of length k, and there were n windows in the sequence, then it would require n·k steps for the brute force algorithm to complete. But, because only two items change with every move, we can reach an overall running time roughly proportional to 2n.

If we say that only walking through the sequence takes O(n) time, that means that no algorithm can be faster than O(n) on a general sequence. What previous analysis has just discovered is that proper application of the sliding window technique can lead to invention of full-blown sequence processing algorithms which still run in O(n) time.

In other words, the promise is that we can invent perfect algorithms, such that no faster algorithm can be derived for a given problem!

Now that we’ve done with the necessary introduction, we will walk you through three programming problems that can be solved using this general algorithm concept, and give you concrete examples of how it has been used in real world scenarios.

Coding Problem #1: Moving Average

Problem to solve: Create an algorithm that calculates the moving average of a numeric series.

For a given series a0, a1, … an-1 and parameter k, 0 < k <= n, the task is to generate a new sequence such that every element is the average of the k subsequent elements of the original sequence:

Context: The moving average is useful when smoothing out an input data stream. If the numbers are affected by noise, the raw data can be hard to view. Smoothing can help obtain a more informative diagram, as shown in the two diagrams below.

This problem can be solved efficiently using the sliding window technique.
It immediately uncovers a common trait of the majority of such algorithms: The leading k-1 elements produce no output. Only when the entire first window is populated can we pull the first piece of result. All subsequent windows produce one result each. Therefore, the sequence of n elements produces a sequence of n-k+1 results when subjected to a sliding window algorithm.

Now to implementation. Average of a window is the sum of all elements divided by the window length.

When said this way, we can immediately see the advantage of using the sliding window technique. The sum of a window can be calculated from the sum of the window that immediately precedes it:

It will take k steps to compute the sum in the first window, and only two additional operations for every other window.

Below is the C++ implementation of this answer, passing through the leading k elements to produce the first output. All other output numbers are calculated using the optimized summation formula.

double* moving_average(double* data, int n, int k){
   assert(data != NULL);
   assert(n > 0);
   assert(0 < k && k <= n);   double* result = new double[n — k + 1];   double sum = 0;
   for (int i = 0; i < k; i++)
   {
      sum += data[i];
   }
   result[0] = sum / k;   for (int i = k; i < n; i++)
   {
      sum = sum — data[i — k] + data[i];
      result[i — k + 1] = sum / k;
   }   return result;
}

The main point about this algorithm is that every element of the original sequence is processed at most twice, making the overall time complexityO(n).

Coding Problem #2: Maximum Sum Subsequence

Problem to solve: Create an algorithm to find the subsequence with the highest sum among all possible subsequences.

This becomes a real problem when the input data can contain negative values.

Once again, the sliding window technique can be used to come up with a O(n) solution. Only this time, the window length will not be fixed. In fact, as the problem itself is to find the fittest window, the window length will vary along the route.

The idea is to observe what happens when we already have a window, which has a certain sum. Then we wish to include the next coming value. This value could be added to the window’s sum. But it could also be taken as an entire new window of unit length. Now we ask: Which one of these has greater sum? Whichever it is, we keep that one as the new window and move to the next input value repeating the same procedure. You can look at the diagram above, showing how windows are gradually sliding along the sequence.

The winning option is always the maximum sum subsequence ending in the current input element. Every window will be abandoned the first time its sum becomes negative: it’s the situation where one number is better off alone than combined with the entire maximum window preceding it.

The only step remaining now is to determine the overall maximum. All windows are candidates as they slide towards the end of the sequence. Once the sequence has been exhausted, the window with the highest sum seen this far is the overall maximum sum subsequence.

Below is a straightforward C++ implementation. Once again, every element of the sequence is considered at most twice, making the overall time complexity of the functionO(n).

std::tuple<int, int, int> max_sum_subsequence(int* data, int n)
{
   assert(data != NULL);
   assert(n > 0);   int bestStart = 0;
   int bestLength = 1;
   int maxSum = data[0];
     int curStart = bestStart;
   int curLength = bestLength;
   int curSum = maxSum;
     for (int i = 1; i < n; i++)
   {
     if (curSum < 0)
     {
       curStart = i;
       curLength = 1;
       curSum = data[i];
     }
     else
     {
       curLength += 1;
       curSum += data[i];
     }     if (curSum > maxSum)
     {
       bestStart = curStart;
       bestLength = curLength;
       maxSum = curSum;
     }
   }   return std::tuple<int, int, int>(bestStart, bestLength, maxSum);
}

Coding Problem #3: All k-Subsequence Maximums

Problem to solve: Create an algorithm that calculates the maximums of all subsequences of length k in the numeric sequence of length n. Note: this is a tough one.

This algorithm has its use in image processing where, as you may suspect, algorithms that run in O(n) time are valued more than any others.

As the window slides, it produces a maximum contained value on the output. The hard part in solving this problem is that there is no formula which tells the maximum, given a window. We have to pick one of the elements as the result.

That is still not to say that we cannot benefit from the sliding window technique. Here is the idea. Suppose that we have a window with four values, like the one from the image above.

As one additional value comes to the frame we need to understand how it relates to the values already there. For one thing, as the window continues to slide, all previous values will drop out before this new value drops out. That is an important conclusion. If a previous value is smaller than the new value, then it will never become a maximum, simply because the new, larger value will always be there to overshadow it.

This leads to an idea to let every new value invalidate and remove all smaller values it finds present in the window when the window slides, as shown in the picture below. This operation, conversely, has a different consequence.

If every value added to the right of the window removes all smaller values, then the window will only contain a non-increasing, non-contiguous subsequence of the original window. Another consequence which now becomes obvious is that the leftmost element in the window is the maximum value we were supposed to calculate.

There is one more detail to clarify. When the window slides, the leftmost value in the sequence drops off. This value may have already dropped off if it were removed by a larger value. Or it could have survived all its successors on the right. In the latter case, that value from input will be the leftmost value in the frame, and now is the time to remove it.

Picture below demonstrates the entire process applied to a sequence of seven elements, with window length of four.

This completes the description of the algorithm and we can start implementing it. Usual implementation is based on double-ended queue (a.k.a. dequeue). Dequeue supports enqueuing and dequeuing on both ends, and those will be the operations we will use to implement the algorithm.

void insert_maximum_candidate(int value, bounded_deque<int> &maximums)
{
   while (!maximums.empty() && maximums.back() < value)
           maximums.pop_back();
   maximums.push_back(value);}void remove_maximum_candidate(int value, bounded_deque<int> &maximums)
{
   if (!maximums.empty() && maximums.front() == value)
        maximums.pop_front();
}int* range_maximums(int* data, int n, int k)
{
   assert(data != NULL);
   assert(n > 0);
   assert(0 < k && k <= n);   bounded_deque<int> maximums(k);   for (int i = 0; i < k — 1; i++)
        insert_maximum_candidate(data[i], maximums);   int* result = new int[n — k + 1];   for (int i = k — 1; i < n; i++)
   {
        insert_maximum_candidate(data[i], maximums);
        result[i — k + 1] = maximums.front();
        remove_maximum_candidate(data[i — k + 1], maximums);
   }   return result;
}

In this solution, we’re using our own Dequeue implementation, named fixed_deque. Unlike std::deque, this class maintains fixed-size buffer for data, which makes it at least an order of magnitude faster. Internally, it works as a circular buffer, which is extremely efficient. You can download implementation of fixed_deque from the bundle included in this post. Anyhow, fixed_deque class has exactly the same public interface as std::deque (the only difference is that its constructor expects buffer size), and you are free to replace it with std::deque if you like. There will be no other consequences but noticeable drop in running speed.

As in previous examples, we can analyze time complexity of this implementation. Every value from the input sequence is subdued to enqueuing exactly once and to dequeuing at most once. That makes at most two operations per input number, and the overall time complexity of the algorithm is O(n). This algorithm also requires O(k) additional space, where k is the window length. (Note that previous algorithms required only O(1) space.)

You’re prepping for an upcoming interview, and want to get better, fast? Practice coding questions live, with peers, on Pramp.

Thinking Outside the Box

We have seen three different algorithms based on the sliding window technique. Each of them executes in O(n) time just as we promised. Before we split, we wanted to show you how this same technique was applied in two grossly different areas.

First, in packet routing protocols, such as TCP/IP, sliding window was used to reconcile the Internet Protocol (IP) with the overlay Transmission Control Protocol (TCP). IP never guaranteed that packets will be received in the same order in which they were sent. At the same time, TCP adds that very guarantee. That is where the sliding window becomes one of just a few critical enablers for success of the TCP/IP protocol suite.

TCP receiver maintains a window of packets it expects. Packets arrive over a less perfect (but more feasible) IP, and they may arrive out of order to populate their respective positions in the window. However, as soon as the leftmost packet arrives, the TCP window slides as much as it can to the right, acknowledges all contiguous packets to the sender and pushes them to the output. This, in turn, signals the sender to start pushing subsequent packets into the IP network.

You already know what the second (and last) section is about.

It’s about Snake. While the game appeared decades ago, most people know it from Nokia cell phones.

Guess what? The snake itself is the sliding window!
When the snake moves, we only have to draw two blocks on the entire screen — the tail becomes a background block, and the former background in front of the snake becomes the new head.

The result of applying the sliding window technique is that every tick of the game costs us drawing at most two primitive blocks, no matter how long the snake is. It enabled the game to be implemented on primitive hardware without draining the phone’s battery.

Summary

In this article we’ve analyzed a general technique called sliding window. You’ve learned that this technique can be applied to optimize data sequence processing algorithms. When successful, the technique produces algorithms running in O(n) time for a sequence of n objects, which is usually as far as we can go regarding algorithm design.

As concrete problem solving examples, we’ve developed three distinct algorithms that are dealing with numeric sequences. All these algorithms have their respective applications in the real world, in general data processing and image processing. It explains why the sliding window technique has survived to date as a valuable tool in algorithm design, and why you’re likely to hear about it in your coding interviews.

Author: Zoran Horvat — Principal consultant at Coding Helmet Consultancy, speaker and author of 100+ articles and independent trainer.