Saturday, 21 December 2013

Facebook Sample Question and my 20 min Solution in C++


While surfing on the internet and a bit of facebooking I came across facebook's university careers page. At the end of that page I found a link to facebook programming challenge . While reading the guidelines, there was a link to  their sample test. I was not in the mood of taking the actual test but i wanted to try the sample question. So I opened the sample test page and the question was as follows:
  • 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

    Constraints
    3 <= N <= 2500

I have posted almost all of the details of the question . The time to solve this question was 45 minutes. Of course, the question was too easy and the time was actually more than enough to solve this problem. So I succeeded in solving it in approximately 20 minutes and I thought of sharing it on my blog. Obviously , the solution I came up with is a bit naive and I didn't even try to optimize it after all the tests executed successfully.

 I chose C++ as programming language whereas the choices were C , C++ , Java , PHP , Python, C# , Javascript , Ruby, Perl, Haskell, Scala, Clojure Except last 4 languages I have a hands on experience in all of the others but in such time ( thinking of the actual test )  we have to make a quick decision and C++ seemed like a better option to me . So the final code was as follows:


#include <iostream>
using namespace std;
int main() {
    int num ;
    cin >> num ;
    int * diff_array = new int [num-1];
    int * nums_array = new int [num];
    for ( int i = 0 ; i < num ; ++i )
    {
        cin >> nums_array[i] ;
    }
    for ( int i = 0 ; i < num - 1 ; ++i )
    {
        diff_array[i] = nums_array[i+1] - nums_array[i];
    }
    int diff_index = -1 ;
    int first = diff_array[0] , second = diff_array[1];
    for ( int i = 2 ; i < num - 1 ; ++i )
    {
        if ( first == second )
        {
            if ( first != diff_array[i] )
            {   
                diff_index = i ;
                break;
            }
        }
        else if ( first != diff_array[i] )
        {
            diff_index = i - 2 ;
            break;
        }
        else
        {
            diff_index = i - 1;
            break;
        }
        first = second;
        second = diff_array[i];           
    }
    // found difference
    cout << nums_array[diff_index] + diff_array[diff_index ? 0 : 1]  ;
  
    return 0;
}