CodingGyan

Class Loader Parent Delegation

medium JVM, Memory and Performance

Problem

Java class loaders form a chain. A loader first asks its parent to load a class, and only loads it itself if all parents fail (parent-first delegation). The first line has k, the number of loaders. The next k lines are name: classes, from the child loader (first) to the top parent (last); the classes are the ones that loader can load. Then every line LOAD X asks the child loader (the first one) to load class X. For each query print the name of the loader that really loads it, or ClassNotFoundException if no loader has it.

Constraints

  • 1 <= k <= 10
  • 1 <= queries <= 1000

Examples

Input

2
app: Main String
boot: String
LOAD String
LOAD Main
LOAD Foo

Output

boot
app
ClassNotFoundException

Solutions

Best approachTime O(queries * k)Space O(k)

The call goes up the chain before any loader looks into its own classes. So the top parent that has the class always wins. This is why you cannot replace java.lang.String with your own class: the bootstrap loader answers first.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Process lines.
 * Input   : Several lines.
 * Output  : One loader name per query.
 * Approach: Recursive delegation.
 * Time    : O(queries * k)
 * Space   : O(k)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
        // Ask loader "index" to load the class. It asks its parent (index + 1) first.
        private static String load(String[] names, java.util.List<java.util.Set<String>> classes, int index, String cls) {
            if (index == names.length) {
                return null;
            }
            String fromParent = load(names, classes, index + 1, cls);
            if (fromParent != null) {
                return fromParent;
            }
            return classes.get(index).contains(cls) ? names[index] : null;
        }

    // This method solves the task. It receives the input and returns the answer.
    static String[] solve(String[] lines) {
        // Step 1: Read the loaders: the name before the colon and the set of class names after it.
        int k = Integer.parseInt(lines[0]);
        String[] names = new String[k];
        java.util.List<java.util.Set<String>> classes = new java.util.ArrayList<java.util.Set<String>>();
        for (int i = 0; i < k; i++) {
            int colon = lines[1 + i].indexOf(':');
            names[i] = lines[1 + i].substring(0, colon);
            String rest = lines[1 + i].substring(colon + 1).trim();
            classes.add(rest.isEmpty() ? new java.util.HashSet<String>() : new java.util.HashSet<String>(java.util.Arrays.asList(rest.split("\\s+"))));
        }
        // Step 2: Every LOAD query starts at the child loader (index 0). The recursion goes up first and answers on the way back.
        String[] output = new String[lines.length - 1 - k];
        for (int i = 1 + k; i < lines.length; i++) {
            String found = load(names, classes, 0, lines[i].split(" ")[1]);
            output[i - 1 - k] = found == null ? "ClassNotFoundException" : found;
        }
        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)
  1. Who is asked first?
  2. What is returned if the parent answers?

Try these next