Loadingone moment…
Sign in to run and submit your work
Reading is open to everyone. Running code and saving drafts need an account so your work is yours and comes back on your next visit.
or
CODE WORKSPACE
A log shipper keeps its last N records in a fixed-size ring buffer. Each record gets a sequence number higher than the last (numbers can skip, for example when records are filtered), and when the buffer is full the write head wraps to slot 0 and overwrites the oldest entry. On restart the shipper must resume replay from the oldest record still in the buffer, and it has to find that slot without reading every slot.
Write oldest_index(sequence_numbers). It takes the buffer's contents in slot order as a list of distinct integers that increase and then wrap, for example [41, 42, 43, 37, 38, 39, 40]. It returns the index of the smallest sequence number, or None when the buffer is empty.
Function to write
oldest_index(sequence_numbers: list[int]) -> int | NoneThe index of the smallest sequence number, or None when the buffer is empty.
How to approach it
The right end of the range is always on the same side of the wrap as the oldest record. Compare the middle with it to know which half still contains the drop.
Sample cases
+ 3 held back until you submit
a buffer that wrapped part-way
The write head wrapped after 43, so the oldest entry, 37, sits at index 3.
Input
Argument 1
[
41,
42,
43,
37,
38,
39,
40
]Returns
3a buffer that never wrapped
No rotation at all means the oldest is index 0; comparing to the left end walks to the newest.
Input
Argument 1
[
12,
15,
18,
21,
24
]Returns
0an empty buffer
Nothing has been written yet, so there is no oldest entry and the answer is None.
Input
Argument 1
[] (empty list)
Returns
None
wrapped one slot from the end
The oldest entry is the very last slot, so the search must be able to reach index 5.
Input
Argument 1
[
205,
207,
209,
211,
213,
200
]Returns
5Constraints
sequence_numbers is an ascending list of distinct integers that may have been rotated: some suffix of the sorted list was moved to the front. It has at most one point where a value is followed by a smaller one.None.sequence_numbers.index(min(sequence_numbers)) is correct but reads every slot.Worked example
Take [41, 42, 43, 37, 38, 39, 40]. The rule is to compare the middle to the right end of the range still being searched.
low 0, high 6. Middle 3 holds 37 and the right end holds 40. 37 is not bigger than 40, so slots 3 to 6 are one increasing run and the oldest is at 3 or to its left: high becomes 3.
low 0, high 3. Middle 1 holds 42 and the right end now holds 37. 42 is bigger, so the wrap point is strictly right of 1: low becomes 2.
low 2, high 3. Middle 2 holds 43, still bigger than 37: low becomes 3. low equals high, so the answer is index 3.
The trap is comparing to the left end instead. On the buffer that never wrapped, [12, 15, 18, 21, 24], every middle is at least as big as the left end, so that version keeps moving right and returns 4, the newest record, instead of 0.
What this tests
Binary search on a rotated sorted array, where the sorted property only holds on one side of the middle and the comparison decides which side. This is LeetCode 'Find Minimum in Rotated Sorted Array' in data clothing. The target is O(log n) time and O(1) space. min() gives the right answer in O(n), and the interview question is whether you can do better. Data engineers meet this when resuming from a circular WAL or ring buffer, and when finding the rollover point in a wrapped sequence or offset counter. Its close variant, 'number of rotations in a circularly sorted array', is tagged for data engineers at AMD, Visa, Atlassian and Microsoft on Exponent, and plain 'Search in Rotated Sorted Array' is tagged at Apple, LinkedIn, Salesforce, Goldman Sachs and Oracle.
oldest_index(sequence_numbers: list[int]) -> int | NoneSubmit for review to find out what your query gets right, what it gets wrong, and how it compares with the best working query for this exercise.
This scenario runs a full workspace — editor, canvas and results side by side. It needs a laptop or desktop to be usable. Open this page on a bigger screen to start building.