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
Binary Search Tree
Circular Buffer
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 two nested loops to iterate through all possible subarrays.
Use dynamic programming to store the minimal length for all subarrays ending at each index.
Use binary search to find the minimal length.
Use a sliding window approach to find the minimal length subarray.
External Merge Sort is particularly well-suited for scenarios where:
The elements are already nearly sorted.
The dataset is small and fits entirely in memory.
Real-time sorting is required.
The data is stored on a slow, disk-based storage device.
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 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.
Use quickselect, a selection algorithm with an average time complexity of O(n).
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 guarantees stability, while Quick Sort and Merge Sort do not.
Radix Sort can achieve better than O(n log n) time complexity in certain cases.
Radix Sort is always more space-efficient than comparison-based algorithms.
Which sorting algorithm is the MOST suitable for sorting a massive dataset that cannot fit entirely in RAM?
Bubble Sort
Merge Sort
Quick Sort
External Merge Sort
Which of the following factors significantly influences the choice of sorting algorithm for large datasets?
Available memory and storage space
Data distribution (uniform, sorted, reverse sorted, etc.)
All of the above
Stability of the sorting algorithm (whether it maintains relative order of equal elements)
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
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)
Radix Sort operates by:
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.
Building a binary tree and performing an in-order traversal.