String Pool and intern()
Problem
Simulate the Java string pool. Objects get numbers 1, 2, 3, ... in the order they are created. LIT s uses a string literal: it reuses the pooled object of s if there is one, otherwise it creates a new object and puts it in the pool. NEW s always creates a new object that is not in the pool. INTERN k returns the pooled object with the same text as object k (if no pooled object has this text, object k itself enters the pool). SAME i j tells if i and j are the same object (==). EQUALS i j tells if the texts are equal. LIT, NEW and INTERN print an object number; SAME and EQUALS print true or false.
Constraints
- 1 <= lines <= 1000
- texts are words without spaces
Examples
Input
LIT hi LIT hi NEW hi SAME 1 2 INTERN 2
Output
1 1 2 false 1
Solutions
The pool is a map from text to object. Literals and intern() look in the map, NEW never does. That is why new String("hi") == "hi" is false and new String("hi").intern() == "hi" is true.
/*
* Problem : Process lines.
* Input : Several lines.
* Output : One result per command.
* Approach: Map as the pool.
* Time : O(n)
* 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: "texts" holds the text of each object (index = object number). "pool" maps a text to the pooled object.
java.util.List<String> texts = new java.util.ArrayList<String>();
texts.add(null);
java.util.Map<String, Integer> pool = new java.util.HashMap<String, Integer>();
String[] output = new String[lines.length];
for (int i = 0; i < lines.length; i++) {
String[] part = lines[i].split(" ");
if (part[0].equals("LIT")) {
// Step 2: A literal reuses the pooled object when one exists.
if (!pool.containsKey(part[1])) {
texts.add(part[1]);
pool.put(part[1], texts.size() - 1);
}
output[i] = String.valueOf(pool.get(part[1]));
} else if (part[0].equals("NEW")) {
texts.add(part[1]);
output[i] = String.valueOf(texts.size() - 1);
} else if (part[0].equals("INTERN")) {
// Step 3: intern() returns the pooled object of the same text, or puts this object in the pool.
int k = Integer.parseInt(part[1]);
String text = texts.get(k);
if (!pool.containsKey(text)) {
pool.put(text, k);
}
output[i] = String.valueOf(pool.get(text));
} else if (part[0].equals("SAME")) {
output[i] = String.valueOf(part[1].equals(part[2]));
} else {
output[i] = String.valueOf(texts.get(Integer.parseInt(part[1])).equals(texts.get(Integer.parseInt(part[2]))));
}
}
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)
- Does NEW touch the pool?
- What does intern() do when the text is not in the pool?