5
\$\begingroup\$

This my solution to this Good Range Coding Challenge

There is a number space given from 1 to N. And there are M queries followed by that. In each query, we were given a number between 1 to N (both inclusive). We add these number one by one into a set.

Good range: A range in which there is exactly one element present from the set.

For each query, we need to find the good ranges. We need to return the sum of boundry of all good ranges.

Input:

First line will take two integer for input N and M. Then following m lines would be numbers between 1 and N (both inclusive).

Output:

Following M lines contains sum of boudaries of good ranges.

Note:

Range can consist of single element and represented as (x-x) where boundary sum will be x+x.

Example:

Input:

10 4 
2 
5 
7 
9 

Output:

11 
18 
30 
46 

Explaination:

step-1) set: 2 
good range: (1-10) 
sum: 1+10=11 

step-2) set: 2 5 
good range: (1-4), (3-10) 
sum: 1+4+3+10=18 

step-3) set: 2 5 7 
good range: (1-4), (3-6), (6-10) 
sum: 1+4+3+6+6+10=30 

step-4) set: 2 5 7 9 
good range: (1-4), (3-6), (6-8), (8-10) 
sum: 1+4+3+6+6+8+8+10=46
#include <iostream>
#include <set>
using namespace std;

class Solution
{
    public: 
    Solution(const unsigned int _N, const unsigned int _M) : N(_N), M(_M) {}


    void solve()
    {
        for(unsigned int i=0; i<M; ++i)
        {
            unsigned int v; 
            cin >> v; 
            cout << "New Element = " << v << endl; 
            q.insert(v); 
            print_res(); 
            cout << endl; 
        }
    }

    void print_res()
    {       
        unsigned int left=1;
        auto it=q.begin(); 
        unsigned int last = *it; 

        for(++it; it!=q.end(); ++it)
        {
            const unsigned int curr = *it; 
            const unsigned int right = curr-1; 
            cout << "[" << left << ", "<< right << "] contains " << last << " and sum = " << (left+right) << endl; 
            left = last+1; 
            last = curr; 
        }
        const unsigned right = N; 
        cout << "[" << left << ", "<< right << "] contains " << last << " and sum = " << (left+right) << endl; 
    }

    private: 
    unsigned int N; 
    unsigned int M; 
    set<unsigned int> q; 
}; 


int main() {
    // your code goes here
    unsigned int N=0; 
    unsigned int M=0; 
    cin >> N >> M; 
    Solution sol(N,M); 
    sol.solve(); 
    return 0;
}

Note: I am aware I'm returning more information than required by the problem description but I have chosen to do it to include also debugging information

\$\endgroup\$
8
\$\begingroup\$
  1. Don't force a class where a function is perfectly fine.

  2. The namespace std is not designed for wholesale importation, see "Why is “using namespace std” considered bad practice?" for more detail.

  3. Identifiers starting with an underscore followed by an uppercase letter are reserved.

  4. Input is generally unreliable. But you don't test for error at all.

  5. Always recomputing the current result from first principles, instead of just updating it with the newest addition, is a waste of time.

  6. Flushing is expensive, so avoid std::endl and explicitly request it with std::flush where unavoidable.

  7. You should probably follow the requested output-format...

  8. You know that int in unsigned int is implicit?

  9. In C++ and C99+, return 0; is implicit for main().

  10. I wonder why you sometimes surround binary operators with space, and sometimes don't.

  11. Having over-long lines is very cumbersome to read. Admittedly, you need not make a hard cut at 79 nowadays.

  12. You should double-check whether duplicate inputs can occurr (there are none in the example), and if so whether they should cause anything but repeated output.
    I assumed duplicated possible, and they only cause output.

    • Duplicates have an effect would destroy ranges instead of adding them, thus needing an ordered std::set.
    • Duplicates not possible would mean the std::unordered_set can be dispensed with.
#include <cstdlib>
#include <iostream>
#include <unordered_set>

int main() {
    unsigned n, m, x;
    std::cin >> n >> m;
    if (!std::cin || !n) {
        std::cerr << "Bad Input!\n";
        return EXIT_FAILURE;
    }
    std::unordered_set<unsigned> nums;
    auto r = 0ULL;
    while (--m) {
        std::cin >> x;
        if (!std::cin || x < 1 || x > n) {
            std::cerr << "Bad Input!\n";
            return EXIT_FAILURE;
        }
        auto [iter, created] = nums.insert(x);
        if (created)
            r += 2 * x;
        std::cout << r << '\n';
    }
}
\$\endgroup\$
  • \$\begingroup\$ 13) As set is not unordered_set, it keeps the keys ordered while iterating over its content (not implemented with hash but with tree) \$\endgroup\$ – Nicola Bernini May 30 at 5:40
  • \$\begingroup\$ 4) As it is an algorithmic interview question the goal is on the algo (implementation, complexity, ...) so reasonable assumptions on the input are typically used in order to avoid a bunch of trivial sanity checks \$\endgroup\$ – Nicola Bernini May 30 at 5:42
  • \$\begingroup\$ 2) I know this but as it is an algorithmic interview question I simply wanted to avoid a bunch of std::aaa (saves time typing) \$\endgroup\$ – Nicola Bernini May 30 at 5:44
  • \$\begingroup\$ re 2+4: As a matter of course, you should at least mention that you left did so and why, unless you want to be marked down. re 13: It was about whether the algorithm can be drastically simplified, but considering the algorithm too restrictively formulated. Folded into 12 and reformulated to ask only what is relevant. No idea why I didn't switch to a std::unordered_set after I had the best algorithm figured out... \$\endgroup\$ – Deduplicator May 30 at 8:48
4
\$\begingroup\$

No comments on the algorithm itself. But I have many style improvements a interviewer probably looks for.

int main() {
    ...
    return 0;
}

Unlike in C the statement return 0 is automatically generated for main. So its common to omit it.

then this line in the main is problematic as well:

unsigned int N = 0;
unsigned int M = 0;
cin >> N >> M;

You expect you get an unsigned integer from the input. But who says the user types it?

You should better read in as std::string and convert the result to integer after if possible:

for (;;) {
    std::string input;
    std::cin >> input;

    if (is_convertible_to_integer(input)) { // write a function to check if is convertible to unsigned int
        // convert to int
        break;
    }
}

This can be probably in a function as well like unsigned int read_unsigend_int();

Then a classic mistake in C++. Don't use using namespace std. It is not a good habit. Read about it here: https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice.

The next thing I wonder. Do you really need unsigned int? Often it is not worth the hassle. It can introduce hard to spot errors: https://stackoverflow.com/questions/22587451/c-c-use-of-int-or-unsigned-int

Then you create a class just for solving basically some computations. In this case I think its over-engineering. It could be simply solved by using free standing functions. Unlike in some other Programming languages where everything is a class you can just use free standing functions.

However it is a good idea to wrap your functions and classes in its own namespace to prevent name clashes. So do something like:

namespace good_range {

    // youre functions and classes
}

Another small thing:

Solution(const unsigned int _N, const unsigned int _M) : N(_N), M(_M) {}

No need to use const here since you have the values by value copied anyway.

Also you should not use std::endl for a newline. I even saw it in many wrong books. std::endl gives you a newline and an expensive flushing operation of the buffer. Instead just use \n.

A opinion based thing. This line:

    cout << "[" << left << ", " << right << "] contains " << last << " and sum = " << (left + right) << endl;

I would split it into two:

    cout << "[" << left << ", " << right << "] contains " << last 
        << " and sum = " << (left + right) << endl;

why? It is easier to read and you have the option to open two source files on one screen next to each other. I personally stick usually with 80 spaces per line. But some people user 100 or 120. To see a discussion about it:

https://stackoverflow.com/questions/276022/line-width-formatting-standard

\$\endgroup\$
  • \$\begingroup\$ Thanks for your feedback I appreciate all the comments make sense but let me say here my focus was on solving the algorithmic challenge so I have not paid much attention to good practices \$\endgroup\$ – Nicola Bernini May 29 at 18:18
  • 1
    \$\begingroup\$ im sorry i don't have the time at the moment to check the algorithm. But I still wanted to contribute the style stuff I could spot right away. I think is alway important to write a good style. It shows youre professionalism. \$\endgroup\$ – Sandro4912 May 29 at 18:33
  • 2
    \$\begingroup\$ @NicolaBernini Hint: do not compute the sum from scratch every time; each insertion affects at most two ranges, and the sum can be updated in a constant time. \$\endgroup\$ – vnp May 29 at 19:03
  • \$\begingroup\$ I disagree that omitting the return is "common" in C++. Sure, it happens, and it's something to be aware of, but I certainly wouldn't think anything of an interview candidate who included it. I write it myself, and I think it's excellent for clarity. Personally, though, I prefer return EXIT_SUCCESS if that's what you actually mean (or, conversely, return EXIT_FAILURE) from <cstdlib>. \$\endgroup\$ – Cody Gray May 30 at 2:28
  • \$\begingroup\$ @NicolaBernini Definitely you should pay attention to good practices. They are no less important than algorithms. \$\endgroup\$ – L. F. May 30 at 11:16

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.