Keep At Most K Copies in a Sorted Array
Company: Oracle
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
# Keep At Most K Copies in a Sorted Array
Implement `dedupe_sorted(nums, k)`. Modify the sorted input array in place so each distinct integer appears at most `k` times while order is preserved, and return the retained prefix as an integer array. Use the input as the write buffer with `O(1)` working space; the returned prefix is the portable graded value in all four languages.
Constraints: up to `200000` integers; each is in `[-10^9, 10^9]`; `0 <= k <= 200000`.
```hint Exercise each multiplicity boundary
Test a value appearing fewer than, exactly, and more than `k` times, plus `k = 0`.
```
Quick Answer: Implement `dedupe_sorted(nums, k)`. Work through the function contract, boundary cases, correctness argument, and time and space complexity expected in a production-quality solution.
Modify the sorted integer array `nums` in place so that every distinct value appears at most `k` times while preserving order. Return the retained prefix as the portable graded integer array. Use `nums` as the write buffer with constant working space.
Constraints
- 0 <= len(nums) <= 200000.
- nums is sorted and every value is an integer from -10^9 through 10^9.
- 0 <= k <= 200000.
- The input is the in-place write buffer; the exact retained prefix is the graded return value.
Examples
Input: ([], 0)
Expected Output: []
Explanation: An empty array returns an empty prefix when k is zero.
Input: ([], 3)
Expected Output: []
Explanation: An empty array also returns an empty prefix for a positive limit.
Hints
- Test a run appearing fewer than, exactly, and more than k times.
- Include k = 0, k = 1, and a limit larger than the array length.
- Use several sorted runs with negative, zero, and numeric-boundary values.