How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Take-home Project rounds at Kneron.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Kneron during technical interviews.

Compute sum of minima with removals | Kneron Coding Question

Quick Overview

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.

Compute sum of minima with removals

Company: Kneron

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Take-home Project

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.

Quick Answer: 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 arranged in a line. Repeat the following until no products remain: 1. Choose the lightest remaining product. If several products share the minimum weight, choose the one with the smallest current index. 2. Add its weight to a running total. 3. Remove it along with up to its two current neighbors — the one immediately to its left and the one immediately to its right, if they still exist. If only one neighbor exists, remove just that neighbor. Return the final running total. Note that "current" neighbors are determined by the remaining products at the moment of selection: when products are removed, the line closes up so that previously non-adjacent products can become neighbors. Example: `weights = [4, 3, 2, 1]`. Choose 1 (the minimum); remove 1 and its left neighbor 2, leaving `[4, 3]`. Choose 3 (now the minimum); remove 3 and its left neighbor 4. Total = 1 + 3 = 4.

Constraints

1 <= n (the array may also be empty, in which case return 0)
All weights are positive integers
On ties for the minimum, the smallest current index is chosen
Neighbors are determined by the current (post-removal) arrangement, not the original indices

Examples

Input: ([4, 3, 2, 1],)

Expected Output: 4

Explanation: Choose 1, remove {2,1} -> [4,3]; choose 3, remove {4,3}. Total = 1 + 3 = 4.

Input: ([5],)

Expected Output: 5

Explanation: Single product: choose 5, no neighbors to remove. Total = 5.

Input: ([],)

Expected Output: 0

Explanation: Empty array: nothing to choose, total = 0.

Input: ([1, 2, 3, 4, 5],)

Expected Output: 9

Explanation: Choose 1, remove {1,2} -> [3,4,5]; choose 3, remove {3,4} -> [5]; choose 5. Total = 1 + 3 + 5 = 9.

Input: ([2, 2, 2],)

Expected Output: 4

Explanation: Tie minimum -> smallest index 0; remove {2(idx0),2(idx1)} -> [2(idx2)]; choose remaining 2. Total = 2 + 2 = 4.

Input: ([3, 1, 2],)

Expected Output: 1

Explanation: Choose 1 (idx1), remove its left 3 and right 2; nothing remains. Total = 1.

Input: ([7, 7],)

Expected Output: 7

Explanation: Tie -> smallest index 0; remove idx0 and its only neighbor idx1. Total = 7.

Input: ([1, 5, 1, 5, 1],)

Expected Output: 3

Explanation: Choose first 1 (idx0), remove right 5 -> [1,5,1]; choose 1 (idx2), remove right 5 -> [1]; choose last 1. Total = 1 + 1 + 1 = 3.

Hints

Maintain a doubly-linked-list view of the line using left[] and right[] index arrays so that after a removal the surviving products close up and become neighbors in O(1).
Each round, scan for the lightest non-removed product, preferring the smallest index on ties; add its weight, then remove it plus its current left and right neighbors if they exist.
Only the chosen (minimum) product's weight is added to the total — the removed neighbors do NOT contribute to the sum.

Quick Overview