Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the missing number.
Calculate the sum of all numbers from 0 to n and subtract the sum of the array elements.
Sort the array and find the missing element.
Use a hash table to store the presence of each number.
Use the XOR operation to find the missing number.
Which sorting algorithm is generally considered IN-PLACE, meaning it requires minimal additional memory overhead?
Bucket Sort
External Merge Sort
Quick Sort
Radix Sort (using counting sort as a subroutine)
What is the time complexity of Bucket Sort in the average case, assuming uniformly distributed data and a fixed number of buckets?
O(n)
O(n log n)
O(log n)
O(n^2)
Given an unsorted array of integers, find the length of the longest consecutive sequence.
Use a sliding window approach to find the longest consecutive sequence.
Sort the array and iterate through it to find the longest consecutive sequence.
Use dynamic programming to store the length of the longest consecutive sequence ending at each index.
Use a hash table to store the elements of the array and their visited status.
In the context of external sorting, what does the term 'run' typically refer to?
A sequence of sorted elements that can be held in memory.
The process of merging two sorted subarrays.
A single pass through the entire dataset.
The number of disk I/O operations performed.
You need to perform matrix multiplication on two large matrices, A and B, where A is of size M x N and B is of size N x P. You have multiple machines available for distributed computing. Which approach would likely yield the BEST performance improvement?
Performing the matrix multiplication sequentially on a single machine without any distribution.
Divide both matrices A and B into smaller, equally sized submatrices and distribute the computation of these submatrices across the machines.
Divide matrix B into column blocks and distribute each block with a copy of A to different machines.
Divide matrix A into row blocks and distribute each block with a copy of B to different machines.
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?
Any of the above would be equally efficient for this scenario
Bucket Sort with buckets representing time intervals (e.g., hours, days)
Radix Sort using a base that aligns with the structure of the timestamps
External Merge Sort, as timestamps are naturally comparable
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
Doubly Linked List
Singly Linked List
Circular Buffer
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
Bubble Sort
Linear Search
Binary Search
Radix Sort operates by:
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.
Distributing elements into buckets based on individual digits or characters.