Citadel · Data Structures & Algorithms

GQS SWE Whiteboard: Boundary Search + Sliding-Window Top K

TrueInterview

July 18, 2026 · 2 min read

Requirements

A discussion-focused GQS SWE phone interview with a Quant Developer interviewer. No code is produced; the round proceeds in a whiteboard-like sequence through two algorithmic questions.

Problem 1 - Boundary search with constrained APIs

Locate every occurrence of K in a sorted array.

Basic approach: use binary search to find the left and right boundaries, then return that interval.
Constraint 1: only one binary-search operation may be used. With integer arrays, using just lower_bound can still identify the range: left = lower_bound(K) and right = lower_bound(K + 1).
Constraint 2: the array's element type may not define a successor. For floats, strings, or user-defined comparable objects, K + 1 has no meaningful interpretation. The conversation therefore moves from implementation details to whether the available API can express the right boundary in O(log n) time.
The important clarification is whether the type has a clearly defined next value, or whether the API needs to provide both lower-bound and upper-bound semantics.

Problem 2 - Sliding-window top K

Given an array and a moving window, report the largest K values in every window rather than only its maximum.

Straightforward brute force: copy and sort each window, then select its top K values, giving O(n * W log W) when W denotes the window size.
A monotonic queue does not solve the problem because it retains only the maximum; entries removed to preserve monotonicity might later be required in the top-K collection.
A heap is inconvenient because taking out the largest K values disrupts the structure unless they are inserted again, while removing elements that have left the window requires additional bookkeeping.
The expected direction is a sorted structure with insert, erase, and ordered-iteration support. A balanced BST, ordered set, or ordered map provides the natural abstraction, with O(log W) updates and top-K iteration beginning at the largest values.

Notes

This is not a conventional pair-programming interview. The interviewer may keep the entire discussion focused on API design, complexity boundaries, and data-structure trade-offs.
In Problem 1, the pitfall is presuming that every ordered type has an obvious successor. A better response distinguishes binary search over indices from assumptions about values and checks whether an upper_bound operation is exposed.
In Problem 2, the interviewer steers the conversation away from isolated tricks and toward an abstract data-structure interface. Be prepared to contrast a monotonic queue, a heap with lazy deletion, a sorted list, a balanced BST / ordered multiset, and two-heap partitions without choosing an implementation prematurely.

Preparation

Practice describing lower_bound and upper_bound as API agreements rather than merely coding templates: specify the returned index, duplicate behavior, empty-range semantics, and what fails when only one primitive is provided.
Rehearse comparisons among sliding-window structures: a monotonic queue for top-1, a heap with lazy deletion, a sorted list, a balanced BST / ordered multiset, and two-heap divisions.
Practice articulating whiteboard reasoning. State the invariant, point out the unavailable operation, and determine whether the interviewer is seeking an implementable data structure or an impossibility / API-expressiveness argument.

Requirements

A discussion-focused GQS SWE phone interview with a Quant Developer interviewer. No code is produced; the round proceeds in a whiteboard-like sequence through two algorithmic questions.

Problem 1 - Boundary search with constrained APIs

Locate every occurrence of K in a sorted array.

Basic approach: use binary search to find the left and right boundaries, then return that interval.

Constraint 1: only one binary-search operation may be used. With integer arrays, using just lower_bound can still identify the range: left = lower_bound(K) and right = lower_bound(K + 1).

Constraint 2: the array's element type may not define a successor. For floats, strings, or user-defined comparable objects, K + 1 has no meaningful interpretation. The conversation therefore moves from implementation details to whether the available API can express the right boundary in O(log n) time.

The important clarification is whether the type has a clearly defined next value, or whether the API needs to provide both lower-bound and upper-bound semantics.

Problem 2 - Sliding-window top K

Given an array and a moving window, report the largest K values in every window rather than only its maximum.

Straightforward brute force: copy and sort each window, then select its top K values, giving O(n * W log W) when W denotes the window size.

A monotonic queue does not solve the problem because it retains only the maximum; entries removed to preserve monotonicity might later be required in the top-K collection.

A heap is inconvenient because taking out the largest K values disrupts the structure unless they are inserted again, while removing elements that have left the window requires additional bookkeeping.

The expected direction is a sorted structure with insert, erase, and ordered-iteration support. A balanced BST, ordered set, or ordered map provides the natural abstraction, with O(log W) updates and top-K iteration beginning at the largest values.

Notes

This is not a conventional pair-programming interview. The interviewer may keep the entire discussion focused on API design, complexity boundaries, and data-structure trade-offs.

In Problem 1, the pitfall is presuming that every ordered type has an obvious successor. A better response distinguishes binary search over indices from assumptions about values and checks whether an upper_bound operation is exposed.

In Problem 2, the interviewer steers the conversation away from isolated tricks and toward an abstract data-structure interface. Be prepared to contrast a monotonic queue, a heap with lazy deletion, a sorted list, a balanced BST / ordered multiset, and two-heap partitions without choosing an implementation prematurely.

Preparation

Practice describing lower_bound and upper_bound as API agreements rather than merely coding templates: specify the returned index, duplicate behavior, empty-range semantics, and what fails when only one primitive is provided.

Rehearse comparisons among sliding-window structures: a monotonic queue for top-1, a heap with lazy deletion, a sorted list, a balanced BST / ordered multiset, and two-heap divisions.

Practice articulating whiteboard reasoning. State the invariant, point out the unavailable operation, and determine whether the interviewer is seeking an implementable data structure or an impossibility / API-expressiveness argument.