C++ interviews at Maven focus on knowledge and fluency. Fluency, because it demonstrates the experience of people who can code productively without having to lose (too much) time to visiting Stack Overflow and cppreference.com. Knowledge, because it is needed and reflects an enthusiasm for the profession and love for the language.
Why does C++ knowledge matter to Maven? One significant reason is the ability to move runtime computations to compile time because our domain demands the performance advantages of doing so. Therefore our code base relies on significant use of C++ templates as well as C++20, and our C++ interviews reflect this.
To give an insight, here is an example solution to a compile time template question that we used to ask candidates in the past.
Given a vector
template<int…I> struct Vector;
Assume the vector is sorted. Remove adjacent duplicates from the vector.
For example:
given Vector<1, 2, 2, 2, 3, 4, 4, 5>
produce Vector<1, 2, 3, 4, 5>
If the Vector is unsorted, it is expected that duplicates will remain:
given Vector<1, 2, 2, 2, 3, 4, 4, 1, 5>
produce Vector<1, 2, 3, 4, 1, 5>
One way to do this is to use a meta-function. In this case the result is a type, so it can be of the form:
template <typename Vector>
struct uniq
{
using type = XXX;
};It is invoked like so: uniq<Vector<1, 2>>::type. It can be verified with
static_assert(std::is_same_v<uniq<Vector<1, 2, 2, 2, 3, 4, 4, 5>>::type, Vector<1, 2, 3, 4, 5>>);
C++ templates can be a stumbling block for applicants to Maven. This does not need to be the case as this knowledge can be obtained. Our best candidates have in their enthusiastic pursuit of knowledge often invested money in buying books and time in reading them. Why? Because the internet is a complement to, but not a substitute for, a well written book. You can never google “what do I not know”, but the table of contents of a C++ book is a good checklist for finding the answer to this and to go on to acquiring the missing knowledge by reading and trying things out.
If template metaprogramming is unfamiliar to you, then starting out by imagining a runtime solution to this problem might help. It could be implemented in the following way.
auto uniq(std::vector<int> const& input)
{
std::vector<int> output;
if (!input.empty())
{
int previous = input.front();
output.push_back(previous);
for (int element : input)
{
if (element != previous)
{
output.push_back(element);
previous = element;
}
}
}
return output;
}In brief, iterate through the input vector while building an output vector as a result. If the current element is different from the previous element then add it to the result.
There are two control structures here; iteration and conditional selection. Remarkably both of these can be achieved with partial template specialization. A prerequisite however is knowing about the parameter packs of variadic templates.
First iteration, which is implemented as compile time recursion. This is done by looking at the first element, then removing it and recursing on the remaining elements. This would work similarly to the following.
// declare the iteration as a traversal of a int parameter pack
template <int... Remaining> struct IterateByRecursion;
// define the “iteration” by removing the first element and recursing on
// the remaining elements
template <int First, int... Remaining>
struct IterateByRecursion<First, Remaining...>
{
using type = typename IterateByRecursion<Remaining...>::type;
};
// define the termination of the recursion
template <>
struct IterateByRecursion<>
{
using type = void;
};
// checking the result of the iteration
using Result = typename IterateByRecursion<1, 2, 3>::type;
static_assert(std::is_same_v<void, Result>);How did this iteration take place at compile time? What the compiler did is equivalent to the following pseudo code using types as variables.
// expressed as recursion
auto getType(auto Iterator)
{
if (Iterator == IterateByRecursion<>) return Iterator::type;
else return getType(Iterator::type);
}
auto Result = getType(IterateByRecursion<1, 2, 3>);
// expressed as iteration
auto Iterator = IterateByRecursion<1, 2, 3>;
while (Iterator != IterateByRecursion<>) Iterator = Iterator::type;
auto Result = Iterator::type;This way the compiler traverses through
IterateByRecursion<1, 2, 3>
IterateByRecursion<2, 3>
IterateByRecursion<3>
IterateByRecursion<>
to get to the nested type ‘type’ of IterateByRecursion<> where the parameter pack is empty. IterateByRecursion<> is not defined as a recursion and the traversal stops here.
Next conditional selection can again be achieved by using the pattern matching of partial template specialization. std::conditional_t could also be considered for a solution, but is left as an exercise for the reader.
Looking at conditional selection for the first elements only without considering the iteration, the following is possible.
// define uniq with one parameter (intended as a Vector)
template <typename T> struct uniq;
// use partial specialisation matching for when the first two elements
// are the same
template <int First, int... Remaining>
struct uniq<Vector<First, First, Remaining...>>
{
using type = Vector<First, Remaining...>;
};
// use partial specialisation matching for when the first two elements
// are not the same
template <int First, int... Remaining>
struct uniq<Vector<First, Remaining...>>
{
using type = Vector<First, Remaining...>;
};
// support matching of special case when the Vector is empty
template <>
struct uniq<Vector<>>
{
using type = Vector<>;
};
// check that it works
static_assert(std::is_same_v<uniq<Vector<1, 2, 3>>::type,
Vector<1, 2, 3>>);
static_assert(std::is_same_v<uniq<Vector<1, 1, 2, 3>>::type,
Vector<1, 2, 3>>);Vector<First, First, Remaining…> matches more than Vector<First, Remaining…> so is considered the better match, which will identify the duplicate cases. Note that despite the varying number of type parameters given in template <…>, these are used in a way so that the number of type arguments for the specialization in struct uniq<…> remains the same as the number of parameters in the generalized template declaration i.e. one.
Finally with a technique for iteration and a technique for conditional selection established, they can be combined together with the building up of the result (during iteration/recursion) in an output Vector.
// define the meta-function, seeding the output as an empty vector.
template <typename Input, typename Output = Vector<>> struct uniq;
// define the partial specialization for recursion for filtering duplicates
template <int First, int... Remaining, int... Result>
struct uniq<Vector<First, First, Remaining...>, Vector<Result...>>
{
// recurse without the duplicate first element and do not add
// the duplicate to the result
using type = typename uniq<Vector<First, Remaining...>,
Vector<Result...>>::type;
};
// define the partial specialization for recursion when no duplicates
// need filtering
template <int First, int... Remaining, int... Result>
struct uniq<Vector<First, Remaining...>, Vector<Result...>>
{
// recurse without the first element and add the non-duplicate
// to the result
using type = typename uniq<Vector<Remaining...>,
Vector<Result..., First>>::type;
};
// define the partial specialization to terminate the recursion by
// assigning the now built up Output to the meta-function’s resulting type
template <typename Output>
struct uniq<Vector<>, Output>
{
// Output is Vector<Result...> built up over previous recursion
using type = Output;
};
// check that it works
static_assert(std::is_same_v<uniq<Vector<1, 2, 2, 2, 3, 4, 4>>::type,
Vector<1, 2, 3, 4>>);And that’s it! There are naturally more ways to solve this problem. This example hopes to demystify template metaprogramming by showing that there are known techniques for implementing familiar control structures at compile time. Once these are known, the problem is reduced to a familiar programming task, and the interview can be passed successfully.
