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.
Deleting an element from the end of an array.
Accessing an element at a given 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?
Binary Search
Selection Sort
Linear Search
Bubble Sort
Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the missing number.
Use a hash table to store the presence of each number.
Use the XOR operation to find the missing number.
Sort the array and find the missing element.
Calculate the sum of all numbers from 0 to n and subtract the sum of the array elements.
Given an array of integers, find the kth largest element in the array.
Sort the array and return the element at the kth position from the end.
Use a max-heap to store all the elements and extract the kth largest element.
Use quickselect, a selection algorithm with an average time complexity of O(n).
Use a min-heap of size k to store the k largest elements encountered so far.
What is a significant disadvantage of using arrays for storing and processing extremely large datasets, particularly in the context of limited memory resources?
Arrays have slow access times for individual elements.
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.
External Merge Sort is particularly well-suited for scenarios where:
Real-time sorting is required.
The elements are already nearly sorted.
The dataset is small and fits entirely in memory.
The data is stored on a slow, disk-based storage device.
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
Circular Buffer
Singly Linked List
Doubly Linked List
You are given an unsorted array of integers where each element represents the height of a bar in a histogram. Find the largest rectangular area in the histogram.
Use dynamic programming to store the maximum area ending at each index.
Iterate through the array and maintain a stack to track potential rectangle heights.
Use a divide and conquer approach to find the minimum element in each subarray.
Sort the array and calculate the area for each subarray.
In the context of external sorting, what does the term 'run' typically refer to?
The number of disk I/O operations performed.
A sequence of sorted elements that can be held in memory.
The process of merging two sorted subarrays.
A single pass through the entire dataset.
Given an array of integers, find the subarray with the maximum sum in linear time. The subarray must contain at least one element.
Kadane's Algorithm, which iterates through the array, keeping track of the maximum sum ending at each index.
Divide and conquer approach by finding the maximum subarray in the left half, right half, and the one crossing the midpoint.
Brute force approach by checking all possible subarrays.
Dynamic programming approach by building a table to store the maximum sum ending at each index.