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 Technical Screen rounds at Microsoft.

What role is this question designed for?

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

Retain Top K Elements | Microsoft Coding Question

Retain Top K Elements

Company: Microsoft

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Given a list of integers `nums` and an integer `k`, return a new list formed from the original list after removing every element except the `k` largest elements. Requirements: - Preserve the relative order of the retained elements from the original list. - Duplicates are treated as separate elements. - If multiple equal values are tied at the cutoff, keep the leftmost occurrences needed to retain exactly `k` elements. - If `k <= 0`, return an empty list. - If `k >= nums.length`, return the original list. Example: ```text nums = [5, 1, 3, 5, 2, 4], k = 3 The 3 largest elements are 5, 5, and 4. Output: [5, 5, 4] ``` Example with a tie: ```text nums = [4, 1, 4, 3, 4], k = 2 The cutoff value is 4. Keep the leftmost two occurrences of 4. Output: [4, 4] ```

Quick Answer: This question evaluates array manipulation and order-statistics skills, specifically stable selection, handling duplicates with leftmost tie-breaking, and edge-case reasoning for k values and list bounds.

Given a list of integers `nums` and an integer `k`, return a new list formed by removing every element except the `k` largest elements. Rules: - Preserve the relative order of the retained elements from the original list. - Duplicates are treated as separate elements. - If multiple equal values are tied at the cutoff, keep the leftmost occurrences needed to retain exactly `k` elements. - If `k <= 0`, return an empty list. - If `k >= len(nums)`, return a copy of the original list. Example: - `nums = [5, 1, 3, 5, 2, 4]`, `k = 3` -> `[5, 5, 4]` - `nums = [4, 1, 4, 3, 4]`, `k = 2` -> `[4, 4]`

Constraints

0 <= len(nums) <= 200000
-10^9 <= nums[i] <= 10^9
-10^9 <= k <= 10^9

Examples

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

Expected Output: [5, 5, 4]

Explanation: The 3 largest elements are 5, 5, and 4. Keeping them in original order gives [5, 5, 4].

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

Expected Output: [4, 4]

Explanation: The cutoff value is 4. Three 4s exist, but only two should be kept, so keep the leftmost two occurrences.

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

Expected Output: [1, 2, 2]

Explanation: The 3 largest elements are 2, 2, and 1. Two 1s are tied for the cutoff, so keep the leftmost 1 and both 2s.

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

Expected Output: []

Explanation: When k <= 0, no elements are retained.

Input: ([], 5)

Expected Output: []

Explanation: An empty input list always produces an empty output list.

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

Expected Output: [-2, -1]

Explanation: The 2 largest values are -1 and -2. Preserving their original order gives [-2, -1].

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

Expected Output: [2, -1, 2]

Explanation: When k is at least the array length, return a copy of the original list.

Hints

If you sort a copy of the array in descending order, the first `k` values tell you exactly which multiset of values must be kept.
Use a frequency map for those top `k` values, then scan the original list from left to right and keep an element only while its remaining frequency is positive.

Quick Overview

This question evaluates array manipulation and order-statistics skills, specifically stable selection, handling duplicates with leftmost tie-breaking, and edge-case reasoning for k values and list bounds.