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 Onsite rounds at Amazon.

What role is this question designed for?

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

Implement two array-cost minimization algorithms

Company: Amazon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Implement two array-cost minimization algorithms. 1) Minimize merge cost: Given a list of positive integers workloads representing task sizes, you may repeatedly merge any two items a and b into a single item of size a+b, incurring cost a+b for that merge. Implement minimizeSystemCost(workloads: int[]) -> long that returns the minimal total cost to end with one item. State the algorithm and its time/space complexity. 2) Remove a contiguous block: Given an integer array machines representing machine strengths and an integer k (1 <= k < machines.length), remove exactly k consecutive elements so that, for the remaining sequence in original order, the sum over all adjacent pairs of |strength[i] - strength[i+1]| is minimized. Implement minimizeRemainingAdjDiff(machines: int[], k: int) -> (long minCost, int startIndex), returning the minimal cost and a valid starting index of the removed block. Target O(n) or O(n log n).

Quick Answer: This question evaluates algorithm design, data structure selection, and complexity analysis by requiring implementations for minimizing total merge cost and for removing a contiguous block to minimize the sum of adjacent absolute differences.

Minimize Total Merge Cost (Optimal Merge / Huffman)

You are given a list of positive integers `workloads`, where each value is a task size. You may repeatedly pick any two items `a` and `b`, merge them into a single item of size `a + b`, and pay a cost of `a + b` for that merge. Repeat until a single item remains. Implement `minimizeSystemCost(workloads) -> long` returning the minimum possible total cost to reduce the list to one item. The final cost equals the sum over every merge of the produced item's size — equivalently, each original value times its depth in the merge tree. To minimize, always merge the two smallest current items (the optimal-merge / Huffman pattern), accumulating `a + b` into the running total at every pop-pop-push step. A list of length 0 or 1 needs no merges and costs 0. The total can exceed 32-bit range, so accumulate in a 64-bit integer.

Constraints

workloads values are positive integers
0 <= len(workloads); the list may be empty or a single element (cost 0)
The result can exceed 32-bit range; accumulate in a 64-bit integer (long)

Examples

Input: ([4, 6, 8],)

Expected Output: 28

Explanation: Merge 4+6=10 (cost 10), then 10+8=18 (cost 18). Total 28. Merging the two smallest first is optimal.

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

Expected Output: 33

Explanation: 1+2=3 (3), 3+3=6 (6), 4+5=9 (9), 6+9=15 (15) -> 3+6+9+15 = 33.

Input: ([10],)

Expected Output: 0

Explanation: Single element: no merges needed, cost 0.

Input: ([],)

Expected Output: 0

Explanation: Empty list: no merges, cost 0.

Input: ([5, 5],)

Expected Output: 10

Explanation: One merge 5+5=10, cost 10.

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

Expected Output: 8

Explanation: 1+1=2 (2), 1+1=2 (2), 2+2=4 (4) -> 2+2+4 = 8.

Input: ([2, 3, 6, 9],)

Expected Output: 36

Explanation: 2+3=5 (5), 5+6=11 (11), 11+9=20 (20) -> 5+11+20 = 36.

Hints

Reframe: the total cost is the sum over every merge of the produced item's size, i.e. each original value times its depth in the merge tree. Large values should be merged last (shallow), small values first (deep).
Always merging the two smallest current items is optimal (optimal-merge / Huffman). Use a min-heap that hands you the two smallest and lets you push the sum back.
A merged item's size is paid again on every later merge, so add `a + b` to the running total at each pop-pop-push step, not just once. Handle n <= 1 (cost 0).

Remove a Contiguous Block to Minimize Adjacent Differences

You are given an integer array `machines` (machine strengths, possibly negative) and an integer `k` with 1 <= k < machines.length. Remove exactly `k` consecutive elements. For the remaining sequence (kept in original order), its cost is the sum over all adjacent pairs of |strength[i] - strength[i+1]|. Implement `minimizeRemainingAdjDiff(machines, k) -> (long minCost, int startIndex)` returning the minimal achievable cost and a valid starting index of the removed block (the index of the first removed element). If several starts tie, the smallest valid start index is returned. For a removed block at start `s` (indices s..s+k-1), the remaining cost splits into three independent pieces: prefix-internal adjacencies `P[s-1]` (when s >= 1), suffix-internal adjacencies `P[n-1] - P[s+k]` (when s+k <= n-1), and at most one join `|a[s+k] - a[s-1]|` that exists only when both sides are non-empty. Here `P` is the prefix sum of the absolute adjacent-difference array, making each candidate O(1) and the whole sweep O(n). Use 64-bit accumulation.

Constraints

machines values are arbitrary integers (possibly negative or zero)
1 <= k < n where n = len(machines)
There are n - k + 1 valid start positions; on ties the smallest valid start index is returned
Differences and their sums can exceed 32-bit range; use 64-bit accumulation

Examples

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

Expected Output: (3, 1)

Explanation: Removing the spike 100 (start 1) leaves [1,2,3,4] with cost 1+1+1=3, the minimum.

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

Expected Output: (18, 0)

Explanation: Every removal of a length-2 block leaves an oscillating remainder; start 0 gives [10,1,10] -> 9+9=18, which is minimal (smallest index on tie).

Input: ([5, 8, 6, 3, 10], 1)

Expected Output: (8, 4)

Explanation: Removing the last element (start 4, value 10) leaves [5,8,6,3] with cost 3+2+3=8, the minimum; no join term at the end.

Input: ([1, 2], 1)

Expected Output: (0, 0)

Explanation: k = n-1, exactly one element survives; no adjacencies so cost 0 for any valid start (smallest is 0).

Input: ([-5, 0, 5, 100, 5, 0, -5], 1)

Expected Output: (20, 3)

Explanation: Removing the peak 100 (start 3) joins 5 and 5 (|5-5|=0), leaving |-5-0|+|0-5|+|5-5|+|5-0|+|0--5| = 5+5+0+5+5 = 20, the minimum.

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

Expected Output: (0, 0)

Explanation: All equal, every adjacent difference is 0, so any removal yields cost 0; smallest start is 0.

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

Expected Output: (91, 0)

Explanation: Removing the first two (start 0) leaves [2,48,3] with cost 46+45=91, the minimum over all length-2 removals.

Hints

For a block removed at start s, the remaining sequence is a[0..s-1] then a[s+k..n-1]. Its cost splits into prefix-internal adjacencies, suffix-internal adjacencies, and at most one new join between a[s-1] and a[s+k].
Let diff[i] = |a[i+1]-a[i]| and P its prefix sum. Any contiguous run of adjacencies is then a constant-time range query, so each candidate s is O(1) and the full sweep is O(n).
The join term exists only when both sides are non-empty: s >= 1 and s+k <= n-1. When the block touches the start or end there is no join. Empty/one-element remainders cost 0.

Quick Overview

This question evaluates algorithm design, data structure selection, and complexity analysis by requiring implementations for minimizing total merge cost and for removing a contiguous block to minimize the sum of adjacent absolute differences.