To-Do List Manager
Problem
Build a to-do list. Task ids start at 1 and are never reused. Commands: add title (the title is the rest of the line and can have spaces) prints added ID; done ID marks the task as done and prints done ID; remove ID deletes the task and prints removed ID; for an unknown id both print no task ID; list prints one line per task in id order, written as ID [x] title for a done task and ID [ ] title for a pending task, followed by a line pending N with the number of pending tasks; if there are no tasks list prints empty.
Constraints
- 1 <= commands <= 10^4
- titles are not empty
Examples
Input
add buy milk add call mom done 1 list
Output
added 1 added 2 done 1 1 [x] buy milk 2 [ ] call mom pending 1
Solutions
This is a CRUD program (create, read, update, delete) in miniature. Ids are never reused: a removed id stays unused, so old references cannot point to a new task by mistake. The same design is behind most database-backed apps.
/*
* Problem : Process lines.
* Input : Several lines.
* Output : Results of the commands.
* Approach: A small CRUD model.
* Time : O(n log n)
* Space : O(n)
* Java : 8 or newer.
*/
import java.util.Scanner;
public class Main {
// Step 1: A TreeMap keeps the tasks sorted by id. Each task has a title and a done flag.
static class TodoList {
private final java.util.TreeMap<Integer, String> titles = new java.util.TreeMap<>();
private final java.util.Set<Integer> done = new java.util.HashSet<>();
private int nextId = 1;
String add(String title) {
titles.put(nextId, title);
return "added " + nextId++;
}
String markDone(int id) {
if (!titles.containsKey(id)) {
return "no task " + id;
}
done.add(id);
return "done " + id;
}
String remove(int id) {
if (titles.remove(id) == null) {
return "no task " + id;
}
done.remove(id);
return "removed " + id;
}
// Step 2: list gives one line per task, then a summary line. An empty list gives one word.
java.util.List<String> list() {
java.util.List<String> result = new java.util.ArrayList<>();
if (titles.isEmpty()) {
result.add("empty");
return result;
}
int pending = 0;
for (java.util.Map.Entry<Integer, String> entry : titles.entrySet()) {
boolean finished = done.contains(entry.getKey());
pending += finished ? 0 : 1;
result.add(entry.getKey() + " [" + (finished ? "x" : " ") + "] " + entry.getValue());
}
result.add("pending " + pending);
return result;
}
}
// This method solves the task. It receives the input and returns the answer.
static String[] solve(String[] lines) {
TodoList todo = new TodoList();
java.util.List<String> output = new java.util.ArrayList<>();
for (String line : lines) {
if (line.trim().isEmpty()) {
continue;
}
// Step 3: Split into the command and the rest of the line. The rest can contain spaces (a title).
String[] part = line.split(" ", 2);
if (part[0].equals("add")) {
output.add(todo.add(part[1]));
} else if (part[0].equals("done")) {
output.add(todo.markDone(Integer.parseInt(part[1])));
} else if (part[0].equals("remove")) {
output.add(todo.remove(Integer.parseInt(part[1])));
} else {
output.addAll(todo.list());
}
}
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()) {
all.add(scanner.nextLine());
}
String[] lines = all.toArray(new String[0]);
System.out.println(String.join("\n", solve(lines)));
}
}
Hints (1)
- Why should ids of removed tasks not be reused?