Need feedback on this code for the tinyUrl.


  • 0
    M
    // You can type code here and execute it.
    import java.lang.*;
    import java.util.*;
    
    
    class Main {
        public static void main(String[] args) {
            String s = "https://leetcode.com/problems/design-tinyurl";
            // HashTable<String, String> tiny = new HashTable<String, String>();
            Hashtable<Integer,String> tiny = new Hashtable<Integer, String>();
            int id = generateId(tiny, s);
            System.out.println(generateTinyUrl(id));
        }
        
        private static String generateTinyUrl(int id){
            char[] set = {'0','1','2','3','4','5','6','7','8','9','a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u',
                'v','w','x','y','z','A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'
            };
            StringBuilder st = new StringBuilder();
            while(id > 0){
                char ch = set[id % 62];
                st.append(ch);
                id = id / 62;
            }
            int size = st.length();
            // for(int i=size; i < 6;i++){
            //     st.append(set[randomWithRange(0,61)]);
            // }
            
            System.out.println(st);
            return new String(st);
        }
        
        private static int randomWithRange(int min, int max)
        {
            int range = (max - min) + 1;     
            return (int)(Math.random() * range) + min;
        }
        
        private static int generateId(Hashtable<Integer, String> tiny, String longUrl){
            if(tiny.containsValue(longUrl)){
                for(int key: tiny.keySet()){
                    if(tiny.get(key) == longUrl){
                        return key;
                    }
                }
            }
            
            int size = tiny.size();
            return size+1;
        }
    }
    

  • 0
    G

    @m.sharathiitg02

    1. You can change the 'size' to Long instead of Integer as 'int' can only have max value as 2.1 billion (approx). [considering the max urls we can have is about 56 billion ]
    2. For the commented code, instead of appending random number, you can prepend zeros. As 0001Ac is equivalent to 1Ac.

    This is what I observed. Thanks :)


  • 0
    M
    This post is deleted!

  • 0
    R

    I was wondering how the following problems would be handled -

    1. Thread-safety - I think if the generateId() function were invoked in a multi-threaded setting, duplicate Id could be generated.

    2. Because of the above mentioned issue with a deterministic algorithm using the ID, there may be collisions in the tinyUrl.

    3. If we chose to go the random-number generation route, then some probabilistic bounds should be set up to estimate the collision rate to see if this solution would really work in practice.


  • 1
    I

    @rohanb Would it be a good idea to start with a hardcoded value and increment for every new ID?
    This would solve the collision of the same random number being generated.
    Edit: Generating the ASCII value is now a new challenge

    For the multi threading part, randomWithRange would be our critical section. In C we could perhaps use semaphores or monitors(Not sure what the equivalent is called in Java).

    Also it would be nice if people also shared their ideas on the 12 follow up questions.


  • 0
    W

    @imranmanzoor31 Your suggestion works for avoiding collisions, but it means that you must either perform 1 increment after each addition and store it for next time its called, or perform n increments each time a new url is added.

    The first one does sound better than the second but you can still do much better by generating a key that can be greatly distributed among your storage space to avoid collisions most of the times and just perform increments each time you find yourself with a collision. Prime numbers will help you here and if you search a little bit on how the first hash algorithms were done you'll come across with number 31.

    Lets say you start with an array of numbers, of size equal to the length of the string to be encoded, and where each number identifies a unique character.
    Also lets assume that your maximum number of indexes is m, where m is also a prime number.
    You could generate a key by summing the products of each of those numbers by your prime like in S = a[0]*31 + a[1]*31 + a[2]*31 ... + a[n]*31, and then diving S over m for its reminder, R = S%m.
    R would be your identifier and only if its already used you would perform increments until you find one available.


Log in to reply
 

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