Three different approaches in java


  • 12

    Approach 1- Using simple counter

    public class Codec {
        Map<Integer, String> map = new HashMap<>();
        int i=0;
        public String encode(String longUrl) {
            map.put(i,longUrl);
            return "http://tinyurl.com/"+i++;
        }
        public String decode(String shortUrl) {
            return map.get(Integer.parseInt(shortUrl.replace("http://tinyurl.com/", "")));
        }
    }
    

    Approach 2- using hashcode

    public class Codec {
        Map<Integer, String> map = new HashMap<>();
        public String encode(String longUrl) {
            map.put(longUrl.hashCode(),longUrl);
            return "http://tinyurl.com/"+longUrl.hashCode();
        }
        public String decode(String shortUrl) {
            return map.get(Integer.parseInt(shortUrl.replace("http://tinyurl.com/", "")));
        }
    }
    

    Approach 3- using random function

    public class Codec {
        Map<Integer, String> map = new HashMap<>();
        Random r=new Random();
        int key=r.nextInt(10000);
        public String encode(String longUrl) {
            while(map.containsKey(key))
                key= r.nextInt(10000);
            map.put(key,longUrl);
            return "http://tinyurl.com/"+key;
        }
        public String decode(String shortUrl) {
            return map.get(Integer.parseInt(shortUrl.replace("http://tinyurl.com/", "")));
        }
    }
    

  • 0
    S

    @vinod23 The third solution will be wedged in an infinite loop eventually. In fact, I bet it would be slow as hell after encoding a couple of thousand urls.


  • 0
    M

    @scabbage Why?


  • 0
    S

    @MoCool Because every encode call will randomly pick one integer between 0 and 10000, which means that, after 10000 invocations, we will exhaust all available keys. Hence the while loop will be stuck.


  • 1
    E

    For the second solution, we calculate the hashcode twice inside encode(longUrl.hashCode()).

    Instead of that I calculated it once and stored it as a local int. Why did this drop my runtime from 23% to 8%? I figured storing the operation into an int to use it in two places would improve runtime?


  • 0
    D

    What if the URL has been encoded? Your solution seems to create a new URL? Is that necessary?


  • 0
    F

    I think the concurrency issues should be addressed in this question by using synchronized blocks, a ConcurrentMap or something more sophisticated.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.