Let’s face a Facebook Programming Challenge together: finding the missing term in an arithmetic progression

Facebook Programming Challenges are a great way to challenge yourself in a demanding, timed programming task. FPCs usually last between 45-60 min. and ask you to solve a given problem, stated in the description, picking the programming language you feel most comfortable with (i.e. PHP, Java, Python, C, C++, C# and others).

You can write, compile and run your program directly in the editor in the browser, though you’ll probably miss all the features and comfort of your IDE, which you can use anyway if you prefer, as long as you eventually paste, run and test your code in the online editor.

The solution you provide must satisfy a small set of rules, in order for the remote compiler to “understand” your code and must pass a provided set of test cases, otherwise it won’t be considered correct.

Facebook Programming Challenge

Are you ready to get in the game?

“Why should I try to solve a FPC?”

Well, do you still remember all the times you dreamed of getting the job of your life at a top IT company? Right, Facebook Programming Challenges are intended as a means to find top-notch developers from all around the globe. Once you successfully complete a Challenge, you’re highly likely to be contacted by Facebook’s HR department to schedule a phone interview session. If you perform well on both 45-minutes technical tests, well, you’re in!

A sample Facebook Programming Challenge

Before you dive right into a real Facebook Programming Challenge, you should know that Facebook gives you the opportunity to get acquainted with the process by a sample Challenge. In the past, they proposed a different Challenge from the one I’ll discuss here, so it is reasonable to think they change them periodically; in order to avoid losing references to our today’s Challenge, I’ll rewrite the description, then I’ll discuss the approach I took to solve it.

Challenge description

Task: 
Find the missing term in an Arithmetic Progression. An Arithmetic Progression is defined as one in which there is a constant difference between the consecutive terms of a given series of numbers. You are provided with consecutive elements of an Arithmetic Progression. There is however one hitch: exactly one term from the original series is missing from the set of numbers which have been given to you. The rest of the given series is the same as the original AP. Find the missing term.

Input Format:
The first line contains an Integer N, which is the number of terms which will be provided as input. This is followed by N consecutive Integers, with a space between each pair of integers. All of these are on one line, and they are in AP (other than the point where an integer is missing).

Output Format:
One Number which is the missing integer from the series.

Sample Input:
5
1 3 5 9 11

Sample Output:
7

Explanation:
You are provided with 5 integers. As you can can observe, they have been picked from a series, in which the starting term is 1 and the common difference is 2. The only aberration, i.e. the missing term (7), occurs between 5 and 9. This is the missing element which you need to find.

Constraints:
3 <= N <= 2500
All integers in the series will lie in the range [-10^6,+10^6].

So, pretty straight, uh? We’re given an arithmetic progression (increasing or decreasing) of arbitrary (positive and/or negative) numbers in the interval [-1 million, +1 million] and we’re asked to find the single missing number in the progression. For example, the missing element in the progression 1, 3, 7, 9 is of course 5. Our program must be capable of giving such a response.

Since there must be a constant difference between consecutive terms (see the problem description above) and since the minimum size for our progressions is 3, we understand easily that this difference can’t be zero, because otherwise we’d have progressions with a single element repeating over and over again (e.g. 3, 3, 3, 3). But in this case we would have no element to find. So, we can legitimately exclude pathological cases of progressions where at least two consecutive numbers are equal, by imposing that couples of any consecutive numbers must contain non-equal values. From this, we can naturally deduce we’ll deal only with monotonic progressions; that’s to say, pure always-increasing or always-decreasing progressions, in which any element is strictly greater than or less than the element following.

Finding the minimal step (or difference)

As said, we have a constraint on the progression: its size must be at least of 3 and at most of 2500 elements. So, our simplest progression (from now on: series, in the most general sense of the term: a series of values, not a sum) will contain exactly 3 elements and, since we know that the distance between any two consecutive numbers must be always the same and this can’t trivially be zero, we must find the series’ step (or difference) and verify it’s the same between any two consecutive numbers. This will be our general strategy, yet there are some cases which need special meditation. For now, let’s start thinking of some sample series for N = 3.

1) 11, 21, 41
2) 31, 21, 1

The missing element is obviously 31 for series 1) and 11 for series 2).

How do we find the step? If the series is (monotonically) increasing like the series 1), we take the second element (which we’re sure it’s there, since we have at least 3 elements in any series) and subtract the first element from it. Viceversa, if the series is (monotonically) decreasing as in case 2), we take the first element and subtract the second element from it. At this point, an alarm should be sounding desperately. Look at this series:

3) 1, 21, 31

One can easily see that the step here is obviously 10 and the missing element is 11, yet the approach to find the step we described just above is going to fail miserably: our algorithm will think that the step is  21 – 1 = 20. Ops. How do we deal with this? Simple: we improve our strategy of finding the step by not just finding the step we claim to be the real step, but instead finding a left step (the difference between the first two elements in the series) and a right step (the difference between the last two elements in the series). The minimum between these two “proto”-steps will be our final minimal step. Why the minimum? Because our goal is somewhat like filling an hole, so we expect to find a bigger hole than others at some point, which can’t be the real step value, because we must fill it and split it in two; moreover, since there’s exactly one missing number, we can be sure that the bigger hole is the only one to be filled, so there’s no need to scan the entire series for even bigger holes. Note that, in the case of arbitrary series of size N, we expect this bigger hole to be inside – rather than on the edge of – the series, so taking the minimum between the left step and the right step would simply mean picking the minimum between two exactly equal values, which will be both the real step value we need. Let’s try this strategy in practice on series 3) and all will be clear:

leftStep = 21 - 1 = 20
rightStep = 31 - 21 = 10
minimumStep = min(leftStep, rightStep) = 10

So, in O(2) = O(1) we have found the minimal step, without scanning the entire series. A similar reasoning applies in the case of descending series. At this point, half of the work is already done.

Finding the missing number

Now that we’ve found the minimal step, we can scan the series until we find the “big hole”: when we do find it, we make sure that the value on the left of the hole plus the step is equal to the value on the right of the hole minus the step and then conclude that the missing number is equal to the value on the left of the hole (or on the right) plus the step (or minus the step). That’s it.

In the worst case, this stage has a complexity of O(N), N being the size of the series, so the whole algorithm will be an O(1) + O(N) = O(N).

Source Code

The image below shows a sample output. Click on it to view and download the entire source code from my GitHub page. In the source code I used a slightly different idea of step: I’ve meant it not like the difference between two consecutive numbers, but like the elements that would fit between two consecutive numbers, so that the step between 2 and 10 wouldn’t be 10 – 2 = 8, but 7, because 7 elements would fit between 2 and 10. I’ve been talking about differences merely because it is a more manageable idea, but in practice I’ve found more comfortable working the way I’ve mentioned.

I decided not to cover the cases when the elements in the series are all negative or both negative and positive, but all these cases have been thoroughly tested and showed to work perfectly. Also note that the version hosted on GitHub is a more refined one with respect to the one submitted in the Challenge, because the Challenge needed no input by the user and required no other messages printed on the screen except the missing element. I felt I had to improve that code furthermore and I did.

The code differentiates between increasing series and decreasing series. I didn’t manage to unify the two cases into a general case because, as far as I know, combinations intersects in ways that apparently can’t be unified. Should someone manage to do this, I welcome him or her to let me know in the comments.

Arithmetic Progression

Testing

The code passed the sample test case listed in the problem description and the other hidden (who knows why) six, by first clicking on the Compile and Test button and then on the Test against all testcases button, and the image below proves this:

Test cases passed

What should have you learnt so far?

When dealing with potentially large collections of objects, it is always a good idea to start rebuilding the problem on the smallest collection ever. In our case, it was of size 3. What should happen when we have a series of only 3 numbers? The missing number could be fitting in only 2 positions (between the first and the second elements or between the second and the third elements). How do we find it? First, we need to find the step, because we know it is fixed, so once we’ve found it we can split the big hole in two and add the step value to the element on the left of the edge… and so on, until we build a strong (in the sense that it respects all the constraints and never fails) algorithm that works perfectly on the all the possible minimal structures. As our algorithm gets stronger and stronger, we can think of what happens if we start to consider larger series: new special cases arise? Does our initial algorithm fail onto these? If no, we can explore new cases further, otherwise we think at how could our algorithm respect them. For example: at a certain point, we’ve found that our algorithm wouldn’t have worked properly in finding the step on certain conditions (namely when the missing element was between the first two or the last two elements). We have thought at how to solve this issue and verified than even for bigger series it would have been possible to find the right step. While the structures get bigger and bigger, at a certain point we can think if we can reasonably abstract the dimension to an arbitrary one and move to edge cases: if our algorithm works on structure of dimension 7, most probably it will work on structures of dimension 8, 9 and 10 and so on. Will it be the case to test even for 11 and 12? Probably not. Probably will make much more sense to test the algorithm for structures of dimension 2499 and 2500 (maybe building such structures programmatically…) – which, I confess, I didn’t.

Another great tip I can give is to write down our thoughts on paper and work heavily on it. Only once things start to become clearer we can write down something on the keyboard, but pens and papers must be a programmer’s best friends. Note that in this article I’ve never mentioned words like Java, array, index. That’s because they refer to the implementation, not the design of a problem’s solution, which completely ignores these concepts. Spend 60-70% of the time working on paper and the remaining 40-30% working on the keyboard and you’ll never regret this. My professor was right, I can tell you this.

Final considerations

So why did I wrote this article, after all? Facebook Programming Challenges, like any other challengesare a great way to test your programming skills in relation to the capabilities hirers want you to have. If, at any point, you feel like lost in the sea (or – better – universe!) of concepts, algorithms, data structures, indices, loops and so on, maybe you should pick up some algorithms and data structures and/or programming books, in order to sharpen those skills the software industry needs you to have.

As a bottom line, I personally think that facing these challenges on a regular basis keeps you mind fresh, opened, reactive to problems in general. Of course you don’t need to stay in line with the industry if your dream job is to become a front-end developer (I myself am currently examining this field more in depth) but, even in that case, I would suggest to stay in shape with such exercises. I certainly will.

Advertisements