InterviewDB
Experience
Reduce List - Repeatedly Remove Elements by Rule Until One Remains
phone
Interview Experience
Problem
Given a list of integers and a reduction rule, repeatedly apply the rule until only one element remains.
Return that element.
Rule: In each pass, scan left to right. Remove any element that is smaller than its right neighbor. If no element is removed in a pass, stop.
Return the last remaining element.
python
def reduce_list(nums: List[int]) -> int:
...
Example:
**Input**: [3, 1, 4, 1, 5, 9, 2, 6]
Pass 1: remove 3 (3<4)? No, 3>1. Remove 1 (1<4) -> [3,4,1,5,9,2,6]
remove 1 (1<5) -> [3,4,5,9,2,6]
remove 2 (2<6) -> [3,4,5,9,6]
Pass 2: no element < right neighbor that qualifies -> stops at [3,4,5,9,6]
**Note**: clarify exact rule with interviewer.
Simpler variant: nums=[5,3,1], remove smallest each pass
[5,3,1] -> remove 1 -> [5,3] -> remove 3 -> [5] ->
**output** 5
Follow-ups
- Prove the invariant: what property does the remaining list always satisfy after each pass?
- What is the worst-case number of passes for a list of length n?
- How does the answer change if you remove elements larger than their right neighbor instead?
- How would you parallelize the reduction using a segment tree?
Full Details
Problem
Given a list of integers and a reduction rule, repeatedly apply the rule until only one element remains.
Return that element.
Rule: In each pass, scan left to right. Remove any element that is smaller than its right neighbor. If no element is removed in a pass, stop.
Return the last remaining element.
python
def reduce_list(nums: List[int]) -> int:
...
Example:
**Input**: [3, 1, 4, 1, 5, 9, 2, 6]
Pass 1: remove 3 (3<4)? No, 3>1. Remove 1 (1<4) -> [3,4,1,5,9,2,6]
remove 1 (1<5) -> [3,4,5,9,2,6]
remove 2 (2<6) -> [3,4,5,9,6]
Pass 2: no element < right neighbor that qualifies -> stops at [3,4,5,9,6]
**Note**: clarify exact rule with interviewer.
Simpler variant: nums=[5,3,1], remove smallest each pass
[5,3,1] -> remove 1 -> [5,3] -> remove 3 -> [5] ->
**output** 5
Follow-ups
- Prove the invariant: what property does the remaining list always satisfy after each pass?
- What is the worst-case number of passes for a list of length n?
- How does the answer change if you remove elements larger than their right neighbor instead?
- How would you parallelize the reduction using a segment tree?
Free preview. Unlock all Grammarly questions →
About This Question
This is a candidate experience report from a grammarly interview during the phone round.
More Grammarly Interview Questions
1p3a
grammarly software engineer onsite interview experience
InterviewDB
All K Substrings - Generate All Substrings of Exactly Length K
InterviewDB
Grammarly SWE Phone - Duplicate and Missing Numbers
InterviewDB
Grammarly SWE Phone - Fibonacci Number
InterviewDB
Grammarly SWE Onsite - Merge Correction