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

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.

My approach:

import java.util.HashMap;
import java.util.Random;
import java.lang.StringBuilder;

public class Codec {

     //HashMap to store the longUrl and the randomly generated string
     HashMap<String,String> urlMap = new HashMap<>();  

    // Encodes a URL to a shortened URL.
    public String encode(String longUrl) {
        Random rand = new Random();
        int urlLen = 6;
        char [] shortURL = new char[urlLen];
        String randChars = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz1234567890";

        for(int i = 0; i < urlLen; i++ )
            shortURL[i] = randChars.charAt(rand.nextInt(randChars.length()));

        StringBuilder sb = new StringBuilder("http://tinyurl.com/");
        sb.append(new String(shortURL));
        System.out.println(sb);

        urlMap.put(sb.toString(),longUrl);

        return sb.toString();

    }

    // Decodes a shortened URL to its original URL.
    public String decode(String shortUrl) {

            return urlMap.get(shortUrl);

    }
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.decode(codec.encode(url));

With regards to the above code, I have the following questions:

  1. Is there a better approach to do this question?
  2. Can I decrease the number of lines or variables used in the program?
  3. Can I improve the space and time complexity of the program?

Reference

\$\endgroup\$
  • \$\begingroup\$ There are more than 62^6 possible url's you know... :D \$\endgroup\$ – Koekje May 5 '18 at 12:56
  • \$\begingroup\$ @Koekje, that is an unavoidable concern, whatever number of characters they use. There are at least as many URLs as TinyUrls! \$\endgroup\$ – Josiah May 5 '18 at 13:16
  • 1
    \$\begingroup\$ @Josiah yes I know, but I think it is good to at least think about it a little bit. And should this be more than a toy example, it is a rightful concern? :D \$\endgroup\$ – Koekje May 5 '18 at 13:46
  • \$\begingroup\$ Do you guys think that this is a good question to assess the problem-solving skills of a candidate? \$\endgroup\$ – Anirudh Thatipelli May 5 '18 at 14:13
  • \$\begingroup\$ Essentially any question can be good if it gives them a chance to talk through what problem specific challenges (efficiently, security, etc) they see and how they solve them. \$\endgroup\$ – Josiah May 6 '18 at 6:06
3
\$\begingroup\$

Janos has covered most of the key issues I could see.

One question that I have is "why do you want your identifying strings to be random?" If you want to associate the url with an id, the easiest option is counting. This has a number of advantages, in particular

  1. Sequential numbers are ideal for indexing. For your in memory demo, you could replace your hash map with a simple array or ArrayList. If you wanted something you could commit to disk, numbers make for natural database keys.
  2. There is minimal memory overhead. Especially in the array case, you don't have to store the number that you assigned to a given URL: it is implied by the location in the array.
  3. There is no chance of collisions between sequential numbers, which is the simplest possible solution to handling collisions.
  4. Counting is really easy. (Much more so than generating a random string)

Now you presumably want your urls to be strings, but that's not a problem. All you have to do is encode the number that you have counted to into Base62† and stick it onto your URL. The lookup process is to decode the Base62 string into a number and use it to index into your array or database.

† Base62 is fine, but not necessarily the best choice. It would be much easier to find library support for URL safe Base64 than Base62, and the encoding is inherently simpler and more efficient. It all depends whether you're okay having "-" and "_" in you strings.

\$\endgroup\$
  • \$\begingroup\$ Thanks, @Josiah for this advice. I will keep this in mind. \$\endgroup\$ – Anirudh Thatipelli May 6 '18 at 4:57
3
\$\begingroup\$

Flawed approach

There are severals flaws in the current approach:

  1. The program doesn't check if the generated key already exists for a different URL. And it might. And when it does, the new value will overwrite the old one. The old value will be no longer retrievable.

  2. encode returns a different output for the same input, with very high probability. In fact you can make the program run out of memory by calling encode on the same string enough times.

  3. The implementation wastes a lot of memory. There's no need to use the full tiny URL as the key of the cache, the unique part would be enough, and divide the storage size of the keys by 3.

  4. It's unrealistic to expect a URL shortening service to run forever without server reboots. Since this implementation doesn't use any storage outside RAM, all previously stored URLs will be completely lost when the process is restarted.

Technical issues

There are many technical implementation flaws:

  • No need to create a new Random in every call of encode. Better use a shared instance.
  • Magic numbers and strings should be constants or class parameters: the target key length (6), the alphabet.
  • The names are not great. urlLen is not the length of a URL, but the length of the unique part only (6 letters). randChars are not "random chars", but an alphabet from which to pick a random character.
  • It's a bad practice to print to stdout from methods that are not particularly designed to print stuff.
  • Prefer to declare variables using interface types: Map instead of HashMap.
  • Using a StringBuilder is overkill, a simple concatenation with + would be better.
\$\endgroup\$
  • \$\begingroup\$ Thanks for the advice, @janos. I had thought earlier that my approach is incorrect as I am just getting some value from memory without actual computation of any sort. The stdout was to test if the hashMap was storing the values correctly. \$\endgroup\$ – Anirudh Thatipelli May 5 '18 at 14:10
  • \$\begingroup\$ "the unique unique part would be enough" what is the unique unique part in this case? \$\endgroup\$ – Marian Paździoch May 9 '18 at 10:09
  • \$\begingroup\$ @MarianPaździoch the 6-letter random string \$\endgroup\$ – janos May 9 '18 at 10:50

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.