External Merge Sort is particularly well-suited for scenarios where:
The dataset is small and fits entirely in memory.
The data is stored on a slow, disk-based storage device.
The elements are already nearly sorted.
Real-time sorting is required.
What is a key advantage of Radix Sort over comparison-based sorting algorithms like Quick Sort and Merge Sort?
Radix Sort guarantees stability, while Quick Sort and Merge Sort do not.
Radix Sort is always more space-efficient than comparison-based algorithms.
Radix Sort is generally more suitable for sorting strings than numerical data.
Radix Sort can achieve better than O(n log n) time complexity in certain cases.
What is a significant disadvantage of using arrays for storing and processing extremely large datasets, particularly in the context of limited memory resources?
Arrays do not support dynamic resizing, making it challenging to handle growing datasets.
Arrays are not suitable for storing structured data, such as key-value pairs.
Arrays require contiguous blocks of memory, which can be difficult to allocate for massive datasets.
Arrays have slow access times for individual elements.
Which sorting algorithm is generally considered IN-PLACE, meaning it requires minimal additional memory overhead?
Bucket Sort
Radix Sort (using counting sort as a subroutine)
Quick Sort
External Merge Sort
In the context of external sorting, what does the term 'run' typically refer to?
The number of disk I/O operations performed.
The process of merging two sorted subarrays.
A single pass through the entire dataset.
A sequence of sorted elements that can be held in memory.
Given an array of integers, find the kth largest element in the array.
Use quickselect, a selection algorithm with an average time complexity of O(n).
Sort the array and return the element at the kth position from the end.
Use a min-heap of size k to store the k largest elements encountered so far.
Use a max-heap to store all the elements and extract the kth largest element.
Given an unsorted array of integers, find the length of the longest consecutive sequence.
Use a hash table to store the elements of the array and their visited status.
Use a sliding window approach to find the longest consecutive sequence.
Sort the array and iterate through it to find the longest consecutive sequence.
Use dynamic programming to store the length of the longest consecutive sequence ending at each index.
Imagine you have a sorted array, and you want to find the index of the first element that is greater than a given target value. Which algorithm would provide the most efficient solution?
Bubble Sort
Binary Search
Selection Sort
Linear Search
Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the missing number.
Use the XOR operation to find the missing number.
Use a hash table to store the presence of each number.
Calculate the sum of all numbers from 0 to n and subtract the sum of the array elements.
Sort the array and find the missing element.
Consider an algorithm that iterates through a sorted array of size N. In each iteration, it performs a binary search on the array. What is the overall time complexity of this algorithm?
O(N^2)
O(N)
O(N log N)
O(log N)