C++ quant interview questions

[sagredo]

During my interview process, I often get asked to solve a couple of problems and submit the code, and I just thought that I would share a couple here with the group to help them along:

- write a class, in an OO programming language, which performs arithmetic operations between arbitrarily large numbers.
- with an integer represented as a string, write a function that represents this number with the thousands separated by commas.

I have been asked variants of these two questions on most of my developer interviews, so those of you pursuing the developer route would probably do well to study these questions as a test of your C++ or other object oriented programming capability. I'd be interested to see how others approach the problem.

 

[Mr Doe]

I have a solution for the second problem. Take it, from someone who is self-thought in C++.

#include<string>
#include<iostream>

using namespace std;

string sep_digit_by_comma( string s ){
    string temp;
    int num= ( s.size()%3 ) ? ( s.size()/3 ) : ( s.size()/3 - 1 );
    for( int i=0, j=0; i<=num; ++i ){
        for( ; j<s.size()-3*(num-i); ++j ){
            temp+=s.substr(j,1);
        }
        if( j!=s.size() )
            temp+=",";
    }
    return temp;
}

void main(){
    string s;
    cin >> s;
    cout << sep_digit_by_comma(s) << endl;
}

I am not skilled enough to answer the first question. I'm anxious to hear what is the point with this questions (that is, what do they test with this questions, and what do they expect to hear as an answer).

 

[wildcolor]

for the 1st question, I think the clue is to use several 32bit integers to construct a larger integer. Then write the algorithm for + - x / operations

I have a solution for the second problem. Take it, from someone who is self-thought in C++.

#include<string>
#include<iostream>

using namespace std;

string sep_digit_by_comma( string s ){
    string temp;
    int num= ( s.size()%3 ) ? ( s.size()/3 ) : ( s.size()/3 - 1 );
    for( int i=0, j=0; i<=num; ++i ){
        for( ; j<s.size()-3*(num-i); ++j ){
            temp+=s.substr(j,1);
        }
        if( j!=s.size() )
            temp+=",";
    }
    return temp;
}

void main(){
    string s;
    cin >> s;
    cout << sep_digit_by_comma(s) << endl;
}

I am not skilled enough to answer the first question. I'm anxious to hear what is the point with this questions (that is, what do they test with this questions, and what do they expect to hear as an answer).

 

[APalley]

for the 1st question, I think the clue is to use several 32bit integers to construct a larger integer. Then write the algorithm for + - x / operations

That's on the right track. However, we need it to be 'arbitrarily large' -- we need some type of expandable container. The best way would be to create an object, with the different operations using operator overloading. That way it will actually operate as an int.

 

[Steven Sun]

That's on the right track. However, we need it to be 'arbitrarily large' -- we need some type of expandable container. The best way would be to create an object, with the different operations using operator overloading. That way it will actually operate as an int.

to be arbitrarily large... I guess need a string to hold the value then truncate and parse it piece by piece....

 

[APalley]

to be arbitrarily large... I guess need a string to hold the value then truncate and parse it piece by piece....

That would work.

I think something like this:

class BigInt {
public:
BigInt() { ints = new int[0]; }
~BigInt() { delete [] ints; }
BigInt & operator=(const BigInt &rhs);
BigInt & operator+(const BigInt &rhs);
BigInt & operator-(const BigInt &rhs);
BigInt & operator*(const BigInt &rhs);
BigInt & operator/(const BigInt &rhs);
private:
int *ints;
};

etc ... The operators will make the ints array larger as needed -- meaning when one int becomes full, add another to the array. A stack may be a better data type than an array for this. Then define the operations -- Like you said the operations will use strings and will have to be parsed. If you want it to be a signed int, things can get a little more complicated. One can use a long data type as well in the object.

Then the object can be used just like a regulat int. for example:

BigInt number;
number = 9999999999999999999999999999999;
number += 2;

etc....

 

[owinebar]

- write a class, in an OO programming language, which performs arithmetic operations between arbitrarily large numbers.

That's a loaded question. There are a lot of sophisticated algorithms for performing arithmetic operations on arbitrarily large integers. If you don't care about performance you can use elementary school algorithms.

Implementing Karatsuba multiplication might be easier if you explicitly represent the integers as trees. Another potentially fun approach would be to defer actually performing the operations and build expression trees to represent the integers until some event requires a final result. For large enough integers it might pay to implement an optimizing compiler of the expression tree.

Of course IRL the best solution is likely to be just using an existing free implementation. I doubt they want to hear about these other approaches except to briefly note that elementary school algorithms are not the most efficient known.

 

[Lecter]

This is the legendary first "Divide and Conquer" algorithm, for anybody who did basic algorithmics, this is the first of the recursive kind of algorithms.

Do they ask anything about dynamic programming, simulations (variance reduction techniques), mathematical programming,...?

I have to say I feel a bit rusty in my basic algorithmics barely saw the divide and conquer in that problem, remembers me than while is equivalent to goto and also to recursion.
Also that recursion equations are a form of discrete differential equations.

I would had done recursions for those, last time I had a QMC brownian bridge, did it that way, lazziness is a quality for programmers.

 

[Christophe]

It seems like many assume that large numbers are integers. When I read arbitrarily large numbers, I read operations between int, double, floats... which I think one should make sure that the result of the operation is not truncated to the shortest type. I would probably go for a template class in C++.

 

[yankeson]

I have one solution to the question 1, but it's only for "+" and unsigned integer. For other cases, it's much more complicated.

 

[RKG]

I have an answer for 2:
#include <string>
#include <deque>
#include<iostream>
using namespace std;
string fn(string s) {
string temp("");
deque<string> temp1;
int len = s.size();
string::const_iterator j;
j = s.end();
j--;
int k = 0;
for (string::const_iterator i = j; i != s.begin(); i--) {
k++;
string ss(1,*i);
temp1.push_front(ss);
if (k % 3 == 0) { temp1.push_front(","); }
}
k++;
if (k % 3 == 0) {
temp1.push_front(",");
}
string ss(1, *s.begin());
temp1.push_front(ss);
for (std::deque<string>::const_iterator j = temp1.begin(); j != temp1.end(); ++j) {
temp.append(*j);
}
return temp;
}
void main() {
cout << fn("10000") << endl;
getchar();
}

 

[Daniel Duffy]

You can use the include code option.

BTW using namespace std; etc. is not good practice in general.
Indented code promotes readability.

#include <string>
#include <deque>
#include<iostream>
using namespace std;
string fn(string s) {
string temp("");
deque<string> temp1;
int len = s.size();
string::const_iterator j;
j = s.end();
j--;
int k = 0;
for (string::const_iterator i = j; i != s.begin(); i--) {
k++;
string ss(1,*i);
temp1.push_front(ss);
if (k % 3 == 0) { temp1.push_front(","); }
}
k++;
if (k % 3 == 0) {
temp1.push_front(",");
}
string ss(1, *s.begin());
temp1.push_front(ss);
for (std::deque<string>::const_iterator j = temp1.begin(); j != temp1.end(); ++j) {
temp.append(*j);
}
return temp;
}
void main() {
cout << fn("10000") << endl;
getchar();
}

 

[RKG]

You can use the include code option.

BTW using namespace std; etc. is not good practice in general.
Indented code promotes readability.

#include <string>
#include <deque>
#include<iostream>
using namespace std;
string fn(string s) {
string temp("");
deque<string> temp1;
int len = s.size();
string::const_iterator j;
j = s.end();
j--;
int k = 0;
for (string::const_iterator i = j; i != s.begin(); i--) {
k++;
string ss(1,*i);
temp1.push_front(ss);
if (k % 3 == 0) { temp1.push_front(","); }
}
k++;
if (k % 3 == 0) {
temp1.push_front(",");
}
string ss(1, *s.begin());
temp1.push_front(ss);
for (std::deque<string>::const_iterator j = temp1.begin(); j != temp1.end(); ++j) {
temp.append(*j);
}
return temp;
}
void main() {
cout << fn("10000") << endl;
getchar();
}

My bad! Copied and pasted it directly and lost the indentation.

 

[Daniel Duffy]

I took the liberty to clean + standardize this (undocumented) code (I ran it and discovered it is pattern matching).

It should be possible to do the same more compactly using STL modifying algorithms (few lines of code). That be a good exercise!

In general, we should avoid reinvention of the wheel.

//DD
#include <string>
#include <deque>
#include <iostream>

std::string fn(std::string s)
{ // What does this long function do?

    std::string temp("");
    std::deque<std::string> temp1;

    auto len = s.size();
    auto j = s.end();
    j--;
    int k = 0;
    for (auto i = j; i != s.begin(); i--)
    {
        k++;
        std::string ss(1, *i);
        temp1.push_front(ss);
        if (k % 3 == 0) { temp1.push_front(","); }
    }
    k++;
    if (k % 3 == 0)
    {
        temp1.push_front(",");
    }
    std::string ss(1, *s.begin());
    temp1.push_front(ss);
    for (auto j = temp1.begin(); j != temp1.end(); ++j)
    {
        temp.append(*j);
    }
    return temp;
}

int main()
{
// CRASH    std::cout << fn("") << '\n';
//    std::cout << fn(" ") << '\n';
    std::cout << fn(" \n \t ") << '\n';
    std::cout << fn("1") << '\n';
    std::cout << fn("10") << '\n';
    std::cout << fn("01") << '\n';
    std::cout << fn("1000") << '\n';
    std::cout << fn("10000") << '\n';
    std::cout << fn("100000") << '\n';
    std::cout << fn("1000000") << '\n';
    std::cout << fn("   10000000  ") << '\n';
    std::cout << fn("00040000") << '\n';
    std::cout << fn("1234567890") << '\n';

    return 0;
}

 

[Daniel Duffy]

Any ideas on an STL solution?