Skip to main content

Poridhi: Heaps & Priority Queues



Heaps & Priority Queues related problems:

In this blog post, we tackle three widely asked coding interview questions that revolve around the use of data structures and efficient algorithm design: Kth Largest Element in an Array, LRU Cache, and Min Stack. Each problem requires a strategic approach to managing and retrieving data under specific constraints, making them excellent practice for mastering Python collections and optimizing performance.

First, the Kth Largest Element in an Array problem is a classic selection problem that can be efficiently solved using a min-heap. Instead of sorting the entire array, we maintain a heap of the k largest elements seen so far and simply return the smallest among them. This reduces time complexity and enhances performance on large datasets. Next, the LRU (Least Recently Used) Cache is a real-world inspired problem that simulates caching behavior. We use Python's OrderedDict to maintain insertion order, allowing us to quickly update recently accessed items and discard the least recently used ones when the cache exceeds capacity. Finally, the Min Stack problem requires designing a special stack that, in addition to push/pop, can also return the minimum element in constant time. We achieve this using an auxiliary stack to keep track of minimum values alongside the main stack.

✅ Kth Largest Element in an Array

Use a min-heap of size k to track the k largest elements.

import heapq

def findKthLargest(nums, k):
    return heapq.nlargest(k, nums)[-1]

# Example
nums = [3,2,1,5,6,4]
k = 2
print(findKthLargest(nums, k))  # Output: 5

✅ LRU Cache

Use OrderedDict from collections to implement an efficient Least Recently Used Cache.


from collections import OrderedDict

class LRUCache:

    def __init__(self, capacity: int):
        self.cache = OrderedDict()
        self.capacity = capacity

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)  # Mark as recently used
        return self.cache[key]

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False)  # Remove least recently used

# Example
lru = LRUCache(2)
lru.put(1, 1)
lru.put(2, 2)
print(lru.get(1))  # Output: 1
lru.put(3, 3)
print(lru.get(2))  # Output: -1

✅ Min Stack

Use two stacks: one for values and one for the current minimum.


class MinStack:

    def __init__(self):
        self.stack = []
        self.min_stack = []

    def push(self, val: int) -> None:
        self.stack.append(val)
        if not self.min_stack or val <= self.min_stack[-1]:
            self.min_stack.append(val)

    def pop(self) -> None:
        val = self.stack.pop()
        if val == self.min_stack[-1]:
            self.min_stack.pop()

    def top(self) -> int:
        return self.stack[-1]

    def getMin(self) -> int:
        return self.min_stack[-1]

# Example
min_stack = MinStack()
min_stack.push(-2)
min_stack.push(0)
min_stack.push(-3)
print(min_stack.getMin())  # Output: -3
min_stack.pop()
print(min_stack.top())     # Output: 0
print(min_stack.getMin())  # Output: -2

Comments

Post a Comment

Popular posts from this blog

Poridhi: Stacks & Queues

  Stacks & Queues related problems: This collection of solutions tackles three classic problems often encountered in technical interviews and competitive programming. The Valid Parentheses problem checks whether a string has properly matched and ordered brackets using a stack. The Sliding Window Maximum efficiently finds the maximum value in every window of size k across an array using a deque, a popular sliding window pattern that ensures optimal performance. The Stock Span Problem simulates a real-world stock analysis scenario and calculates the number of consecutive days before today for which the stock price was less than or equal to today's, also utilizing a stack for efficient computation. These problems test understanding of stacks, queues, and sliding window techniques. ✅ Valid Parentheses def isValid ( s: str ) -> bool : stack = [] mapping = { ')' : '(' , '}' : '{' , ']' : '[' } for char in s: ...
Post a Comment
Read more

Data Recovery: DevOps pre-state learning

  Data Backup Data backup is the practice of copying data from a primary to a secondary location, to protect it in case of equipment failure, cyberattack, natural disaster or other data loss events. This can include documents, media files, configuration files, machine images, operating systems, and registry files. Essentially, any data that we want to preserve can be stored as backup data. Data Restore Data restore is the process of copying backup data from secondary storage and restoring it to its original location or a new location. A restore is performed to return data that has been lost, stolen or damaged to its original condition or to move data to a new location. Pilot Light A pilot light approach minimizes the ongoing cost of disaster recovery by minimizing the active resources, and simplifies recovery at the time of a disaster because the core infrastructure requirements are all in place. Warm Standby The warm standby approach involves ensuring that there is a scaled down, ...
Post a Comment
Read more

Poridhi: Basic Programming & Math

Basic Programming and math related problems: Extracting digits means breaking a number like 1234 into [1, 2, 3, 4], often using string conversion or modulo/division. Counting digits involves finding how many digits are in a number using length of a string or repeated division. Reversing an integer flips its digits (e.g., 123 becomes 321), with care for signs and 32-bit limits. A palindrome number reads the same forward and backward, often checked by comparing the original and reversed number. Armstrong numbers are those equal to the sum of their digits each raised to the number of digits, like 153 = 1³ + 5³ + 3³. To find the sum of all divisors of a number, loop through integers and check which divide the number without a remainder. Prime numbers are only divisible by 1 and themselves, and checking up to the square root is efficient. GCD, the greatest common divisor of two numbers, can be found using a simple loop or more efficiently with the Euclidean algorithm, which uses repeated mo...
Post a Comment
Read more