Sprinter Health·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Jun 2026

Summary

Coding round at Sprinter Health for a software engineer role. One algorithmic question, fairly focused, felt like a standard technical screen.

Questions Asked (1)

Given a sorted list of integers and a target value, count how many times the target appears. Your solution must run in O(log N) time.

Algorithms & Data Structures

Author's notes

The O(log N) constraint is what makes this non-trivial.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use binary search to find the first and last occurrence of the target, then compute the count as last - first + 1. This achieves O(log N) time by leveraging the sorted property and avoiding linear scans.

Pro tip: Mention that you can use a single binary search to find the first occurrence and then another to find the last, or modify binary search to find the insertion point of target and target+1. Also, clarify edge cases like empty array or target not present.

1. Clarify requirements and edge cases

Confirm the input is sorted, discuss handling of empty array, target not present, and potential duplicates. Ask about integer overflow or large inputs.

2. Outline binary search approach

Explain that you'll perform two binary searches: one for the first occurrence and one for the last occurrence. Alternatively, use binary search to find the lower bound (first index where target appears) and upper bound (first index where target+1 appears).

3. Detail the binary search logic

For first occurrence: when target is found, continue searching left. For last occurrence: continue searching right. Or, implement a lower_bound function that returns the first index where element >= target, and call it for target and target+1.

4. Compute the count and handle edge cases

If first occurrence is -1 (not found), return 0. Otherwise, count = last - first + 1. Ensure indices are within bounds.

5. Analyze complexity and test

State time complexity O(log N) and space O(1). Walk through examples like [1,2,2,2,3] with target 2, and edge cases like target not present or all elements equal.

Key Points to Mention

Binary search is optimal for sorted arrays, achieving O(log N) time.
Two binary searches: one for first occurrence, one for last occurrence.
Alternative: use lower_bound for target and target+1 to get range.
Handle edge cases: empty array, target not found, all elements equal to target.
Time complexity: O(log N), space complexity: O(1).
Avoid linear scan; emphasize the importance of O(log N) requirement.

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