Capital One·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Jun 2026

Summary

Capital One software engineer interview with a streaming data / consecutive integers problem. Pretty clean problem once you see the pattern, but the incremental output requirement adds a wrinkle that can trip you up if you're not careful.

Questions Asked (1)

You're given a stream of integers where each integer represents an index being inserted into a set. After every insertion, return the length of the longest consecutive run currently in the set. For example, inserting [2, 3, 0, 4] one at a time should produce outputs [1, 2, 2, 3].

Algorithms & Data Structures

Author's notes

The part that got me was that you have to output after EACH insertion, not just at the end.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use a hash set to track inserted numbers and a hash map to store the length of the consecutive run each number belongs to. For each insertion, check if the number is already present; if not, compute the new run length by combining the left and right neighboring runs, then update the boundaries of the new run. Track the maximum run length seen so far and output it after each insertion.

Pro tip: Emphasize that the solution achieves O(1) average time per insertion by only updating the endpoints of the merged run, and mention that this is crucial for handling large streams efficiently.

1. Clarify requirements and edge cases

Confirm that the stream is processed one integer at a time, duplicates are ignored, and the output is the current longest consecutive run length after each insertion. Discuss edge cases like empty stream, duplicate insertions, and negative numbers.

2. Choose data structures

Select a hash set to track which numbers are present and a hash map to store the length of the consecutive run for each number (only needed at the boundaries). This allows O(1) average-time lookups and updates.

3. Define insertion logic

For each new number, if it's already in the set, skip. Otherwise, compute the left run length (map.get(num-1) or 0) and right run length (map.get(num+1) or 0). The new run length is left + right + 1. Update the map for num, num-left, and num+right to the new length.

4. Track and output the maximum

Maintain a variable for the longest run seen so far, updating it with the new run length after each insertion. After each insertion, output the current longest run length.

5. Analyze complexity and test

State that each insertion takes O(1) average time and O(n) space for the set and map. Walk through the example [2,3,0,4] to verify the outputs [1,2,2,3].

Key Points to Mention

Use of hash set for O(1) membership check and hash map for run lengths.
Only updating the boundaries of the merged run to achieve O(1) per insertion.
Handling duplicates by checking if the number is already in the set.
Tracking the maximum run length dynamically after each insertion.
Time complexity: O(1) average per insertion, O(n) total; space complexity: O(n).
Edge cases: empty stream, all duplicates, negative numbers, large stream.

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