Uber·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Jun 2026

Summary

Uber SWE interview with a tree path problem that's basically a twist on a known LeetCode problem. Not the hardest round I've had but definitely requires you to know your bitmask tricks cold.

Questions Asked (1)

You're given a tree (as a list of edges) rooted at node 0, where each node holds a lowercase letter. For each query node, count how many paths from that node up to the root have a character multiset that can be rearranged into a palindrome (at most one character with odd frequency).

Algorithms & Data Structures

Author's notes

I recognized the palindrome-via-bitmask pattern pretty quickly since I'd seen something similar before, but the node-vs-edge distinction tripped me up for a bit.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use a bitmask to represent the parity of character counts along the path from root to each node. For each query node, count the number of ancestors (including itself) whose bitmask differs by at most one bit from the node's bitmask, using a frequency map during DFS.

Pro tip: Precompute answers for all nodes in a single DFS to handle multiple queries efficiently, and use a hash map to store bitmask frequencies along the current path.

1. Define State Representation

Represent the character parity of a path as a 26-bit integer (bitmask), where each bit indicates whether the corresponding letter appears an odd number of times.

2. DFS Traversal with Frequency Map

Perform a DFS from the root, maintaining the current bitmask and a frequency map of bitmasks seen along the path from root to the current node.

3. Count Valid Ancestors

At each node, count how many ancestors (including itself) have a bitmask that differs by at most one bit from the current node's bitmask, using the frequency map.

4. Store and Return Answers

Store the count for each node as the answer for that node, and after DFS, return the answers for the queried nodes.

Key Points to Mention

Palindrome condition: at most one character with odd frequency.
Bitmask representation of character parities (26 bits).
XOR operation to update bitmask when moving along an edge.
Frequency map to count bitmasks along the current path.
Checking bitmasks that differ by 0 or 1 bit (using XOR with 0 and each single-bit mask).
Time complexity: O(26 * N) for preprocessing, O(1) per query.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.