Uber·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Jul 2026

Summary

Uber SWE interview with a tree path palindrome problem. Pretty niche stuff, the kind of question that sounds approachable until you realize the naive solution won't cut it at 10^5 nodes.

Questions Asked (1)

Given a tree where each edge is labeled with a lowercase character, count the number of unordered pairs of distinct nodes whose path edge-characters can be rearranged to form a palindrome.

Algorithms & Data Structures

Author's notes

My first instinct was to just enumerate pairs and check each path, which obviously blows up.

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 the root to each node. For any two nodes, the path's character counts are the XOR of their root-to-node masks; the path can form a palindrome if and only if the XOR has at most one bit set. Count pairs by grouping nodes by mask and checking masks that differ by at most one bit.

Pro tip: Mention that you can optimize the counting step by using a hash map to store frequencies of each mask and then for each mask, check the mask itself and masks with one bit flipped. This reduces the time complexity to O(N * 26) after the initial DFS, which is efficient for large trees.

1. Understand the palindrome condition

A string can be rearranged into a palindrome if and only if at most one character has an odd count. For a path, this means the XOR of character parities must have at most one bit set.

2. Compute root-to-node parity masks

Perform a DFS from any root, maintaining a 26-bit mask where each bit represents the parity of a character's count along the path. Store the mask for each node.

3. Relate path mask to node masks

For any two nodes u and v, the parity mask of the path between them is mask[u] XOR mask[v]. The path is palindrome-valid if this XOR has at most one bit set.

4. Count valid pairs efficiently

Use a hash map to count frequencies of each mask. For each mask, add the frequency of the same mask (for XOR=0) and frequencies of masks that differ by exactly one bit (for XOR with one bit set). Sum and divide by 2 for unordered pairs.

5. Analyze complexity and edge cases

Time complexity is O(N * 26) due to checking 26 possible single-bit flips per node. Space is O(N) for masks and hash map. Handle large N and ensure no integer overflow.

Key Points to Mention

Palindrome rearrangement condition: at most one character with odd frequency.
Bitmask representation of character parity (26 bits for lowercase letters).
XOR operation to combine parities along paths.
Using a hash map to count mask frequencies and check single-bit differences.
Time complexity O(N * 26) and space O(N).
Handling unordered pairs by dividing by 2 or counting each pair once.

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