Return k smallest elements using heap
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.