Classic programming interview questions

Question

I'm going to post some of my solutions to common interview questions. I would love it if you could critique me from a C++ purist's standpoint. Also, tell me if there's a better algorithm for each one of these.

Find the mode (most common element) of an array.

Note: My solution returns an arbitrary mode if there's a tie; assumes the array is non-empty, too

int mode(int* arr, int sz) { 
    std::map<int,int> cntMap;
    int most = arr[0]; 
    for (int i = 0; i < sz; i++) {
       if (!cntMap.count(arr[i])) {
          cntMap[arr[i]] = 0;
       } else {
          cntMap[arr[i]]++;
       }
       if (cntMap[arr[i]] > most) {
          most = cntMap[arr[i]];
       }
    }
    return most;
}

Sum the largest 2 largest elements of an array.

Note: Assumes the array contains at least 2 elements

int largest2(int* arr, int sz) { 
    int largest(arr[0]), secondLargest[arr[0]];
    for (int i = 0; i < sz; i++) { 
       if (arr[i] > largest) {
          secondLargest = largest; 
          largest = arr[i];

       } else if (arr[i] > secondLargest && arr[i] <= largest) { 
          secondLargest = arr[i];
       }
    }
    return (largest + secondLargest);
}

Find whether an array as repeated elements, where it's known that the numbers of the array are between 1 and 100.

bool contains_repeats(int* arr, int sz) { 
    std::vector<bool> booVec(100,false);
    for (int i = 0; i < sz; i++) { 
       if (booVec[arr[i]-1]) { 
           return true; 
       } else { 
           booVec[arr[i]-1] = true;
       }
    }
    return false;
} 

Answer 1

• Is the signature of the function imposed ? Your solution would work for any kind of iterable objects and would be probably more idiomatic than passing a pointer and a size. Also, the logic would work for any (comparable) types and not just int so it might be worth making it a templated function.

• In your search of the most common element, do you want to return the number of occurences or the element itself ?

• In your sum of the two biggest, I think you can compare to largest only once.

You just need to do something like :

   if (arr[i] > secondLargest) {
       if (arr[i] > largest) { 
           secondLargest = largest; 
           largest = arr[i];
       } else {
           secondLargest = arr[i]; 
       }
   }

Answer 2

Your largest2 function has at least 3 errors, one of them will prevent the code from compiling: assignments like secondLargest = largest, comparision arr[i] > secondLargest would not compile because the variable secondLargest is declared as an array:

secondLargest[arr[0]];

The same causes the final addition in

return (largest + secondLargest);

to become a pointer arithmetics, whose result may surprise you when converted to the function's return type (int).

IMHO using parenthesized expression as an initializer for simple arithmetic types is a syntactic overkill compared to the old, good C-style 'equals' form.

When you fix it, either by replacing with secondLargest(arr[0]) or secondLargest=arr[0], the function will produce incorrect result, for example for input array

int testarr[3] = {7, 2, 1};

It is quite obvious the largest term in this three-item array is 7 and the second-largest one is 2, isn't it? But your code will store arr[0], which is 7, both in largest and in secondLargest, so the value 2 will not get into account (it is not greater than 7, stored in secondLargest), and the result will be 14 = 7+7 instead of 9=7+2.

You need to store two terms of the input array in your local variables instead of duplicating the first one. Of course, you need to sort them, so that the initial values of the largest and secondLargest actually are what variables' names say:

    int largest       = max(arr[0], arr[1]),
        secondLargest = min(arr[0], arr[1]);

That, however, does not cure the code yet! The routine still returns 14 for my testarr. The reason is a wrong starting point of your for loop.

Once we store 7 in largest and 2 in secondLargest, you start a loop with i = 0 ...and you compare arr[0] (which is 7) to largest first, then to secondLargest. As a result of those comparisions the apparently 'new' value gets stored as a new second-largest, thus making answer 14=7+7.

The corrected code is:

int largest2(int* arr, int sz) { 
    int largest       = max(arr[0], arr[1]),
        secondLargest = min(arr[0], arr[1]);

    for (int i = 2; i < sz; i++) { 
       if (arr[i] > largest) {
          secondLargest = largest; 
          largest = arr[i];
       }
       else if (arr[i] > secondLargest) { 
          secondLargest = arr[i];
       }
    }
    return (largest + secondLargest);
}

We may also simplify initialization a bit by putting a small value to both local variables - if it only is small enough, it will get overwritten by the actual largest and second-largest term of the array. Such 'small enough' must be smaller than, or at most equal to the smaller of two first terms. Then we can start iteration from index 0 to consider all terms as candidates:

int largest2(int* arr, int sz) { 
    int largest       = min(arr[0], arr[1]),
        secondLargest = largest;

    for (int i = 0; i < sz; i++) { 
       if (arr[i] > largest) {
          secondLargest = largest; 
          largest = arr[i];
       }
       else if (arr[i] > secondLargest) { 
          secondLargest = arr[i];
       }
    }
    return (largest + secondLargest);
}