← Sprinter Health Interview Insights

Sprinter Health·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say
Jun 2026

Summary

Coding screen for a software engineer role at Sprinter Health. One algorithmic problem, binary search flavored, nothing too wild but it does require knowing your stdlib well.

Questions Asked (1)

Q1

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 naive loop solution pops into your head immediately and you have to actively stop yourself from writing it.

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 any occurrence, then expand left and right with binary searches to find boundaries, but be careful about worst-case O(N) if the target appears many times. Instead, explicitly implement two binary searches for first and last occurrence to guarantee O(log N).

1. Clarify requirements and edge cases

Confirm that the list is sorted, may contain duplicates, and that the target may or may not be present. Discuss edge cases like empty list, target smaller than all elements, or larger than all elements.

2. Design binary search for first occurrence

Modify standard binary search to find the leftmost index where the target appears. When the middle element equals the target, continue searching in the left half to find an earlier occurrence.

3. Design binary search for last occurrence

Similarly, modify binary search to find the rightmost index where the target appears. When the middle element equals the target, continue searching in the right half to find a later occurrence.

4. Compute count and handle absence

If either search returns -1 (target not found), return 0. Otherwise, return lastIndex - firstIndex + 1.

5. Analyze complexity and test

Explain that each binary search takes O(log N) time, so total time is O(log N) and space is O(1). Walk through a small example to verify correctness.

Key Points to Mention

  • Binary search is the optimal approach for sorted arrays to achieve O(log N) time.
  • Finding first and last occurrence requires careful handling of the equality condition to continue searching in the correct half.
  • The count is simply lastIndex - firstIndex + 1 when the target is present.
  • Edge cases: empty array, target not present, all elements equal to target.
  • Time complexity: O(log N) for two binary searches; space complexity: O(1) iterative.
  • Avoid linear scan after finding one occurrence, as it could degrade to O(N) in worst case.

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