Amazon·Software Engineer·Technical Phone Screen
- Given a list of positive integers representing task sizes, you can repeatedly merge any two items at a cost equal to their combined size. Implement a function that returns the minimum total cost to reduce the list to a single item. Also explain the algorithm and its time and space complexity.
- Given an array of machine strengths and an integer k, remove exactly k consecutive elements such that the sum of absolute differences between all adjacent pairs in the remaining array is minimized. Return the minimum cost and the starting index of the removed block. Aim for O(n) or O(n log n).
“This is basically Huffman coding in disguise, and I knew that immediately which felt good.”