Here is my answer. I try to be as verbose as possible with all my assumptions because I hear the interviewers want to hear the way you think.
There are just a handful of comparisons that need to take place for each element so it it would be O(n) linear time in execution.
I did use 2 integer variables to store the highest and second highest. Since no magic value was defined for an integer that could never appear in the list, I also needed 2 flags to tell me if each storage integer had been pulled out of the list or was still the initial value.
If I needed the nth highest, I would need to come up with another solution. I would probably opt to sort the array unless n was very small relative to the list size.
My code will handle the case where there are duplicate integers. I also assumed you could have negative integers in the array. It also has some error handling built in and handles the error with a printf.
I chose C++ because I'm most comfortable with it and the ability to declare variables whenever you want. I could have easily made this a standard C program.
#include "stdlib.h"
#include "stdio.h"
#include
#define SIZE_OF_ARRAY 11
int array[SIZE_OF_ARRAY] = {-1, 0, 200003, 9, 2, 3, 4, 5, 6, 7, 8};
int main()
{
int highest = 0;
int _2nd = 0;
bool highest_set= false;
bool _2nd_set= false;
for(int i = 0; i highest)
{
//we have a new highest!
//if 2nd highest hasn't been set yet, put highest there
if(_2nd_set == false)
{
_2nd_set = true;
_2nd = highest;
}
//or if 2nd highest has been set, compare it to see if it
//highest is greater or equal. set it if it is.
else if(highest >= _2nd)
{
_2nd = highest;
}
else
{
printf("Error: somehow highest got to be greater than 2nd highest\n");
}
//set highest to the array value.
highest = array[i];
}
else if (_2nd_set == false)
{
//2nd hasn't been set yet so set it.
_2nd = array[i];
_2nd_set = true;
}
else if(array[i] > _2nd)
{
//a higher 2nd.
_2nd = array[i];
}
else
{
//nothing to do array[i] is less than both highest and 2nd and
//both have been set already.
}
}
}
printf("The 2nd Highest is %d\n", _2nd);
//cout << "then" << endl;
return 0;
}