C++ Interview Questions
Filed in: C++
Given my 30 or so years experience in investment banking here is a list of C++ Interview questions that I have been asked. All the code complies with C++11 unless there are comments specifying C++17 functionality,
Please note just because you know the std library it does not mean clients will not ask you to implement something from the std library just to see your algorithm knowledge. For example: sorting and Binary Search algorithms.
Q: Implement a Binary search algorithm - without using the std library.
//*********************************** Binary Search
template <typename T>
/*
Recursive call splitting by half every time till we find the item or not
return item or T if we found item - std::nullopt from Optional if not found.
*/
//Optional is C++17 specific
std::optional splitlist(size_t start, size_t end,const int v, const std::vector array){
//midpoint
size_t mid=(end-start)/2 + start;
if(array[mid]==v){
return array[mid];//true;
}
//if only 1 element left and its not the one its not in list
if(end-start == 1 ){
return std::nullopt;//false;
}
//is it in left or right half
if( v < array[mid]){
return splitlist( start, mid, v, array);
}else{
return splitlist(mid, end, v, array);
}
}
template <typename T>
std::optional binary_search( const std::vector &array, const T v){
int start=0;
//int end=length;
size_t end=array.size();
return splitlist(start, end, v, array);
}
template <typename T>
void testBinarySearch(){
constexpr int size=200;
//T array[size];
std::vector array(size);
ptional found;
found=binary_search( array, 170);
assert(found.has_value());
found=binary_search( array, 999);
assert(!found.has_value());
}
Binary search is one of the easier algorithms. You need to use a sorted list and then you can take advantage of the sorted idea by seeing if the item is in the top half or bottom half of the list - Then you search that list by calling the recursive splitList function this goes on until we have nothing left to split or we found the item. This is also a good question to demonstrate the idea of recursion.
Follow up question what is tail recursion ?
Tail recursion is when the last item returned is the recursive call itself not the call + some value or some value + recursive call. The idea behind tail recursion is it can be optimised to a loop by the compiler and therefore does not deeply use the stack so there is little chance of running out of stack space.
Q: Write a simple bubble Sort algorithm
//Complexity is between O(n*n) and O(n^2)
//Does more swapping than Selection but is more stable
//Not allowed to use std::sort(std::begin(array), std::end(array));
void bubbleSort(int length, int array[length])
{
for (int i = 0; i < length; i++)
{
for (int j = i; j > 0; j--)
{
if (array[j-1] > array[j])
{
int x=array[j];
array[j]=array[j-1];
array[j-1]=x;
}
else break;
}
}
}
void testBubbleSort(){
constexpr int size=5;
int array[size] = { 30, 20, 10, 40, 5 };
bubbleSort(size, array);
assert(array[0]==5);
assert(array[4]==40);
for(int i=0; i
}
std::cout << '\n';
}
Q: Write a a Selection Sort algorithm
//Complexity O(n^2)
//Not allowed to use std library std::sort(std::begin(array), std::end(array));
void selectionSort(int length, int array[length]){
//Sort array in place
for( int i=0; i1; ++i){
int smallestIndex=i;
for( int j=i+1; j
smallestIndex=j;
}
//swap them
int tmp=array[smallestIndex];
array[smallestIndex]=array[i];
array[i]=tmp;
}
}
void testSelectionSort(){
constexpr int size=5;
int array[size] = { 30, 20, 10, 40, 5 };
selectionSort(size, array);
assert(array[0]==5);
assert(array[4]==40);
for(int i=0; i
}
std::cout << '\n';
}
Q: Write some code to test if a given number is Prime or not
bool isPrime(int x){
if(x<=0||x==1) return false;
for(int i=2; i<=x/2; i++){
if( (x % i) ==0 ){
return false;
}
}
return true;
}
void testPrime(){
int prime[] = {2,3,5,7,11,13,17,19};
for(int i=-10; i<20; i++){
std::string z=isPrime(i)?"Prime":"-" ;
int *arrPtr = std::find(std::begin(prime), std::end(prime), i);
// When the element is not found, std::find returns the end of the range
if (arrPtr != std::end(prime)) {
assert(z=="Prime");
} else {
assert(z=="-");
}
//if is in list of Primes - assert Prime
//else assert -
std::cout << i << " is " << z << '\n';
}
}
Q: Generate a set of Random numbers using the Mersenne Twister algorithm from the std library. This question is generally used if you are working as a quant
#include
#include
namespace MyRandom
{
// Initialize our mersenne twister with a random seed based on the clock (once at system startup)
std::mt19937 mersenne{ static_cast<std::mt19937::result_type>(std::time(nullptr)) };
}
int getRandomNumber(int min, int max)
{
std::uniform_int_distribution range{ min, max }; // we can create a distribution in any function that needs it
return range(MyRandom::mersenne); // and then generate a random number from our global generator
}
/*
Overloaded method to support real distributions float, double, long double
*/
double getRandomNumber(double min, double max)
{
std::uniform_real_distribution range( min, max);
return range(MyRandom::mersenne);
}
void testMersenne()
{
std::cout << getRandomNumber(1, 6) << '\n';
std::cout << getRandomNumber(1, 10) << '\n';
std::cout << getRandomNumber(1, 20) << '\n';
std::cout << getRandomNumber(0.0, 1.0) << '\n';
}
C++ Asynch future promise package_task and shared_future
Blocking Queue in C++ using condition variable
Creating C++ threads
Low Latency Java using CAS and LongAdder
Naive Bayes classification AI algorithm
K-Means Clustering AI algorithm
Equity Derivatives tutorial
Fixed Income tutorial
Java
python
Scala
Investment Banking tutorials
HOME
Please note just because you know the std library it does not mean clients will not ask you to implement something from the std library just to see your algorithm knowledge. For example: sorting and Binary Search algorithms.
Q: Implement a Binary search algorithm - without using the std library.
//*********************************** Binary Search
template <typename T>
/*
Recursive call splitting by half every time till we find the item or not
return item or T if we found item - std::nullopt from Optional if not found.
*/
//Optional is C++17 specific
std::optional
size_t mid=(end-start)/2 + start;
if(array[mid]==v){
return array[mid];//true;
}
//if only 1 element left and its not the one its not in list
if(end-start == 1 ){
return std::nullopt;//false;
}
//is it in left or right half
if( v < array[mid]){
return splitlist( start, mid, v, array);
}else{
return splitlist(mid, end, v, array);
}
}
template <typename T>
std::optional
int start=0;
//int end=length;
size_t end=array.size();
return splitlist(start, end, v, array);
}
template <typename T>
void testBinarySearch(){
constexpr int size=200;
//T array[size];
std::vector
found=binary_search
assert(found.has_value());
found=binary_search
assert(!found.has_value());
}
Binary search is one of the easier algorithms. You need to use a sorted list and then you can take advantage of the sorted idea by seeing if the item is in the top half or bottom half of the list - Then you search that list by calling the recursive splitList function this goes on until we have nothing left to split or we found the item. This is also a good question to demonstrate the idea of recursion.
Follow up question what is tail recursion ?
Tail recursion is when the last item returned is the recursive call itself not the call + some value or some value + recursive call. The idea behind tail recursion is it can be optimised to a loop by the compiler and therefore does not deeply use the stack so there is little chance of running out of stack space.
Q: Write a simple bubble Sort algorithm
//************************************ Bubble Sort
//Complexity is between O(n*n) and O(n^2)
//Does more swapping than Selection but is more stable
//Not allowed to use std::sort(std::begin(array), std::end(array));
void bubbleSort(int length, int array[length])
{
for (int i = 0; i < length; i++)
{
for (int j = i; j > 0; j--)
{
if (array[j-1] > array[j])
{
int x=array[j];
array[j]=array[j-1];
array[j-1]=x;
}
else break;
}
}
}
void testBubbleSort(){
constexpr int size=5;
int array[size] = { 30, 20, 10, 40, 5 };
bubbleSort(size, array);
assert(array[0]==5);
assert(array[4]==40);
for(int i=0; i
}
std::cout << '\n';
}
Q: Write a a Selection Sort algorithm
//************************************ Selection Sort an Array
//Complexity O(n^2)
//Not allowed to use std library std::sort(std::begin(array), std::end(array));
void selectionSort(int length, int array[length]){
//Sort array in place
for( int i=0; i
int smallestIndex=i;
for( int j=i+1; j
smallestIndex=j;
}
//swap them
int tmp=array[smallestIndex];
array[smallestIndex]=array[i];
array[i]=tmp;
}
}
void testSelectionSort(){
constexpr int size=5;
int array[size] = { 30, 20, 10, 40, 5 };
selectionSort(size, array);
assert(array[0]==5);
assert(array[4]==40);
for(int i=0; i
}
std::cout << '\n';
}
Q: Write some code to test if a given number is Prime or not
// **********************************************PRIME
bool isPrime(int x){
if(x<=0||x==1) return false;
for(int i=2; i<=x/2; i++){
if( (x % i) ==0 ){
return false;
}
}
return true;
}
void testPrime(){
int prime[] = {2,3,5,7,11,13,17,19};
for(int i=-10; i<20; i++){
std::string z=isPrime(i)?"Prime":"-" ;
int *arrPtr = std::find(std::begin(prime), std::end(prime), i);
// When the element is not found, std::find returns the end of the range
if (arrPtr != std::end(prime)) {
assert(z=="Prime");
} else {
assert(z=="-");
}
//if is in list of Primes - assert Prime
//else assert -
std::cout << i << " is " << z << '\n';
}
}
Q: Generate a set of Random numbers using the Mersenne Twister algorithm from the std library. This question is generally used if you are working as a quant
//*************************************** RANDOM - Mersenne
#include
#include
namespace MyRandom
{
// Initialize our mersenne twister with a random seed based on the clock (once at system startup)
std::mt19937 mersenne{ static_cast<std::mt19937::result_type>(std::time(nullptr)) };
}
int getRandomNumber(int min, int max)
{
std::uniform_int_distribution range{ min, max }; // we can create a distribution in any function that needs it
return range(MyRandom::mersenne); // and then generate a random number from our global generator
}
/*
Overloaded method to support real distributions float, double, long double
*/
double getRandomNumber(double min, double max)
{
std::uniform_real_distribution range( min, max);
return range(MyRandom::mersenne);
}
void testMersenne()
{
std::cout << getRandomNumber(1, 6) << '\n';
std::cout << getRandomNumber(1, 10) << '\n';
std::cout << getRandomNumber(1, 20) << '\n';
std::cout << getRandomNumber(0.0, 1.0) << '\n';
}
People who enjoyed this article also enjoyed the following:
C++ Asynch future promise package_task and shared_future
Blocking Queue in C++ using condition variable
Creating C++ threads
Low Latency Java using CAS and LongAdder
Naive Bayes classification AI algorithm
K-Means Clustering AI algorithm
Equity Derivatives tutorial
Fixed Income tutorial
And the following Trails:
C++Java
python
Scala
Investment Banking tutorials
HOME