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
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).
/*
* 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)
- Why do we need url-to-code?
- Which command changes the visit count?