Quick Overview

Given a list of integers, return its elements rearranged to alternate between extremes: the largest value, then the smallest, then the second largest, then the second smallest, and so on. It tests reasoning about sorted order, odd lengths, repeated values and producing an exact output sequence.

Rearrange an Array to Alternate Largest and Smallest Remaining Values

Company: Verisk

Role: Data Scientist

Category: Coding & Algorithms

Difficulty: easy

Interview Round: Online Assessment

Given a list of integers, rearrange its elements so that they alternate between the extremes of what is left: the first element is the largest value, the second is the smallest, the third is the second largest, the fourth is the second smallest, and so on. Return the rearranged list. The report gives the ordering and the length bound only; this version also fixes the value range and how repeated values are handled. ### Function Signature ```python def alternate_max_min(values: list[int]) -> list[int]: ``` ### Rules - Build the output one element at a time from the elements not yet placed. Steps alternate, starting with a largest step: a largest step appends the largest remaining value, and a smallest step appends the smallest remaining value. Each step removes exactly one element. - Repeated values are separate elements. Removing one copy of a value leaves the other copies available for later steps. - When the length is odd, the final step is a largest step and appends the single element that is left. - Return a list of the same length that contains exactly the input's elements. Because equal values are interchangeable, the returned list is unique. - The input may be in any order. ### Constraints - `2 <= len(values) <= 10^4` - `-10^6 <= values[i] <= 10^6` - Values may be negative, zero or repeated. ### Examples **Example 1** ```text Input: values = [-1, 6, 3, 0, 9] Output: [9, -1, 6, 0, 3] ``` The largest value is 9 and the smallest is -1. Of what remains, the largest is 6 and the smallest is 0. The last remaining element, 3, is appended by the final largest step. **Example 2** ```text Input: values = [7, 7, 2, 7, 2, 5] Output: [7, 2, 7, 2, 7, 5] ``` The steps take one 7, one 2, a second 7 and the second 2. The remaining elements are 5 and 7, so the next largest step takes the last 7 and the final smallest step takes 5. **Example 3** ```text Input: values = [-8, 3] Output: [3, -8] ```

Overview: Given a list of integers, return its elements rearranged to alternate between extremes: the largest value, then the smallest, then the second largest, then the second smallest, and so on. It tests reasoning about sorted order, odd lengths, repeated values and producing an exact output sequence.

Read the full Verisk Data Scientist interview experience this question came from

Given a list of integers `values`, rearrange its elements so that they alternate between the extremes of what is left: the first element is the largest value, the second is the smallest, the third is the second largest, the fourth is the second smallest, and so on. Return the rearranged list. Build the output one element at a time from the elements not yet placed. Steps alternate, starting with a largest step: a largest step appends the largest remaining value, and a smallest step appends the smallest remaining value. Each step removes exactly one element. - Repeated values are separate elements. Removing one copy of a value leaves the other copies available for later steps. - When the length is odd, the final step is a largest step and appends the single element that is left. - Return a list of the same length that contains exactly the input's elements. Because equal values are interchangeable, the returned list is unique. - The input may be in any order. Every value fits in a signed 32-bit integer; no value can exceed 2^31 - 1. **Constraints** - `2 <= len(values) <= 10^4` - `-10^6 <= values[i] <= 10^6` - Values may be negative, zero or repeated. **Example 1** ```text Input: values = [-1, 6, 3, 0, 9] Output: [9, -1, 6, 0, 3] ``` The largest value is 9 and the smallest is -1. Of what remains, the largest is 6 and the smallest is 0. The last remaining element, 3, is appended by the final largest step. **Example 2** ```text Input: values = [7, 7, 2, 7, 2, 5] Output: [7, 2, 7, 2, 7, 5] ``` The steps take one 7, one 2, a second 7 and the second 2. The remaining elements are 5 and 7, so the next largest step takes the last 7 and the final smallest step takes 5.

Constraints

  • 2 <= len(values) <= 10^4
  • -10^6 <= values[i] <= 10^6
  • Values may be negative, zero or repeated.

Examples

Input: ([-8, 3],)

Expected Output: [3, -8]

Explanation: Source Example 3: minimum length 2 given in ascending order; the largest step takes 3, the smallest step takes -8.

Input: ([5, 1],)

Expected Output: [5, 1]

Explanation: Minimum length 2 already in descending order: largest 5, then smallest 1.

Hints

  1. Repeated values are separate elements: taking one copy of the maximum leaves its other copies available for later largest or smallest steps.
  2. Each step removes exactly one element, so the output has the same length as the input. Keep track of which elements remain, not just which values have been seen.
  3. With an odd length, the last step is a largest step that takes the single element left. Check that it is neither skipped nor appended twice.

Loading coding console...

Show the approach

Approach

Sort a copy of the input in ascending numeric order into s. The elements not yet placed are then always the contiguous slice s[lo..hi]: its largest remaining value is s[hi] and its smallest is s[lo]. Alternate steps starting with a largest step: a largest step appends s[hi] and decrements hi, a smallest step appends s[lo] and increments lo.

Invariant: before every step, s[lo..hi] holds exactly the multiset of unplaced elements in sorted order. A largest step removes one element from the top end and a smallest step removes one from the bottom end, so the slice stays sorted and each step removes exactly one element; other copies of an equal value remain in the slice for later steps, which is what the duplicate rule requires. Because equal values are interchangeable, the output is unique.

The loop runs while lo <= hi, which is exactly n steps. For odd n the final step has lo == hi and is a largest step (step n has an even 0-based index), so the single remaining element is appended exactly once; for even n the final step is a smallest step.

Edge cases: all-equal input returns the same values; copies of the max and min are taken one per step; negatives and zero need a numeric sort, not a string sort (for example -10 < -9 < 9 < 10). Values are within [-10^6, 10^6], so 32-bit int arrays suffice in Java and C++.

Time complexity:
O(n log n)
Space complexity:
O(n)