Implement a Dependency Injection Container

A container is a map from a type to a lambda that builds it, plus a link to a parent container. You register with two methods, one for a shared instance and one for a new instance each time, you resolve with a third, and a child container can see its parent while the parent can never see the child. Everything else people expect in this answer, lazy resolution, cycle detection, startup validation, is a small addition on top of those three ideas.

Say the honest thing early. What you can write at a whiteboard is a runtime container, and Dagger exists because it does the same job at compile time. It generates the same provider lambdas as real Java, so a missing binding is a build error and not a crash on screen twelve. Naming that difference before the interviewer asks for it is most of the signal in this question.

What this really tests

Whether you know what a dependency injection framework actually does once the annotations are taken away, and whether you can tell dependency injection from a service locator. That second one is the follow up that catches people, because the two are the same container used two different ways.

What to clarify first

Ask these before you write a line. Two of them change the whole shape.

Runtime or compile time. Runtime, almost always, because a code generator is not a whiteboard exercise. Say you know the difference and that Dagger picks the other one.
Is reflection allowed. Say no even if it is. Reflection turns this into ten lines of Constructor.newInstance and answers nothing, and on Android it costs startup time and fights R8.
Are scopes in scope. If the answer is yes, and it usually is, you need child containers from the start. Retrofitting them onto a flat map is a rewrite.
Do two bindings ever share a type. Almost always yes, because a real graph has two Strings and two clients in it. That is what pushes a qualifier into the key.
Is it thread safe. On Android, yes. Two threads can hit the same singleton on the first frame.
What should a missing binding do. Fail loudly at resolution, and ideally fail at startup instead. Say both.

State the out of scope list too. Annotation processing, code generation, assisted injection, and multibindings.

The registry, and what compile time buys

A binding is a key and a way to build the thing. The key is the type plus an optional qualifier, because the type alone collides the moment two Strings are in the graph. The way to build it is a lambda that is handed the resolver, so a provider body is an ordinary constructor call whose arguments come out of the graph.

val app = container("application") {
    instance("https://api.example.com", qualifier = "baseUrl")
    single { HttpClient(get(qualifier = "baseUrl")) }  // built once, shared
    single { UserRepository(get()) }
}

val screen = app.child("profile-screen") {
    instance(userId, qualifier = "userId")
    // a new presenter per request, and the repository comes from the parent
    factory { ProfilePresenter(inject(), get(qualifier = "userId")) }
}

That is constructor injection, written by hand. There is no reflection anywhere. The type is used as a map key and nothing ever asks it for its constructors. Kotlin makes the surface pleasant with inline fun <reified T>, so the type is written once and there is no class literal in the wiring at all.

What Dagger does is write those lambdas for you at build time from the constructors it can see. The graph is the same graph. The gain is that a binding you forgot is a compile error in a generated file rather than an exception on a device, and there is no lookup at runtime because the call is direct. The cost is build time and a generated layer to read through when something is wrong. Both are real, and saying so is better than picking a side.

Scopes are containers, and the arrow points one way

The word scope means two different things, and mixing them is the most common muddle in this answer.

A lifetime is whether a binding is cached. Singleton means built once and kept, factory means built again on every request. That is a property of one binding.

A scope is a container. The application container holds what lives as long as the process. A screen container holds what lives as long as one screen, and it holds a link to the application container so it can see everything above it. The application container is never told the child exists.

That single direction is the design. A long lived singleton has no way to reach a short lived object, so the classic leak, an application singleton still holding something owned by a screen that closed twenty minutes ago, is not a bug you have to be careful about. It cannot be expressed.

There is one detail that makes it true, and it is the part most implementations get wrong. When a screen asks for something the application container owns, the application container resolves it, not the screen. Look up which container owns the binding, then run the provider against that container. If you run it against the caller instead, a provider registered up top can suddenly see a screen binding, the singleton captures it, and you have built exactly the leak you were preventing. Closing the screen container then drops its own singletons, closes anything closeable, and refuses every later resolution, and the parent is untouched.

The classes

Ten small classes, and each one is doing one job.

Key is the type plus an optional qualifier. It exists because a map keyed by type alone cannot hold two Strings, and every real graph has two Strings in it. Its toString prints the full type name, because "no binding for String" is useless and "no binding for java.lang.String named baseUrl" is a fix.
Provider is how one type gets built. A lambda handed the resolver, not an annotation. In Java it is a functional interface, in Kotlin a typealias for a function with the resolver as its receiver, which is what makes single { UserRepository(get()) } read the way it does.
Lifetime is the enum, singleton or factory. Two values, and there is no third one worth having, because everything else people call a scope is a container.
Binding is one registry entry. It holds the provider, the lifetime, the instance once there is one, and its own lock. The lock is per binding, not per container, and that is deliberate.
Resolver is the read side of the graph and the only thing a provider is handed. Splitting it from the builder means a provider cannot register a binding halfway through a resolution.
ContainerBuilder is the write side. Registration is explicit, it happens once, and the builder is thrown away when the graph goes live, so nothing can add a binding to a running container.
Container is the graph. Its own bindings, a link to its parent, and the three public verbs, resolve, validate, close.
ResolutionStack is cycle detection. The keys being built right now, held per thread, because two threads building two graphs are not a cycle.
DiException is the family, with a missing binding case and a cycle case, so a caller catches wiring failures with one clause.
Lazy is a dependency resolved on first use. In Java it is a small class. In Kotlin it is the standard library Lazy, which means it works as a property delegate and its double checked locking is already written and already correct.

A provider is handed the Resolver and not the Container, so it can ask the graph for its own arguments and cannot register anything, which is why constructor injection here is one lambda per class.

Opening a screen, step by step

A profile screen opens and asks for its presenter. Here is what happens between the objects.

The screen container is built as a child of the application container. It registers the user id as an instance binding and the presenter as a factory, so two visits to the screen never share one.
Something calls get for the presenter on the screen container. The container is open, so the lookup starts.
The container walks itself and then its parents until it finds who owns that key. The presenter is its own, so it is the owner.
The key goes on the resolution stack for this thread. If it were already there, that alone is a cycle and it throws before any recursion.
The binding is a factory, so the provider runs immediately with the owner as its resolver. The provider asks for the repository and for the user id.
The repository is not in the screen container, so the walk continues to the application container, which owns it. The application container resolves it, not the screen, which is what stops an application singleton from capturing anything short lived. It is a singleton, so it is built once under that binding's own lock and cached there.
The user id is found in the screen container itself, one step up from nothing. The presenter is constructed, the key comes off the stack, and it is handed back.

When the screen goes away, its container is closed. Its own singletons are dropped and anything closeable is closed, the application container is untouched, and any late reference that tries to resolve through the dead container gets an error naming it rather than a stale object.

Failing at launch, not on screen twelve

Three failures, and all three are worth writing.

A missing binding is found at resolution. The message carries the full type name, the qualifier, and the chain of container names that was searched, because the fix is usually to notice you registered it in the wrong container.

A cycle is found by the resolution stack. A key asked for while it is already being built can only be a cycle, and the stack from that key onward is the cycle, so the error is UserRepository -> Session -> UserRepository rather than a stack overflow two hundred frames deep. Holding it per thread matters, because two threads building two unrelated graphs would otherwise look like one. If the cycle is genuine and both sides really do need each other, making one side lazy breaks it, since the second half is resolved after the first is already built and cached.

A wiring mistake anywhere is found by validate, which resolves every binding in the container once and collects the failures rather than stopping at the first. Call it at startup and a graph with six holes in it reports six holes in one launch instead of six builds. Be honest about the cost. Validating warms every singleton, so if something in the graph is genuinely expensive to build, run it in debug builds only. This is the poor relation of what Dagger gives you for free, and saying that out loud is the right note to end on.

Service locator, and why the difference is a direction

This is the follow up, and it is not about the class, it is about who calls it. The container in this design can be used either way.

Dependency injection is when a class declares what it needs in its constructor and something else supplies it. UserRepository takes an HttpClient, has no idea a container exists, and can be built in a test with UserRepository(FakeClient()) and nothing else.

A service locator is when a class reaches into the container itself and pulls out what it needs. Now the dependency is invisible in the signature, the class imports the container, and a test has to stand up a container before it can build one object.

The rule that keeps you on the right side is a single place. Only the composition root calls get. Everything else takes constructor parameters. The container appears in the wiring file and nowhere else, and on Android the one honest exception is the Activity, because the framework constructs it and you cannot pass it anything.

Testing shows the difference immediately. With injection you often need no container at all, you construct the class with fakes. When you do want the whole graph, you register the same module and replace one binding, which is why registration has two words, one that refuses a duplicate key and one that replaces on purpose. Shadowing in a child container is the other route, and it is worth knowing that shadowing does not reach upward. A fake registered in a child cannot change what an application singleton sees, because the owner resolves. To fake something underneath a singleton you rebuild the graph with an override.

Where Hilt and Koin land on this

Both are this design with different ergonomics, so map it out loud and you have answered the last question before it is asked.

Hilt components are these child containers. SingletonComponent, ActivityRetainedComponent and ActivityComponent are a parent chain exactly like the one here, and a scope annotation is just a statement of which container owns the binding. An unscoped binding is our factory.
A Hilt module method is the provider lambda, written by you and wired by generated code rather than by a map lookup. @Binds is the same thing for the interface to implementation case, generated with no body at all.
Hilt validates at compile time, which is our validate moved to javac. That is the whole trade, build time for launch time.
Koin is almost literally this. A module is a block of registrations, single and factory are the two lifetimes, get resolves from the graph inside a provider, by inject() is our Lazy, a Koin scope is a child container tied to a lifecycle, and checkModules is validate.

Patterns actually used

Three patterns, and the interesting half is which ones to refuse.

The registry, which is the whole design. A map from a key to a way of building something. Everything else is policy on top of it.
A factory as a lambda, not a class. Every provider is a one line function. A Factory interface per type would be dozens of classes carrying nothing that the lambda does not.
A builder for registration, and here it genuinely earns its place, because it is what makes the graph immutable once it is live. This is not the tic tac toe case of a builder for three parameters, it is a mutable phase and a frozen phase with two different types.

Say no to these, and say why.

No reflection and no annotation processing. With reflection this is ten lines and demonstrates nothing. Without it every dependency is visible in a lambda you can read.
No global static container. A container held in a static field is a service locator with extra confidence, and it is the reason tests start leaking state into each other. The application owns the root container and passes it down.
No proxy based lazy resolution. A Lazy handle is explicit and one class. Generating a proxy that resolves on first method call hides the moment of construction, which is exactly the thing you want visible when a graph misbehaves.

The implementation

Both trees are the same design. A key, a binding, a container with a parent, and a builder that stops being usable once the graph is built. The sample package at the bottom of each tree is a small real graph, an application container and a screen container, so the scoping rules are something you can run rather than something you have to take on trust.

The Kotlin is a third shorter, and the reason is the API surface. Provider is a typealias for a function with the resolver as its receiver instead of an interface, registration is a lambda with a receiver so a module is an extension function on the builder, inline fun <reified T> removes every class literal, and lazy resolution is the standard library Lazy used as a property delegate rather than a class we wrote.

Java

com.androidinterview.di.Binding.java

package com.androidinterview.di;

// One entry in the registry. It knows how to build the thing, whether the
// result is kept, holds the instance once there is one, and carries its own
// lock.
//
// The lock is per binding on purpose. A single lock over the container would
// serialise every construction in the app behind whichever provider is
// slowest, and it would be held while arbitrary user code runs inside that
// provider, which is how a container deadlocks.
final class Binding<T> {

    private final Lifetime lifetime;
    private final Provider<T> provider;
    private final Object lock = new Object();

    private volatile T instance;

    Binding(Lifetime lifetime, Provider<T> provider) {
        this.lifetime = lifetime;
        this.provider = provider;
    }

    Lifetime lifetime() {
        return lifetime;
    }

    // Checked twice, and the field is volatile, which is the half people
    // forget. Without volatile a second thread can see a non null reference
    // to an object whose constructor has not finished running.
    T get(Resolver resolver) {
        if (lifetime == Lifetime.FACTORY) {
            return provider.provide(resolver);
        }
        T local = instance;
        if (local == null) {
            synchronized (lock) {
                local = instance;
                if (local == null) {
                    local = provider.provide(resolver);
                    instance = local;
                }
            }
        }
        return local;
    }

    // Called when the owning container is closed. A singleton holding a
    // socket or a thread pool gets told to let go of it. Best effort, because
    // one noisy dependency must not stop a screen scope being released.
    void release() {
        T local = instance;
        instance = null;
        if (local instanceof AutoCloseable closeable) {
            try {
                closeable.close();
            } catch (Exception ignored) {
                // Nothing useful to do here, and nothing to gain by stopping.
            }
        }
    }
}

com.androidinterview.di.Container.java

package com.androidinterview.di;

import java.util.ArrayList;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;

// The graph. A container holds its own bindings and a link to its parent, so
// a screen container can see the application container and the application
// container can never see the screen. That one direction is the whole scoping
// story. A long lived singleton has no way to reach a short lived object, so
// the classic leak, an application singleton still holding something owned by
// a screen that closed twenty minutes ago, is not a bug to be careful about.
// It is unreachable.
public final class Container implements Resolver, AutoCloseable {

    private final String name;
    private final Container parent;
    private final Map<Key, Binding<?>> bindings;

    private volatile boolean closed;

    Container(String name, Container parent, Map<Key, Binding<?>> bindings) {
        this.name = name;
        this.parent = parent;
        this.bindings = new LinkedHashMap<>(bindings);
    }

    // A child scope. It can see this container, and this container is never
    // told the child exists, which is the point.
    public ContainerBuilder child(String childName) {
        return new ContainerBuilder(childName, this);
    }

    @Override
    public <T> T get(Key key) {
        if (closed) {
            throw new DiException("container " + name + " is closed, so " + key
                + " cannot be resolved. Something outlived the scope that owns it.");
        }
        Container owner = ownerOf(key);
        if (owner == null) {
            throw new DiException.MissingBindingException(key, chain());
        }
        ResolutionStack.enter(key);
        try {
            @SuppressWarnings("unchecked")
            Binding<T> binding = (Binding<T>) owner.bindings.get(key);
            // The owner resolves, not the caller. A binding registered on the
            // application container is always built against the application
            // container, even when the request arrived through a screen, so
            // an application singleton cannot capture a screen object.
            return binding.get(owner);
        } finally {
            ResolutionStack.exit();
        }
    }

    // Resolve every binding once, so a wiring mistake fails at launch and not
    // on screen twelve on a customer's phone. Failures are collected and
    // reported together, because fixing six of these one build at a time is a
    // slow afternoon. The cost is that this warms every singleton, so on a
    // graph with something genuinely expensive in it, validate in debug only.
    public void validate() {
        List<String> failures = new ArrayList<>();
        for (Key key : bindings.keySet()) {
            try {
                get(key);
            } catch (DiException failure) {
                failures.add("  " + failure.getMessage());
            }
        }
        if (!failures.isEmpty()) {
            throw new DiException("container " + name + " has " + failures.size()
                + " broken binding(s):\n" + String.join("\n", failures));
        }
    }

    // Releasing a scope. Drop this container's singletons, close anything
    // closeable, refuse every later resolution. The parent is untouched.
    @Override
    public void close() {
        if (closed) {
            return;
        }
        closed = true;
        for (Binding<?> binding : bindings.values()) {
            binding.release();
        }
    }

    private Container ownerOf(Key key) {
        for (Container container = this; container != null; container = container.parent) {
            if (container.bindings.containsKey(key)) {
                return container;
            }
        }
        return null;
    }

    private String chain() {
        StringBuilder text = new StringBuilder();
        for (Container container = this; container != null; container = container.parent) {
            if (text.length() > 0) {
                text.append(" -> ");
            }
            text.append(container.name);
        }
        return text.toString();
    }
}

com.androidinterview.di.ContainerBuilder.java

package com.androidinterview.di;

import java.util.LinkedHashMap;
import java.util.Map;

// The write side. Registration is explicit, it happens once, and it happens
// through an object that is thrown away when the graph goes live, so nothing
// can add a binding to a running container.
public final class ContainerBuilder {

    private final String name;
    private final Container parent;
    private final Map<Key, Binding<?>> bindings = new LinkedHashMap<>();

    public ContainerBuilder(String name) {
        this(name, null);
    }

    ContainerBuilder(String name, Container parent) {
        this.name = name;
        this.parent = parent;
    }

    public <T> ContainerBuilder singleton(Class<T> type, Provider<T> provider) {
        return bind(Key.of(type), Lifetime.SINGLETON, provider);
    }

    public <T> ContainerBuilder singleton(Class<T> type, String qualifier, Provider<T> provider) {
        return bind(Key.of(type, qualifier), Lifetime.SINGLETON, provider);
    }

    public <T> ContainerBuilder factory(Class<T> type, Provider<T> provider) {
        return bind(Key.of(type), Lifetime.FACTORY, provider);
    }

    // Something already built, usually a value from outside the graph.
    public <T> ContainerBuilder instance(Class<T> type, String qualifier, T value) {
        return bind(Key.of(type, qualifier), Lifetime.SINGLETON, resolver -> value);
    }

    // The test seam. Registering the same key twice by accident is a bug and
    // doing it on purpose is a test, so they are two method names rather than
    // one method with a flag. The lifetime comes from the binding being
    // replaced, so a fake cannot quietly turn a singleton into a factory.
    public <T> ContainerBuilder override(Class<T> type, Provider<T> provider) {
        Key key = Key.of(type);
        Binding<?> existing = bindings.get(key);
        if (existing == null) {
            throw new DiException("nothing to override for " + key + " in container " + name);
        }
        bindings.put(key, new Binding<>(existing.lifetime(), provider));
        return this;
    }

    public Container build() {
        return new Container(name, parent, bindings);
    }

    private <T> ContainerBuilder bind(Key key, Lifetime lifetime, Provider<T> provider) {
        if (bindings.containsKey(key)) {
            throw new DiException("duplicate binding for " + key + " in container " + name
                + ". Use override if that was deliberate.");
        }
        bindings.put(key, new Binding<>(lifetime, provider));
        return this;
    }
}

com.androidinterview.di.DiException.java

package com.androidinterview.di;

import java.util.List;
import java.util.stream.Collectors;

// One family, so a caller can catch every wiring failure with one clause.
public class DiException extends RuntimeException {

    public DiException(String message) {
        super(message);
    }

    // Reported at resolution, with the full type name and the chain of
    // container names that was searched, so the message contains the fix.
    public static final class MissingBindingException extends DiException {

        public MissingBindingException(Key key, String chain) {
            super("no binding for " + key + ". Searched " + chain);
        }
    }

    // Reported the moment a key is asked for while it is already being built.
    // The path is the cycle itself, from the repeated key back round to it.
    public static final class CycleException extends DiException {

        public CycleException(List<Key> path) {
            super("dependency cycle "
                + path.stream().map(Key::toString).collect(Collectors.joining(" -> ")));
        }
    }
}

com.androidinterview.di.Key.java

package com.androidinterview.di;

import java.util.Objects;

// What a binding is looked up by. A type on its own is not enough, because a
// real graph has two Strings and two clients in it, so an optional qualifier
// rides along and the pair is the key.
//
// The type is held as a Class only to be compared and printed. Nothing here
// ever asks it for its constructors, which is the line between this container
// and a reflective one.
public record Key(Class<?> type, String qualifier) {

    public Key {
        Objects.requireNonNull(type, "type");
    }

    public static Key of(Class<?> type) {
        return new Key(type, null);
    }

    public static Key of(Class<?> type, String qualifier) {
        return new Key(type, qualifier);
    }

    // The full name, always. "No binding for String" is useless and "no
    // binding for java.lang.String named baseUrl" is a fix.
    @Override
    public String toString() {
        return qualifier == null ? type.getName() : type.getName() + " named " + qualifier;
    }
}

com.androidinterview.di.Lazy.java

package com.androidinterview.di;

// A dependency resolved on first use rather than at construction. Two reasons
// to want one. A screen that declares ten dependencies and touches two of
// them on a normal visit pays for two. And a pair of classes that genuinely
// need each other stops being a cycle, because the second half is resolved
// after the first is already built and cached.
public final class Lazy<T> {

    private final Resolver resolver;
    private final Key key;
    private volatile T value;

    Lazy(Resolver resolver, Key key) {
        this.resolver = resolver;
        this.key = key;
    }

    public T get() {
        T local = value;
        if (local == null) {
            synchronized (this) {
                local = value;
                if (local == null) {
                    local = resolver.get(key);
                    value = local;
                }
            }
        }
        return local;
    }
}

com.androidinterview.di.Lifetime.java

package com.androidinterview.di;

// Two lifetimes, and there is no third one worth having. Everything people
// call a scope is a container, not a lifetime.
public enum Lifetime {

    // Built once by the container that owns the binding, then cached there.
    SINGLETON,

    // Built again on every request. Nothing is cached, so nothing is retained
    // and a screen object cannot outlive the screen by accident.
    FACTORY
}

com.androidinterview.di.Provider.java

package com.androidinterview.di;

// How one type gets built. A lambda, not an annotation, and it is handed the
// resolver so that its own arguments come out of the graph. That makes
// constructor injection an ordinary constructor call,
//
//   b.singleton(UserApi.class, r -> new UserApi(r.get(HttpClient.class)))
//
// which is exactly what Dagger generates for you at compile time.
@FunctionalInterface
public interface Provider<T> {
    T provide(Resolver resolver);
}

com.androidinterview.di.ResolutionStack.java

package com.androidinterview.di;

import java.util.ArrayList;
import java.util.List;

// Cycle detection, and it is short because the data structure is right. The
// keys currently being built, per thread, since two threads building two
// graphs are not a cycle and a shared list would report one.
//
// A key asked for while it is already on the stack can only be a cycle, and
// the stack from that key onwards is the cycle, so the message writes itself
// instead of saying stack overflow from a recursion two hundred frames deep.
final class ResolutionStack {

    private static final ThreadLocal<List<Key>> ACTIVE = ThreadLocal.withInitial(ArrayList::new);

    private ResolutionStack() {
    }

    static void enter(Key key) {
        List<Key> active = ACTIVE.get();
        int start = active.indexOf(key);
        if (start >= 0) {
            List<Key> cycle = new ArrayList<>(active.subList(start, active.size()));
            cycle.add(key);
            throw new DiException.CycleException(cycle);
        }
        active.add(key);
    }

    static void exit() {
        List<Key> active = ACTIVE.get();
        active.remove(active.size() - 1);
        if (active.isEmpty()) {
            // Never leave an empty list bolted to a pooled thread.
            ACTIVE.remove();
        }
    }
}

com.androidinterview.di.Resolver.java

package com.androidinterview.di;

// The read side of the graph, and the only thing a provider is ever handed.
// Keeping it apart from the builder means a provider cannot register a
// binding halfway through a resolution, which is how a graph turns into a
// puzzle that only works if you call things in the right order.
public interface Resolver {

    <T> T get(Key key);

    default <T> T get(Class<T> type) {
        return get(Key.of(type));
    }

    default <T> T get(Class<T> type, String qualifier) {
        return get(Key.of(type, qualifier));
    }

    // A handle to something that has not been built yet.
    default <T> Lazy<T> lazy(Class<T> type) {
        return new Lazy<>(this, Key.of(type));
    }
}

com.androidinterview.di.sample.AppGraph.java

package com.androidinterview.di.sample;

import com.androidinterview.di.Container;
import com.androidinterview.di.ContainerBuilder;

// The wiring, and the only place in the codebase that knows how anything is
// built. Every provider is a lambda that pulls its own arguments out of the
// resolver, which is constructor injection written by hand.
public final class AppGraph {

    private AppGraph() {
    }

    // One reusable block of registrations, the equivalent of a Koin module.
    // It takes the builder so a test can register the same graph and then
    // replace one binding in it.
    public static void appModule(ContainerBuilder builder) {
        builder
            .singleton(HttpClient.class, r -> new HttpClient(r.get(String.class, "baseUrl")))
            .singleton(UserRepository.class, r -> new UserRepository(r.get(HttpClient.class)));
    }

    public static Container application(String baseUrl) {
        ContainerBuilder builder = new ContainerBuilder("application")
            .instance(String.class, "baseUrl", baseUrl);
        appModule(builder);
        Container application = builder.build();
        // Fail at launch, not on screen twelve.
        application.validate();
        return application;
    }

    // A screen scope. It can see the application container, the application
    // container cannot see it, and closing it releases only what it owns. The
    // presenter is a factory, so two visits never share one.
    public static Container profileScreen(Container application, String userId) {
        return application.child("profile-screen")
            .instance(String.class, "userId", userId)
            .factory(ProfilePresenter.class, r -> new ProfilePresenter(
                r.lazy(UserRepository.class), r.get(String.class, "userId")))
            .build();
    }

    // The test seam. The same module, one binding replaced, and everything
    // downstream of it is still the real class.
    public static Container underTest(HttpClient fake) {
        ContainerBuilder builder = new ContainerBuilder("test")
            .instance(String.class, "baseUrl", "http://fake");
        appModule(builder);
        builder.override(HttpClient.class, r -> fake);
        return builder.build();
    }
}

com.androidinterview.di.sample.HttpClient.java

package com.androidinterview.di.sample;

// Stands in for the network stack. It is AutoCloseable so that releasing a
// scope has something real to release.
public final class HttpClient implements AutoCloseable {

    private final String baseUrl;
    private boolean open = true;

    public HttpClient(String baseUrl) {
        this.baseUrl = baseUrl;
    }

    public String fetch(String path) {
        if (!open) {
            throw new IllegalStateException("client is closed");
        }
        return baseUrl + path;
    }

    @Override
    public void close() {
        open = false;
    }
}

com.androidinterview.di.sample.ProfilePresenter.java

package com.androidinterview.di.sample;

import com.androidinterview.di.Lazy;

// Screen scoped, and built with the id of the screen it belongs to, which is
// the reason a screen container exists at all. That id is a binding in the
// child container and nothing above it can see it. The repository arrives
// lazily, so a screen opened and closed without anyone looking at a profile
// builds nothing at all.
public final class ProfilePresenter {

    private final Lazy<UserRepository> repository;
    private final String userId;

    public ProfilePresenter(Lazy<UserRepository> repository, String userId) {
        this.repository = repository;
        this.userId = userId;
    }

    public String title() {
        return repository.get().load(userId);
    }
}

com.androidinterview.di.sample.UserRepository.java

package com.androidinterview.di.sample;

public final class UserRepository {

    private final HttpClient client;

    public UserRepository(HttpClient client) {
        this.client = client;
    }

    public String load(String id) {
        return client.fetch("/users/" + id);
    }
}

Kotlin

com.androidinterview.di.Binding.kt

package com.androidinterview.di

// One entry in the registry. It knows how to build the thing, whether the
// result is kept, holds the instance once there is one, and carries its own
// lock.
//
// The lock is per binding on purpose. A single lock over the container would
// serialise every construction in the app behind whichever provider is
// slowest, and it would be held while arbitrary user code runs inside that
// provider, which is how a container deadlocks.
class Binding<T : Any> internal constructor(
    val lifetime: Lifetime,
    private val provider: Provider<T>,
) {
    private val lock = Any()

    @Volatile
    private var instance: T? = null

    fun get(resolver: Resolver): T {
        if (lifetime == Lifetime.FACTORY) return resolver.provider()
        instance?.let { return it }
        // Checked twice, and the field is volatile, which is the half people
        // forget. Without volatile a second thread can see a non null
        // reference to an object whose constructor has not finished running.
        return synchronized(lock) {
            instance ?: resolver.provider().also { instance = it }
        }
    }

    // Called when the owning container is closed. A singleton holding a socket
    // or a thread pool gets told to let go of it. Best effort, because one
    // noisy dependency must not stop a screen scope being released.
    internal fun release() {
        val held = instance
        instance = null
        (held as? AutoCloseable)?.let { runCatching { it.close() } }
    }
}

// Cycle detection, and it is short because the data structure is right. The
// keys currently being built, per thread, since two threads building two
// graphs are not a cycle and a shared list would report one.
//
// A key asked for while it is already on the stack can only be a cycle, and
// the stack from that key onwards is the cycle, so the message writes itself
// instead of saying stack overflow from a recursion two hundred frames deep.
internal object ResolutionStack {

    private val active = ThreadLocal.withInitial { ArrayDeque<Key>() }

    fun <T> guard(key: Key, resolve: () -> T): T {
        val stack = active.get()
        val start = stack.indexOf(key)
        if (start >= 0) throw DiException.Cycle(stack.drop(start) + key)
        stack.addLast(key)
        try {
            return resolve()
        } finally {
            stack.removeLast()
            // Never leave an empty deque bolted to a pooled thread.
            if (stack.isEmpty()) active.remove()
        }
    }
}

com.androidinterview.di.Container.kt

package com.androidinterview.di

// The graph. A container holds its own bindings and a link to its parent, so
// a screen container can see the application container and the application
// container can never see the screen. That one direction is the whole scoping
// story. A long lived singleton has no way to reach a short lived object, so
// the classic leak, an application singleton still holding something owned by
// a screen that closed twenty minutes ago, is not a bug to be careful about.
// It is unreachable.
class Container internal constructor(
    private val name: String,
    private val parent: Container?,
    private val bindings: Map<Key, Binding<*>>,
) : Resolver, AutoCloseable {

    @Volatile
    private var closed = false

    override fun <T : Any> get(key: Key): T {
        if (closed) {
            throw DiException("container $name is closed, so $key cannot be resolved. " +
                "Something outlived the scope that owns it.")
        }
        val owner = ownerOf(key) ?: throw DiException.MissingBinding(key, chain())
        return ResolutionStack.guard(key) {
            @Suppress("UNCHECKED_CAST")
            val binding = owner.bindings.getValue(key) as Binding<T>
            // The owner resolves, not the caller. A binding registered on the
            // application container is always built against the application
            // container, even when the request arrived through a screen, so an
            // application singleton cannot capture a screen object.
            binding.get(owner)
        }
    }

    // A child scope. It can see this container, and this container is never
    // told the child exists, which is the point.
    fun child(name: String, block: ContainerBuilder.() -> Unit): Container =
        container(name, this, block)

    // Resolve every binding once, so a wiring mistake fails at launch and not
    // on screen twelve on a customer's phone. Failures are collected and
    // reported together, because fixing six of these one build at a time is a
    // slow afternoon. The cost is that this warms every singleton, so on a
    // graph with something genuinely expensive in it, validate in debug only.
    fun validate() {
        val failures = bindings.keys.mapNotNull { key ->
            try {
                get<Any>(key)
                null
            } catch (failure: DiException) {
                "  ${failure.message}"
            }
        }
        if (failures.isNotEmpty()) {
            throw DiException("container $name has ${failures.size} broken binding(s):\n" +
                failures.joinToString("\n"))
        }
    }

    // Releasing a scope. Drop this container's singletons, close anything
    // closeable, refuse every later resolution. The parent is untouched.
    override fun close() {
        if (closed) return
        closed = true
        bindings.values.forEach { it.release() }
    }

    private fun ownerOf(key: Key): Container? =
        generateSequence(this) { it.parent }.firstOrNull { key in it.bindings }

    private fun chain(): String =
        generateSequence(this) { it.parent }.joinToString(" -> ") { it.name }
}

// The write side. Registration is explicit, it happens once, and it happens
// inside a lambda whose receiver is thrown away when the graph goes live, so
// nothing can add a binding to a running container.
class ContainerBuilder internal constructor(private val name: String) {

    internal val bindings = LinkedHashMap<Key, Binding<*>>()

    inline fun <reified T : Any> single(qualifier: String? = null, noinline provider: Provider<T>) {
        bind(Key(T::class, qualifier), Lifetime.SINGLETON, provider)
    }

    inline fun <reified T : Any> factory(qualifier: String? = null, noinline provider: Provider<T>) {
        bind(Key(T::class, qualifier), Lifetime.FACTORY, provider)
    }

    // Something already built, usually a value from outside the graph.
    inline fun <reified T : Any> instance(value: T, qualifier: String? = null) {
        bind(Key(T::class, qualifier), Lifetime.SINGLETON) { value }
    }

    // The test seam. Registering the same key twice by accident is a bug and
    // doing it on purpose is a test, so they are two words rather than one
    // word with a flag. The lifetime comes from the binding being replaced, so
    // a fake cannot quietly turn a singleton into a factory.
    inline fun <reified T : Any> override(qualifier: String? = null, noinline provider: Provider<T>) {
        replace(Key(T::class, qualifier), provider)
    }

    fun <T : Any> bind(key: Key, lifetime: Lifetime, provider: Provider<T>) {
        if (key in bindings) {
            throw DiException("duplicate binding for $key in container $name. " +
                "Use override if that was deliberate.")
        }
        bindings[key] = Binding(lifetime, provider)
    }

    fun <T : Any> replace(key: Key, provider: Provider<T>) {
        val existing = bindings[key]
            ?: throw DiException("nothing to override for $key in container $name")
        bindings[key] = Binding(existing.lifetime, provider)
    }
}

fun container(
    name: String,
    parent: Container? = null,
    block: ContainerBuilder.() -> Unit,
): Container = Container(name, parent, ContainerBuilder(name).apply(block).bindings)

com.androidinterview.di.Key.kt

package com.androidinterview.di

import kotlin.reflect.KClass

// What a binding is looked up by. A type on its own is not enough, because a
// real graph has two Strings and two clients in it, so an optional qualifier
// rides along and the pair is the key.
//
// The KClass is only ever compared and printed. Nothing here asks it for its
// constructors, which is the line between this container and a reflective one.
data class Key(val type: KClass<*>, val qualifier: String? = null) {

    // The full name, always. "No binding for String" is useless and "no
    // binding for kotlin.String named baseUrl" is a fix.
    override fun toString(): String {
        val name = type.qualifiedName ?: type.toString()
        return if (qualifier == null) name else "$name named $qualifier"
    }
}

// Two lifetimes, and there is no third one worth having. Everything people
// call a scope is a container, not a lifetime.
enum class Lifetime {
    // Built once by the container that owns the binding, then cached there.
    SINGLETON,

    // Built again on every request, so nothing is cached and nothing retained.
    FACTORY,
}

// One family, so a caller can catch every wiring failure with one clause.
open class DiException(message: String) : RuntimeException(message) {

    // Reported at resolution, with the full type name and the chain of
    // container names that was searched, so the message contains the fix.
    class MissingBinding(key: Key, chain: String) :
        DiException("no binding for $key. Searched $chain")

    // Reported the moment a key is asked for while it is already being built.
    // The path is the cycle itself, from the repeated key back round to it.
    class Cycle(path: List<Key>) :
        DiException("dependency cycle ${path.joinToString(" -> ")}")
}

com.androidinterview.di.Resolver.kt

package com.androidinterview.di

// How one type gets built. A function with the resolver as its receiver, so a
// provider body reads as an ordinary constructor call whose arguments come
// out of the graph, `UserRepository(get())`. No interface, no annotation, no
// annotation processor.
typealias Provider<T> = Resolver.() -> T

// The read side of the graph, and the only thing a provider is ever handed.
// Keeping it apart from the registry means a provider cannot register a
// binding halfway through a resolution.
interface Resolver {
    fun <T : Any> get(key: Key): T
}

// The API a caller actually uses. Reified, so the type is written once and
// there is no class literal anywhere in the wiring.
inline fun <reified T : Any> Resolver.get(qualifier: String? = null): T =
    get(Key(T::class, qualifier))

// Lazy resolution, and in Kotlin it is the standard library's Lazy rather
// than a class of our own, so it works as a property delegate and its
// double checked locking is already written and already correct.
//
//   private val repository: UserRepository by resolver.inject()
//
// Two reasons to want it. A screen that declares ten dependencies and touches
// two of them pays for two. And a pair of classes that genuinely need each
// other stops being a cycle, because the second half resolves after the first
// is already built and cached.
inline fun <reified T : Any> Resolver.inject(qualifier: String? = null): Lazy<T> =
    lazy { get<T>(qualifier) }

com.androidinterview.di.sample.AppGraph.kt

package com.androidinterview.di.sample

import com.androidinterview.di.Container
import com.androidinterview.di.ContainerBuilder
import com.androidinterview.di.container
import com.androidinterview.di.get
import com.androidinterview.di.inject

// Stands in for the network stack. It is AutoCloseable so that releasing a
// scope has something real to release.
class HttpClient(private val baseUrl: String) : AutoCloseable {

    private var open = true

    fun fetch(path: String): String {
        check(open) { "client is closed" }
        return baseUrl + path
    }

    override fun close() {
        open = false
    }
}

class UserRepository(private val client: HttpClient) {
    fun load(id: String): String = client.fetch("/users/$id")
}

// Screen scoped, and built with the id of the screen it belongs to, which is
// the reason a screen container exists at all. That id is a binding in the
// child container and nothing above it can see it. The repository arrives as
// a Lazy and is used as a delegate, so a screen opened and closed without
// anyone looking at a profile builds nothing at all.
class ProfilePresenter(lazyRepository: Lazy<UserRepository>, private val userId: String) {

    private val repository by lazyRepository

    fun title(): String = repository.load(userId)
}

// One reusable block of registrations, the equivalent of a Koin module. It is
// an extension on the builder, so a test can register the same graph and then
// replace one binding in it.
fun ContainerBuilder.appModule() {
    single { HttpClient(get(qualifier = "baseUrl")) }
    single { UserRepository(get()) }
}

// The wiring, and the only place in the codebase that knows how anything is
// built. Every provider is a lambda that pulls its own arguments out of the
// graph, which is constructor injection written by hand.
object AppGraph {

    fun application(baseUrl: String): Container = container("application") {
        instance(baseUrl, qualifier = "baseUrl")
        appModule()
    }.also {
        // Fail at launch, not on screen twelve.
        it.validate()
    }

    // A screen scope. It can see the application container, the application
    // container cannot see it, and closing it releases only what it owns. The
    // presenter is a factory, so two visits never share one.
    fun profileScreen(application: Container, userId: String): Container =
        application.child("profile-screen") {
            instance(userId, qualifier = "userId")
            factory { ProfilePresenter(inject(), get(qualifier = "userId")) }
        }

    // The test seam. The same module, one binding replaced, and everything
    // downstream of it is still the real class.
    fun underTest(fake: HttpClient): Container = container("test") {
        instance("http://fake", qualifier = "baseUrl")
        appModule()
        override<HttpClient> { fake }
    }
}

Concurrency and edge cases

Two threads asking for the same singleton at once. This is the concurrency question, and the answer is a lock per binding with a double checked read. The field holding the instance has to be volatile, and that is the half people forget. Without it a second thread can see a non null reference to an object whose constructor has not finished running, and it will read fields that are still zero.

Say why the lock is per binding rather than one lock over the container. A container wide lock serialises every construction in the app behind whichever provider is slowest, and it is held while arbitrary user code runs inside that provider. That is how a container deadlocks. Per binding, two threads building unrelated things never meet.

Reentrancy on the same thread. A provider that resolves its own key would re enter its own lock, which succeeds, because these locks are reentrant, and then recurse forever. The resolution stack catches it first, which is a second reason to check the cycle before touching any lock.

The rest, a sentence each.

A cycle across two threads. Two threads holding one binding each and waiting for the other really can deadlock. That requires a cycle in the graph, which is why validate at startup is the fix rather than a cleverer locking scheme.
Resolving through a closed container. Refused, with the container named, because handing back an object from a screen that is gone is worse than an error.
Closing a parent while a child is alive. Nothing stops it here, and the honest answer is that scopes are released in the order they were created, innermost first, which is what a lifecycle already gives you on Android.
A factory binding that returns something closeable. The container never sees those instances again, so it cannot close them. Factories are for objects the caller owns, and if it needs closing it should be scoped.
Registering the same key twice. Refused, and the message says to use override if it was deliberate.
A qualifier that is a plain String. Fine here and a typo risk in a real codebase. The upgrade is a small value type, which is what a Dagger qualifier annotation is doing.