Tips for an entry level C++ quant dev interview

[Quasar Chunawala]

I removed all dynamic allocations, so the code becomes consistent. The fixed size array is being created at compile time, so I should not use new. Does it still look like a potpourri of C and C++ code..?

#ifndef QPARRAY_H
#define QPARRAY_H
#include <cstring>

template <class T, std::size_t N>
class QPArray
{
private:
    T items[N];
    int maxsize;
public:
    /*Constructors and destructors*/
    QPArray();
    QPArray(const T value);
    QPArray(const QPArray<T, N>& a);
    virtual ~QPArray();

    /* Overload = operator*/
    QPArray<T, N>& operator =(const QPArray<T, N>& a);

    /* Selectors - Element access*/
    T& at(int index);
    T& operator [](int index);
    T& front();
    T& back();
 
    /* Capacity*/
    bool empty();
    virtual int size();
    virtual int max_size();

    /*Operations*/
    QPArray<T, N>& fill(T value);
};

template <class T,std::size_t N>
QPArray<T, N>::QPArray()
{
    maxsize = N;
}

template <class T, std::size_t N>
QPArray<T, N>::QPArray(T value)
{
    maxsize = N;

    if (N > 0)
    {
        for (int i = 0; i < maxsize; i++)
        {
            items[i] = value;
        }
    }
}

template <class T, std::size_t N>
QPArray<T,N>::QPArray(const QPArray<T, N>& a)
{
    maxsize = a.maxsize;
    for (int i = 0; i < maxsize; i++)
        items[i] = a.items[i];
}

template<class T, std::size_t N>
QPArray<T, N>::~QPArray(){}

template<class T, std::size_t N>
QPArray<T, N>& QPArray<T, N>::operator =(const QPArray<T, N>& a)
{
    if (this == &a)
        return *this;

    if (maxsize != a.maxsize)
        throw std::runtime_error(std::string("Src and target array bounds do not match"));

    for (int i = 0; i < maxsize; i++)
    {
        items[i] = a.items[i];
    }

    return *this;
}

template <class T, std::size_t N>
T& QPArray<T, N>::at(int i)
{
    return items[i];
}

template <class T, std::size_t N>
T& QPArray<T, N>::operator [](int index)
{
    return items[index];
}

//Access the first element of the array
template <class T, size_t N>
T& QPArray<T, N>::front() {
    return items[0];
}

//Access the last element of the array
template <class T, std::size_t N>
T& QPArray<T, N>::back() {
    return items[maxsize - 1];
}

template <class T, std::size_t N>
bool QPArray<T, N>::empty()
{
    if (maxsize == 0)
        return true;
    else
        return false;
}

template <class T, std::size_t N>
int QPArray<T,N>::size()
{
    return maxsize;
}

template <class T, std::size_t N>
int QPArray<T, N>::max_size()
{
    return maxsize;
}

template <class T, std::size_t N>
QPArray<T, N>& QPArray<T, N>::fill(T value)
{
    for (int i = 0; i < maxsize; i++)
    {
        items[i] = value;
    }

    return *this;
}


#endif // !ARRAY_H

 

[Pavlos Sakoglou]

I removed all dynamic allocations, so the code becomes consistent. The fixed size stack is being created at compile time, so I should not use new. Would it still qualify as mixed C/C++ code..?

#ifndef QPARRAY_H
#define QPARRAY_H
#include <cstring>

template <class T, std::size_t N>
class QPArray
{
private:
    T items[N];
    int maxsize;
public:
    /*Constructors and destructors*/
    QPArray();
    QPArray(const T value);
    QPArray(const QPArray<T, N>& a);
    virtual ~QPArray();

    /* Overload = operator*/
    QPArray<T, N>& operator =(const QPArray<T, N>& a);

    /* Selectors - Element access*/
    T& at(int index);
    T& operator [](int index);
    T& front();
    T& back();
 
    /* Capacity*/
    bool empty();
    virtual int size();
    virtual int max_size();

    /*Operations*/
    QPArray<T, N>& fill(T value);
};

template <class T,std::size_t N>
QPArray<T, N>::QPArray()
{
    maxsize = N;
}

template <class T, std::size_t N>
QPArray<T, N>::QPArray(T value)
{
    maxsize = N;

    if (N > 0)
    {
        for (int i = 0; i < maxsize; i++)
        {
            items[i] = value;
        }
    }
}

template <class T, std::size_t N>
QPArray<T,N>::QPArray(const QPArray<T, N>& a)
{
    maxsize = a.maxsize;
    for (int i = 0; i < maxsize; i++)
        items[i] = a.items[i];
}

template<class T, std::size_t N>
QPArray<T, N>::~QPArray(){}

template<class T, std::size_t N>
QPArray<T, N>& QPArray<T, N>::operator =(const QPArray<T, N>& a)
{
    if (this == &a)
        return *this;

    if (maxsize != a.maxsize)
        throw std::runtime_error(std::string("Src and target array bounds do not match"));

    for (int i = 0; i < maxsize; i++)
    {
        items[i] = a.items[i];
    }

    return *this;
}

template <class T, std::size_t N>
T& QPArray<T, N>::at(int i)
{
    return items[i];
}

template <class T, std::size_t N>
T& QPArray<T, N>::operator [](int index)
{
    return items[index];
}

//Access the first element of the array
template <class T, size_t N>
T& QPArray<T, N>::front() {
    return items[0];
}

//Access the last element of the array
template <class T, std::size_t N>
T& QPArray<T, N>::back() {
    return items[maxsize - 1];
}

template <class T, std::size_t N>
bool QPArray<T, N>::empty()
{
    if (maxsize == 0)
        return true;
    else
        return false;
}

template <class T, std::size_t N>
int QPArray<T,N>::size()
{
    return maxsize;
}

template <class T, std::size_t N>
int QPArray<T, N>::max_size()
{
    return maxsize;
}

template <class T, std::size_t N>
QPArray<T, N>& QPArray<T, N>::fill(T value)
{
    for (int i = 0; i < maxsize; i++)
    {
        items[i] = value;
    }

    return *this;
}


#endif // !ARRAY_H

So there are a few issues with this implementation, certainly some bugs, redundant code, and logical errors.

Your compile time array has already size N, whats the purpose of maxsize?
Why you have virtual methods and destructor -- what is your inheritance hierarchy?
If you try to model a stack, you need to emulate stack functionality i.e. push, pop, etc. Similar for other data structures.
What happens if someone attempts arr.at(-1) or arr[-1] ?
QPArray::fill() shouldn't be void? Why it needs to return the object?
In empty() method you can just return !m_index, where m_index is a counter of elements that keeps track of the current population.
All getters should be const.
Etc.

A good idea would be to create a simple dynamic array class of compile time T type and then encapsulate it in other data structures i.e. a stack, a queue, a bag, etc.

 

[Quasar Chunawala]

@Pavlos Sakoglou, thanks again!! Let me address the points you suggested. I shall add bounds checking.

Quick question though - my idea was to keep arrays as fixed size objects & create another dynamic container Vector that could be part of other data structures such as Queues, Stacks & Lists. Is that design okay? Could you elaborate a little on what you meant by a dynamic array class?

 

[Pavlos Sakoglou]

@Pavlos Sakoglou, thanks again!! Let me address the points you suggested. I shall add bounds checking.

Quick question though - my idea was to keep arrays as fixed size objects & create another dynamic container Vector that could be part of other data structures such as Queues, Stacks & Lists. Is that design okay? Could you elaborate a little on what you meant by a dynamic array class?

Ok yeah, it's good to practice both dynamic and static array classes. Static is when the size is determined at compile time (via template size parameter) and dynamic is when the size can be determined and change while the program runs already (run time).

What you are building is basically a wrapper class around a dynamic array. Instead of having many arrays here and there in main, now you wrap such an array in a class (you encapsulate the array) and you provide methods to manipulate that array. As a result your code is factored, reusable, readable, and maintainable, cause instead of dealing with multiple individual arrays, you have one point of reference of the array (the class) and can create multiple instances of it.

Taking that a step further, you create more wrapper classes that now encapsulate that enhanced array class, and manipulate it via other methods, that internally use the array's methods. You are adding more abstaction in other words.

 

[Daniel Duffy]

@Pavlos Sakoglou, thanks again!! Let me address the points you suggested. I shall add bounds checking.

Could you elaborate a little on what you meant by a dynamic array class?

Look up std::vector<T>

 

[Quasar Chunawala]

Hi @Pavlos Sakoglou and @Daniel Duffy ,

I learnt about an efficient algorithm to compute Fibonacci \(F_{n}\). I didn't know this earlier. Using the well-known fact that,

\(((F_{n+1},F_{n}),(F_{n},F_{n-1}))=((1,1),(1,0))^{n}\)

and assuming that multiplying two \(2\times{2}\) matrices takes constant time(I know, that for an input of size \(n\), naive matrix multiplication takes \(n^{3}\) time), one can use recursive squaring to compute the \(n\)th power of this matrix. Recursive squaring takes time \(T({n})=T(n/2)+O(1)\), which has upper bound \(O(\lg({n}))\). We can do better than linear time.

I was able to program it.

#include <iostream>

class matrix
{
    int items[2][2];

public:
    matrix();
    matrix(const matrix& A);
    matrix(int init_value);
 
    matrix& operator = (const matrix& A);
    matrix operator * (const matrix& A) const;
 
    void print() const;
    void set(int i, int j, int x);
    matrix rec_power(int n);
};


int main()
{
    matrix A;
    matrix B = A.rec_power(5);

    std::cout << "\nA^5 = ";
    B.print();

    std::cin.clear();
    std::cin.get();
    return 0;
}

matrix::matrix()
{
    items[0][0] = items[1][0] = items[0][1] = 1;
    items[1][1] = 0;
}

matrix::matrix(const matrix& A)
{
    for (int i = 0; i < 2; i++)
        for (int j = 0; j < 2; j++)
            items[i][j] = A.items[i][j];
}

matrix::matrix(int init_value)
{
    for (int i = 0; i < 2; i++)
        for (int j = 0; j < 2; j++)
            items[i][j] = init_value;
}

matrix& matrix::operator = (const matrix& A)
{
    if (this == &A)
        return *this;

    for (int i = 0; i < 2; i++)
        for (int j = 0; j < 2; j++)
            items[i][j] = A.items[i][j];

    return *this;
}

matrix matrix::operator * (const matrix& A) const
{
    matrix temp(0);
    for (int i = 0; i < 2; i++)
    {
        for (int j = 0; j < 2; j++)
        {
            for (int k = 0; k < 2; k++)
            {
                temp.items[i][j] += items[i][k] * A.items[k][j];
            }
        }
    }
    return temp;
}

void matrix::print() const
{
    std::cout << "\n(" << items[0][0] << "," << items[0][1] << ")";
    std::cout << "\n(" << items[1][0] << "," << items[1][1] << ")";
}

void matrix::set(int i, int j, int x)
{
    items[i][j] = x;
}

matrix matrix::rec_power(int n)
{
    if (n == 0)
    {
        matrix temp;
        temp.items[0][0] = temp.items[1][1] = 1;
        temp.items[0][1] = temp.items[1][0] = 0;
        return temp;
    }

    if (n == 1)
    {
        return *this;
    }
    else
    {
        if (n % 2 == 0)
        {
            matrix temp = rec_power(n / 2);
            return temp * temp;
        }
        else
        {
            matrix temp = rec_power((n - 1) / 2);
            return temp * temp * (*this);
        }
    }
}

 

[Daniel Duffy]

Lots of matrices are being thrashed on the stack.
Why not use the recurrence relation?

or even

https://www.quora.com/Why-do-the-diagonals-of-pascals-triangle-add-to-Fibonacci-numbers

 

[Quasar Chunawala]

Hi Daniel,

The recursive algorithm takes exponential time \(\Phi^{n}\), so for large Fibonacci numbers wouldn't it take a bit long?

Diagonals of a pascal triangle is awesome!

 

[Daniel Duffy]

Getting template metaprogramming compile-time constants at runtime

 

[pingu]

You should unroll the loops in the matrix multiplication that's how you achieve constant time for 2x2 matrix multiplication. This technique has been used in game development for ages (or assembly language).

If you want to hide the complexity of the matrix multiplication and be more efficient than the recursive version, a simple loop implementation of the Fibonacci series will probably suffice.

 

[Quasar Chunawala]

You should unroll the loops in the matrix multiplication that's how you achieve constant time for 2x2 matrix multiplication. This technique has been used in game development for ages (or assembly language).

If you want to hid the complexity of the matrix multiplication and be more efficient than the recursive version, a simple implementation of the fibonacci series will probably suffice.

By unrolling the loops, you mean writing four assignment statements for each entry in the \(2\times{2}\) matrix, right?

 

[Quasar Chunawala]

Ordered my copy of Numerical recipes in C++.

https://www.amazon.in/gp/product/8175960965.

 

[Daniel Duffy]

By unrolling the loops, you mean writing four assignment statements for each entry in the \(2\times{2}\) matrix, right?

I think this is for another day; it's like an orange belt learning black belt stuff. It's a Pandora's box.

I would concentrate on the essentials for the moment.

Many quants learn programming/C++ by osmosis/on need be basis with the result that many gaps remain to haunt you in later life.

 

[Daniel Duffy]

Ordered my copy of Numerical recipes in C++.

https://www.amazon.in/gp/product/8175960965.

In fairness, 95% of the code is C (nothing wrong with that mind you). Just sayin'
Boost C++ and Eigen have libraries for maths and are more modern than NR.

 

[Quasar Chunawala]

In fairness, 95% of the code is C (nothing wrong with that mind you). Just sayin'
Boost C++ and Eigen have libraries for maths and are more modern than NR.

I know that the book is slightly dated. I want to use it as a companion book alongside my numerical methods course to gain intuition and also learn their implementation nuances - though if the book was OO, it would be even more awesome.

 

[Quasar Chunawala]

I think this is for another day; it's like an orange belt learning black belt stuff. It's a Pandora's box.

I would concentrate on the essentials for the moment.

Many quants learn programming/C++ by osmosis/on need be basis with the result that many gaps remain to haunt you in later life.

And I want to spend some time on the essentials and get them down well.

 

[Daniel Duffy]

I know that the book is slightly dated. I want to use it as a companion book alongside my numerical methods course to gain intuition and also learn their implementation nuances - though if the book was OO, it would be even more awesome.

Actually, IMO OOP is the wrong paradigm for numerical computation. FORTRAN is best. Or these days functional programming model.

 

[Quasar Chunawala]

I see. That's something insightful and new I learnt today.

Out of curiosity, the BOOST, Eigen, LAPACK libraries - under the hood, they may be using many numerical algorithms originally implemented in good old FORTRAN, that were memory efficient & super-fast. Is that accurate?

 

[Quasar Chunawala]

The book that I am reading on data structures, suggests that the array based implementation of ascending & descending priority queues can be realized using circular, ordered arrays. The author leaves the implementation of the routines as an exercise to the reader.

While my code works okay, my implementation of insert() and remove() routines is very cryptic. I produce the code verbatim for completeness.

Questions

• Could my implementation from an abstraction/encapsulation standpoint, be optimized?
• Would you in general call it good object oriented design?

PQueue.h

#ifndef PQueue_H
#define PQueue_H

#include <cmath>
#include <iostream>

const int maxsize = 5;

template <class T>
class PQueue
{
    T items[maxsize];
    int front, rear,n;

public:
    PQueue(T val);
    PQueue(const PQueue<T>& q);
    ~PQueue();
    void insert(T x, int& overflow);
    int search_position(T x);
    T remove(int& underflow);
    T first(int& underflow) const;
    T last(int& underflow) const;
    int size() const;
    bool empty() const;
    void print () const;
    void increment(int& i);
    void decrement(int& i);
};

template <class T>
PQueue<T>::PQueue(T val)
{
    for (int i = 0; i < maxsize; i++)
        items[i] = val;

    front = rear = maxsize - 1;
    n = 0;
}

template <class T>
PQueue<T>::PQueue(const PQueue<T>& q)
{
    for (int i = 0; i < q.n; i++)
    {
        items[i] = q.items[i];
    }
    front = rear = maxsize - 1;
    n = 0;
}

template <class T>
PQueue<T>::~PQueue() {};

template <class T>
int PQueue<T>::search_position(T x)
{
    int low = front, high = rear;
    int i;

    if (empty()) {
        return (rear+1)%maxsize;
    }

 
    for (i = (front+1)%maxsize; i != (rear+1)%maxsize; increment(i))
    {
        if (items[i] > x)
            break;
    }
    return i;
}

template <class T>
void PQueue<T>::insert(T x, int& overflow)
{
    overflow = 0;
    if ((rear + 1) % maxsize == front)
    {
        overflow = 1;
        return;
    }
    else
    {
        int index = search_position(x);
        std::cout << "\nInserting item " << x << " at position " << index;

        increment(rear);

        //If index matches the updated value of rear,
        //there must be nothing to shift.
        if(index!=rear)
        {
            int i = rear - 1, j = rear;
            i += maxsize; i %= maxsize;
            j += maxsize; j %= maxsize;

            do
            {
                //Shift all elements 1 position to
                //the right in item[index...rear]
                items[j] = items[i];
                std::cout << "\nShifting item " << items[i] << " from index "
                    << i << " to " << j;
                decrement(i);
                decrement(j);

            } while (j != index);
        }
        n++;
        items[index] = x;
    }
}

template <class T>
T PQueue<T>::remove(int& underflow)
{
    underflow = 0;
    if (empty())
    {
        underflow = 1;
        return -1;
    }
    else
    {
        increment(front);

        std::cout << "\nRemoving item " << items[front] << " from the front";
        n--;
        return items[front];
    }
}

template <class T>
T PQueue<T>::first(int& underflow) const
{
    if (empty())
    {
        underflow = 1;
        return -1;
    }
    else
    {
        return items[(front + 1) % maxsize];
    }
}

template <class T>
T PQueue<T>::last(int& underflow) const
{
    if (empty())
    {
        underflow = 1;
        return -1;
    }
    else
    {
        return items[rear];
    }
}

template <class T>
int PQueue<T>::size() const
{
    return n;
}

template <class T>
bool PQueue<T>::empty() const
{
    if (front == rear)
        return true;
    else
        return false;
}

template <class T>
void PQueue<T>::print() const
{
    std::cout << "\nQueue items : ";
    for (int i = (front + 1) % maxsize; i != (rear+1)%maxsize; i=(++i)%maxsize)
    {
        std::cout << "items[" << i << "] = " << items[i] << "\t";
    }
}

template <class T>
void PQueue<T>::increment(int& i)
{
    ++i;
    i %= maxsize;
}

template <class T>
void PQueue<T>::decrement(int& i)
{
    --i;
    i += maxsize; i %= maxsize;
}


#endif // !PriorityQueue_H

TestPQueue.cpp

#include <iostream>
#include "PQueue.h"

int main()
{
    int x, overflow = 0, underflow=0;
    PQueue<int> pq(0);
    std::cout << "\nQueue size = " << pq.size();

    pq.insert(5, overflow);
    pq.insert(4, overflow);
    pq.insert(3, overflow);
    pq.insert(2, overflow);
    pq.insert(1, overflow);

    if (overflow)
        std::cout << "\nQueue overflow occurred";

    pq.print();
 
    x = pq.remove(underflow);
    x = pq.remove(underflow);
    x = pq.remove(underflow);

    std::cout << "\nQueue front = " << pq.first(underflow);
    std::cout << "\nQueue rear = " << pq.last(underflow);
    std::cout << "\nQueue size = " << pq.size();

    pq.insert(6, overflow);
    pq.print();
    pq.insert(7, overflow);
    pq.print();
    pq.insert(8, overflow);

    x = pq.remove(underflow);
    x = pq.remove(underflow);
    x = pq.remove(underflow);
    pq.print();
    x = pq.remove(underflow);

    if (underflow)
        std::cout << "\nQueue underflow occurred";

    std::cout << "\nQueue rear = " << pq.last(underflow);
    std::cout << "\nQueue front = " << pq.first(underflow);
    std::cout << "\nQueue size = " << pq.size();

    pq.insert(12, overflow);
    pq.insert(11, overflow);

    x = pq.remove(underflow);
    x = pq.remove(underflow);
    x = pq.remove(underflow);

    pq.print();

    std::cin.clear();
    std::cin.get();
    return 0;
}

Output

Queue size = 0
Inserting item 5 at position 0
Inserting item 4 at position 0
Shifting item 5 from index 0 to 1
Inserting item 3 at position 0
Shifting item 5 from index 1 to 2
Shifting item 4 from index 0 to 1
Inserting item 2 at position 0
Shifting item 5 from index 2 to 3
Shifting item 4 from index 1 to 2
Shifting item 3 from index 0 to 1
Queue overflow occurred
Queue items : items[0] = 2      items[1] = 3    items[2] = 4    items[3] = 5
Removing item 2 from the front
Removing item 3 from the front
Removing item 4 from the front
Queue front = 5
Queue rear = 5
Queue size = 1
Inserting item 6 at position 4
Queue items : items[3] = 5      items[4] = 6
Inserting item 7 at position 0
Queue items : items[3] = 5      items[4] = 6    items[0] = 7
Inserting item 8 at position 1
Removing item 5 from the front
Removing item 6 from the front
Removing item 7 from the front
Queue items : items[1] = 8
Removing item 8 from the front
Queue rear = -1
Queue front = -1
Queue size = 0
Inserting item 12 at position 2
Inserting item 11 at position 2
Shifting item 12 from index 2 to 3
Removing item 11 from the front
Removing item 12 from the front
Queue items :

 

[Quasar Chunawala]

I guess my code still looks more like C with classes. I haven't learnt STL yet - so I am not using the STL containers.