面试任务的 C++ 解决方案的差异

Question

一位招聘人员最近找到我，邀请我为他们的客户申请 C++ 职位，并参与一项技术任务。我实现了自己的测试，以及使用 @TheWisp 定义的测试，如他对这篇文章的回答所示。

虽然“interval_map”类的定义在提供给我的任务中与提供给@TheWisp 的任务略有不同，但@TheWisp 的所有测试用例都适用于我的任务。所有测试均成功通过，尽管我尝试破解该解决方案，但它似乎很可靠。

我对我的实现与 @TheWisp 的实现进行了比较测试：两者产生相同的输出，但当我坚持 O(logN) 时，使用更大的输入，我的实现速度明显更快。

您可以在浏览器内无限次编译，但只能提交两次。我的解决方案根据浏览器编译得很好，但在我第一次提交后，他们的自动评估得出结论：

我无法理解我的解决方案为何不符合 K 和 V 的要求：

如果我使用了不应该使用的运算符，那么我想浏览器会通知我编译失败。我的结论是，可能存在某种形式的使用正则表达式运行的代码分析，并且它们可能错误地将迭代器运算符的使用确定为 K/V 运算符，因此我使用 'std::prev 替换了 ++/-- ' 和 'std::next'，但在重新提交我的解决方案后，我收到了同样的投诉。

我随后给公司发了电子邮件：

我收到的回复：

我非常喜欢这项技术任务，但当解决方案的反馈如此有限时，我感到相当沮丧。希望你们能够帮助我了解我哪里/是否出错了。

技术任务：

我的解决方案：

      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);

据我所知，我的解决方案满足所有标准。 我创建了以下定义来帮助测试：

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

您的解决方案对第一行的密钥类型施加了额外的约束：

std::numeric_limits<K>

存在。虽然您链接到的问题有一个要点，表明您可以假设这一点，但您分配的任务似乎不允许。