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 Meta.

What role is this question designed for?

This question is commonly asked for Machine Learning Engineer candidates at Meta during technical interviews.

Return k smallest elements using heap

Quick Overview

This question evaluates proficiency with heap-based data structures, efficient algorithm design and complexity analysis for large inputs (O(n log k)) while reasoning about edge cases such as duplicates and negative values, and it falls under the Coding & Algorithms domain.

Company: Meta

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Onsite

Given an unsorted array nums of up to 1,000,000 integers and an integer k (1 <= k <= nums.length), return the k smallest elements in ascending order. Design an algorithm that runs in O(n log k) time and uses O(k) extra space via a heap. Clarify handling of duplicates and negative numbers; stable ordering among equal values is not required. Follow-up: streaming version where numbers arrive online and you must support getSmallestK() at any time.

Quick Answer: This question evaluates proficiency with heap-based data structures, efficient algorithm design and complexity analysis for large inputs (O(n log k)) while reasoning about edge cases such as duplicates and negative values, and it falls under the Coding & Algorithms domain.

Given an unsorted array `nums` of up to 1,000,000 integers and an integer `k` (1 <= k <= nums.length), return the `k` smallest elements in ascending order. Design an algorithm that runs in O(n log k) time and uses O(k) extra space via a heap. Handle duplicates and negative numbers correctly. Stable ordering among equal values is not required — only the multiset of returned values and their ascending order matter. Example: for `nums = [7, 10, 4, 3, 20, 15]` and `k = 4`, return `[3, 4, 7, 10]`. The canonical heap approach maintains a max-heap of size k while scanning the array: push the first k elements, then for each remaining element, if it is smaller than the current heap maximum, replace the max. At the end the heap holds the k smallest elements, which you sort ascending before returning.

Constraints

1 <= nums.length <= 1,000,000
1 <= k <= nums.length
Elements may be negative, zero, or positive
Duplicates are allowed and must be preserved in the output multiset
Stable ordering among equal values is not required

Examples

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

Expected Output: [1, 2, 3]

Explanation: The three smallest values are 1, 2, 3, returned in ascending order.

Input: ([7, 10, 4, 3, 20, 15], 4)

Expected Output: [3, 4, 7, 10]

Explanation: The four smallest values out of the six are 3, 4, 7, 10.

Input: ([5], 1)

Expected Output: [5]

Explanation: Single-element array with k=1 returns that element.

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

Expected Output: [1, 1, 2]

Explanation: Duplicates are preserved: the three smallest are 1, 1, 2.

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

Expected Output: [-5, -2]

Explanation: Negative numbers handled correctly; the two smallest are -5 and -2.

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

Expected Output: [4, 4, 4, 4]

Explanation: All elements equal and k equals the array length, so the whole array is returned.

Input: ([10, 9, 8, 7, 6], 5)

Expected Output: [6, 7, 8, 9, 10]

Explanation: k equals the length, so all elements are returned sorted ascending.

Hints

Sorting the whole array is O(n log n). To hit O(n log k), avoid touching all elements with a full sort — keep only the k candidates you care about.
Use a max-heap of size k. The root is the largest of your current k smallest. When a new element is smaller than the root, it deserves a spot, so pop the root and push the new element.
Python's heapq is a min-heap; simulate a max-heap by negating values on the way in and negating again on the way out.
After the scan, the heap contains exactly the k smallest elements in no particular order — sort them ascending (O(k log k)) before returning.
For the streaming follow-up, keep the same size-k max-heap as a running data structure: each incoming number does an O(log k) push/replace, and getSmallestK() returns the sorted heap contents in O(k log k).

Quick Overview