1
\$\begingroup\$

I solve problems to prepare for interviews. Now I have written the algorithm of finding K largest numbers in array. Various solutions are described here: https://www.geeksforgeeks.org/k-largestor-smallest-elements-in-an-array/. Initially, I came up with the solution myself and looks my solution corresponds to that described as Method 2 on the site, with the difference that I additionally use the "old minimum" to cut off unnecessary steps along the nested loop.

What could be written better in my code? What could be used instead of pmin?

Here is my implementation:

using namespace std;

vector<int> largest_part_of_vector(const vector<int>& vec, int K_PartSize)
{
    assert(K_PartSize < vec.size());

    vector<int> ret(K_PartSize);

    // Initial filling of temporary vector
    int ind = 0; // main end-to-end index
    int* pmin = const_cast<int*>(&vec[0]); // current minimum
    // How `pmin` could be declared and used better?

    for (auto& elemRef : ret)
    {
        elemRef = vec[ind];

        if (elemRef < *pmin)
        {
            pmin = &elemRef; // pmin is from `vecPart` now and will not modify `vec`
        }

        ind++;
    }

    // the rest part
    auto oldMin = *pmin;
    for (; ind < vec.size(); ind++)
    {
        auto v = vec[ind];

        if (v > oldMin) // preliminary check to avoid unnecessary checks
        {
            for (auto& elemRef : ret)
            {
                if (elemRef < *pmin)
                {
                    pmin = &elemRef;
                }
            }

            if (v > * pmin)
            {
                oldMin = *pmin;
                *pmin = v;
            }
        }
        /*else
        {
            savedIterations++;
        }*/
    }

    return ret; // As I understand, moving operator=( vector&& other ) will be used here
}
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Of course, the real answer to such an interview question is to just call std::partial_sort_copy. \$\endgroup\$
    – JDługosz
    Oct 27, 2021 at 14:23

1 Answer 1

1
\$\begingroup\$

using namespace std; is poor practice - don't do that.

K_PartSize should probably be a std::size_t.

assert() is not a good way to validate arguments - it's intended for making claims about invariants in the logic. It won't be present in non-debug builds, and when it is present, it can abort the program, without running destructors or any other cleanup.

Instead, implement some useful behaviour:

if (!partsize) {
    return {};
}
if (partsize >= vec.size()) {
    return vec;
}

I dislike the const_cast for pmin. I think it would be better to construct ret from the beginning part of the input vector, and start pmin pointing to the first element of that:

std::vector<int> ret(vec.begin(), vec.begin()+partsize);
int* pmin = &ret[0];

I'd suggest that this would be better as an iterator than a pointer:

auto pmin = ret.begin();

I'd swap round the test of (v > oldMin):

if (v <= oldMin) {
    continue;
}
for (auto& elemRef : ret)

I don't think we need both pmin and oldMin, certainly if we use the standard min_element algorithm:

#include <algorithm>
#include <vector>

std::vector<int> largest_part_of_vector(const std::vector<int>& vec, std::size_t partsize)
{
    if (!partsize) {
        return {};
    }
    if (partsize >= vec.size()) {
        return vec;
    }

    std::vector<int> ret(vec.begin(), vec.begin()+partsize);
    auto pmin = std::min_element(ret.begin(), ret.end());

    // the rest part
    for (auto ind = vec.begin() + ret.size();  ind != vec.end();  ++ind)
    {
        auto const v = *ind;

        if (v <= *pmin) { continue; }

        *pmin = v;
        pmin = std::min_element(ret.begin(), ret.end());
    }

    return ret;
}

Test program:

#include <iostream>

template<typename V>
class printable_vector
{
    V const& v;
public:
    explicit printable_vector(const V& v) : v{v} {}
    friend std::ostream& operator<<(std::ostream& os, const printable_vector& p) {
        os << '{';
        char const* sep = "";
        for (auto const& e: p.v) {
            os << sep << e;
            sep = ", ";
        }
        return os << '}';
    }
};

int main()
{
    auto const a = std::vector{ 1, 2, 12, 3, 2, 6 };

    for (auto k: {0, 1, 4, 5, 9}) {
        std::cout << printable_vector{largest_part_of_vector(a, k)} << '\n';
    }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.