Question 76
Which data structure is suitable for implementing Least Recently Used (LRU) Cache eviction policy in O(1) time?
A Doubly Linked List allows O(1) removal/addition of LRU nodes, while a Hash Map provides O(1) direct key lookup.
Which data structure is suitable for implementing Least Recently Used (LRU) Cache eviction policy in O(1) time?
A Doubly Linked List allows O(1) removal/addition of LRU nodes, while a Hash Map provides O(1) direct key lookup.
In a Max-Heap with N elements, where are the leaf nodes stored in 0-based array indexing?
In a 0-based array binary heap of size N, non-leaf internal nodes occupy indices 0 to floor(N/2) - 1, so leaves occupy indices floor(N/2) to N - 1.
What is the time complexity of a range-sum query in a standard Segment Tree containing N elements?
A standard Segment Tree has height O(log N). A range query visits O(log N) relevant tree nodes (with a constant-factor bound), so its time complexity is O(log N).
Which algorithmic paradigm is used in Dijkstra's Shortest Path algorithm?
Dijkstra's algorithm greedily selects the unvisited vertex with the minimum tentative distance at each step.
How many binary heaps are sufficient to implement a priority queue?
A single binary heap is sufficient to implement a priority queue. A min-heap supports efficient access to the minimum-priority element, while a max-heap supports the maximum-priority element.