In the context of external sorting, what does the term 'run' typically refer to?
The process of merging two sorted subarrays.
The number of disk I/O operations performed.
A single pass through the entire dataset.
A sequence of sorted elements that can be held in memory.
You are given an array of integers nums and an integer k. Find the total number of continuous subarrays whose sum equals to k.
Use a hash table to store the cumulative sum of elements and their frequency.
Use dynamic programming to store the number of subarrays with sum k ending at each index.
Use two nested loops to iterate through all possible subarrays.
Use a sliding window approach to find subarrays with the given sum.
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 a divide and conquer approach to find the minimum element in each subarray.
Iterate through the array and maintain a stack to track potential rectangle heights.
Use dynamic programming to store the maximum area ending at each index.
Sort the array and calculate the area for each subarray.
What is a significant disadvantage of using arrays for storing and processing extremely large datasets, particularly in the context of limited memory resources?
Arrays require contiguous blocks of memory, which can be difficult to allocate for massive datasets.
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 have slow access times for individual elements.
Which sorting algorithm is generally considered IN-PLACE, meaning it requires minimal additional memory overhead?
Quick Sort
Bucket Sort
Radix Sort (using counting sort as a subroutine)
External Merge Sort
Given an array of n integers, find three elements in the array such that the sum is closest to a given target number. Return the sum of the three integers.
Use a hash table to store the sum of all pairs of elements.
Sort the array and use two pointers to find pairs of elements with a sum close to the target minus the current element.
Use dynamic programming to store the closest sum for all subarrays of size three.
Use three nested loops to iterate through all possible triplets.
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?
Singly Linked List
Circular Buffer
Binary Search Tree
Doubly Linked List
Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn't one, return 0 instead.
Use binary search to find the minimal length.
Use a sliding window approach to find the minimal length subarray.
Use dynamic programming to store the minimal length for all subarrays ending at each index.
Radix Sort operates by:
Recursively dividing the array and sorting subarrays.
Distributing elements into buckets based on individual digits or characters.
Building a binary tree and performing an in-order traversal.
Comparing elements and swapping them based on their values.
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?
Multidimensional Array
Linked List
Hash Table
Binary Tree