Coding Challenge Solution - Good Range

Question

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

Answer 1

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';
    }
}

Answer 2

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