URL Shortener Service

Problem

Build a tiny URL shortener. Commands: SHORTEN url prints a short code. Codes are c1, c2, c3, ... in the order that new urls arrive; the same url always gets the same code. RESOLVE code prints the original url and counts one visit (print unknown for an unknown code). STATS code prints the number of visits of that code (unknown for an unknown code).

Constraints

  • 1 <= lines <= 10^4
  • urls are words without spaces

Examples

Input

SHORTEN a.com
SHORTEN b.org
SHORTEN a.com
RESOLVE c1
STATS c1

Output

c1
c2
c1
a.com
1

Solutions

Best approachTime O(n)Space O(urls)

Two look-ups are needed: from the url to its code (so repeated urls reuse a code) and from the code to the record (to resolve and count visits). Both maps make every command O(1).

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Process lines.
 * Input   : Several command lines.
 * Output  : One result per command.
 * Approach: Two maps in a class.
 * Time    : O(n)
 * Space   : O(urls)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
        // Step 1: The service keeps two maps: url to code, and code to a record with the url and the visit count.
        static class Shortener {
            private final java.util.Map<String, String> codeOf = new java.util.HashMap<String, String>();
            private final java.util.Map<String, Object[]> records = new java.util.HashMap<String, Object[]>();

            String shorten(String url) {
                String code = codeOf.get(url);
                if (code == null) {
                    code = "c" + (codeOf.size() + 1);
                    codeOf.put(url, code);
                    records.put(code, new Object[] {url, 0});
                }
                return code;
            }

            // Step 2: resolve() counts a visit. stats() only reads the count.
            String resolve(String code) {
                Object[] record = records.get(code);
                if (record == null) {
                    return "unknown";
                }
                record[1] = (Integer) record[1] + 1;
                return (String) record[0];
            }

            String stats(String code) {
                Object[] record = records.get(code);
                return record == null ? "unknown" : String.valueOf(record[1]);
            }
        }

    // This method solves the task. It receives the input and returns the answer.
    static String[] solve(String[] lines) {
        Shortener service = new Shortener();
        String[] output = new String[lines.length];
        for (int i = 0; i < lines.length; i++) {
            String[] part = lines[i].split(" ");
            if (part[0].equals("SHORTEN")) {
                output[i] = service.shorten(part[1]);
            } else if (part[0].equals("RESOLVE")) {
                output[i] = service.resolve(part[1]);
            } else {
                output[i] = service.stats(part[1]);
            }
        }
        return output;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        java.util.List<String> all = new java.util.ArrayList<>();
        while (scanner.hasNextLine()) {
            String line = scanner.nextLine().trim();
            if (!line.isEmpty()) {
                all.add(line);
            }
        }
        String[] lines = all.toArray(new String[0]);
        System.out.println(String.join("\n", solve(lines)));
    }
}
Hints (2)
  1. Why do we need url-to-code?
  2. Which command changes the visit count?