Coding Error Interview

Computer Science Level 2

imagine you're in a coding interview where you are asked to solve in an example array [1,2,3,4,5] the sum of 9 with only two digits of the best possible algorithmic complexity, the following code is the one that was done in the interview: (and it is in which an error must be found, it must be put in the line of code that is the error or if there are several write (123) and if it is none error write (0): (in order)

CODE: 1. bool PairNums(const vector<int> & data, int sum) { 2. set<int>comp; 3. for (int value : data) { 4. if (comp.find(value) == comp.end) 5. return true; 6. comp.add(sum+ (value-sum)); 7. } 8. return false; }

16 246 46 14 235

1 solution

Piotr Idzik
Nov 24, 2020

Assuming, that the code was supposed to be written in C++:

(line 4) end is a method not a field,
(line 6) the set has no method add , it has insert instead.

Besides:

I would add the namespace std into your code,
the variable value could be const .

Concerning the algorithm itself:

the lines marked as 4 and 6 contain some logical bug (cf. below for my suggestion of the improvement),
one could use unorderedset instead of set . In C++ unorderedset uses hash tables (in average constant access/insertion time) and set relies on binary search trees (access and insertion time is, in average, logarithmic in size)

bool PairNums(const std::vector<int>& data, const int sum) //1
{
    std::unordered_set<int> comp; //2
    for (const int value : data) //3
    {
        if (comp.find(sum-value) != comp.end()) //4
        {
            return true; //5
        }
        comp.insert(value); //6
    }
    return false; //8
}

It is correct and the problem was finding these errors (I know they were errors, I wanted to see who could identify them) and the thing of the unorderedset yeah in This is the only real error that I have you’re right.

Elijah Frank - 6 months, 2 weeks ago

The set vs. unorderedset issue is quite subtle. It highly depends on the data - it might turn out, that the set will be faster than the unordered set.

I run some benchmarks. I got 0.74 [s] for set vs. 0.71 [s] for the unorderedset. I am attaching the code below.

#include <iostream>
#include <random>
#include <chrono>
#include <vector>
#include <unordered_set>
#include <set>

#include <type_traits>

template<typename DataType, typename CompType>
bool pairNums(const DataType& data, const int sum) //1
{
    static_assert(std::is_same<typename DataType::value_type, typename CompType::key_type>::value);
    CompType comp; //2
    for (const int value : data) //3
    {
        if (comp.find(sum-value) != comp.end()) //4
        {
            return true; //5
        }
        comp.insert(value); //6
    }
    return false; //8
}

template<typename DataType, typename CompType>
long double speedTest(const std::size_t minSize, const std::size_t maxSize,
                      const int minValue, const int maxValue,
                      const std::size_t maxIterNum)
{
    std::mt19937 randomEngine(0); //same seed for all of the tests
    std::uniform_int_distribution<std::size_t> sizeDist{minSize, maxSize};
    std::uniform_int_distribution<int> valDist{minValue, maxValue};
    long double res = 0;
    for (std::size_t testNum = 0; testNum < maxIterNum; ++testNum)
    {
        const std::size_t dataSize = sizeDist(randomEngine);
        std::vector<int> data;
        data.reserve(dataSize);
        for (std::size_t i = 0; i < dataSize; ++i)
        {
            data.push_back(valDist(randomEngine));
        }
        const int sumVal = valDist(randomEngine);
        const auto startTime = std::chrono::steady_clock::now();
        pairNums<DataType, CompType>(data, sumVal);
        const auto endTime = std::chrono::steady_clock::now();
        const std::chrono::duration<long double> runTime = endTime-startTime;
        res += runTime.count();
    }
    return res;
}

int main()
{
    const std::size_t minSize = 1;
    const std::size_t maxSize = 4000;
    const int minVal = -800;
    const int maxVal = -minVal;
    const std::size_t maxIterNum = 100000;
    std::cout<<"runtimes: "<<std::endl;
    std::cout<<"set: "
             <<speedTest<std::vector<int>, std::set<int>>(
                  minSize, maxSize, minVal, maxVal, maxIterNum)
             <<" [s]"<<std::endl;
    std::cout<<"unordered_set: "
             <<speedTest<std::vector<int>, std::unordered_set<int>>(
                  minSize, maxSize, minVal, maxVal, maxIterNum)
             <<" [s]"<<std::endl;
    return 0;
}

Piotr Idzik - 6 months, 2 weeks ago

Coding Error Interview

1 solution

0 pending reports