Program to shorten URL and decode it back to get original URL

Question

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

Answer 1

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.

Answer 2

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.