In the context of external sorting, what does the term 'run' typically refer to?
A single pass through the entire dataset.
A sequence of sorted elements that can be held in memory.
The process of merging two sorted subarrays.
The number of disk I/O operations performed.
Which sorting algorithm is the MOST suitable for sorting a massive dataset that cannot fit entirely in RAM?
Quick Sort
Merge Sort
Bubble Sort
External Merge Sort
What is a key advantage of Radix Sort over comparison-based sorting algorithms like Quick Sort and Merge Sort?
Radix Sort is generally more suitable for sorting strings than numerical data.
Radix Sort is always more space-efficient than comparison-based algorithms.
Radix Sort can achieve better than O(n log n) time complexity in certain cases.
Radix Sort guarantees stability, while Quick Sort and Merge Sort do not.
You are given an array of integers and a target sum. Find all unique quadruplets in the array that sum up to the target sum.
Sort the array and use two pointers to find pairs of elements that sum up to a specific value.
Use four nested loops to iterate through all possible combinations of four elements.
Use a hash table to store the sum of all pairs of elements.
Use a backtracking algorithm to explore all possible combinations of elements.
You are designing a dynamic array implementation that needs to support efficient insertion at both the beginning and the end. Which of the following underlying data structures would be the MOST suitable to achieve this with optimal time complexity?
Binary Search Tree
Singly Linked List
Circular Buffer
Doubly Linked List
Radix Sort operates by:
Building a binary tree and performing an in-order traversal.
Recursively dividing the array and sorting subarrays.
Distributing elements into buckets based on individual digits or characters.
Comparing elements and swapping them based on their values.
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?
Linear Search
Binary Search
Selection Sort
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 log N)
O(N^2)
O(N)
O(log N)
Which data structure would be the MOST suitable for implementing a sparse matrix efficiently, where most elements are zero, to save memory and potentially improve computation speed?
Hash Table
Binary Tree
Multidimensional Array
Linked List
Which of the following array operations has an average-case time complexity that differs from its worst-case time complexity?
Inserting an element at the beginning of a dynamic array (implemented with reallocation).
Searching for a specific value in a sorted array.
Accessing an element at a given index.
Deleting an element from the end of an array.