New 60 Heaps and Maps Interview Questions
Introduction
Heaps and Maps are important data structures often encountered in programming interviews.
A heap is a specialized tree-based structure that satisfies the heap property, which means that the parent node has a certain relationship with its child nodes. Heaps are commonly used to efficiently extract the minimum or maximum element from a collection.
Maps, also known as dictionaries or associative arrays, are data structures that store key-value pairs. They allow fast retrieval of values based on their associated keys. Maps are useful for solving problems that involve storing and retrieving data efficiently.
In interviews, questions about heaps may involve tasks such as finding the kth smallest element or implementing priority queues, while map-related questions often revolve around solving problems that require efficient lookup or counting occurrences of elements.
Questions
1. What is a Heap? Explain with example.
A Heap is a specialized tree-based data structure that satisfies the “heap property,” which means the value of each node is either greater than or equal to (in a max-heap) or less than or equal to (in a min-heap) the values of its children nodes. Heaps are typically implemented as binary heaps, where each node has at most two children.
Example of a Max-Heap:
9
/ \
7 6
/ \ /
5 3 42. Explain the difference between a min-heap and a max-heap.
| Heap Type | Heap Property | Root Node |
|---|---|---|
| Max-Heap | Parent >= Children | Maximum |
| Min-Heap | Parent <= Children | Minimum |
3. What are the applications of Heaps?
Heaps are used in various applications, including:
- Priority Queues: Heaps are used to implement priority queues, where elements with higher priorities (or lower values) are served before those with lower priorities (higher values).
- Dijkstra’s Algorithm: It uses a min-heap to find the shortest path in a weighted graph.
- Heap Sort: Heaps are used to efficiently sort elements in an array.
- Huffman Encoding: Heaps help build efficient prefix codes in data compression algorithms.
4. Explain how Heapify operation works in a Heap.
Heapify is an essential operation to maintain the heap property after inserting or deleting an element. It ensures that the tree remains a valid heap.
Example of Max-Heapify (assuming left and right subtrees are already heaps):
Input Max-Heap:
9
/ \
7 6
/ \ /
5 3 4
After Max-Heapify(1):
9
/ \
7 6
/ \ /
5 3 45. What is the time complexity to build a heap?
The time complexity to build a heap is O(n), where n is the number of elements in the input array. It can be achieved using a bottom-up approach, starting from the first non-leaf node and applying heapify on each of those nodes.
Example of building a Max-Heap:
Input array: [4, 10, 3, 5, 1]
Step 1: Heapify(1) -> [10, 5, 3, 4, 1]
Step 2: Heapify(0) -> [10, 5, 3, 4, 1] (already a Max-Heap)
Final Max-Heap: [10, 5, 3, 4, 1]6. What is a Binary Heap? How does it differ from a Binary Search Tree?
A Binary Heap is a specific type of heap that is implemented using a binary tree data structure. It has two main variations: Max-Heap and Min-Heap. As mentioned before, the heap property is satisfied in a binary heap, which distinguishes it from a binary search tree (BST).
Difference between Binary Heap and Binary Search Tree:
| Binary Heap | Binary Search Tree |
| Heap property: Parent >= Children (Max-Heap), Parent <= Children (Min-Heap) | Ordering property: Left Child < Parent < Right Child (for all nodes) |
| Shape: It is a balanced binary tree, but not necessarily a complete binary tree | Shape: It is a binary tree with a specific ordering of elements. |
| Used for: Priority queues, heap sort, etc. | Used for: Efficient searching, insertion, and deletion operations. |
Example C++ code for a Binary Heap (Max-Heap):
#include <iostream>
#include <vector>
using namespace std;
class BinaryHeap {
private:
vector<int> heap;
// Helper function to heapify a subtree rooted at index i
void heapify(int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < heap.size() && heap[left] > heap[largest])
largest = left;
if (right < heap.size() && heap[right] > heap[largest])
largest = right;
if (largest != i) {
swap(heap[i], heap[largest]);
heapify(largest);
}
}
public:
// Constructor
BinaryHeap() {}
// Insert an element into the heap
void insert(int value) {
heap.push_back(value);
int i = heap.size() - 1;
while (i > 0 && heap[i] > heap[(i - 1) / 2]) {
swap(heap[i], heap[(i - 1) / 2]);
i = (i - 1) / 2;
}
}
// Extract the maximum element (root) from the heap
int extractMax() {
if (heap.empty())
return -1;
int maxElement = heap[0];
heap[0] = heap.back();
heap.pop_back();
heapify(0);
return maxElement;
}
};
int main() {
BinaryHeap maxHeap;
maxHeap.insert(5);
maxHeap.insert(10);
maxHeap.insert(3);
maxHeap.insert(7);
cout << "Max element: " << maxHeap.extractMax() << endl; // Output: Max element: 10
cout << "Max element: " << maxHeap.extractMax() << endl; // Output: Max element: 7
return 0;
}7. What is the time complexity of insert, delete, and extract operations in a heap?
The time complexity for each operation in a binary heap is as follows:
- Insert: O(log n) – It involves the heapify-up operation, which has a logarithmic time complexity.
- Delete: O(log n) – It involves the heapify-down operation, which has a logarithmic time complexity.
- Extract: O(log n) – It also involves the heapify-down operation after removing the root element.
Example of insert operation in Max-Heap:
BinaryHeap maxHeap;
maxHeap.insert(5); // O(log n)
maxHeap.insert(10); // O(log n)
maxHeap.insert(3); // O(log n)
maxHeap.insert(7); // O(log n)8. Explain how heaps can be implemented using arrays.
Heaps can be efficiently implemented using arrays due to their binary tree structure. In a binary heap, each node can be mapped to an array index with the following relationships:
- Parent of node at index i: (i – 1) / 2
- Left child of node at index i: 2 * i + 1
- Right child of node at index i: 2 * i + 2
Example C++ code for the array-based implementation of a Max-Heap:
#include <iostream>
#include <vector>
using namespace std;
class MaxHeap {
private:
vector<int> heap;
// Helper function to heapify a subtree rooted at index i
void heapify(int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < heap.size() && heap[left] > heap[largest])
largest = left;
if (right < heap.size() && heap[right] > heap[largest])
largest = right;
if (largest != i) {
swap(heap[i], heap[largest]);
heapify(largest);
}
}
public:
// Constructor
MaxHeap() {}
// Insert an element into the heap
void insert(int value) {
heap.push_back(value);
int i = heap.size() - 1;
while (i > 0 && heap[i] > heap[(i - 1) / 2]) {
swap(heap[i], heap[(i - 1) / 2]);
i = (i - 1) / 2;
}
}
// Extract the maximum element (root) from the heap
int extractMax() {
if (heap.empty())
return -1;
int maxElement = heap[0];
heap[0] = heap.back();
heap.pop_back();
heapify(0);
return maxElement;
}
};
int main() {
MaxHeap maxHeap;
maxHeap.insert(5);
maxHeap.insert(10);
maxHeap.insert(3);
maxHeap.insert(7);
cout << "Max element: " << maxHeap.extractMax() << endl; // Output: Max element: 10
cout << "Max element: " << maxHeap.extractMax() << endl; // Output: Max element: 7
return 0;
}9. What is a priority queue and how is it implemented using a heap?
A priority queue is an abstract data type that allows efficient insertion of elements with associated priorities and quick access to the element with the highest (or lowest) priority.
A priority queue can be implemented using a binary heap, where the heap’s root always contains the highest-priority element (in a max-heap) or the lowest-priority element (in a min-heap).
Example C++ code for a priority queue implemented using a Max-Heap:
#include <iostream>
#include <vector>
using namespace std;
class MaxHeap {
private:
vector<int> heap;
// Helper function to heapify a subtree rooted at index i
void heapify(int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < heap.size() && heap[left] > heap[largest])
largest = left;
if (right < heap.size() && heap[right] > heap[largest])
largest = right;
if (largest != i) {
swap(heap[i], heap[largest]);
heapify(largest);
}
}
public:
// Constructor
MaxHeap() {}
// Insert an element into the heap
void insert(int value) {
heap.push_back(value);
int i = heap.size() - 1;
while (i > 0 && heap[i] > heap[(i - 1) / 2]) {
swap(heap[i], heap[(i - 1) / 2]);
i = (i - 1) / 2;
}
}
// Extract the maximum element (root) from the heap
int extractMax() {
if (heap.empty())
return -1;
int maxElement = heap[0];
heap[0] = heap.back();
heap.pop_back();
heapify(0);
return maxElement;
}
// Check if the heap is empty
bool isEmpty() {
return heap.empty();
}
};
int main() {
MaxHeap maxHeap;
maxHeap.insert(5);
maxHeap.insert(10);
maxHeap.insert(3);
maxHeap.insert(7);
while (!maxHeap.isEmpty()) {
cout << "Max element: " << maxHeap.extractMax() << endl;
}
return 0;
}10. What are the various types of heaps (e.g., binary heap, binomial heap, Fibonacci heap)?
There are several types of heaps, each with different properties and use-cases:
- Binary Heap: It is the most common type of heap, and we’ve discussed it in the previous answers. It can be implemented efficiently using arrays and satisfies the heap property.
- Binomial Heap: It is a type of heap that allows for efficient merge operations, making it suitable for priority queue implementations. It consists of a collection of binomial trees, where each binomial tree follows the heap property. Binomial heaps are used in Dijkstra’s algorithm and some graph algorithms.
- Fibonacci Heap: It is an advanced type of heap that provides efficient merge and decrease-key operations. It is used in certain graph algorithms like Dijkstra’s algorithm and Prim’s algorithm due to its better time complexities for these operations.
11. What is a Map (or Hashmap)?
A Map, also known as a Hashmap, is a data structure that stores key-value pairs and allows efficient retrieval, insertion, and deletion of elements based on their keys. It uses a technique called “hashing” to map keys to specific locations in the underlying array, which enables fast access to values associated with the keys.
Example of a Map (Hashmap):
Consider a Map that stores the ages of people:
{"Alice": 25, "Bob": 30, "John": 22}In this example, “Alice,” “Bob,” and “John” are keys, and 25, 30, and 22 are their corresponding values.
12. Explain how hashing works in a Map.
Hashing is a technique used in Maps to convert keys into unique indices (hash codes) that can be used as array indices for efficient data retrieval. A good hash function minimizes collisions and distributes the keys evenly across the array.
Example of Hashing in a Map:
Let’s assume we have a simple hash function that calculates the ASCII sum of the characters in the key and takes the modulo of the array size:
Hash Function: hash(key) = sum of ASCII values of characters in key % array_size
Consider the Map example from the previous question:
{"Alice": 25, "Bob": 30, "John": 22}Assuming the array size is 5, here’s how the hashing would work:
hash("Alice") = (65 + 108 + 105 + 99 + 101) % 5 = 479 % 5 = 4
hash("Bob") = (66 + 111 + 98) % 5 = 275 % 5 = 0
hash("John") = (74 + 111 + 104 + 110) % 5 = 399 % 5 = 4 (collision with "Alice")As you can see, the hash function maps “Alice” to index 4, “Bob” to index 0, and “John” also to index 4. A collision occurs when multiple keys are hashed to the same index, and this needs to be handled appropriately in the Map implementation.
13. What is the time complexity of insert, delete, and search operations in a Map?
The time complexity of insert, delete, and search operations in a Map (Hashmap) depends on the underlying hash function and the handling of collisions.
In the average case, assuming a well-distributed hash function and a load factor not close to 1, the time complexities are:
- Insertion: O(1) – Constant time on average for inserting a key-value pair into the Map.
- Deletion: O(1) – Constant time on average for deleting a key-value pair from the Map.
- Search: O(1) – Constant time on average to retrieve the value associated with a given key.
14. Explain collision in a Hashmap and how it can be resolved.
Collision occurs in a Hashmap when two or more keys are mapped to the same hash code or array index. This situation can lead to data loss or incorrect retrieval of values if not handled properly.
Chaining: In this method, each array index holds a linked list or some other data structure to store multiple key-value pairs that have the same hash code. The collision is resolved by appending the new key-value pair to the existing list at that index.
Example C++ code for resolving collisions using chaining:
#include <iostream>
#include <list>
#include <string>
using namespace std;
class HashMap {
private:
static const int arraySize = 5;
list<pair<string, int>> hashArray[arraySize];
// Hash function
int hash(string key) {
int sum = 0;
for (char c : key)
sum += c;
return sum % arraySize;
}
public:
// Insert a key-value pair into the Map
void insert(string key, int value) {
int index = hash(key);
hashArray[index].push_back(make_pair(key, value));
}
// Search for a value using the key
int search(string key) {
int index = hash(key);
for (const auto& kvPair : hashArray[index]) {
if (kvPair.first == key)
return kvPair.second;
}
return -1; // Key not found
}
};
int main() {
HashMap myMap;
myMap.insert("Alice", 25);
myMap.insert("Bob", 30);
myMap.insert("John", 22);
myMap.insert("Dave", 28);
myMap.insert("Eve", 31);
cout << "Age of Bob: " << myMap.search("Bob") << endl; // Output: Age of Bob: 30
cout << "Age of Eve: " << myMap.search("Eve") << endl; // Output: Age of Eve: 31
cout << "Age of Sam: " << myMap.search("Sam") << endl; // Output: Age of Sam: -1 (not found)
return 0;
}In the code above, the hashArray is an array of lists, and the chaining technique is used to handle collisions.
15. What are the different types of Hashing Techniques?
There are several hashing techniques used in practice. Some of them include:
- Division Hashing: This technique involves taking the modulo of the hash code with the array size to get the array index.
hash(key) = hash_code(key) % array_size. - Multiplication Hashing: In this technique, the hash code is multiplied by a constant factor between 0 and 1 and then the fractional part is used to find the array index.
- Folding Hashing: In this technique, the key is divided into equal-sized parts, and these parts are added together to form the hash code.
- Universal Hashing: Universal hashing uses a randomized approach to select a hash function from a family of hash functions, reducing the likelihood of collisions.
- Double Hashing: It involves using two hash functions, one for the primary hash and another as a step size to resolve collisions.
16. Explain the concept of Load Factor in a Hashmap.
The load factor in a Hashmap is the ratio of the number of elements currently stored in the map to the total number of slots (buckets) available. It helps in determining when to resize the underlying array to maintain efficient operations.
Load Factor (LF) = (Number of elements in the Map) / (Total number of buckets)
The load factor is used to measure the occupancy of the Hashmap. When the load factor increases, it implies that the number of elements in the Map is approaching the array size, and it might lead to increased collisions and degraded performance.
To avoid this, we can resize the array and rehash the elements to a new array with more buckets, reducing the load factor and spreading the elements more evenly.
Example C++ code demonstrating load factor and resizing:
#include <iostream>
#include <list>
#include <string>
using namespace std;
class HashMap {
private:
static const int initialSize = 5;
list<pair<string, int>> hashArray[initialSize];
int numElements;
// Hash function
int hash(string key) {
int sum = 0;
for (char c : key)
sum += c;
return sum % currentSize;
}
// Resize the array and rehash elements
void resize() {
int newSize = currentSize * 2;
list<pair<string, int>> newArray[newSize];
// Rehash all elements to the new array
for (int i = 0; i < currentSize; i++) {
for (const auto& kvPair : hashArray[i]) {
int newIndex = hash(kvPair.first);
newArray[newIndex].push_back(kvPair);
}
}
// Update the array and currentSize
for (int i = 0; i < currentSize; i++)
hashArray[i].clear();
currentSize = newSize;
// Reassign the elements from the new array
for (int i = 0; i < currentSize; i++)
hashArray[i] = newArray[i];
}
public:
int currentSize;
// Constructor
HashMap() {
currentSize = initialSize;
numElements = 0;
}
// Insert a key-value pair into the Map
void insert(string key, int value) {
if ((double)numElements / currentSize >= 0.7)
resize();
int index = hash(key);
hashArray[index].push_back(make_pair(key, value));
numElements++;
}
// Search for a value using the key
int search(string key) {
int index = hash(key);
for (const auto& kvPair : hashArray[index]) {
if (kvPair.first == key)
return kvPair.second;
}
return -1; // Key not found
}
};
int main() {
HashMap myMap;
myMap.insert("Alice", 25);
myMap.insert("Bob", 30);
myMap.insert("John", 22);
myMap.insert("Dave", 28);
myMap.insert("Eve", 31);
cout << "Age of Bob: " << myMap.search("Bob") << endl; // Output: Age of Bob: 30
cout << "Age of Eve: " << myMap.search("Eve") << endl; // Output: Age of Eve: 31
return 0;
}In the code above, the resize() function is called whenever the load factor exceeds 0.7 (70%), and it increases the array size and rehashes the elements to ensure an optimal load factor.
17. What is rehashing in a Hashmap and when is it done?
Rehashing is the process of resizing the underlying array of a Hashmap and rehashing all the elements to new positions. It is done to maintain a balanced load factor and ensure efficient operations in the Hashmap.
Rehashing is typically performed when the load factor exceeds a certain threshold (e.g., 0.7) to avoid too many collisions and deteriorating performance. By resizing the array and rehashing the elements, the Hashmap can achieve a better distribution of keys and values, leading to improved lookup, insert, and delete operations.
Example C++ code demonstrating rehashing:
#include <iostream>
#include <list>
#include <string>
using namespace std;
class HashMap {
private:
static const int initialSize = 5;
list<pair<string, int>> hashArray[initialSize];
int numElements;
// Hash function
int hash(string key) {
int sum = 0;
for (char c : key)
sum += c;
return sum % currentSize;
}
// Resize the array and rehash elements
void rehash() {
int newSize = currentSize * 2;
list<pair<string, int>> newArray[newSize];
// Rehash all elements to the new array
for (int i = 0; i < currentSize; i++) {
for (const auto& kvPair : hashArray[i]) {
int newIndex = hash(kvPair.first);
newArray[newIndex].push_back(kvPair);
}
}
// Update the array and currentSize
for (int i = 0; i < currentSize; i++)
hashArray[i].clear();
currentSize = newSize;
// Reassign the elements from the new array
for (int i = 0; i < currentSize; i++)
hashArray[i] = newArray[i];
}
public:
int currentSize;
// Constructor
HashMap() {
currentSize = initialSize;
numElements = 0;
}
// Insert a key-value pair into the Map
void insert(string key, int value) {
if ((double)numElements / currentSize >= 0.7)
rehash();
int index = hash(key);
hashArray[index].push_back(make_pair(key, value));
numElements++;
}
// Search for a value using the key
int search(string key) {
int index = hash(key);
for (const auto& kvPair : hashArray[index]) {
if (kvPair.first == key)
return kvPair.second;
}
return -1; // Key not found
}
};
int main() {
HashMap myMap;
myMap.insert("Alice", 25);
myMap.insert("Bob", 30);
myMap.insert("John", 22);
myMap.insert("Dave", 28);
myMap.insert("Eve", 31);
cout << "Age of Bob: " << myMap.search("Bob") << endl; // Output: Age of Bob: 30
cout << "Age of Eve: " << myMap.search("Eve") << endl; // Output: Age of Eve: 31
return 0;
}In the code above, rehashing is triggered whenever the load factor exceeds 0.7 (70%) in the insert function. The rehash function is called to resize the array and rehash the elements, ensuring that the Hashmap remains efficient.
18. What is the difference between a Map and a Set?
| Map | Set |
|---|---|
| Stores key-value pairs | Stores only unique elements (keys) |
| Each element has an associated value | Each element is unique and does not have a value |
| Example: {“name”: “Alice”, “age”: 25} | Example: {“Alice”, “Bob”, “John”} |
| Lookup based on keys | Lookup based on elements |
| Allows duplicate values for different keys | Does not allow duplicate elements |
19. What are the applications of Maps?
Maps are used in various applications, including:
- Databases: Maps are used to store and index data in databases, where keys are used for fast data retrieval.
- Caches: Maps are used in caching systems to store frequently accessed data for quick retrieval.
- Language Processing: Maps are used to build dictionaries and for word frequency counting in natural language processing tasks.
- Configuration Management: Maps are used to store configuration settings and their corresponding values in applications.
20. What are the differences between a Heap and a Map in terms of structure and use-cases?
Structure Differences:
- Heap: A heap is a tree-based data structure, typically implemented as a binary heap, where the elements satisfy the heap property (max-heap or min-heap). It is mainly used for priority queue operations, sorting, and selecting extreme elements quickly.
- Map: A map (or Hashmap) is a key-value store where each element has an associated key and value. It uses a hashing technique to map keys to unique array indices for efficient retrieval of values based on keys.
Use-Cases Differences:
- Heap: Heaps are commonly used for priority queue operations, where elements with higher priorities (max-heap) or lower priorities (min-heap) are accessed quickly. It is also used in sorting algorithms like Heap Sort and in graph algorithms like Dijkstra’s algorithm.
- Map: Maps are used for associative storage, where each value is uniquely identified by its key. They are commonly used for caching, databases, language processing tasks, and various other scenarios where fast key-based retrieval is required.
Example C++ code showcasing the use of a Heap and a Map:
#include <iostream>
#include <vector>
#include <map>
#include <queue>
using namespace std;
int main() {
// Heap (Priority Queue)
priority_queue<int> maxHeap;
maxHeap.push(5);
maxHeap.push(10);
maxHeap.push(3);
maxHeap.push(7);
cout << "Max element from the heap: " << maxHeap.top() << endl; // Output: Max element from the heap: 10
// Map (Hashmap)
map<string, int> ageMap;
ageMap["Alice"] = 25;
ageMap["Bob"] = 30;
ageMap["John"] = 22;
cout << "Age of Bob from the map: " << ageMap["Bob"] << endl; // Output: Age of Bob from the map: 30
return 0;
}In the code above, we use the priority_queue as an example of a heap (priority queue) and map as an example of a Hashmap. The priority queue efficiently retrieves the maximum element, and the map efficiently retrieves the value associated with the key “Bob.”
Coding Questions
1. Implement a basic Heap data structure.
#include <vector>
class Heap {
private:
std::vector<int> heap;
public:
Heap() {}
void insert(int value) {
heap.push_back(value);
int currentIndex = heap.size() - 1;
int parentIndex = (currentIndex - 1) / 2;
while (currentIndex > 0 && heap[currentIndex] > heap[parentIndex]) {
std::swap(heap[currentIndex], heap[parentIndex]);
currentIndex = parentIndex;
parentIndex = (currentIndex - 1) / 2;
}
}
int remove() {
if (heap.empty()) {
throw std::out_of_range("Heap is empty");
}
int root = heap[0];
heap[0] = heap.back();
heap.pop_back();
heapify(0);
return root;
}
void heapify(int index) {
int largest = index;
int left = 2 * index + 1;
int right = 2 * index + 2;
if (left < heap.size() && heap[left] > heap[largest]) {
largest = left;
}
if (right < heap.size() && heap[right] > heap[largest]) {
largest = right;
}
if (largest != index) {
std::swap(heap[index], heap[largest]);
heapify(largest);
}
}
};2. Write a function to insert an element into a Heap.
void insertIntoHeap(std::vector<int>& heap, int value) {
heap.push_back(value);
int currentIndex = heap.size() - 1;
int parentIndex = (currentIndex - 1) / 2;
while (currentIndex > 0 && heap[currentIndex] > heap[parentIndex]) {
std::swap(heap[currentIndex], heap[parentIndex]);
currentIndex = parentIndex;
parentIndex = (currentIndex - 1) / 2;
}
}3. Write a function to delete an element from a Heap.
void deleteFromHeap(std::vector<int>& heap) {
if (heap.empty()) {
throw std::out_of_range("Heap is empty");
}
heap[0] = heap.back();
heap.pop_back();
heapify(heap, 0);
}4. Implement a Priority Queue using a Heap.
class PriorityQueue {
private:
Heap heap;
public:
PriorityQueue() {}
void enqueue(int value) {
heap.insert(value);
}
int dequeue() {
return heap.remove();
}
bool isEmpty() {
return heap.isEmpty();
}
};5. Write a program to build a Min-Heap.
void buildMinHeap(std::vector<int>& heap) {
int n = heap.size();
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(heap, i);
}
}6. Write a program to build a Max-Heap.
void buildMaxHeap(std::vector<int>& heap) {
int n = heap.size();
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(heap, i);
}
}7. Implement Heap Sort.
void heapSort(std::vector<int>& arr) {
int n = arr.size();
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
for (int i = n - 1; i > 0; i--) {
std::swap(arr[0], arr[i]);
heapify(arr, i, 0);
}
}8. Write a program to find the kth largest element in an array using a Heap.
int findKthLargest(std::vector<int>& arr, int k) {
std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;
for (int i = 0; i < arr.size(); i++) {
minHeap.push(arr[i]);
if (minHeap.size() > k) {
minHeap.pop();
}
}
return minHeap.top();
}9. Write a program to find the kth smallest element in an array using a Heap.
int findKthSmallest(std::vector<int>& arr, int k) {
std::priority_queue<int> maxHeap;
for (int i = 0; i < arr.size(); i++) {
maxHeap.push(arr[i]);
if (maxHeap.size() > k) {
maxHeap.pop();
}
}
return maxHeap.top();
}10. Implement a function to merge K sorted lists using a Heap.
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(nullptr) {}
};
struct CompareListNode {
bool operator()(ListNode* a, ListNode* b) {
return a->val > b->val;
}
};
ListNode* mergeKSortedLists(std::vector<ListNode*>& lists) {
std::priority_queue<ListNode*, std::vector<ListNode*>, CompareListNode> minHeap;
for (ListNode* list : lists) {
if (list) {
minHeap.push(list);
}
}
ListNode dummy(0);
ListNode* current = &dummy;
while (!minHeap.empty()) {
ListNode* node = minHeap.top();
minHeap.pop();
current->next = node;
current = current->next;
if (node->next) {
minHeap.push(node->next);
}
}
return dummy.next;
}11. Write a program to check if a given array represents a Min-Heap.
bool isMinHeap(std::vector<int>& arr) {
int n = arr.size();
for (int i = 0; i <= (n - 2) / 2; i++) {
if (arr[i] > arr[2 * i + 1] || (2 * i + 2 < n && arr[i] > arr[2 * i + 2])) {
return false;
}
}
return true;
}12. Write a program to check if a given array represents a Max-Heap.
bool isMaxHeap(std::vector<int>& arr) {
int n = arr.size();
for (int i = 0; i <= (n - 2) / 2; i++) {
if (arr[i] < arr[2 * i + 1] || (2 * i + 2 < n && arr[i] < arr[2 * i + 2])) {
return false;
}
}
return true;
}13. Implement a basic Hashmap (or Map) data structure.
#include <list>
#include <vector>
class HashMap {
private:
std::vector<std::list<std::pair<int, int>>> buckets;
int size;
int capacity;
const double LOAD_FACTOR = 0.75;
public:
HashMap(int capacity) : size(0), capacity(capacity) {
buckets.resize(capacity);
}
int hash(int key) {
return key % capacity;
}
void insert(int key, int value) {
int index = hash(key);
for (auto& pair : buckets[index]) {
if (pair.first == key) {
pair.second = value;
return;
}
}
buckets[index].push_back(std::make_pair(key, value));
size++;
if (static_cast<double>(size) / capacity >= LOAD_FACTOR) {
rehash();
}
}
int get(int key) {
int index = hash(key);
for (auto& pair : buckets[index]) {
if (pair.first == key) {
return pair.second;
}
}
return -1;
}
void remove(int key) {
int index = hash(key);
buckets[index].remove_if([&key](const std::pair<int, int>& pair) { return pair.first == key; });
}
void rehash() {
std::vector<std::list<std::pair<int, int>>> oldBuckets = buckets;
capacity *= 2;
size = 0;
buckets.clear();
buckets.resize(capacity);
for (const auto& bucket : oldBuckets) {
for (const auto& pair : bucket) {
insert(pair.first, pair.second);
}
}
}
};14. Write a function to insert a key-value pair into a Hashmap.
void insertIntoHashMap(std::vector<std::list<std::pair<int, int>>>& buckets, int key, int value, int capacity) {
int index = key % capacity;
for (auto& pair : buckets[index]) {
if (pair.first == key) {
pair.second = value;
return;
}
}
buckets[index].push_back(std::make_pair(key, value));
}15. Write a function to delete a key-value pair from a Hashmap.
void deleteFromHashMap(std::vector<std::list<std::pair<int, int>>>& buckets, int key, int capacity) {
int index = key % capacity;
buckets[index].remove_if([&key](const std::pair<int, int>& pair) { return pair.first == key; });
}16. Write a function to get the value of a given key in a Hashmap.
int getValue(std::vector<std::list<std::pair<int, int>>>& buckets, int key, int capacity) {
int index = key % capacity;
for (auto& pair : buckets[index]) {
if (pair.first == key) {
return pair.second;
}
}
return -1;
}17. Write a program to find the frequency of elements in an array using a Hashmap.
std::unordered_map<int, int> findFrequency(std::vector<int>& arr) {
std::unordered_map<int, int> frequency;
for (int num : arr) {
frequency[num]++;
}
return frequency;
}18. Write a program to find the first non-repeating character in a string using a Hashmap.
char findFirstNonRepeatingCharacter(std::string str) {
std::unordered_map<char, int> count;
for (char c : str) {
count[c]++;
}
for (char c : str) {
if (count[c] == 1) {
return c;
}
}
return '\0';
}19. Implement a LRU Cache using a Hashmap and a doubly linked list.
class LRUCache {
private:
int capacity;
std::unordered_map<int, std::pair<int, std::list<int>::iterator>> cache;
std::list<int> lruList;
public:
LRUCache(int capacity) : capacity(capacity) {}
int get(int key) {
if (cache.find(key) == cache.end()) {
return -1;
}
updateLRU(key);
return cache[key].first;
}
void put(int key, int value) {
if (cache.find(key) != cache.end()) {
updateLRU(key);
} else {
if (cache.size() == capacity) {
evictLRU();
}
lruList.push_front(key);
}
cache[key] = { value, lruList.begin() };
}
void updateLRU(int key) {
lruList.erase(cache[key].second);
lruList.push_front(key);
cache[key].second = lruList.begin();
}
void evictLRU() {
int key = lruList.back();
lruList.pop_back();
cache.erase(key);
}
};20. Write a program to find the pair of elements in an array with a given sum using a Hashmap.
std::pair<int, int> findPairWithSum(std::vector<int>& arr, int targetSum) {
std::unordered_map<int, int> numMap;
for (int i = 0; i < arr.size(); i++) {
int complement = targetSum - arr[i];
if (numMap.find(complement) != numMap.end()) {
return { numMap[complement], i };
}
numMap
[arr[i]] = i;
}
return { -1, -1 };
}21. Write a program to count the number of subarrays with a given sum in an array using a Hashmap.
int countSubarraysWithSum(std::vector<int>& arr, int targetSum) {
std::unordered_map<int, int> prefixSum;
int count = 0;
int sum = 0;
prefixSum[0] = 1;
for (int num : arr) {
sum += num;
if (prefixSum.find(sum - targetSum) != prefixSum.end()) {
count += prefixSum[sum - targetSum];
}
prefixSum[sum]++;
}
return count;
}22. Write a program to find the longest subsequence with consecutive elements in an array using a Hashmap.
int findLongestConsecutiveSubsequence(std::vector<int>& arr) {
std::unordered_set<int> numSet;
int maxLength = 0;
for (int num : arr) {
numSet.insert(num);
}
for (int num : arr) {
if (numSet.find(num - 1) == numSet.end()) {
int currentNum = num;
int currentLength = 1;
while (numSet.find(currentNum + 1) != numSet.end()) {
currentNum++;
currentLength++;
}
maxLength = std::max(maxLength, currentLength);
}
}
return maxLength;
}23. Write a program to find the longest substring without repeating characters in a string using a Hashmap.
int findLongestSubstringWithoutRepeatingCharacters(std::string str) {
std::unordered_map<char, int> charMap;
int maxLength = 0;
int start = 0;
for (int end = 0; end < str.length(); end++) {
if (charMap.find(str[end]) != charMap.end()) {
start = std::max(start, charMap[str[end]] + 1);
}
charMap[str[end]] = end;
maxLength = std::max(maxLength, end - start + 1);
}
return maxLength;
}24. Implement a function to perform rehashing in a Hashmap.
void rehashHashMap(std::vector<std::list<std::pair<int, int>>>& buckets, int& capacity) {
std::vector<std::list<std::pair<int, int>>> oldBuckets = buckets;
capacity *= 2;
buckets.clear();
buckets.resize(capacity);
for (const auto& bucket : oldBuckets) {
for (const auto& pair : bucket) {
insertIntoHashMap(buckets, pair.first, pair.second, capacity);
}
}
}25. Write a program to check if two given strings are anagrams of each other using a Hashmap.
bool areAnagrams(std::string str1, std::string str2) {
if (str1.length() != str2.length()) {
return false;
}
std::unordered_map<char, int> charCount;
for (char c : str1) {
charCount[c]++;
}
for (char c : str2) {
if (charCount.find(c) == charCount.end() || charCount[c] == 0) {
return false;
}
charCount[c]--;
}
return
true;
}26. Write a program to find common elements in three sorted arrays using a Hashmap.
std::vector<int> findCommonElements(std::vector<int>& arr1, std::vector<int>& arr2, std::vector<int>& arr3) {
std::unordered_map<int, int> elementCount;
std::vector<int> commonElements;
for (int num : arr1) {
elementCount[num]++;
}
for (int num : arr2) {
elementCount[num]++;
}
for (int num : arr3) {
if (elementCount[num] == 2) {
commonElements.push_back(num);
}
}
return commonElements;
}27. Implement Dijkstra’s algorithm using a Heap.
#include <vector>
#include <queue>
#include <limits>
#define INF std::numeric_limits<int>::max()
typedef std::pair<int, int> Pair;
std::vector<int> dijkstraAlgorithm(std::vector<std::vector<Pair>>& graph, int source) {
int V = graph.size();
std::vector<int> distances(V, INF);
std::priority_queue<Pair, std::vector<Pair>, std::greater<Pair>> minHeap;
minHeap.push(std::make_pair(0, source));
distances[source] = 0;
while (!minHeap.empty()) {
int u = minHeap.top().second;
minHeap.pop();
for (const auto& neighbor : graph[u]) {
int v = neighbor.first;
int weight = neighbor.second;
if (distances[u] + weight < distances[v]) {
distances[v] = distances[u] + weight;
minHeap.push(std::make_pair(distances[v], v));
}
}
}
return distances;
}28. Write a program to find the smallest range in K sorted lists using a Heap.
#include <vector>
#include <queue>
#include <limits>
#define INF std::numeric_limits<int>::max()
struct Element {
int value;
int listIndex;
int elementIndex;
Element(int value, int listIndex, int elementIndex) : value(value), listIndex(listIndex), elementIndex(elementIndex) {}
};
struct ElementComparator {
bool operator()(const Element& e1, const Element& e2) {
return e1.value > e2.value;
}
};
std::pair<int, int> findSmallestRange(std::vector<std::vector<int>>& lists) {
int k = lists.size();
std::priority_queue<Element, std::vector<Element>, ElementComparator> minHeap;
int currentMax = INT_MIN;
int rangeStart = 0;
int rangeEnd = INT_MAX;
for (int i = 0; i < k; i++) {
if (!lists[i].empty()) {
minHeap.push(Element(lists[i][0], i, 0));
currentMax = std::max(currentMax, lists[i][0]);
}
}
while (!minHeap.empty()) {
Element current = minHeap.top();
minHeap.pop();
if (currentMax - current.value < rangeEnd - rangeStart) {
rangeStart = current.value;
rangeEnd = currentMax;
}
if (current.elementIndex + 1 < lists[current.listIndex].size()) {
int nextValue = lists[current.listIndex][current.elementIndex + 1];
minHeap.push(Element(nextValue, current.listIndex, current.elementIndex + 1));
currentMax = std
::max(currentMax, nextValue);
} else {
break;
}
}
return std::make_pair(rangeStart, rangeEnd);
}29. Write a program to print all elements less than a value X in a Min Heap.
void printElementsLessThanX(std::vector<int>& heap, int x) {
int i = 0;
while (i < heap.size() && heap[i] < x) {
std::cout << heap[i] << " ";
i++;
}
}30. Implement a function to convert a max heap to a min heap.
void convertMaxHeapToMinHeap(std::vector<int>& heap) {
std::make_heap(heap.begin(), heap.end(), std::greater<int>());
}31. Write a program to find the median of a stream of integers using Heaps.
class MedianFinder {
private:
std::priority_queue<int> maxHeap;
std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;
public:
void addNum(int num) {
if (maxHeap.empty() || num < maxHeap.top()) {
maxHeap.push(num);
} else {
minHeap.push(num);
}
if (maxHeap.size() > minHeap.size() + 1) {
minHeap.push(maxHeap.top());
maxHeap.pop();
} else if (minHeap.size() > maxHeap.size()) {
maxHeap.push(minHeap.top());
minHeap.pop();
}
}
double findMedian() {
if (maxHeap.size() == minHeap.size()) {
return (maxHeap.top() + minHeap.top()) / 2.0;
} else {
return maxHeap.top();
}
}
};32. Write a program to implement LRU Cache using a Hashmap and doubly linked list.
class LRUCache {
private:
struct Node {
int key;
int value;
Node* prev;
Node* next;
Node(int key, int value) : key(key), value(value), prev(nullptr), next(nullptr) {}
};
int capacity;
std::unordered_map<int, Node*> cache;
Node* head;
Node* tail;
public:
LRUCache(int capacity) : capacity(capacity), head(nullptr), tail(nullptr) {}
int get(int key) {
if (cache.find(key) != cache.end()) {
Node* node = cache[key];
updateLRU(node);
return node->value;
}
return -1;
}
void put(int key, int value) {
if (cache.find(key) != cache.end()) {
Node* node = cache[key];
node->value = value;
updateLRU(node);
} else {
if (cache.size() == capacity) {
removeLRU();
}
Node* newNode = new Node(key, value);
addToFront(newNode);
cache[key] = newNode;
}
}
void updateLRU(Node* node) {
if (node == tail) {
return;
}
if (node == head) {
head = head->next;
} else {
node->prev->next = node->next;
node->next->prev = node->prev;
}
addToFront(node);
}
void addToFront(Node* node) {
if (head == nullptr) {
head = node;
tail = node;
} else {
node->next = head;
head->prev = node;
head = node;
}
}
void removeLRU() {
if (tail == nullptr) {
return;
}
if (head == tail) {
cache.erase(tail->key);
delete tail;
head = nullptr;
tail = nullptr;
} else {
Node* temp = tail;
tail = tail->prev;
tail->next = nullptr;
cache.erase(temp->key);
delete temp;
}
}
};33. Implement a Trie using a Hashmap.
class TrieNode {
public:
std::unordered_map<char, TrieNode*> children;
bool isEndOfWord;
TrieNode() : isEndOfWord(false) {}
};
class Trie {
private:
TrieNode* root;
public:
Trie() {
root = new TrieNode();
}
void insert(std::string word) {
TrieNode* current = root;
for (char c : word) {
if (current->children.find(c) == current->children.end()) {
current->children[c] = new TrieNode();
}
current = current->children[c];
}
current->isEndOfWord = true;
}
bool search(std::string word) {
TrieNode* current = root;
for (char c : word) {
if (current->children.find(c) == current->children.end()) {
return false;
}
current = current->children[c];
}
return current->isEndOfWord;
}
bool startsWith(std::string prefix) {
TrieNode* current = root;
for (char c : prefix) {
if (current->children.find(c) == current->children.end()) {
return false;
}
current = current->children[c];
}
return true;
}
};34. Write a program to implement Topological sorting using a Heap.
#include <vector>
#include <queue>
std::vector<int> topologicalSort(std::vector<std::vector<int>>& graph) {
int V = graph.size();
std::vector<int> indegree(V, 0);
for (int u = 0; u < V; u++) {
for (int v : graph[u]) {
indegree[v]++;
}
}
std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;
for (int u = 0; u < V; u++) {
if (indegree[u] == 0) {
minHeap.push(u);
}
}
std::vector<int> sortedOrder;
while (!minHeap.empty()) {
int u = minHeap.top();
minHeap.pop();
sortedOrder.push_back(u);
for (int v : graph[u]) {
indegree[v]--;
if (indegree[v] == 0) {
minHeap.push(v);
}
}
}
return sortedOrder;
}35. Implement Huffman coding using a Heap.
#include <queue>
#include <vector>
#include <string>
struct HuffmanNode {
char data;
int frequency;
HuffmanNode* left;
HuffmanNode* right;
HuffmanNode(char data, int frequency) : data(data), frequency(frequency), left(nullptr), right(nullptr) {}
};
struct HuffmanComparator {
bool operator()(const HuffmanNode* node1, const HuffmanNode* node2) {
return
node1->frequency > node2->frequency;
}
};
HuffmanNode* buildHuffmanTree(std::vector<char>& data, std::vector<int>& frequency) {
std::priority_queue<HuffmanNode*, std::vector<HuffmanNode*>, HuffmanComparator> minHeap;
for (int i = 0; i < data.size(); i++) {
minHeap.push(new HuffmanNode(data[i], frequency[i]));
}
while (minHeap.size() > 1) {
HuffmanNode* left = minHeap.top();
minHeap.pop();
HuffmanNode* right = minHeap.top();
minHeap.pop();
HuffmanNode* newNode = new HuffmanNode('\0', left->frequency + right->frequency);
newNode->left = left;
newNode->right = right;
minHeap.push(newNode);
}
return minHeap.top();
}
void generateHuffmanCodes(HuffmanNode* root, std::string code, std::unordered_map<char, std::string>& codes) {
if (root == nullptr) {
return;
}
if (root->data != '\0') {
codes[root->data] = code;
}
generateHuffmanCodes(root->left, code + "0", codes);
generateHuffmanCodes(root->right, code + "1", codes);
}36. Write a program to check if a given binary tree is a min heap.
#include <climits>
#include <queue>
class TreeNode {
public:
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int val) : val(val), left(nullptr), right(nullptr) {}
};
bool isMinHeap(TreeNode* root) {
if (root == nullptr) {
return true;
}
std::queue<TreeNode*> queue;
queue.push(root);
while (!queue.empty()) {
TreeNode* node = queue.front();
queue.pop();
if (node->left != nullptr) {
if (node->left->val < node->val) {
return false;
}
queue.push(node->left);
}
if (node->right != nullptr) {
if (node->right->val < node->val) {
return false;
}
queue.push(node->right);
}
}
return true;
}37. Write a program to implement a Deque in C++ or Java.
#include <deque>
int main() {
std::deque<int> dq;
dq.push_front(1);
dq.push_back(2);
dq.push_back(3);
std::cout << dq.front() << std::endl; // Output: 1
std::cout << dq.back() << std::endl; // Output: 3
dq.pop_front();
std::cout << dq.front() << std::endl; // Output: 2
return 0;
}38. Write a program to implement Radix Sort
#include <vector>
#include <algorithm>
void radixSort(std::vector<int>& arr) {
int maxElement = *std::max_element(arr.begin(), arr.end());
int exp = 1;
while (maxElement / exp > 0) {
std::vector<std::vector<int>> buckets(10, std::vector<int>());
for (int i = 0; i < arr.size(); i++) {
buckets[(arr[i] / exp) % 10].push_back(arr[i]);
}
int index = 0;
for (int i = 0; i < buckets.size(); i++) {
for (int j = 0; j < buckets[i].size(); j++) {
arr[index++] = buckets[i][j];
}
}
exp *= 10;
}
}39. Write a program to check if two strings are anagram using a Hashmap.
#include <unordered_map>
bool areAnagrams(std::string str1, std::string str2) {
if (str1.length() != str2.length()) {
return false;
}
std::unordered_map<char, int> charCount;
for (char c : str1) {
charCount[c]++;
}
for (char c : str2) {
if (charCount.find(c) == charCount.end() || charCount[c] == 0) {
return false;
}
charCount[c]--;
}
return true;
}40. Write a program to implement an iterator for a binary tree.
#include <stack>
class TreeNode {
public:
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int val) : val(val), left(nullptr), right(nullptr) {}
};
class BinaryTreeIterator {
private:
std::stack<TreeNode*> stack;
public:
BinaryTreeIterator(TreeNode* root) {
while (root != nullptr) {
stack.push(root);
root = root->left;
}
}
bool hasNext() {
return !stack.empty();
}
int next() {
TreeNode* current = stack.top();
stack.pop();
int val = current->val;
if (current->right != nullptr) {
current = current->right;
while (current != nullptr) {
stack.push(current);
current = current->left;
}
}
return val;
}
};MCQ Questions
1. What is a heap data structure?
a) A binary search tree
b) A data structure used for implementing priority queues
c) A data structure used for implementing hash maps
d) A data structure used for implementing stacks
Answer: b) A data structure used for implementing priority queues
2. Which of the following operations has the highest time complexity in a binary heap?
Options:
a) Insertion
b) Deletion
c) Searching
d) Heapify
Answer: d) Heapify
3. What is the maximum number of children a node can have in a binary heap?
Options:
a) 1
b) 2
c) 3
d) It can vary depending on the implementation
Answer: b) 2
4. In a max heap, what is the value of each node greater than or equal to?
Options:
a) The value of its parent node
b) The value of its left child node
c) The value of its right child node
d) The value of both its left and right child nodes
Answer: a) The value of its parent node
5. Which of the following sorting algorithms uses a heap data structure?
Options:
a) Bubble sort
b) Insertion sort
c) Merge sort
d) Heap sort
Answer: d) Heap sort
6. What is the time complexity of inserting a new element into a binary heap?
Options:
a) O(1)
b) O(log n)
c) O(n)
d) O(n log n)
Answer: b) O(log n)
7. Which of the following data structures is commonly used to implement a hash map?
Options:
a) Array
b) Linked list
c) Stack
d) Queue
Answer: a) Array
8. What is the time complexity of searching for an element in a hash map in the average case?
Options:
a) O(1)
b) O(log n)
c) O(n)
d) O(n log n)
Answer: a) O(1)
9. What is the key characteristic of a hash map?
Options:
a) Maintains elements in sorted order
b) Allows duplicate keys
c) Provides constant-time access to elements
d) Provides guaranteed insertion order
Answer: c) Provides constant-time access to elements
10. Which collision resolution technique is commonly used in hash maps?
Options:
a) Linear probing
b) Binary search
c) Depth-first search
d) Breadth-first search
Answer: a) Linear probing
11. Which of the following operations has a worst-case time complexity of O(n) in a hash map?
Options:
a) Insertion
b) Deletion
c) Searching
d) Updating
Answer: b) Deletion
12. Which data structure is typically used to implement an open-addressed hash map?
Options:
a) Binary search tree
b) Linked list
c) Stack
d) Array
Answer: d) Array
13. What is the purpose of a hash function in a hash map?
Options:
a) To generate a unique identifier for each element
b) To determine the position of an element in the hash map
c) To sort the elements in the hash map
d) To calculate the average search time in the hash map
Answer: b) To determine the position of an element in the hash map
14. Which of the following statements about heaps is true?
Options:
a) Heaps guarantee the order of insertion and retrieval of elements.
b) Heaps provide constant-time access to any element.
c) Heaps are always balanced binary trees.
d) Heaps can be min heaps or max heaps.
Answer: d) Heaps can be min heaps or max heaps.
15. Which of the following statements about hash maps is true?
Options:
a) Hash maps maintain elements in sorted order.
b) Hash maps provide constant-time access to any element.
c) Hash maps do not allow duplicate keys.
d) Hash maps can only store primitive data types.
Answer: b) Hash maps provide constant-time access to any element.
16. In a binary heap, what is the relationship between a node and its parent?
Options:
a) The parent node is always greater than its child nodes.
b) The parent node is always less than its child nodes.
c) There is no specific relationship between a node and its parent.
d) The parent node is either greater or equal to its child nodes.
Answer: d) The parent node is either greater or equal to its child nodes.
17. Which of the following statements about heaps and hash maps is true?
Options:
a) Heaps are based on arrays, while hash maps are based on linked lists.
b) Heaps are used for sorting, while hash maps are used for efficient key-value storage.
c) Heaps use a hash function for element retrieval, while hash maps use a heapify operation.
d) Heaps and hash maps are equivalent terms for the same data structure.
Answer: b) Heaps are used for sorting, while hash maps are used for efficient key-value storage.
18. Which of the following is an advantage of using a heap over a balanced binary search tree?
Options:
a) Faster element insertion and deletion
b) Guaranteed logarithmic time complexity for all operations
c) Support for efficient key-value storage
d) Built-in collision resolution techniques
Answer: a) Faster element insertion and deletion
19. What is the maximum height of a binary heap with N elements?
Options:
a) N
b) log N
c) N/2
d) log (N+1)
Answer: b) log N
20. Which of the following operations can be performed efficiently on both heaps and hash maps?
Options:
a) Searching for a specific element
b) Insertion of a new element
c) Deletion of an element
d) Sorting the elements
Answer: c) Deletion of an element
21. What is the time complexity of extracting the minimum element from a min heap?
Options:
a) O(1)
b) O(log N)
c) O(N)
d) O(N log N)
Answer: b) O(log N)
22. Which data structure is typically used to implement a priority queue?
Options:
a) Stack
b) Queue
c) Heap
d) Hash map
Answer: c) Heap
23. In a min heap, which element is always at the root?
Options:
a) The smallest element
b) The largest element
c) The median element
d) The middle element
Answer: a) The smallest element
24. Which of the following operations can be performed on a max heap?
Options:
a) Extracting the maximum element
b) Extracting the minimum element
c) Inserting a new element
d) Searching for a specific element
Answer: a) Extracting the maximum element
25. How is the order of elements maintained in a hash map?
Options:
a) By using a sorting algorithm
b) By using a hash function
c) By using a linked list
d) By using a heapify operation
Answer: b) By using a hash function
26. Which of the following data structures provides constant-time access to elements based on their keys?
Options:
a) Array
b) Linked list
c) Stack
d) Hash map
Answer: d) Hash map
27. What is the purpose of collision resolution techniques in hash maps?
Options:
a) To prevent collisions from occurring
b) To rearrange the elements for better performance
c) To handle cases when two keys map to the same index
d) To ensure that all elements are stored in sorted order
Answer: c) To handle cases when two keys map to the same index
28. Which type of heap orders elements in ascending order?
Options:
a) Min heap
b) Max heap
c) Binary heap
d) Balanced heap
Answer: a) Min heap
29. What is the primary advantage of using a hash map over an array?
Options:
a) Constant-time access to elements
b) Support for duplicate elements
c) Ordered storage of elements
d) Reduced memory usage
Answer: a) Constant-time access to elements
30. Which operation is not supported by a heap data structure?
Options:
a) Insertion
b) Deletion
c) Searching
d) Updating
Answer: c) Searching
