Capital One·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

May 2026Remote

Summary

Capital One coding round, one problem the whole time. Pretty standard array manipulation question but the follow-up about non-zero colors tripped me up more than I expected.

Questions Asked (1)

You have a zero-initialized array of length n and a sequence of update queries, each setting a specific index to a given color. After each update, return the count of adjacent index pairs where both neighbors share the same non-zero color.

Algorithms & Data Structures

Author's notes

I got the basic structure pretty fast, the part that slowed me down was handling the non-zero constraint.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Maintain a running count of adjacent equal non-zero color pairs. For each update, adjust the count by checking the neighbors of the updated index before and after the color change, updating the count based on whether each neighbor pair transitions from equal to unequal or vice versa. This yields O(1) time per update after O(1) initialization.

Pro tip: Explicitly handle edge cases like index 0 or n-1 (only one neighbor) and updates that set a color to the same value (no change). Also, clarify that 'adjacent index pairs' means pairs (i, i+1) for i from 0 to n-2.

1. Clarify the problem

Confirm that we need to return the count after each update, and that only non-zero colors count. Ask about constraints (n, number of queries) to determine if O(1) per update is needed.

2. Design the data structure

Use an array to store the current colors and a variable to keep the running count of adjacent equal non-zero pairs.

3. Update logic

For an update at index i to color c, if the current color is already c, do nothing. Otherwise, for each neighbor j (i-1 and i+1 if they exist), check if the pair (min(i,j), max(i,j)) was previously equal and non-zero, and adjust the count accordingly. Then set the new color and re-check the pairs to add back if they become equal and non-zero.

4. Return the count

After each update, append or return the current count.

5. Analyze complexity

Time: O(1) per update, O(n) initialization. Space: O(n) for the array. This is optimal.

Key Points to Mention

Maintain a running count to avoid recomputing from scratch each time.
Only consider pairs where both colors are non-zero and equal.
Handle boundary indices (0 and n-1) carefully.
Check if the new color equals the old color to skip unnecessary work.
Update the count by removing old contributions and adding new ones for affected pairs.
Time complexity: O(1) per update, O(n) initialization; space O(n).

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