CodingGyan

Class Initialization Order

medium JVM, Memory and Performance

Problem

Simulate how the JVM initializes classes. Commands: class X declares a class without a parent, class X extends Y declares a class with an already declared parent Y. load X uses class X for the first time. A class is initialized only once, and its parent must be initialized first (the parent's parent before that, and so on). For each class that gets initialized, print init Name, parents before children. If X was already initialized, print already loaded X.

Constraints

  • 1 <= commands <= 10^4
  • Parents are declared before children

Examples

Input

class A
class B extends A
load B
load A

Output

init A
init B
already loaded A

Solutions

Best approachTime O(n)Space O(n)

In Java the static initializer blocks of a class run once, when the class is first used, and the superclass is always initialized before its subclass. Knowing this order explains many surprising outputs in interview questions about static blocks.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Process lines.
 * Input   : Several lines.
 * Output  : The init messages.
 * Approach: Class declarations and loads.
 * Time    : O(n)
 * Space   : O(n)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
        // Step 1: The registry knows the parent of each class and which classes are already initialized.
        static class Registry {
            final java.util.Map<String, String> parent = new java.util.HashMap<>();
            final java.util.Set<String> initialized = new java.util.HashSet<>();
            final java.util.List<String> output = new java.util.ArrayList<>();

            // Step 2: Initialize the parent first (if there is one and it is not done yet), then the class itself.
            void initialize(String name) {
                if (initialized.contains(name)) {
                    return;
                }
                String above = parent.get(name);
                if (above != null) {
                    initialize(above);
                }
                initialized.add(name);
                output.add("init " + name);
            }
        }

    // This method solves the task. It receives the input and returns the answer.
    static String[] solve(String[] lines) {
        Registry registry = new Registry();
        for (String line : lines) {
            String[] part = line.split(" ");
            if (part[0].equals("class")) {
                registry.parent.put(part[1], part.length > 2 ? part[3] : null);
            } else if (registry.initialized.contains(part[1])) {
                // Step 3: A class that is already initialized is not initialized again.
                registry.output.add("already loaded " + part[1]);
            } else {
                registry.initialize(part[1]);
            }
        }
        return registry.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)
  1. Which class initializes first when you load a subclass?

Try these next