What is the time complexity of Bucket Sort in the average case, assuming uniformly distributed data and a fixed number of buckets?
O(log n)
O(n)
O(n log n)
O(n^2)
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?
Doubly Linked List
Singly Linked List
Circular Buffer
Binary Search Tree
Given an array of integers, find the subarray with the maximum sum in linear time. The subarray must contain at least one element.
Dynamic programming approach by building a table to store the maximum sum ending at each index.
Kadane's Algorithm, which iterates through the array, keeping track of the maximum sum ending at each index.
Brute force approach by checking all possible subarrays.
Divide and conquer approach by finding the maximum subarray in the left half, right half, and the one crossing the midpoint.
Which sorting algorithm is the MOST suitable for sorting a massive dataset that cannot fit entirely in RAM?
External Merge Sort
Bubble Sort
Merge Sort
Quick Sort
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 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.
Sort the array and use two pointers to find pairs of elements that sum up to a specific value.
Use a backtracking algorithm to explore all possible combinations of elements.
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.
Sort the array and calculate the area for each subarray.
Use a divide and conquer approach to find the minimum element in each subarray.
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.
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)
O(N log N)
O(log N)
O(N^2)
Given an array of integers, find the kth largest element in the array.
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.
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.
What is a key advantage of Radix Sort over comparison-based sorting algorithms like Quick Sort and Merge Sort?
Radix Sort guarantees stability, while Quick Sort and Merge Sort do not.
Radix Sort is always more space-efficient than comparison-based algorithms.
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.
Given an unsorted array of integers, find the length of the longest consecutive sequence.
Use dynamic programming to store the length of the longest consecutive sequence ending at each index.
Sort the array and iterate through it to find the longest consecutive sequence.
Use a hash table to store the elements of the array and their visited status.
Use a sliding window approach to find the longest consecutive sequence.