← Walmart Interview Insights

Walmart·Software Engineer·Technical Phone Screen·Senior

SeniorRejected
Apr 2026Remote

Summary

First technical screen for a senior backend role at a product-based company. It was a live code pair session and it did not go well. After a resume walkthrough, I got hit with a leetcode hard tree problem and basically froze.

Questions Asked (1)

Q1

Given a tree with node values, find the minimum possible score after removing two edges to split the tree into three components, where the score is defined as the difference between the maximum and minimum XOR values of the three subtrees.

Algorithms & Data Structures
Author's notes

Couldn't even get a brute force sketch on the board.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, compute the XOR of every subtree using a post-order traversal. Then, for each pair of edges, compute the XORs of the three resulting components and track the minimum difference between max and min. To optimize, use a hash map to store subtree XORs and check for complementary values that yield a balanced split.

Pro tip: Clarify that the tree is rooted arbitrarily (e.g., at node 1) and that removing two edges always yields three connected components. Mention that the XOR of a component is the XOR of all node values in that component, and that the total XOR is the XOR of the three component XORs.

1. Understand the problem and define terms

Restate the problem: given a tree, remove two edges to get three components; score = max XOR - min XOR of the three components. Clarify that XOR is bitwise XOR of all node values in a component.

2. Compute subtree XORs

Root the tree arbitrarily. Perform a post-order DFS to compute the XOR of each subtree. Store these values in a hash map for quick lookup.

3. Enumerate edge pairs efficiently

For each edge (u, v) where v is a child, consider removing it. The component containing v has XOR = subtreeXor[v]. The rest of the tree has XOR = totalXor ^ subtreeXor[v]. Then, for the remaining tree, consider removing another edge to split it into two components. Use the hash map to find a subtree XOR that, when removed, yields a balanced split.

4. Compute score and track minimum

For each valid pair of edges, compute the three component XORs, then compute max - min. Keep track of the minimum score found.

5. Optimize and handle edge cases

Use a hash map to avoid O(n^2) by checking for complementary XOR values. Handle cases where the tree has fewer than 3 nodes (impossible) and ensure the two edges are distinct and not adjacent in a way that creates an empty component.

Key Points to Mention

  • Subtree XOR computation using post-order traversal
  • Total XOR of the tree and its relation to component XORs
  • Using a hash map to store subtree XORs for O(1) lookups
  • Enumerating edge pairs and computing component XORs efficiently
  • Time complexity: O(n) or O(n log n) with optimization, space complexity: O(n)
  • Handling edge cases: tree size, edge distinctness, and component connectivity

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