Question Details
Problem
You are given an integer array nums and a list of mutation operations. Each operation is one of:
- SET i v: set nums[i] = v
- ADD i v: set nums[i] += v
- REVERSE l r: reverse the subarray nums[l..r] in place
- QUERY l r:
return the sum of nums[l..r]
Process all operations and return the results of all QUERY operations in order.
python
def process_mutations(nums: list[int], ops: list[tuple]) -> list[int]:
...
Example:
nums = [1, 2, 3, 4, 5]
ops = [("ADD",1,10),("QUERY",0,2),("REVERSE",0,4),("QUERY",0,4)]
**Output**: [16, 25]
# After ADD: [1,12,3,4,5] -> QUERY 0..2 = 1+12+3 = 16
# After REVERSE: [5,4,3,12,1] -> QUERY 0..4 = 25
Follow-ups
- A naive solution is O(n) per operation. How would a segment tree or BIT help for SET/ADD/QUERY?
- The REVERSE operation is the hard part -- what advanced data structure supports O(log n) range reversal?
- If there are no REVERSE operations, what is the optimal approach?
Full Details
Problem
You are given an integer array nums and a list of mutation operations. Each operation is one of:
- SET i v: set nums[i] = v
- ADD i v: set nums[i] += v
- REVERSE l r: reverse the subarray nums[l..r] in place
- QUERY l r:
return the sum of nums[l..r]
Process all operations and return the results of all QUERY operations in order.
python
def process_mutations(nums: list[int], ops: list[tuple]) -> list[int]:
...
Example:
nums = [1, 2, 3, 4, 5]
ops = [("ADD",1,10),("QUERY",0,2),("REVERSE",0,4),("QUERY",0,4)]
**Output**: [16, 25]
# After ADD: [1,12,3,4,5] -> QUERY 0..2 = 1+12+3 = 16
# After REVERSE: [5,4,3,12,1] -> QUERY 0..4 = 25
Follow-ups
- A naive solution is O(n) per operation. How would a segment tree or BIT help for SET/ADD/QUERY?
- The REVERSE operation is the hard part -- what advanced data structure supports O(log n) range reversal?
- If there are no REVERSE operations, what is the optimal approach?
About This Question
This is a reported interview question from a codesignal interview.
It covers the following topics: Coding, General Coding Assessment, Q2, Arrays .