3
\$\begingroup\$

I'm posting a solution for LeetCode's "Encode and Decode TinyURL". If you'd like to review, please do. Thank you!

Problem

TinyURL is a URL shortening service where you enter a URL such as https://leetcode.com/problems/design-tinyurl and it returns a short URL such as http://tinyurl.com/4e9iAk.

Design the encode and decode methods for the TinyURL service. There is no restriction on how your encode/decode algorithm should work. You just need to ensure that a URL can be encoded to a tiny URL and the tiny URL can be decoded to the original URL.

Code


// The following block might slightly improve the execution time;
// Can be removed;
static const auto __optimize__ = []() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();

// Most of headers are already included;
// Can be removed;
#include <iostream>
#include <cstdint>
#include <string>
#include <unordered_map>
#include <utility>
#include <random>

static const struct Solution {
    public:
        const std::string encode(
            const std::string long_url
        ) {
            std::string tiny_encoded;

            if (!encoded_url.count(long_url)) {
                for (auto index = 0; index < kTinySize; ++index) {
                    tiny_encoded.push_back(char_pool[rand_generator() % std::size(char_pool)]);
                }

                encoded_url.insert(std::pair<std::string, std::string>(long_url, tiny_encoded));
                decoded_url.insert(std::pair<std::string, std::string>(tiny_encoded, long_url));

            } else {
                tiny_encoded = encoded_url[long_url];
            }

            return kDomain + tiny_encoded;
        }

        const std::string decode(
            const std::string short_url
        ) {

            return std::size(short_url) != kDomainTinySize ||
                   !decoded_url.count(short_url.substr(kDomainSize, kTinySize)) ? "" :
                   decoded_url[short_url.substr(kDomainSize, kTinySize)];
        }

    private:
        static constexpr char kDomain[] = "http://tinyurl.com/";
        static constexpr unsigned int kTinySize = 6;
        static constexpr unsigned int kDomainSize = std::size(kDomain) - 1;
        static constexpr auto kDomainTinySize = kDomainSize + kTinySize;
        static constexpr char char_pool[] = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
        std::unordered_map<std::string, std::string> encoded_url;
        std::unordered_map<std::string, std::string> decoded_url;
        std::random_device rand_generator;
};

// Your Solution object will be instantiated and called as such:
// Solution solution;
// solution.decode(solution.encode(url));

\$\endgroup\$
4
\$\begingroup\$

You are doing the lookup twice.

            if (!encoded_url.count(long_url)) {

                .. stuff

            } else {
                tiny_encoded = encoded_url[long_url];
            }

I know that it is O(1) for the lookup. But there is a real constant inside that. Avoid it if you can.

Use find(). Then if it is there you can simply use it.

            auto find = encoded_url.find(long_url);
            if (find == encoded_url.end()) {

                .. stuff

            } else {
                tiny_encoded = find->second;
            }

This is great if you want random URL that are hard to guess.

                for (auto index = 0; index < kTinySize; ++index) {
                    tiny_encoded.push_back(char_pool[rand_generator() % std::size(char_pool)]);
                }

But is that a requirement of the puzzle. Seems (not sure how expensive the generating the random number is) like this is very expensive way of generating a name.

There is also a chance for a clash. If you are using randomly generated values append a timestamp on the end to avoid a clash.


Personally I don't like having to specify a type. But if you are goint to do it use the type of the method rather than being this specific:

    encoded_url.insert(std::pair<std::string, std::string>(long_url, tiny_encoded));


    // Top of the class.
    using Map      = std::unordered_map<std::string, std::string>;
    using MapValue = Map::value_type;

    // In the code.
    encoded_url.insert(MapValue(long_url, tiny_encoded));

But I think I would simply have used emplace().

    encoded_url.emplace(long_url, tiny_encoded);

| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

I agree with everything in Martin York's answer. Just one thing: you can avoid having two unordered_maps if you don't create a purely random URL, but instead create one by hashing the original URL. This way, you will always create the same tiny URL for the same long URL, so you don't need encoded_url anymore. Of course, you would still need to handle duplicates in some way.

| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

Others have made good points, but I'll add in a stylistic quibble.

return std::size(short_url) != kDomainTinySize ||
       !decoded_url.count(short_url.substr(kDomainSize, kTinySize)) ? "" :
       decoded_url[short_url.substr(kDomainSize, kTinySize)];

is a heck of a one-liner. The ternary operator is fun but speaking as someone who has absolutely abused it, if you can't fit it comfortably on a line or two then you're going to hate yourself when you go back to read that in 6 months. Also, when you see that many !s running around it's usually time to bust out De Morgan's laws. And it would let us put the uninteresting path further out of sight. So, if we really want the ternary...

return std::size(short_url) == kDomainTinySize &&
       decoded_url.count(short_url.substr(kDomainSize, kTinySize)) ?
       decoded_url[short_url.substr(kDomainSize, kTinySize)] :
       "";

or if I was feeling a bit audacious maybe even

return std::size(short_url) == kDomainTinySize 
       && decoded_url.count(short_url.substr(kDomainSize, kTinySize))
       ? decoded_url[short_url.substr(kDomainSize, kTinySize)]
       : "";

I lied, second point: I would claim that idiomatic C++ should also rely on implicit type conversion as little as possible, which is to say, change that condition to decoded_url.count(...) != 0. It is more verbose, but it's also immediately clearer to the reader what's meant. Reasonable people could disagree though.

| improve this answer | |
\$\endgroup\$
  • 2
    \$\begingroup\$ I would even go so far as to say that you should move the logic of the condition into a named function. return isValidTinyUrl(short) ? decodeUrl(short) : ""; One line ternary operators are fine as long as it is easy to understand the intent. \$\endgroup\$ – Martin York Oct 22 at 16:13

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.