Compute sum of minima with removals
KneronSoftware Engineer · Online AssessmentLast updated
Compute sum of minima with removals evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.
You are given an array weights[0..n-1] of positive integers representing product weights in a line. Repeat until no products remain: choose the lightest remaining product (if multiple, choose the one with the smallest current index), add its weight to a running total, and remove it along with up to its two current neighbors—one on the left and one on the right if they still exist. If only one neighbor exists, remove just that neighbor. Return the final total. Example: weights = [4, 3, 2, 1] -> choose 1 (remove 2 and 1), remaining [4, 3]; choose 3 (remove 3 and 4); total = 1 + 3 = 4. Implement a function that returns this total for any input array.
Solution walkthrough is for members
Get the full walkthrough with reference code and complexity analysis, plus Kitty Coach at 300 messages a day. Hints, the code runner and community answers stay free.