๐น Efficient Approach
Use a Min Heap.
Heap stores:
smallest current node
๐น Python Idea
import heapq
heapq.heappush(heap, (node.val, node))
Repeatedly:
โข Pop smallest node
โข Add next node from same list
๐น Complexity
Complexity - Value
Time - O(n log k)
Space - O(k)
Where:
n = total nodes
k = number of lists
๐น Interview Tip
Very common hard interview problem.
๐ 38. How do you implement LRU / LFU cache?
๐น LRU Cache
LRU: Least Recently Used
Remove least recently accessed item.
๐น Efficient Design
Use:
1. HashMap
2. Doubly Linked List
๐น Python LRU Example
python
from collections import OrderedDict
class LRUCache:
def init(self, capacity):
self.cache = OrderedDict()
self.capacity = capacity
def get(self, key):
if key not in self.cache:
return -1
self.cache.move_to_end(key)
return self.cache[key]
def put(self, key, value):
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)
๐น Complexity
Operation - Complexity
Get - O(1)
Put - O(1)
๐น Interview Tip
LRU cache is a FAANG-favorite system design question.
๐ 39. How do you check for balanced parentheses?
Use a stack.
๐น Idea
โข Push opening brackets.
โข When closing bracket appears: Check top of stack
๐น Python Solution
python
def is_valid(s):
stack = []
mapping = {
')': '(',
'}': '{',
']': '['
}
for char in s:
if char in mapping.values():
stack.append(char)
elif char in mapping:
if not stack or stack.pop() != mapping[char]:
return False
return not stack
print(is_valid("({[]})"))
๐น Output
True
๐น Complexity
Complexity - Value
Time - O(n)
Space - O(n)
๐น Uses
โ Compilers
โ Expression parsing
โ Syntax validation
๐ 40. How do you implement a circular queue?
Circular queue reuses empty spaces efficiently.
๐น Visualization
Front โ [1,2,3,_,_]
After dequeue + enqueue:
[,2,3,4,]
๐น Python Implementation
`python
class CircularQueue:
def init(self, size):
self.queue = [None] * size
self.front = 0
self.rear = 0
self.size = size
self.count = 0
def enqueue(self, value):
if self.count == self.size:
return "Full"
self.queue[self.rear] = value
self.rear = (self.rear + 1) % self.size
self.count += 1
def dequeue(self):
if self.count == 0:
return "Empty"
value = self.queue[self.front]
self.front = (self.front + 1) % self.size
self.count -= 1
return value
`๐น Complexity
Operation - Complexity
Enqueue - O(1)
Dequeue - O(1)
๐น Real-World Uses
โ CPU scheduling
โ Streaming systems
โ Buffers
โ Embedded systems
๐ฅ Double Tap โค๏ธ For Part-5