Discrepancies C++ Solution To Interview Task

Question

A recruiter recently approached me and invited me to apply for a C++ role for their client, and to take part in a technical task. I implemented my own tests, as well as used tests defined @TheWisp, shown in his answer to this post.

Although the 'interval_map' class is defined a little different in the task provided to me, vs the task provided to @TheWisp, all of @TheWisp's test cases apply to my task. All tests passed successfully, and as much as I tried to break the solution it appears to be solid.

I ran comparison tests of my implementation vs @TheWisp's implementation: both produced the same output, but my implementation was significantly faster with larger inputs as I adhered to O(logN).

You are allowed unlimited compiles within the browser, but only two submissions. My solution compiled fine according to the browser, but after my first submission their automated assessment concluded:

I cannot understand how my solution does not adhere to the requirements of K and V:

If I had used operators I should not have, then I would imagine the browser would have informed me that compilation had failed. I concluded that there may be some form of code analysis running using regular expressions, and they potentially erroneously determined the use of iterator operators to be K/V operators, so I replaced ++/-- with the use of 'std::prev' and 'std::next', but after re-submitting my solution I received the same complaint.

I subsequently e-mailed the company:

The response I received:

I thoroughly enjoyed this technical task, but it is rather frustrating when the feedback on the solution is so limited. Hopefully you guys are able to help me understand where/if I went wrong.

The technical task:

My solution:

      const K lowest = std::numeric_limits<K>::lowest();

   typename std::map<K,V>::iterator itPlace, itBefore, itAfter, itEnd, itWrap, itEraseStart, itEraseEnd, itAfterWrap, itT, itInserted, itHint, itBegin;

   bool keyAlreadyExists = false, valueAlreadyExistsAtKey = false, itemAlreadyExistsBeforePlace = false, itemBeforeMatchesValue = false,
       valueToWrap = false, valuesToErase = false, wrapValueIsSame = false, valueExistsAfterBounds = false, valueAfterIsSame = false, assignItem = false,
       insertItem = false, removeWrapItem = false, wrapStartErased = false, valueAfterWrapMatchesWrap = false, removeAfterItemInRange = false,
       removeDuplicateWrapInRange = false, valBeforeIsStartVal = false;

   if(!(keyBegin < keyEnd)) // Cannot use other operators as K is to only be comparable using less-than.
       return; // start should be before end. End is non-inclusive, start is inclusive.

   if(!this->m_map.size())
   {
       if(!(this->m_valBegin == val))
       {
           itBefore = this->m_map.insert(this->m_map.begin(), std::pair<K,V>(keyBegin, val));
           this->m_map.emplace_hint(itBefore, std::pair<K,V>(keyEnd, this->m_valBegin));
       }

       return;
   }

   itPlace = this->m_map.lower_bound(keyBegin);
   itWrap = itAfter = this->m_map.lower_bound(keyEnd);
   itWrap--; // The would-be value to wrap is either going to be within the new range or before it and lower_bound on the end gives us exactly that
   itEnd = this->m_map.end();
   itBegin = this->m_map.begin();

   itAfterWrap = itAfter;

   if(itAfter != itEnd)
       itAfterWrap++;

   itBefore = itPlace;

   if(itBefore != itBegin)
       itBefore--;

   // Due to the complexity of management and readability, it works out better to hash the flags out before operating
   keyAlreadyExists = itPlace != itEnd && !((itPlace->first < keyBegin) || (keyBegin < itPlace->first)); // No comparison operator available for K
   itemAlreadyExistsBeforePlace = itBefore != itPlace;
   valBeforeIsStartVal = !itemAlreadyExistsBeforePlace && this->m_valBegin == val;
   itemBeforeMatchesValue = (valBeforeIsStartVal && val == this->m_valBegin) || (itemAlreadyExistsBeforePlace && itBefore->second == val);
   wrapValueIsSame = itWrap->second == val;
   valueExistsAfterBounds = itAfter != itEnd;
   valueAfterIsSame = valueExistsAfterBounds && itAfter->second == val;

   // There is no need to wrap if the existing value is the same as the value being inserted and a value is already in place at keyEnd
   valueToWrap = (!wrapValueIsSame) && (!valueExistsAfterBounds || keyEnd < itAfter->first); 
   valueAlreadyExistsAtKey = keyAlreadyExists && itPlace->second == val;
   valueAfterWrapMatchesWrap = valueToWrap && valueAfterIsSame && itAfterWrap != itEnd && itAfterWrap->second == itWrap->second;
   // We can only assign if there is a key in the given position already, and there is no point in assigning if the value is already the same directly before or at K
   assignItem = (!valBeforeIsStartVal) && (keyAlreadyExists && !valueAlreadyExistsAtKey) && (!itemAlreadyExistsBeforePlace || !itemBeforeMatchesValue);

   // Should only insert if the key does not already exist at the current location / directly before
   insertItem = !keyAlreadyExists && !itemBeforeMatchesValue && !valBeforeIsStartVal;

   // If the item before the current place matches the value then the current place needs erasing. Any value that is wrapped also needs removing
   valuesToErase = itemBeforeMatchesValue || keyBegin < itWrap->first; // Need to debug and work out how to set this  

   // If there is a value to be wrapped from before the keyBegin, then there will be no erasure and must be removed individually
   removeWrapItem = !valuesToErase && valueToWrap && !(assignItem || insertItem);
   //removeAfterItemInRange = valuesToErase && valueAfterIsSame;
   //removeDuplicateWrapInRange = removeAfterItemInRange && valueAfterWrapMatchesWrap;

   if(insertItem)
       itInserted = this->m_map.emplace_hint(itBefore, std::pair<K,V>(keyBegin, val)); // itBefore points to the position before the location, achieving O(logN)

    if(valuesToErase)
    {
       itEraseStart = itPlace;
       itEraseEnd = itAfter;
       
       if((assignItem) || !(lowest < itEraseStart->first))
           itEraseStart++;

       if(removeAfterItemInRange)
           itEraseEnd++;

       if(removeDuplicateWrapInRange)
           itEraseEnd++;

       // Need to determine if the wrap iterator has been removed from the map as it cannot later be used as a hint if the iterator no longer points to a valid map location
       wrapStartErased = (itEraseStart->first < itWrap->first) || !(itWrap->first < itEraseStart->first);
       this->m_map.erase(itEraseStart, itEraseEnd); // As optimised as possible when removing a range
    }


   if(valueToWrap) // itWrap will point to the position before the place to insert unless erased, then itBefore will point to the position before - achieves O(logN)
   {
       if(assignItem)
           itHint = itPlace;
       else if(insertItem)
           itHint = itInserted;
       else if(wrapStartErased)
           itHint = itBefore;
       else
           itHint = itWrap;

       this->m_map.emplace_hint(itHint, std::pair<K,V>(keyEnd, itWrap->second));  // itWrap points to the position before the location, achieving O(logN)
   }

   if(assignItem) // Better to assign than remove + insert as it reduces map manipulation / run-time
       itPlace->second = val;

   if(removeWrapItem)
       this->m_map.extract(itWrap->first); // Using the iterator would result in Amortized constant, so K is used instead to achieve O(logN)

   if(valueAfterIsSame && !removeAfterItemInRange) // Avoid consecutive values
       this->m_map.extract(itAfter->first); // Using the iterator would result in Amortized constant, so K is used instead to achieve O(logN)

   if(valueAfterWrapMatchesWrap && !removeDuplicateWrapInRange)
       this->m_map.extract(itAfterWrap->first);

My solution meets all criteria, as far as I can tell. I created the following definitions to aid with testing:

template <typename T>
class Key
{
private:
    T k;

public:
constexpr Key(const T k) : k(k)
{
}

constexpr Key(const Key &other) : k(other.k)
{
    *this = other;
}

constexpr Key & operator=(const T &k)
{
    this->k = k;

    return *this;
}

constexpr Key & operator=(const Key &other)
{
    this->k = other.k;

    return *this;
}

constexpr bool operator<(const Key &other) const
{
    return this->k < other.k;
}
};

namespace std
{
template<typename T>
class numeric_limits<Key<T>>
{
public:
    static Key<T> lowest()
    {
        return Key(numeric_limits<T>::lowest());
    }
};
}

class Value
{
private:
    char c;

public:
Value(const char c) : c(c)
{
}

Value(const Value &other)
{
    *this = other;
}

Value & operator=(const char &c)
{
    this->c = c;

    return *this;
}

Value & operator=(const Value &other)
{
    this->c = other.c;

    return *this;
}

bool operator==(const char &c) const
{
    return this->c == c;
}

bool operator==(const Value other) const
{
    return this->c == other.c;
}
};

using KeyType = Key<unsigned int>;//unsigned long;
using ValueType = Value;//char;

Answer 1

Your solution imposes an extra constraint on the key type on the very first line: that std::numeric_limits<K> exists. While the question you've linked to has a bullet point stating that you're allowed to assume that, it appears that the task you've been given does not.