Uber Software Engineer Interview Experience — Missed the OA's Iterative-DFS Trick But Still Advanced

Today's technical screen: 5-minute self-introduction, then 20 minutes of coding:

Given a 2D grid with empty cells, robots, obstacles, and a target like [1, 1, 2, 2] — this represents each robot's distance to the nearest obstacle in the up, left, down, right directions respectively, indexed accordingly. Output a list of robot locations that fit this criteria.

Then a 30-minute deep dive on one of my projects. I got challenged on all kinds of things — they asked very detailed questions.

Q&A: 5 minutes.

For the OA, the first question was easy and the second was hard — I'd seen it in prior interview reports before. Camera required.

Using DFS would exceed the recursion stack and couldn't pass all the test cases — you had to write it iteratively. I didn't figure this out during the interview, but I still got notified to move on to the next round.

For comparison, the source post also included a similar problem (the original post referred to it by an obscured code name to dodge the forum's keyword filters), with char (a-z) living on the node instead of on the edge and different input arguments:

• int treeNodes: number of nodes of the tree
• char[] nodes: node char, nodes[0] is root
• int[] nodeFrom: start node
• int[] nodeTo: end node, nodeFrom has an edge to nodeTo[i]
• int[] queries: query to find number of paths that can form a palindrome, query[i] is the start node

This query description is really convoluted. For example: treeNodes = 4, nodes = [z, a, a, a], nodeFrom = [0, 0, 1], nodeTo = [1, 2, 3], queries = [3]

• You start from node 3(a), the path to root: 3(a) -> 1(a) -> 0(z). The paths that can form a palindrome are:
• end node = 3(a), forms palindrome "a" (a single node is always a palindrome)
• end node = 1(a), forms palindrome "aa"
• end node = 0(z), forms palindrome "aza" (so regardless of order, as long as the characters can be arranged into a palindrome it counts)
• So expected result is int[] res = [3]

import collections
import sys
# increase recursion depth to prevent deep trees from blowing the stack
sys.setrecursionlimit(200000)  # this step is important, otherwise it won't pass all test cases

def countPalindromePaths(treeNodes, nodes, nodeFrom, nodeTo, queries):
    # 1. build the graph
    adj = collections.defaultdict(list)
    for u, v in zip(nodeFrom, nodeTo):
        adj[u].append(v)
        adj[v].append(u)
    # result array, ans[i] stores the number of palindrome paths starting at node i
    ans = [0] * treeNodes
    # tracks how many times each prefix mask has appeared on the path so far (a map)
    # key is the mask, value is the count
    # initializing {0: 1} handles the case where the path extends up to the root
    # logically, this represents the root's "parent" having mask 0
    prefix_counts = collections.defaultdict(int)
    prefix_counts[0] = 1
    # u: current node
    # p: parent node
    # curr_mask: XOR sum from root to current node u
    def dfs(u, p, curr_mask):
        # 1. update the current mask
        val = ord(nodes[u]) - ord('a')
        curr_mask ^= (1 << val)
        # 2. count the valid palindrome paths ending at u going upward
        # we look for an existing prev_mask (belonging to some ancestor) such that:
        # curr_mask ^ prev_mask = 0  (every character appears an even number of times)
        # curr_mask ^ prev_mask = 2^k (exactly one character appears an odd number of times)
        count = 0
        # Case A: find a full palindrome (XOR = 0) -> prev_mask == curr_mask
        count += prefix_counts[curr_mask]
        # Case B: find a palindrome with exactly one odd character (XOR = 2^k)
        for i in range(26):
            target_mask = curr_mask ^ (1 << i)
            count += prefix_counts[target_mask]
        ans[u] = count
        # 3. add the current mask to the map for child nodes to query against
        # note: from a child v's perspective, u is the parent, so it's correct to insert u's mask here
        prefix_counts[curr_mask] += 1
        # 4. recurse into children
        for v in adj[u]:
            if v != p:
                dfs(v, u, curr_mask)
        # 5. backtrack: leaving the current node, remove its mask count
        prefix_counts[curr_mask] -= 1

    # start DFS from the root (0)
    # initial mask is 0, since no node value has been processed yet before entering dfs
    dfs(0, -1, 0)
    # return the query results
    return [ans[q] for q in queries]

# --- test case (based on the problem description) ---
treeNodes = 4
nodes = ['z', 'a', 'a', 'a']
nodeFrom = [0, 0, 1]
nodeTo = [1, 2, 3]
queries = [3]
# run
print(countPalindromePaths(treeNodes, nodes, nodeFrom, nodeTo, queries))
# expected output: [3]