Heap (Priority Queue) Questions at Samsung: What to Expect

Heap (Priority Queue) questions appear in roughly 15% of Samsung's coding problems. This frequency signals that interviewers use these problems to assess a candidate's ability to manage dynamic data, optimize real-time processing, and implement efficient scheduling—core skills for embedded systems, resource management, and data processing roles at Samsung.

What to Expect — Types of Problems

Samsung's heap questions typically fall into two categories.

Simulation & Scheduling: These problems model real-world processes, like task scheduling on a processor, merging sorted data streams from sensors, or handling interrupt requests. You'll often need to maintain a running state (like current time or available resources) and repeatedly pull the next highest or lowest priority item from the heap to process.

Optimization with K: A common pattern involves finding the "top K" or "Kth" element in a dataset, or optimizing a cost function subject to K constraints. Examples include finding the K closest points to a sensor, the K most frequent log entries from a device, or the minimum cost to connect K components. The heap is used to maintain a candidate set efficiently.

The problems are applied, often framed within scenarios like network routing, job queues, or memory allocation, testing if you can recognize the underlying heap pattern.

How to Prepare — Study Tips with One Code Example

Master the standard library implementations: heapq in Python, PriorityQueue or manual array-based heaps in Java, and array-based heaps in JavaScript. Focus on the pattern of pushing all items onto the heap first versus pushing and popping dynamically. A key technique is using a max-heap by inverting values since standard libraries provide min-heaps.

A critical pattern is using a heap to find the K smallest or largest elements. The efficient approach is to maintain a heap of size K.

import heapq

def k_smallest(nums, k):
    # Use a max-heap by storing negative values
    max_heap = []
    for num in nums:
        heapq.heappush(max_heap, -num)
        if len(max_heap) > k:
            heapq.heappop(max_heap)  # Remove largest (most negative)
    # Return the actual values, stored as negatives
    return [-x for x in max_heap]

Recommended Practice Order

1. Fundamentals: Implement basic heap operations (insert, extract, heapify). Solve "Kth Largest Element."
2. Two-Heap Patterns: Practice problems like "Find Median from Data Stream" to manage two halves of a dataset.
3. Simulation: Tackle scheduling problems, such as "Meeting Rooms II" or "Task Scheduler," where you process events in time order.
4. Samsung-Specific: Finally, solve the actual heap problems from Samsung's question bank to adapt to their problem framing and constraints.

Practice Heap (Priority Queue) at Samsung