0

Palindromic paths from a node to the root

by Frontier Interview· 1 day ago· ⑂ 0 remixes

Question: Palindromic paths from a node to the root

Companies: Uber

Difficulty: Hard

Problem statement

A storage system keeps its directories in a tree. Each directory holds one lowercase letter as a label. You are given:

  • arr: a list of n lowercase letters; arr[i] is the label of node i. Nodes are numbered 0 to n - 1, and node 0 is the root.
  • tree_from and tree_to: two lists of length n - 1. Edge k connects tree_from[k] and tree_to[k]. Edges are undirected; either end may be the parent.
  • queries: a list of m node ids.

For a query node q, look at every node v on the path from q up to the root, including q and the root. Call v good if the labels on the path from q to v (both ends included) can be rearranged into a palindrome.

Return a list where entry i is the number of good nodes for queries[i].

def palindromic_ancestor_counts(
    arr: list[str], tree_from: list[int], tree_to: list[int], queries: list[int]
) -> list[int]: ...

Constraints

  • 1 <= n <= 10^5, 1 <= m <= 10^5
  • The edges form a tree; queries may repeat.
  • The tree can be a single long chain.

Example 1

arr       = ['c', 'd', 'd', 'c']
tree_from = [0, 1, 1]
tree_to   = [1, 2, 3]
queries   = [2, 3]
output    = [3, 2]

Node 2 ('d'): "d", "dd", "ddc" all rearrange into palindromes, so 3. Node 3 ('c'): "c" works, "cd" does not, "cdc" works, so 2.

Example 2

arr       = ['a', 'a', 'b']
tree_from = [1, 2]
tree_to   = [0, 1]
queries   = [2, 0]
output    = [2, 1]

The edges are listed child-first. From node 2: "b" and "baa" work; "ba" does not.

Approach

A string can be rearranged into a palindrome exactly when at most one letter appears an odd number of times. So we never care about the order of letters on a path, only the parity of each letter's count. With 26 lowercase letters, that parity fits in a 26-bit mask.

Brute force. For each query, walk from the query node up to the root, toggling the bit for each node's letter, and count the steps where the running mask has at most one bit set (m & (m - 1) == 0). That is O(depth) per query, so O(m · n) in the worst case (a path-shaped tree with every node queried). Fine to state first; too slow at n, m = 10^5.

Prefix parity masks. Define pre[u] = XOR of the letter bits on the path from the root down to u, inclusive. For an ancestor v of q, the letters on the path q → v (both ends included) are the letters on root → q minus those on root → parent(v). So the parity mask of that path is

pre[q] XOR pre[parent(v)], with pre[parent(root)] = 0.

Call key(v) = pre[parent(v)]. The answer for q is the number of ancestors v of q (including q) with popcount(pre[q] XOR key(v)) <= 1. That means key(v) equals pre[q] or pre[q] with one bit flipped: 27 candidate masks.

One DFS with a counter. Walk the tree from the root, keeping cnt[mask] = how many nodes on the current root-to-node stack have key == mask. On entering u, add key(u) to the counter (u counts as its own ancestor), then compute

ans[u] = cnt[pre[u]] + sum over b in 0..25 of cnt[pre[u] ^ (1 << b)].

On leaving u, remove key(u). Invariant: while u is being processed, cnt holds exactly the keys of u and its ancestors. Every node's answer is computed once, so queries (including repeats) become lookups.

Two practical points the interviewer will watch for:

  • The input is an undirected edge list, so build an adjacency list and orient it by the DFS from node 0 (track the parent, do not assume treeFrom[k] is the parent).
  • Trees can be 10^5 deep. Python recursion will overflow, so use an explicit stack with an enter/exit flag.

Code

from collections import defaultdict
from typing import List


def palindromic_ancestor_counts(
    arr: List[str], tree_from: List[int], tree_to: List[int], queries: List[int]
) -> List[int]:
    n = len(arr)
    if n == 0:
        return [0] * len(queries)
    adj: List[List[int]] = [[] for _ in range(n)]
    for a, b in zip(tree_from, tree_to):
        adj[a].append(b)
        adj[b].append(a)

    bit = [1 << (ord(c) - ord("a")) for c in arr]
    flips = [1 << b for b in range(26)]
    pre = [0] * n          # parity mask of root..u
    key = [0] * n          # parity mask of root..parent(u)
    ans = [0] * n
    cnt: defaultdict[int, int] = defaultdict(int)

    # Iterative DFS: (node, parent, exiting?)
    stack = [(0, -1, False)]
    while stack:
        u, p, exiting = stack.pop()
        if exiting:
            cnt[key[u]] -= 1
            continue
        key[u] = pre[p] if p >= 0 else 0
        pre[u] = key[u] ^ bit[u]
        cnt[key[u]] += 1
        m = pre[u]
        total = cnt.get(m, 0)
        for f in flips:
            total += cnt.get(m ^ f, 0)
        ans[u] = total
        stack.append((u, p, True))
        for w in adj[u]:
            if w != p:
                stack.append((w, u, False))

    return [ans[q] for q in queries]


def brute_force(arr, tree_from, tree_to, queries):
    n = len(arr)
    adj = [[] for _ in range(n)]
    for a, b in zip(tree_from, tree_to):
        adj[a].append(b)
        adj[b].append(a)
    parent = [-1] * n
    seen = [False] * n
    seen[0] = True
    order = [0]
    for u in order:
        for w in adj[u]:
            if not seen[w]:
                seen[w] = True
                parent[w] = u
                order.append(w)
    out = []
    for q in queries:
        m, c, v = 0, 0, q
        while v != -1:
            m ^= 1 << (ord(arr[v]) - 97)
            c += m & (m - 1) == 0
            v = parent[v]
        out.append(c)
    return out

Complexity

  • Building the adjacency list: O(n) time and space.
  • DFS: each node is pushed and popped twice and does 27 hash lookups, so O(27 · n) = O(n · Σ) time with Σ = 26.
  • Queries: O(1) each after the DFS, O(m) total.
  • Space: O(n) for masks, answers, the stack and the counter (it holds at most depth-many distinct keys).

Test cases

  • arr = "x", no edges, queries = [0] → [1] (a single letter is a palindrome).
  • arr = "aab", edges 0-1, 1-2, queries = [2, 1, 0] → [2, 2, 1]. From node 2: "b" ok, "ba" no (two odd letters), "baa" ok.
  • arr = "abc", edges 0-1, 1-2, queries = [2] → [1]: only "c" works; "cb" and "cba" have too many odd letters.
  • arr = "abab", path 0-1-2-3, queries = [3] → "b" ok, "ba" no, "bab" ok, "baba" ok → [3].
  • Edges given child-first, e.g. tree_from = [1, 2], tree_to = [0, 0], arr = "zzz", queries = [1, 2] → [2, 2] (orientation comes from the root, not the edge order).
  • Repeated queries, queries = [3, 3, 3] on the previous path → [3, 3, 3].
  • A 10^5-node path of "a" → query at the deepest node returns 10^5; no recursion error.
  • Randomized trees checked against brute_force.

Follow-ups

  1. Paths between any two nodes (count pairs u, v whose path is palindromic). Use pre[u] ^ pre[v] ^ bit[lca], or the simpler trick of storing edge letters on the child so the LCA cancels (LeetCode 2791 style): one global counter of all pre values, still 27 lookups per node, O(26 · n).
  2. Online queries for arbitrary (u, ancestor v) pairs. Precompute pre once; each check is popcount(pre[u] ^ key(v)) <= 1 in O(1). Ancestry is checked with Euler tour entry/exit times.
  3. Letters change (point updates). Changing a node's letter flips one bit in pre for its whole subtree. Store pre on the Euler tour in a Fenwick tree with XOR (range-XOR, point-query), so each pair check is O(log n). Counting ancestors after updates needs heavier machinery (offline sqrt-decomposition over queries), and it is fair to say so.
  4. Return the longest palindromic upward path per query instead of a count. Keep, for each mask, the minimum depth of an ancestor with that key; the answer is depth of q minus the smallest depth among the 27 candidate masks, plus one.
  5. Larger alphabet (Unicode). Masks no longer fit in a word. Use random 64-bit hashes per character with XOR (Zobrist hashing); "at most one odd" then means h == 0 or h equals one character's hash, which needs a hash set of the alphabet's hashes, O(Σ) per node or a precomputed set lookup per candidate.

Interviewer expectations

Mid-level (L4)

  • States the "at most one odd count" rule and writes the O(depth) brute force correctly.
  • Gets to parity bitmasks with a hint and builds the tree from the undirected edge list.
  • Produces working code for small inputs.

Senior (L5)

  • Derives pre[q] XOR pre[parent(v)] unprompted and handles the "include the query node and the root" boundary cleanly.
  • Writes the single DFS with an add/remove counter and the 27-mask lookup, iteratively to avoid recursion limits.
  • Gives O(26 · n + m) and tests against a brute force on random trees.

Staff (L6+)

  • Generalizes quickly to all-pairs paths and explains why the LCA letter needs care.
  • Discusses updates (Euler tour + XOR Fenwick) and what becomes hard (counting under updates).
  • Talks about input validation (disconnected input, bad characters) and memory for 10^5–10^6 nodes.

Sign in to comment, vote or remix.