Inverted Index Search
Problem
Build a tiny search index. Commands: doc id word1 word2 ... adds a document with a number id and some words (a word can repeat; a document id can be added more than once, and then it simply gets more words). find w prints the ids of all documents that contain the word w, from small to big, or none. both w1 w2 prints the ids of the documents that contain both words, from small to big, or none. Use a map from each word to the sorted set of its document ids.
Constraints
- 1 <= commands <= 10^4
Examples
Input
doc 1 the quick fox doc 2 the dog find the both the fox
Output
1 2 1
Solutions
An inverted index answers 'which documents contain this word' without reading all documents; search engines are built on this idea. Sets make the intersection of two words simple (retainAll in Java, & in Python).
/*
* Problem : Process lines.
* Input : Several lines.
* Output : One result per query.
* Approach: Map of sets.
* Time : O(total words + answer sizes)
* Space : O(total words)
* 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: The index maps every word to the sorted set of ids of documents that contain it.
java.util.Map<String, java.util.TreeSet<Integer>> index = new java.util.HashMap<>();
java.util.List<String> output = new java.util.ArrayList<>();
for (String line : lines) {
String[] part = line.split(" ");
if (part[0].equals("doc")) {
// Step 2: A set ignores repeated words of the same document.
int id = Integer.parseInt(part[1]);
for (int i = 2; i < part.length; i++) {
index.computeIfAbsent(part[i], key -> new java.util.TreeSet<>()).add(id);
}
} else {
java.util.TreeSet<Integer> found = new java.util.TreeSet<>(index.getOrDefault(part[1], new java.util.TreeSet<>()));
// Step 3: "both" keeps only the ids that are also in the set of the second word.
if (part[0].equals("both")) {
found.retainAll(index.getOrDefault(part[2], new java.util.TreeSet<>()));
}
StringBuilder text = new StringBuilder();
for (int id : found) {
text.append(text.length() == 0 ? "" : " ").append(id);
}
output.add(text.length() == 0 ? "none" : text.toString());
}
}
return output.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 is a set better than a list for the ids?