Meta Software Engineer Interview Preparation Guide - Entry Level

Approach (brief): Prefer validating tokens locally when possible (e.g., verify JWT signature and claims). For opaque or short-lived tokens where introspection is needed, call the IdP introspection endpoint but cache results safely to reduce latency. Combine local in-memory LRU cache for hot-path, distributed cache (Redis) for cross-instance sharing, short TTLs tied to token expiry, and conservative revocation handling.

Example (Python-style middleware pseudocode):

import time, hashlib
from cachetools import TTLCache
import redis, requests

local = TTLCache(maxsize=10000, ttl=2)   # very small local TTL for hot hits
redis_client = redis.Redis(...)

INTROSPECT_URL = "https://idp.example.com/introspect"
CLIENT_AUTH = ("client_id","secret")

def token_hash(tok): return hashlib.sha256(tok.encode()).hexdigest()

def introspect(token):
    key = "ti:"+token_hash(token)
    # 1) local cache
    v = local.get(key)
    if v: return v
    # 2) redis cache
    v = redis_client.get(key)
    if v:
        local[key] = v
        return v
    # 3) fallback to IdP
    r = requests.post(INTROSPECT_URL, data={"token": token}, auth=CLIENT_AUTH, timeout=0.5)
    r.raise_for_status()
    payload = r.json()
    if payload.get("active"):
        # TTL = min(token_expiry - now, MAX_CACHE_SECONDS)
        ttl = min(payload.get("exp", int(time.time())+60) - int(time.time()), 60)
        redis_client.setex(key, ttl, payload)
        local[key] = payload
    return payload

Key design decisions and reasoning:

• Cache TTL <= token lifetime to avoid validating expired tokens. Use token "exp" to compute TTL.
• Use token hash as cache key to avoid storing raw tokens.
• Local in-memory cache reduces network hops; Redis provides cross-instance consistency.
• Keep TTLs short (seconds to a minute) for short-lived tokens to balance security vs performance.
• Use mutual TLS and client auth for introspection calls; enforce timeouts, retries with backoff, and circuit-breaker to protect IdP.
• Handle revocation: for immediate revocation, push invalidation messages (pub/sub) to clear caches; otherwise accept short TTL window.
• Stale-while-revalidate: serve slightly stale token if IdP unreachable, but only if last check was very recent and risk acceptable.
• Prefer local JWT verification (signature + KID + JWKs caching) when tokens are JWTs — avoids introspection entirely.

Security caveats:

• Never cache beyond token expiry.
• Store only necessary claims in cache; avoid persisting raw tokens.
• Audit and monitor cache hit/miss, introspection latency, and error rates.

This approach minimizes per-request latency while keeping strong guarantees by tying cache lifetimes to token expiry, using secure introspection, and supporting immediate revocation via invalidation channels.

Direct answer

With 1,000,000 daily users generating 20 API requests each and 10% of that traffic landing in the busiest hour, the expected peak load is approximately 556 requests per second (RPS). That number is entirely a function of one stated assumption (the 10% busiest-hour share), so the first thing a strong candidate does is name that assumption out loud, not hide it inside the arithmetic.

Structured elaboration

Back-of-envelope RPS estimates follow the same three-step conversion every time:

1. Total volume for the period. Multiply the population count by the per-entity activity rate to get a total (here: daily active users times requests per session).
2. Concentrate to the busiest window. Apply the stated (or measured) peak-hour share to get requests in that one hour.
3. Convert to a rate. Divide by the number of seconds in that window.

$\text{Peak RPS} = \frac{U \times r \times f}{3600}$

where $U$ is daily active users, $r$ is requests per user-session, and $f$ is the fraction of daily traffic in the busiest hour (3600 seconds).

The one hidden assumption in this formula is that traffic is roughly uniform within that busiest hour. That is a simplification, not a fact, and it is the piece a candidate should flag rather than silently bake in.

Worked example

Given: $U = 1{,}000{,}000$, $r = 20$, $f = 0.10$.

$\text{Total daily requests} = 1{,}000{,}000 \times 20 = 20{,}000{,}000$

$\text{Busiest-hour requests} = 0.10 \times 20{,}000{,}000 = 2{,}000{,}000$

$\text{Peak RPS} = \frac{2{,}000{,}000}{3600} \approx 555.6 \Rightarrow \approx 556 \text{ RPS}$

Sensitivity to the busiest-hour fraction. Because the formula is linear in $f$, changing the assumption rescales the answer directly:

$f = 0.05 \Rightarrow \frac{0.05 \times 20{,}000{,}000}{3600} \approx 278 \text{ RPS}$

$f = 0.20 \Rightarrow \frac{0.20 \times 20{,}000{,}000}{3600} \approx 1{,}111 \text{ RPS}$

Extending peak RPS to concurrency (Little's Law). Once you have a request rate, you can estimate how many requests are in flight at once if you also assume an average per-request processing time, using Little's Law: $L = \lambda \times W$, where $L$ is the average number of concurrent requests, $\lambda$ is the arrival rate (RPS), and $W$ is the average time a request spends in the system. Assume, as an illustrative input (not derived from the question), an average processing time of 150 ms:

$L_{avg} = 556 \times 0.15 \approx 83 \text{ concurrent requests}$

That average understates what you should actually provision for. If the service has a P99 latency target (the response time under which 99% of requests must complete) of, say, 500 ms rather than the 150 ms average, the concurrency implied at that tail is higher:

$L_{p99} = 556 \times 0.5 \approx 278 \text{ concurrent requests}$

Provisioning a connection pool or thread pool (a fixed, pre-allocated set of database connections or worker threads that requests share rather than each opening its own, sized to how many can be in flight at once) for the 83-request average leaves no room for the tail: any workload approaching its P99 latency target will need roughly 3x the average-case concurrency headroom in this example, purely from the average-versus-tail latency gap.

Trade-offs & pitfalls

• The 10% figure is an assumption, not a measurement. In a real system, replace it with actual traffic-shape data (hourly histograms) as soon as it exists; shipping capacity on an unvalidated guess is the most common mistake here.
• Uniform-within-the-hour is optimistic. Real traffic often has sub-minute bursts well above the hourly average; sizing to the hourly peak RPS without additional headroom under-provisions for the true instantaneous peak.
• Average latency and P99 latency imply very different concurrency needs. Using average latency alone to size a connection or thread pool is a common under-provisioning mistake once tail latency is the real constraint.
• Do not confuse this system-load estimate with a load-balancing or failover concern. This is purely about how much aggregate capacity to provision; how traffic is routed to individual servers is a separate problem.

A 10x tail-latency regression for a small percentage of requests needs a prioritized checklist that captures enough production data to diagnose without adding meaningful overhead to the traffic already struggling.

Prioritized diagnostics

1. Confirm scope first, cheaply: is the regression isolated to one endpoint, one host, one region, or a specific request shape (payload size, a particular parameter value)? A metrics-only slice-and-dice answers this before any heavier tool is needed.
2. Flamegraphs/pprof/CPU sampling, taken specifically during the tail-latency window (continuous low-overhead sampling profilers, or triggered captures when a request exceeds a latency threshold) rather than a generic always-on profile, to catch the actual slow-path code.
3. Thread states: dump thread stacks during a slow request to see if threads are blocked (lock contention, waiting on a downstream call) versus actively burning CPU, which points to very different fixes.
4. DB slow queries and I/O waits: check for a query plan regression or lock contention at the database tier, a common cause of a small-percentage-of-requests tail spike (only requests hitting a specific data shape or a specific lock are affected).

Collecting data with minimal overhead

Use sampling profilers (statistical, low-frequency) rather than full instrumentation, and trigger detailed capture (a full trace, a thread dump) only for requests that already exceed a latency threshold, rather than capturing this level of detail for every request.

What this looks like in practice

Suppose slicing the regression by request shape shows it's isolated to /checkout requests with a payload over 1 MB: p99 latency for that slice jumped from 80ms to 900ms after the deploy, while the overall /checkout p99 barely moved (85ms to 95ms), exactly the kind of tail-only regression an average-based dashboard would miss. A flamegraph captured only during that slow slice's requests then shows about 70% of sampled time inside a JSON-serialization call that wasn't on the hot path before the deploy, pointing the fix at that specific code path rather than at the endpoint in general.

Trade-offs and pitfalls

A tail-latency problem affecting a small percentage of requests is easy to miss with average-based metrics; the investigation needs percentile-based (p95/p99) metrics and threshold-triggered detailed capture specifically, or the affected slice gets averaged away and never even flagged as a regression.

Reframe it: this is not really a binary conflict

Increasing autoscaling cooldowns (the waiting period after a scaling action before scaling again, to avoid reacting to every small fluctuation) as a single global setting is a blunt instrument. DevOps's thrashing problem, rapidly scaling up and down in response to noise, is likely coming from the bulk of ordinary traffic, while Product's non-negotiable is a handful of specific, critical flows. Those two asks are usually compatible once you stop treating "the system" as one uniform thing.

How I'd resolve it

1. Segment the policy. Apply a longer cooldown broadly, which fixes the thrashing and its cost and instability, while giving the critical flows their own scaling policy, or a bit of always-on baseline capacity, with a short cooldown or none at all, so they are insulated from the broader change.
2. Quantify both sides before deciding, not just assert them. For example: if the cooldown moves from 60 seconds to 300 seconds, how many extra seconds of under-provisioned capacity could a critical flow actually see during a genuine spike, and how often has that historically happened. Compare that against the real cost of thrashing, wasted spend, instability, alert fatigue.
3. Bring that data to both sides. Show DevOps the latency-risk numbers for the critical flows so they see why a blanket setting will not work, and show Product the cost and stability data driving DevOps's request. Most "won't budge" positions soften once the other side's cost is made concrete rather than argued in the abstract.
4. If a genuine conflict remains after segmenting, for example the critical flows truly need guaranteed capacity DevOps cannot provide reactively, resolve it as a business trade-off: the cost of always-hot standby capacity for those specific flows, presented as an explicit dollar line item Product can choose to pay for.

The core move as engineering lead

The job is not to pick a winner, it is to find the axis where both requirements can be true at once, which usually exists once you separate critical from non-critical traffic, and to put a concrete number on what it costs if it genuinely does not.

Direct answer
Give the listener a short roadmap up front (what you're about to walk through and in how many steps), narrate one idea at a time in order, and periodically restate where you are relative to that roadmap, rather than free-associating through your thought process.

Structured elaboration

1. State the roadmap before diving in: "There are two things going on here: first the root cause, then the fix I'd propose. Let me start with the root cause." This gives the listener a mental container to place what follows.
2. Narrate conclusions and reasons, not raw stream-of-consciousness. Say what you're checking and why, not just what you're doing: "I'm checking the logs because I suspect this is a timeout, not a crash," rather than silently scrolling and occasionally muttering.
3. Signal transitions explicitly: "okay, that rules out X, so now let's look at Y," so the listener can track your position in the reasoning instead of having to reconstruct it after the fact.
4. Pause at natural checkpoints to check the listener is still following, especially before switching to a new sub-problem, rather than only checking in at the very end.
5. Name your assumptions out loud as you make them, since an unstated assumption is invisible to the listener and, if wrong, can make the rest of your reasoning look wrong for a reason they can't see.

Worked example
Unstructured: "Okay so let me look at this... hmm... yeah so there's this function... wait, let me check something else... okay so actually I think the issue might be... let's see... yeah I think it's the caching."

Structured: "I'm going to check three possible causes in order of likelihood: caching, a race condition, or a bad config value. Starting with caching, since it's the most common cause of this symptom... [checks] ...that rules out caching, the values are fresh. Moving to the race condition..."

The second version gives the listener the plan up front, tells them which hypothesis is being tested and why, and explicitly states when a hypothesis is ruled out, so they can follow the reasoning instead of just watching an unexplained sequence of actions.

Trade-offs and pitfalls

• Over-narrating every micro-step can slow you down and annoy a listener who just wants the conclusion; calibrate the level of narration to whether the audience needs to follow the reasoning (an interview, a mentoring session) or just wants the answer (a peer who trusts you and is short on time).
• It's easy to silently switch approaches mid-thought without saying so; if you change direction, say so explicitly ("actually, let me back up") rather than leaving the listener to notice on their own.
• This is a skill that degrades under real pressure or unfamiliar problems; it's worth practicing the "state the roadmap first" habit specifically, since it's the cheapest part to do consistently even when the rest of your thinking is genuinely uncertain.

Direct answer

A high-level architecture shows the system's scope: the major building blocks (client, API layer, service tier, datastore, cache, external dependencies), how they relate, and the non-functional constraints (scale, availability) that shaped them. A component-level design zooms into one of those blocks and specifies its interfaces, request/response schemas, data flows, and sequencing. You show the high-level view to stakeholders who need to understand what the system is and what it costs or risks; you show component-level design to the people who have to build, test, or integrate against one specific piece.

Structured elaboration

The reason both layers matter: the high-level view sets the strategy and the constraints everyone else has to work inside; the component-level view is what actually gets implemented, tested, and integrated. A good design doc keeps an explicit mapping from each high-level block down to its component-level detail, so a reviewer can move between the two without re-deriving context.

Worked example

Say you're designing a subscription billing feature. At the high level you'd draw: client apps, an API gateway, a billing service, a payments component, a database, and a message queue for async notifications, with an arrow showing the billing service calls out to a third-party payment processor. The one decision that belongs only at this level: whether billing lives inside the existing monolith or is split into its own service, because that choice affects deployment, on-call ownership, and the blast radius of an incident, not just this one feature.

At the component level, you'd zoom into just the billing service and produce: a sequence diagram for "create subscription" (client → billing service → payments component → processor → database write → event published), the exact request/response schema for the POST /subscriptions endpoint, and an entity-relationship diagram for the subscription and invoice tables. None of that detail belongs on the high-level diagram; it would bury the one decision (monolith vs separate service) that the high-level view exists to surface.

Trade-offs & pitfalls

• Showing component-level detail (full schemas, every retry path) to an executive or product stakeholder buries the one decision they actually need to weigh in on.
• Skipping the high-level view and jumping straight to component design risks locking in a boundary (a shared database, a synchronous call where an event would do) that is expensive to undo later, because it was never surfaced as a decision.
• A common weak answer just says "high-level is the big picture, low-level is the details" without naming a decision that is exclusive to one level; naming that decision is the signal an interviewer is listening for.
• Keep a living link between the two artifacts (a component-level design should reference which high-level block it belongs to) so the documentation doesn't drift apart as the system evolves.

Direct answer

The plain two-heap median trick only supports fast insertion: a binary heap (Python's heapq) can pop or peek its root in $O(\log k)$ time, but it has no operation to remove an arbitrary element buried in the middle. Once the window has to evict the oldest value, that value is almost never at either heap's root, so it cannot be deleted directly. The fix is lazy deletion: mark the departing element for removal in a side lookup, only actually pop it once it happens to surface at a heap's root, and track the two heaps' logical sizes (excluding pending-deletion entries) separately from their raw lengths, since the raw heap can be carrying stale entries at any moment.

Structured elaboration

Why removal breaks the plain design

The static two-heap median (max-heap low for the lower half, min-heap high for the upper half) relies on two things staying true after every operation: each heap's physical top is a real, present element, and the two heap sizes differ by at most one (so the median is always readable from one or both tops). Insertion preserves both properties because heapq.heappush only ever adds a real element. Eviction breaks both: the array-index-k-elements-ago value could be sitting anywhere inside either heap, heapq gives no remove(value) operation cheaper than an $O(k)$ linear scan, and even if you found it, popping from the middle of a Python list-backed heap does not preserve the heap invariant without an $O(k)$ re-heapify.

The fix: lazy deletion plus logical size tracking

1. Defer the delete. When an element leaves the window, do not touch the heaps yet. Instead record "this position is now invalid" in a lookup structure.
2. Prune only at the top. Before reading or comparing a heap's root, pop-and-discard while the root is marked invalid. This keeps every actual pop still costing $O(\log k)$; you never search the middle of the heap.
3. Track logical size, not len(heap). The rebalance step that keeps low and high within one element of each other must compare counts of live elements, because the physical heaps can be sitting on stale entries between prunes.
4. Disambiguate by position, not value. Values in the window can repeat. Tagging each heap entry with the index it came from (rather than trusting a bare value match) removes any ambiguity about which duplicate is being evicted.

Worked example

Approach

Store low entries as (-value, index) (max-heap via negation) and high entries as (value, index). A loc map remembers which heap each index currently lives in, and a removed set records indices that have left the window. add places a new index using the same comparison rule as the static design; remove marks an index removed and adjusts the logical count for whichever heap it belonged to; balance restores the size invariant and prunes stale roots as it goes.

import heapq

def median_sliding_window(nums, k):
    small, large = [], []      # small: max-heap as (-val, idx); large: min-heap as (val, idx)
    loc = {}                   # idx -> 'small' or 'large'
    removed = set()            # indices evicted from the window but not yet physically popped
    small_count = large_count = 0
    result = []

    def prune(heap):
        while heap and heap[0][1] in removed:
            heapq.heappop(heap)

    def balance():
        nonlocal small_count, large_count
        prune(small); prune(large)
        if small_count > large_count + 1:
            val, idx = heapq.heappop(small)
            small_count -= 1
            heapq.heappush(large, (-val, idx))
            loc[idx] = 'large'
            large_count += 1
            prune(small)
        elif small_count < large_count:
            val, idx = heapq.heappop(large)
            large_count -= 1
            heapq.heappush(small, (-val, idx))
            loc[idx] = 'small'
            small_count += 1
            prune(large)

    def add(i, num):
        nonlocal small_count, large_count
        if not small or num <= -small[0][0]:
            heapq.heappush(small, (-num, i)); loc[i] = 'small'; small_count += 1
        else:
            heapq.heappush(large, (num, i)); loc[i] = 'large'; large_count += 1
        balance()

    def remove(i):
        nonlocal small_count, large_count
        removed.add(i)
        if loc[i] == 'small':
            small_count -= 1
        else:
            large_count -= 1
        balance()

    n = len(nums)
    for i in range(k):
        add(i, nums[i])
    prune(small); prune(large)
    result.append(float(-small[0][0]) if k % 2 else (-small[0][0] + large[0][0]) / 2.0)

    for i in range(k, n):
        add(i, nums[i])
        remove(i - k)
        prune(small); prune(large)
        result.append(float(-small[0][0]) if k % 2 else (-small[0][0] + large[0][0]) / 2.0)

    return result

print(median_sliding_window([1, 3, -1, -3, 5, 3, 6, 7], 3))

Running this prints [1.0, -1.0, -1.0, 3.0, 5.0, 6.0]: the medians of the six windows [1,3,-1], [3,-1,-3], [-1,-3,5], [-3,5,3], [5,3,6], [3,6,7] respectively, matching a direct sort-each-window check.

Key points

• The removed set and loc map are the entire lazy-deletion mechanism; nothing else changes about how the heaps are used.
• balance() prunes both heap tops before comparing counts, since a stale entry sitting on top would otherwise make a heap look non-empty when its live top is deeper down.
• Tagging entries with index rather than raw value means duplicate values in the window never cause an ambiguous "which one left" decision.

Complexity

Time: $O(n \log k)$. Every element is pushed into a heap once when it enters, at most once moved between heaps by a balance() call during its lifetime, and popped exactly once when it is finally pruned on eviction; each of those is an $O(\log k)$ heap operation, and there are $O(n)$ elements total, so the amortized total is $O(n \log k)$.
Space: $O(k)$ for the two heaps (they can carry at most $O(k)$ live-plus-pending-stale entries at once) plus $O(k)$ for the loc map and removed set.

Edge cases

• k == 1: the window's median is just the current single element; both heaps degenerate correctly (one of them always empty).
• k == len(nums): exactly one window, equivalent to a one-shot median of the whole array.
• Duplicate values in the window: handled correctly because eviction is decided by index, not value.
• Negative numbers and mixed signs: the comparisons are on raw numeric value, unaffected by sign.

Trade-offs & pitfalls

A common shortcut is to lazily delete by value using a plain counter (value -> pending deletions) instead of tagging by index. That works until the window contains a repeated value: deciding "does this departing value belong to small or large" by comparing it against the current (possibly stale) top can silently attribute the deletion to the wrong heap when duplicates straddle the boundary, corrupting the size invariant without raising an error. Tagging by index removes that entire bug class at the cost of one extra dictionary.

A second pitfall is forgetting to re-prune immediately after balance()'s own pop/push pair; the entry it just moved can itself have been marked for lazy deletion in a pathological interleaving, and skipping the follow-up prune leaves a stale top for the next median read.

For small or bounded-range values, an alternative that avoids lazy-deletion bookkeeping entirely is an order-statistics structure, a Fenwick tree (binary indexed tree) or balanced BST over value ranks, giving $O(\log k)$ insert, delete, and median-by-rank directly. That trades the two-heap simplicity for needing coordinate compression when values are large or unbounded.

The idea in plain words

Naive recursive Fibonacci recomputes the same subproblems over and over. fib(6) asks for fib(5) and fib(4), but fib(5) also asks for fib(4), so the work for fib(4) is done twice, and the repetition compounds down the tree. Caching (remembering each answer the first time it is computed, also called memoization) removes the repeats, so each value is computed once.

The call tree for n = 6 and the call count

The program prints one line per call, indented by depth in the tree, and counts the calls.

calls = 0


def fib(n, depth=0):
    global calls
    calls += 1
    print("  " * depth + f"fib({n})")
    if n < 2:
        return n
    return fib(n - 1, depth + 1) + fib(n - 2, depth + 1)


print("value:", fib(6))
print("naive calls:", calls)

memo_calls = 0


def fib_cached(n, cache, depth=0):
    global memo_calls
    memo_calls += 1
    if n < 2:
        note = "base case"
    elif n in cache:
        note = "cache hit"
    else:
        note = "computed"
    print("  " * depth + f"fib({n})  {note}")
    if n < 2:
        return n
    if n not in cache:
        cache[n] = fib_cached(n - 1, cache, depth + 1) + fib_cached(n - 2, cache, depth + 1)
    return cache[n]


print("cached value:", fib_cached(6, {}))
print("cached calls:", memo_calls)


# call counts for growing n (naive), counted not timed
def count_calls(n):
    return 1 if n < 2 else 1 + count_calls(n - 1) + count_calls(n - 2)


def fib_loop(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a


for n in (10, 20, 30):
    print(n, count_calls(n), 2 * fib_loop(n + 1) - 1)
for n in (10, 20, 30):
    print(n, round(fib_loop(n + 1) / fib_loop(n), 4))


def cached_call_count(n):
    seen, count = {}, 0

    def go(m):
        nonlocal count
        count += 1
        if m < 2:
            return m
        if m not in seen:
            seen[m] = go(m - 1) + go(m - 2)
        return seen[m]

    go(n)
    return count


for n in (0, 1, 2, 6, 30):
    print("cached calls for n =", n, ":", cached_call_count(n))

Output:

fib(6)
  fib(5)
    fib(4)
      fib(3)
        fib(2)
          fib(1)
          fib(0)
        fib(1)
      fib(2)
        fib(1)
        fib(0)
    fib(3)
      fib(2)
        fib(1)
        fib(0)
      fib(1)
  fib(4)
    fib(3)
      fib(2)
        fib(1)
        fib(0)
      fib(1)
    fib(2)
      fib(1)
      fib(0)
value: 8
naive calls: 25
fib(6)  computed
  fib(5)  computed
    fib(4)  computed
      fib(3)  computed
        fib(2)  computed
          fib(1)  base case
          fib(0)  base case
        fib(1)  base case
      fib(2)  cache hit
    fib(3)  cache hit
  fib(4)  cache hit
cached value: 8
cached calls: 11
10 177 177
20 21891 21891
30 2692537 2692537
10 1.6182
20 1.618
30 1.618
cached calls for n = 0 : 1
cached calls for n = 1 : 1
cached calls for n = 2 : 3
cached calls for n = 6 : 11
cached calls for n = 30 : 59

The tree has 25 calls for n = 6. Counting the lines per argument: fib(6) 1, fib(5) 1, fib(4) 2, fib(3) 3, fib(2) 5, fib(1) 8, fib(0) 5, which sums to 25. Only 7 distinct values (0 through 6) are ever needed, yet fib(2) is computed 5 times and fib(3) 3 times.

The call count follows its own recurrence: calls(n) = 1 + calls(n-1) + calls(n-2) (one call for this node, plus all the calls made under each child), with calls(0) = calls(1) = 1. It solves to 2 * fib(n+1) - 1, and the reason is short. Add 1 to both sides: calls(n) + 1 = (calls(n-1) + 1) + (calls(n-2) + 1). So the sequence calls(n) + 1 obeys exactly the Fibonacci rule (each term is the sum of the previous two). Its first two terms are calls(0) + 1 = 2 and calls(1) + 1 = 2, which are 2 * fib(1) and 2 * fib(2). A sequence with the Fibonacci rule that starts at twice the Fibonacci start stays twice Fibonacci forever, so calls(n) + 1 = 2 * fib(n+1). Check for n = 6: fib(7) = 13, so 2 * 13 - 1 = 25. The first for n in (10, 20, 30) loop in the program prints the counted value next to the formula (10 177 177, 20 21891 21891, 30 2692537 2692537), and they agree (for n = 30, 2,692,537 calls, with fib(31) = 1,346,269).

Asymptotic time and space (naive version)

• Time: the call count grows like fib(n) itself. The ratio of consecutive Fibonacci numbers settles at about 1.618 (the second for n in (10, 20, 30) loop prints fib(n+1) / fib(n) as 1.6182, 1.618 and 1.618 for n = 10, 20 and 30). That number is the golden ratio, written phi, equal to (1 + sqrt(5)) / 2. So the calls grow like phi^n: every extra step of n multiplies the work by about 1.618. Growth like that is exponential (n sits in the exponent). Compare polynomial growth such as n^2 or n^3, where n is the base: doubling n multiplies n^2 work by 4, but adding just 10 to n here multiplies the work by about 123 (1.618^10). The time is O(phi^n). It is usually quoted as O(2^n), which is a looser upper bound: still true, because 1.618^n never exceeds 2^n, but not as tight as it could be. Going from n = 20 to n = 30 multiplied the calls from 21,891 to 2,692,537, about 123 times.
• Space: O(n). Time is spent on the whole tree, but the stack only holds one root-to-current path at a time, and the longest path (always taking n-1) has n frames: for n = 6 that is fib(6), fib(5), fib(4), fib(3), fib(2), fib(1).

What changes with a cache

With the cache in fib_cached, fib(6) made 11 calls instead of 25. The cached tree printed above shows where each call goes. fib(6) down to fib(2) are marked computed: the five real computations (n = 2 through 6), each done once. Every computed node makes two calls. The 11 calls break down as 5 computed, 3 base cases (fib(1) and fib(0) under fib(2), and fib(1) under fib(3)) and 3 cache hit calls: the second call of fib(4) is fib(2), the second call of fib(5) is fib(3), and the second call of fib(6) is fib(4). Each hit returns the stored value at once, without recursing, which is what cuts the tree down. For n >= 1 the cached version makes 2n - 1 calls (n = 6 gives 11, n = 1 gives 1): there are n - 1 computed nodes (n = 2 through n), each makes two calls, and every call except the first is one of those, so the total is 2(n-1) + 1. The last lines of the output count it for n = 0, 1, 2, 6 and 30 (1, 1, 3, 11, 59). The formula does not apply at n = 0, where the single call is a base case and there are no computed nodes, so the count is 1, not -1. Time drops from exponential to O(n). Space stays O(n): the recursion depth is still n, and for n >= 1 the cache holds n - 1 entries.

This is the bridge to dynamic programming: the subproblems overlap, so storing them turns a tree of repeated work into a straight line.

Edge cases and common mistakes

• fib(0) and fib(1) are the base cases (one call each). Forgetting that both are needed, or writing n == 1 only, makes fib(0) recurse into negative numbers.
• A mutable default cache (def fib(n, cache={})) is shared between calls in Python; here the cache is passed in so every top-level call starts clean.
• For n near 1000 or more, the cached recursive version needs more than Python's default limit of 1000 frames and raises RecursionError; a loop avoids it.

Running the code

python3.12 fib_calls.py

Save the program above as fib_calls.py. No packages are needed. The output is deterministic.

The idea

Given non-negative integers and a target T, ask whether some subset adds up to exactly T. Instead of trying every subset, track which sums are reachable: after looking at the first i numbers, the set of reachable sums is the set after i-1 numbers, plus each of those sums shifted up by the i-th number. This is a yes/no version of knapsack where weight and value are the same number.

The five decisions of the DP

1. What one cell means: dp[i][s] is True when some subset of the first i numbers sums to exactly s (the empty subset counts, so the sum 0 is always reachable).
2. Transition: dp[i][s] = dp[i-1][s] or (a_i <= s and dp[i-1][s - a_i]). Either a subset that ignores the i-th number already reaches s, or a subset of the first i-1 numbers reaches s - a_i and adding a_i finishes it. Those two cases cover every subset.
3. Base cases: dp[i][0] = True for every i (empty subset) and dp[0][s] = False for s > 0 (no numbers, no positive sum).
4. Fill order: i from 1 to n; inside a row, any order of s works because row i reads only row i-1.
5. Where the answer is read: dp[n][T].

The brute force decides each number in turn: take it or skip it. With all-ones numbers and a target that cannot be reached, it makes 1, 3, 7 and 15 calls (root counted) for n = 0 to 3, which is 2^(n+1) - 1. Memoizing (remembering the result of each (position, remaining sum) pair) turns the eight-ones case from 511 calls into 73. The table has (n+1)(T+1) cells.

Code

The driver prints the filled table from table (T means reachable, a dot means not), checks four methods against try-every-subset, shows the edge cases, counts cell updates as the target grows, and finishes with 500 seeded random lists that include zeros. one_row keeps a single row; bitset stores the row as the bits of one Python integer.

import random
from functools import lru_cache
from itertools import combinations

def brute(nums, target):
    return any(sum(c) == target for k in range(len(nums) + 1) for c in combinations(nums, k))

def recursive(nums, target):
    """can(i, s): can nums[i:] make exactly s?  Counts calls."""
    calls = 0
    def can(i, s):
        nonlocal calls
        calls += 1
        if s == 0:
            return True
        if i == len(nums):
            return False
        return can(i + 1, s) or (nums[i] <= s and can(i + 1, s - nums[i]))
    return can(0, target), calls

def memoized(nums, target):
    @lru_cache(maxsize=None)
    def can(i, s):
        if s == 0:
            return True
        if i == len(nums):
            return False
        return can(i + 1, s) or (nums[i] <= s and can(i + 1, s - nums[i]))
    result = can(0, target)
    info = can.cache_info()
    return result, info.hits + info.misses

def table(nums, target):
    """dp[i][s] is True when some subset of the first i numbers sums to exactly s."""
    dp = [[False] * (target + 1) for _ in range(len(nums) + 1)]
    for i in range(len(nums) + 1):
        dp[i][0] = True                          # the empty subset sums to 0
    for i in range(1, len(nums) + 1):
        a = nums[i - 1]
        for s in range(1, target + 1):
            dp[i][s] = dp[i - 1][s] or (a <= s and dp[i - 1][s - a])
    return dp

def one_row(nums, target, descending=True, counter=None):
    dp = [False] * (target + 1)
    dp[0] = True
    for a in nums:
        order = range(target, a - 1, -1) if descending else range(a, target + 1)
        for s in order:
            if counter is not None:
                counter[0] += 1
            if dp[s - a]:
                dp[s] = True
    return dp[target]

def bitset(nums, target):
    """Bit s of `bits` is 1 when sum s is reachable; shifting the OLD value avoids any direction issue."""
    bits = 1
    mask = (1 << (target + 1)) - 1
    for a in nums:
        bits |= (bits << a) & mask
    return bool(bits >> target & 1)

def show_bitset(nums, target):
    """Print the bit pattern after each number: the string is bit `target` on the left down to bit 0 on the right."""
    bits = 1
    mask = (1 << (target + 1)) - 1
    print("  start      ", format(bits, "0%db" % (target + 1)), "reachable sums: [0]")
    for a in nums:
        shifted = (bits << a) & mask
        bits |= shifted
        sums = [s for s in range(target + 1) if bits >> s & 1]
        print("  after %-2d   " % a, format(bits, "0%db" % (target + 1)), "(shifted copy", format(shifted, "0%db" % (target + 1)) + ")", "reachable sums:", sums)

print("bitset on [3, 4], target 9:")
show_bitset([3, 4], 9)

nums, target = [3, 34, 4, 12, 5, 2], 9
tbl = table(nums, target)
print("numbers", nums, "target", target)
print("dp[i][s], columns s = 0.." + str(target))
for i, row in enumerate(tbl):
    print(" i =", i, "".join("T" if x else "." for x in row))
print("answers:", brute(nums, target), tbl[-1][-1], one_row(nums, target), bitset(nums, target))
print("recursion (answer, calls):", recursive(nums, target), " memoized (answer, calls):", memoized(nums, target))
print("recursion calls with all-ones numbers and target 100, n = 0..3:", [recursive([1] * n, 100)[1] for n in range(4)])
print("eight ones, target 20 (unreachable): recursion", recursive([1] * 8, 20), " memoized", memoized([1] * 8, 20))

print("one row, low to high on [3], target 6:", one_row([3], 6, descending=False), " high to low:", one_row([3], 6), " truth:", brute([3], 6))
print("T = 0 ->", one_row([5, 7], 0), "; empty list, T = 4 ->", one_row([], 4), "; zeros are fine:", one_row([0, 0, 4], 4))

print("cell updates for 3 numbers as the target grows (the target has d digits):")
for d in (2, 3, 4, 5):
    count = [0]
    one_row([7, 11, 13], 10 ** d, counter=count)
    print("  target 10^%d -> %d updates" % (d, count[0]))

random.seed(4)
broken = 0
for _ in range(500):
    n, t = random.randint(0, 7), random.randint(0, 25)
    nums_r = [random.randint(0, 9) for _ in range(n)]
    want = brute(nums_r, t)
    assert one_row(nums_r, t) == table(nums_r, t)[-1][-1] == bitset(nums_r, t) == recursive(nums_r, t)[0] == want
    broken += one_row(nums_r, t, descending=False) != want
print("500 random lists (zeros included): all methods agree with brute force; low-to-high loop was wrong on", broken)

Output:

bitset on [3, 4], target 9:
  start       0000000001 reachable sums: [0]
  after 3     0000001001 (shifted copy 0000001000) reachable sums: [0, 3]
  after 4     0010011001 (shifted copy 0010010000) reachable sums: [0, 3, 4, 7]
numbers [3, 34, 4, 12, 5, 2] target 9
dp[i][s], columns s = 0..9
 i = 0 T.........
 i = 1 T..T......
 i = 2 T..T......
 i = 3 T..TT..T..
 i = 4 T..TT..T..
 i = 5 T..TTT.TTT
 i = 6 T.TTTTTTTT
answers: True True True True
recursion (answer, calls): (True, 17)  memoized (answer, calls): (True, 17)
recursion calls with all-ones numbers and target 100, n = 0..3: [1, 3, 7, 15]
eight ones, target 20 (unreachable): recursion (False, 511)  memoized (False, 73)
one row, low to high on [3], target 6: True  high to low: False  truth: False
T = 0 -> True ; empty list, T = 4 -> False ; zeros are fine: True
cell updates for 3 numbers as the target grows (the target has d digits):
  target 10^2 -> 272 updates
  target 10^3 -> 2972 updates
  target 10^4 -> 29972 updates
  target 10^5 -> 299972 updates
500 random lists (zeros included): all methods agree with brute force; low-to-high loop was wrong on 146

Reading the bitset lines

In the bitset, bit s of one integer is 1 when the sum s is reachable, so the integer is the whole row packed into binary. The printed strings show bit target on the left and bit 0 on the right. Three operators do the work in bits |= (bits << a) & mask:

• bits << a (left shift) slides every bit a places up, so a 1 at position s moves to position s + a. That is exactly "add a to every reachable sum". Shifting 0b1001 (sums 0 and 3) left by 4 gives 0b10010000 (sums 4 and 7).
• | (bitwise or) merges the shifted copy with the old bits, which keeps every old sum (skip the number) and adds the new ones (take it).
• & mask clears any bit above position target, so sums larger than the target are dropped and the integer stays at most T+1 bits wide.

After the loop, bits >> target & 1 shifts the integer right by target places (the >> binds tighter than &) so bit target lands in position 0, and & 1 reads it. The printed run on [3, 4] with target 9 shows the pattern after each number: sums 0 and 3 after the 3, then 0, 3, 4 and 7 after the 4.

Reading the table

For the numbers 3, 34, 4, 12, 5, 2 and target 9, row 1 reaches only 0 and 3. Row 3 adds 4, so 4 and 7 (= 3 + 4) appear. The number 34 (row 2) changes nothing because it exceeds the target, and neither does 12 (row 4). Row 5 adds 5, so 5, 8 (= 3 + 5) and 9 (= 4 + 5) appear, and dp[6][9] is True. The one-row and bitset versions print the same True.

Space and the direction of the inner loop

Row i needs only row i-1, so one list of T+1 flags is enough if the sum loop runs from T down to a: then dp[s - a] has not been touched yet by the current number. Run the other way, a number can be reused. In the driver, the list [3] with target 6 returns True when the loop runs low to high (3 + 3, using the same number twice) while the correct answer is False; across the 500 random lists the low-to-high loop gave a wrong answer on 146. The bitset version bits |= (bits << a) & mask has no direction issue because the right side is evaluated from the old integer before the assignment.

Complexity and why it is pseudo-polynomial

Table: time O(nT), space O(nT). One row or bitset: time O(nT) for the row, space O(T) (the bitset does the inner loop a machine word at a time: a machine word is the fixed-size chunk of bits, typically 64, that a CPU combines in one instruction, so one shift-and-or step handles that many sums at once and the work is about nT divided by the word size). The cost depends on the numeric value of T, not on the length of its written form. A target with d decimal digits needs about 3.3 d bits to store but T is about 10^d, so the work grows like 10^d: the update counts printed above rise from 272 to 2972, 29972 and 299972 as the target gains one digit at a time, about ten times per digit. An algorithm is polynomial when its running time is polynomial in the number of bits of the input; this one is polynomial only in the value T, hence "pseudo-polynomial". This does not contradict subset sum being NP-complete (the hardest problems among those whose yes answers can be checked quickly; no algorithm polynomial in the input's bit length is known for any of them; this is background that interviews mention, not something a candidate is expected to prove): when T is small the DP is fast, and when T has hundreds of digits it is hopeless.

Edge cases

• T = 0 returns True (the empty subset).
• An empty list with T > 0 returns False.
• Zeros are harmless: [0, 0, 4] with T = 4 returns True (the driver shows it).
• A number larger than T is skipped (the sum loop is empty).
• Negative numbers are outside the problem: the table's indices would go negative and the reachable range would no longer lie in 0..T.

Running the code

Save the listing as subset.py in the current directory, then run:
docker run --rm -v "$PWD":/w -w /w python:3.12 python subset.py

Python 3.12, standard library only.

The idea in plain words

A palindrome reads the same forwards and backwards. The obvious method picks every centre and grows outward while the two sides match. That costs O(n^2) on a string like aaaa...a, because every centre expands almost to the ends. Manacher's algorithm (1975) does the same expansion but never repeats a comparison it can already deduce. The one fact it uses: inside a palindrome, the left half is the mirror image of the right half, so what you learned about the left half tells you about the right half.

Brute force, and why it is not enough

Expand around each of the 2n-1 centres (n letters plus n-1 gaps between letters). On "a" * n an expansion runs up to n/2 steps (about n/4 on average over all centres), so the total is about n^2/2 steps, which is O(n^2). Manacher keeps the expansion but reuses earlier work to make the total O(n).

The transformed string (separators)

Even-length palindromes (abba) have a gap as centre, odd ones (aba) have a letter. Treating both cases separately doubles the code. Inserting a separator character between every letter and at both ends turns abba into #a#b#b#a#, where every palindrome has a real character as its centre and odd length. The separator can be any character, even one that appears in the input: when two positions are mirrors of each other around a centre, their indices have the same parity, so a separator is only ever compared with a separator and a letter only with a letter.

Define radius[i] as how far the palindrome centred at index i of the transformed string extends on each side. This number equals the length of the palindrome in the original string. For example, radius = 3 at the b in #a#b#a# means the original palindrome is aba, of length 3. The starting index in the original string is (i - radius[i]) // 2.

The mirror property and the right edge

Keep center and right: the centre and right edge of the palindrome that reaches furthest right so far. For a new index i <= right, its mirror is j = 2*center - i, the same distance left of center. Because the big palindrome is symmetric, the palindrome around j is copied around i, with one limit: only the part inside the big palindrome is guaranteed. So:

Two cases follow:

• If radius[j] is smaller than right - i, the mirror palindrome lies strictly inside the big one, and it cannot grow: the characters just outside it differ (otherwise it would have been longer), and by symmetry the same holds at i. The expansion test fails at once.
• If radius[j] >= right - i, only right - i is certain. The loop tries to extend beyond right, and every successful comparison there pushes right further.

A drawn example from the trace: in t = #a#b#a#c#a#b#a#d#, once i=7 (c) has radius 7 the big palindrome spans indices 0 to 14 (#a#b#a#c#a#b#a#). Take i=9: its mirror is j = 2*7 - 9 = 5.

t[0..14]   = # a # b # a # c # a # b # a #
big palindrome: centre 7, right edge 14
j = 5:   t[4..6] = "#a#" is the palindrome around j, radius[5] = 1
         the characters just outside it are t[3] = 'b' and t[7] = 'c' (different)
i = 9:   right - i = 14 - 9 = 5, radius[5] = 1 is smaller
         the mirrored outside characters are t[11] = 'b' and t[7] = 'c' (different)

Because the palindrome around j stopped at a mismatch inside the big palindrome, the palindrome around i stops at the mirrored mismatch, so radius[9] = 1 with no growth: the printed copied=1 final=1.

The code

def longest_palindrome(s: str, trace: bool = False) -> str:
    if not s:
        return ""
    t = "#" + "#".join(s) + "#"          # separators make every palindrome odd length
    n = len(t)
    radius = [0] * n                      # radius[i]: palindrome in t centred at i spans i-r..i+r
    center = right = 0                    # centre and right edge of the rightmost palindrome seen
    for i in range(n):
        if i <= right:
            mirror = 2 * center - i
            radius[i] = min(right - i, radius[mirror])   # reuse, never past the known edge
        start = radius[i]
        while (i - radius[i] - 1 >= 0 and i + radius[i] + 1 < n
               and t[i - radius[i] - 1] == t[i + radius[i] + 1]):
            radius[i] += 1                # only fresh comparisons happen here
        if i + radius[i] > right:
            center, right = i, i + radius[i]
        if trace:
            print(f"i={i:2d} t[i]={t[i]!r} copied={start} final={radius[i]} "
                  f"center={center} right={right}")
    best = max(range(n), key=lambda i: radius[i])   # first maximum = leftmost
    first = (best - radius[best]) // 2
    return s[first:first + radius[best]]


if __name__ == "__main__":
    print(longest_palindrome("abacabad", trace=True))
    for word in ["", "a", "ab", "babad", "cbbd", "forgeeksskeegfor", "aaaa"]:
        print(repr(word), "->", repr(longest_palindrome(word)))

Output:

i= 0 t[i]='#' copied=0 final=0 center=0 right=0
i= 1 t[i]='a' copied=0 final=1 center=1 right=2
i= 2 t[i]='#' copied=0 final=0 center=1 right=2
i= 3 t[i]='b' copied=0 final=3 center=3 right=6
i= 4 t[i]='#' copied=0 final=0 center=3 right=6
i= 5 t[i]='a' copied=1 final=1 center=3 right=6
i= 6 t[i]='#' copied=0 final=0 center=3 right=6
i= 7 t[i]='c' copied=0 final=7 center=7 right=14
i= 8 t[i]='#' copied=0 final=0 center=7 right=14
i= 9 t[i]='a' copied=1 final=1 center=7 right=14
i=10 t[i]='#' copied=0 final=0 center=7 right=14
i=11 t[i]='b' copied=3 final=3 center=7 right=14
i=12 t[i]='#' copied=0 final=0 center=7 right=14
i=13 t[i]='a' copied=1 final=1 center=7 right=14
i=14 t[i]='#' copied=0 final=0 center=7 right=14
i=15 t[i]='d' copied=0 final=1 center=15 right=16
i=16 t[i]='#' copied=0 final=0 center=15 right=16
abacaba
'' -> ''
'a' -> 'a'
'ab' -> 'a'
'babad' -> 'bab'
'cbbd' -> 'bb'
'forgeeksskeegfor' -> 'geeksskeeg'
'aaaa' -> 'aaaa'

Worked trace on abacabad

The transformed string is #a#b#a#c#a#b#a#d#. In the printed lines, copied is the value taken from the mirror before any new comparison and final is the radius after expansion.

• i=3 (b), i=7 (c): right is behind i, nothing to reuse (copied=0), so the loop compares fresh characters and grows to radius 3 and radius 7. After i=7 the window reaches right=14.
• i=9 (a), i=13 (a): the mirrors have radius 1 and right - i is 5 and 1, so the copied value is 1 and the first expansion test fails at once.
• i=11 (b): the mirror has radius 3 and right - i is exactly 3. The copy is the largest safe value, and one extra comparison (c against d) fails.
• Largest radius is 7 at i=7, so the start is (7 - 7) // 2 = 0 and the answer is s[0:7], which is abacaba.

Complexity

Time O(n). The pointer right never moves left. A comparison either succeeds, which moves right forward (and right can advance at most 2n times in total), or fails, which ends the loop for that index (one failure per index). So the total is at most about 4n comparisons. Space O(n) for the transformed string and the radius array (about 2n+1 entries each). Building t with "#".join is O(n).

Edge cases and common mistakes

• Empty string: returned early. One letter: the answer is that letter. No repeated letters (ab): the first letter, the leftmost maximum, because max returns the first index with the largest radius.
• All-equal letters (aaaa) is the case that makes naive expansion quadratic; the output above shows it returns the whole string.
• Common mistakes: forgetting the min(right - i, ...) cap, so the copy overruns the known palindrome and gives wrong answers; forgetting to guard the bounds of t in the expansion loop (dropping the right-hand check raises an IndexError; dropping the left-hand check is worse in Python, because index -1 wraps to the last character, so when the input itself contains # it silently returns a wrong palindrome: b#b# gives # instead of b#b); converting indices back with i // 2 instead of (i - radius) // 2; using the quadratic expansion and claiming linear time.

Going further: palindromic tree (eertree) for distinct palindromes and their counts

A typical interview for this question needs Manacher, the transformed string and the complexity argument above. The palindromic tree below answers a different question (counting palindromes) and goes deeper than an interview usually asks.

Manacher answers "longest palindrome" and "is s[i:j] a palindrome" in O(1) after the pass. For "how many distinct palindromic substrings are there, and how often does each occur", a palindromic tree (also called an eertree) is the standard tool. Each node is one distinct palindrome. An edge labelled c from node P leads to the palindrome cPc. Each node also has a suffix link to its longest proper palindromic suffix (the longest palindrome that is a suffix of this node's palindrome but is not the whole of it; for aba it is a). Two roots start it: an imaginary root of length -1 (wrapping a letter around it gives a palindrome of length -1 + 2 = 1, the single letter) and a root of length 0 (the empty string; wrapping a letter around it gives a two-letter palindrome such as aa). Appending one letter adds at most one new node, so the tree has at most n+2 nodes and the number of distinct palindromic substrings is the number of nodes minus 2.

class PalindromicTree:
    """Node 0: length -1 (imaginary root). Node 1: length 0 (empty string)."""

    def __init__(self, s: str, trace: bool = False):
        self.s = s
        self.length = [-1, 0]
        self.link = [0, 0]
        self.next = [{}, {}]
        self.count = [0, 0]
        self.name = ["", ""]    # the palindrome each node stands for (both roots have no letters)
        show = lambda n: self.name[n] if n > 1 else ("<length -1 root>" if n == 0 else "<empty>")
        last = 1
        for i, ch in enumerate(s):
            cur = last
            while not (i - self.length[cur] - 1 >= 0 and s[i - self.length[cur] - 1] == ch):
                cur = self.link[cur]
            if ch in self.next[cur]:
                last = self.next[cur][ch]
                if trace:
                    print(f"i={i} {ch!r}: wrap {show(cur)} -> {self.name[last]!r} exists already")
            else:
                node = len(self.length)
                self.length.append(self.length[cur] + 2)
                self.next.append({})
                self.count.append(0)
                self.name.append(ch if self.length[cur] == -1 else ch + self.name[cur] + ch)
                if self.length[node] == 1:
                    self.link.append(1)
                else:
                    probe = self.link[cur]
                    while not (i - self.length[probe] - 1 >= 0 and s[i - self.length[probe] - 1] == ch):
                        probe = self.link[probe]
                    self.link.append(self.next[probe][ch])
                self.next[cur][ch] = node
                last = node
                if trace:
                    print(f"i={i} {ch!r}: wrap {show(cur)} -> new node {self.name[node]!r}, "
                          f"suffix link -> {show(self.link[node])!r}")
            self.count[last] += 1
        for node in range(len(self.length) - 1, 1, -1):   # push counts down the suffix links
            self.count[self.link[node]] += self.count[node]

    def distinct(self) -> int:
        return len(self.length) - 2

    def total_palindromic_substrings(self) -> int:
        return sum(self.count[2:])


if __name__ == "__main__":
    PalindromicTree("aabaa", trace=True)
    for word in ["abacaba", "aaaa", "abc", "eertree"]:
        tree = PalindromicTree(word)
        print(word, "distinct:", tree.distinct(), "all occurrences:", tree.total_palindromic_substrings())

Output:

i=0 'a': wrap <length -1 root> -> new node 'a', suffix link -> '<empty>'
i=1 'a': wrap <empty> -> new node 'aa', suffix link -> 'a'
i=2 'b': wrap <length -1 root> -> new node 'b', suffix link -> '<empty>'
i=3 'a': wrap b -> new node 'aba', suffix link -> 'a'
i=4 'a': wrap aba -> new node 'aabaa', suffix link -> 'aa'
abacaba distinct: 7 all occurrences: 12
aaaa distinct: 4 all occurrences: 10
abc distinct: 3 all occurrences: 3
eertree distinct: 7 all occurrences: 12

For abacaba the seven distinct palindromes are a, b, c, aba, aca, bacab, abacaba, and counting every occurrence gives 12. For aaaa the distinct palindromes are a, aa, aaa, aaaa and the occurrences are 4 + 3 + 2 + 1 = 10. Construction takes O(n) steps in total (counted over the whole run: the walk along suffix links is paid for by the lengths of the palindromic suffixes), and each step does one dictionary lookup, which takes constant time on average, so the expected time is O(n) and the space is O(n). The count array is filled in a second pass by adding each node's count into its suffix link, so each node ends with its total number of occurrences.

Building it on aabaa

The first five lines of the output come from PalindromicTree("aabaa", trace=True). At each letter the code takes the longest palindromic suffix found so far (the previous last node) and, following suffix links when needed, the first palindrome that the new letter can wrap: the letter just before that palindrome must equal the new letter. The roots make the two basic cases work: wrapping the length -1 root gives the one-letter palindrome (-1 + 2 = 1) and wrapping the empty root gives a two-letter one.

• i=0, a: wrap the length -1 root, new node a. A one-letter palindrome's suffix link is the empty root.
• i=1, a: the longest palindromic suffix is a, but there is no letter before that a inside the text (the index would be -1), so the code follows the suffix link of a to the empty root; the letter just before the empty palindrome is s[0] = a, which matches, so it wraps the empty root: new node aa. Its suffix link is a.
• i=2, b: the walk ends at the length -1 root again, new node b.
• i=3, a: the longest palindromic suffix of aab is b, and the letter before b is a, so wrap b: new node aba. Its suffix link: the proper palindromic suffixes of aba are a and the empty string, the longest is a.
• i=4, a: wrap aba (the letter before it is a): new node aabaa. Its proper palindromic suffixes are aa, a, the empty string; the code finds the longest by probing from the link of aba (a): the letter before that a is b, not a, so it hops to the empty root, where the letter before is a, giving aa. Printed as suffix link -> 'aa'.

Every letter either creates one node or finds an existing one, so five letters give at most five nodes, and the palindromes a, aa, b, aba, aabaa are the five distinct palindromic substrings.

Running the code

# save the two listings as manacher.py and palindromic_tree.py (Python 3.12, standard library only)
python manacher.py
python palindromic_tree.py