Palantir's Package Manager Concurrency Question

Palantir often hands you working code and asks you to make it better, not to invent an algorithm. This package manager question is a recurring on-site: a blocking lookup across repositories that you make concurrent with futures, then tighten for latency and memory. Here is the full question, Java for each stage, and the rubric.

The question

Stage 1 · Understand the blocking version

The original calls each repository and waits on the result before moving on. With R repositories and latency T per call, a miss on the first few costs you roughly R times T. Name that before touching it.

// Stage 1: blocking - we wait on EACH repository before trying the next.
Package getPackage(String name) {
    for (Repository repo : repositories) {
        try {
            Future<Package> f = getPackageFuture(repo, name);
            return f.get();                 // blocks here on every repo
        } catch (Exception e) {
            // not in this repo; try the next
        }
    }
    throw new NoSuchElementException("Package not found: " + name);
}

Stage 2 · Fire the lookups first, then drain

Submit every lookup before waiting on any. Now the network calls overlap, so total latency is closer to the slowest single repository than the sum.

// Stage 2: launch all lookups, then collect; calls now run in parallel.
Package getPackage(String name) {
    List<Future<Package>> futures = new ArrayList<>();
    for (Repository repo : repositories) futures.add(getPackageFuture(repo, name));
    for (Future<Package> f : futures) {
        try { return f.get(); } catch (Exception e) { /* try the next */ }
    }
    throw new NoSuchElementException("Package not found: " + name);
}

This still returns results in list order. If the first repository is slow but does not have the package, you wait on it before checking faster ones. Stage 3 fixes that.

Stage 3 · Return on first success, and cache

Use a completion service so you take whichever lookup finishes first. Then cache which repository holds a package, not the package itself, because packages are large and the repository mapping is small and stable.

private final Map<String, Repository> repoCache = new ConcurrentHashMap<>();

Package getPackage(String name) throws Exception {
    Repository cached = repoCache.get(name);
    if (cached != null) return getPackageFuture(cached, name).get();

    ExecutorService pool = Executors.newFixedThreadPool(repositories.size());
    CompletionService<Package> cs = new ExecutorCompletionService<>(pool);
    Map<Future<Package>, Repository> origin = new IdentityHashMap<>();
    for (Repository repo : repositories) origin.put(cs.submit(() -> repo.get(name)), repo);
    try {
        for (int i = 0; i < repositories.size(); i++) {
            Future<Package> done = cs.take();          // next lookup to finish
            try {
                Package pkg = done.get();
                if (pkg != null) { repoCache.put(name, origin.get(done)); return pkg; }
            } catch (Exception ignore) { /* this repo failed; keep waiting */ }
        }
        throw new NoSuchElementException("Package not found: " + name);
    } finally {
        pool.shutdownNow();                            // never leak the pool
    }
}

The caching note is a real Palantir hint: do not cache packages (too big), cache which repository contains the package. That single decision is what separates a passing answer from a strong one.

How Palantir scores it

Palantir interview FAQ