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;
}