4
\$\begingroup\$

Here's some code which, given a list of \$N\$ movie lengths, checks if there are two movies that equal the exact length of a flight. This solution runs in \$\mathcal{O}(N)\$ time since I used a hash table.

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

int main() {
    const int LENGTH = 170;
    vector<int> movies = {60, 120, 50, 150, 30, 45};
    unordered_map<int, bool> secondMovies;

    for (int movie: movies)
        secondMovies[movie] = true;

    for (int firstMovie: movies)
        if (secondMovies[LENGTH-firstMovie]) {
            cout << firstMovie << " and " << LENGTH-firstMovie;
            return 0;
        }

    cout << "No movies found.";
    return 0;
}

In the second for loop, I immediately return from main if two valid movies are found. Is this considered bad practice?

\$\endgroup\$
2
\$\begingroup\$

Returning from the body of the loop isn't necessary a problem in itself. Nonetheless, your code does have a fairly significant problem.

When you search for a second movie of a particular length, you use the subscript operator. The problem arises from the fact that when this doesn't find an existing entry for a particular length, it inserts a new entry for that length. The value associated with the key will be value-initialized, will will give false in this case.

That means the code will work, but because you're potentially inserting a lot of unnecessary items into your map, you could waste a lot of time. As long as you're only dealing with half a dozen movies, it's probably irrelevant, but if you deal with a lot it could get ugly.

In fact, there doesn't seem to be any reason to use a map here at all. It looks like an unordered_set will work perfectly fine for the task at hand.

There is something else here that could probably be viewed as a bug: if you have a movie whose length is exactly half the total length of the flight, it appears that your code will suggest watching the same movie twice in succession, which probably isn't something anybody would actually want.

\$\endgroup\$
1
\$\begingroup\$

no its not bad. Some schools of thought dont like returns in the middle of any function. I am not in that school. Doing it in main is slightly weird, but it will never normally happen in non-trivial programs.

If you want to be a guru dont do using namespace

\$\endgroup\$
0
\$\begingroup\$

In your test

if (secondMovies[LENGTH-firstMovie]) {

you optimistically assume LENGTH-firstMovie will never be negative. Add a test somewhere to check that no movie is longer than LENGTH and act appropriately on it.

You also assume that hash table always succeeds in O(1). Where find says

Complexity

Constant on average, worst case linear in the size of the container.

So your program has worst case run time O(N^2).

\$\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.