Bidirectional Map
Problem
Build a map where you can look up in both directions: by key and by value. Every key has one value, and every value has one key. Commands: put K V (store the pair; before that remove any old pair that uses the same key K or the same value V; print ok), getv K (print the value of the key, or none), getk V (print the key of the value, or none), size (print the number of pairs).
Constraints
- 1 <= commands <= 100
- keys and values have no spaces
Examples
Input
put a 1 put b 1 getv a getk 1 size
Output
ok ok none b 1
Solutions
Two maps give O(1) lookup in both directions. The only difficulty is keeping them in step: a put must delete the old pair of the key and the old pair of the value from both maps.
/*
* Problem : Run the bimap.
* Input : Command lines.
* Output : Answer lines.
* Approach: Two mirrored maps
* Time : O(1) per command
* Space : O(n)
* Java : 8 or newer.
*/
import java.util.Scanner;
public class Main {
// This method solves the task. It receives the input and returns the answer.
static String[] solve(String[] lines) {
// Step 1: Two maps that mirror each other: key to value, and value to key.
java.util.Map<String, String> byKey = new java.util.HashMap<String, String>();
java.util.Map<String, String> byValue = new java.util.HashMap<String, String>();
java.util.List<String> out = new java.util.ArrayList<String>();
for (String line : lines) {
String[] part = line.split(" ");
if (part[0].equals("put")) {
// Step 2: Remove the old pairs on both sides first, so the two maps stay in step.
String oldValue = byKey.remove(part[1]);
if (oldValue != null) {
byValue.remove(oldValue);
}
String oldKey = byValue.remove(part[2]);
if (oldKey != null) {
byKey.remove(oldKey);
}
byKey.put(part[1], part[2]);
byValue.put(part[2], part[1]);
out.add("ok");
} else if (part[0].equals("getv")) {
out.add(byKey.getOrDefault(part[1], "none"));
} else if (part[0].equals("getk")) {
out.add(byValue.getOrDefault(part[1], "none"));
} else {
out.add(String.valueOf(byKey.size()));
}
}
return out.toArray(new String[0]);
}
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 (1)
- Why must put remove two old pairs?