Generational GC: Promotion to Old Space
Problem
Simulate a generational garbage collector. New objects start in the young space with age 0 and are reachable. Commands: ALLOC x creates object x. DROP x makes x unreachable. GC is a minor collection: first it removes all unreachable objects of the young space, then every surviving young object gets age + 1, and an object whose age reaches 3 moves to the old space. FULLGC removes all unreachable objects from both spaces (no aging). ALLOC and DROP print ok. GC and FULLGC print young=Y old=O with the object counts after the collection.
Constraints
- 1 <= lines <= 1000
- names are unique and valid
Examples
Input
ALLOC a ALLOC b DROP b GC GC GC
Output
ok ok ok young=1 old=0 young=1 old=0 young=0 old=1
Solutions
Most objects die young, so collecting only the small young space is cheap. An object that survives three minor collections is likely to live long, so it moves to the old space, which is collected rarely (full GC).
/*
* Problem : Process lines.
* Input : Several lines.
* Output : One result per command.
* Approach: Objects with a space flag.
* Time : O(n) per collection
* Space : O(n)
* Java : 8 or newer.
*/
import java.util.Scanner;
public class Main {
// Step 1: One object keeps its space (young or old), its age and whether the program can still reach it.
static class Obj {
boolean young = true;
int age = 0;
boolean reachable = true;
}
// This method solves the task. It receives the input and returns the answer.
static String[] solve(String[] lines) {
java.util.Map<String, Obj> objects = new java.util.LinkedHashMap<String, Obj>();
String[] output = new String[lines.length];
for (int i = 0; i < lines.length; i++) {
String[] part = lines[i].split(" ");
if (part[0].equals("ALLOC")) {
objects.put(part[1], new Obj());
output[i] = "ok";
} else if (part[0].equals("DROP")) {
objects.get(part[1]).reachable = false;
output[i] = "ok";
} else {
boolean minor = part[0].equals("GC");
// Step 2: Remove the unreachable objects. A minor GC looks at the young space only.
java.util.Iterator<Obj> iterator = objects.values().iterator();
while (iterator.hasNext()) {
Obj o = iterator.next();
if (!o.reachable && (!minor || o.young)) {
iterator.remove();
}
}
// Step 3: A minor GC ages the surviving young objects. At age 3 they move to the old space.
int young = 0;
for (Obj o : objects.values()) {
if (minor && o.young) {
o.age++;
if (o.age >= 3) {
o.young = false;
}
}
if (o.young) {
young++;
}
}
output[i] = "young=" + young + " old=" + (objects.size() - young);
}
}
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 is a minor GC cheaper than a full GC?
- When does an object move to the old space?