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
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?
Selection Sort
Binary Search
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.
Sort the array and find the missing element.
Use the XOR operation to find the missing number.
Calculate the sum of all numbers from 0 to n and subtract the sum of the array elements.
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 sliding window approach to find subarrays with the given sum.
Use two nested loops to iterate through all possible subarrays.
Use dynamic programming to store the number of subarrays with sum k ending at each index.
Use a hash table to store the cumulative sum of elements and their frequency.
In the context of external sorting, what does the term 'run' typically refer to?
A single pass through the entire dataset.
The process of merging two sorted subarrays.
A sequence of sorted elements that can be held in memory.
The number of disk I/O operations performed.
Which of the following array operations has an average-case time complexity that differs from its worst-case time complexity?
Accessing an element at a given index.
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.
Given an array of integers, find the kth largest element in the array.
Use a min-heap of size k to store the k largest elements encountered so far.
Sort the array and return the element at the kth position from the end.
Use quickselect, a selection algorithm with an average time complexity of O(n).
Use a max-heap to store all the elements and extract the kth largest element.
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 can achieve better than O(n log n) time complexity in certain cases.
Radix Sort is always more space-efficient than comparison-based algorithms.
Radix Sort guarantees stability, while Quick Sort and Merge Sort do not.
Which sorting algorithm is generally considered IN-PLACE, meaning it requires minimal additional memory overhead?
Bucket Sort
Quick Sort
External Merge Sort
Radix Sort (using counting sort as a subroutine)
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.
Use a backtracking algorithm to explore all possible combinations of elements.
Use a hash table to store the sum of all pairs of elements.
Use four nested loops to iterate through all possible combinations of four elements.
Sort the array and use two pointers to find pairs of elements that sum up to a specific value.