Given an array of integers, find the kth largest element in the array.
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.
Use quickselect, a selection algorithm with an average time complexity of O(n).
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)
You need to sort a massive dataset of social media posts by timestamp. The timestamps are represented as long integers. Which sorting approach is likely the MOST efficient?
Bucket Sort with buckets representing time intervals (e.g., hours, days)
External Merge Sort, as timestamps are naturally comparable
Radix Sort using a base that aligns with the structure of the timestamps
Any of the above would be equally efficient for this scenario
Radix Sort operates by:
Distributing elements into buckets based on individual digits or characters.
Building a binary tree and performing an in-order traversal.
Recursively dividing the array and sorting subarrays.
Comparing elements and swapping them based on their values.
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?
Circular Buffer
Doubly Linked List
Singly Linked List
Binary Search Tree
In the context of amortized analysis, what is the purpose of the potential function?
To analyze the space complexity of an algorithm.
To determine the maximum possible runtime of a single operation in the worst-case scenario.
To optimize the performance of individual array operations.
To calculate the average runtime of a single operation over a sequence of operations.
Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the missing number.
Use the XOR operation to find the missing number.
Sort the array and find the missing element.
Use a hash table to store the presence of each number.
Calculate the sum of all numbers from 0 to n and subtract the sum of the array elements.
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 a sliding window approach to find the minimal length subarray.
Use two nested loops to iterate through all possible subarrays.
Use binary search to find the minimal length.
Use dynamic programming to store the minimal length for all subarrays ending at each index.
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 a sliding window approach to find subarrays with the given sum.
Use dynamic programming to store the number of subarrays with sum k ending at each index.
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.
The number of disk I/O operations performed.
A sequence of sorted elements that can be held in memory.