An array is a _______ structure that stores a collection of _______ elements.
- Linear, Heterogeneous
- Linear, Homogeneous
- Non-linear, Heterogeneous
- Non-linear, Homogeneous
An array is a linear structure that stores a collection of homogeneous elements. It means that all elements in the array are of the same data type.
Topological sorting is often used in _______ resolution, particularly in systems involving tasks with dependencies.
- Conflict
- Dependency
- Priority
- Scheduling
Topological sorting is often used in Scheduling resolution, particularly in systems involving tasks with dependencies. It helps in determining the order of execution for tasks based on their dependencies, ensuring a systematic and correct execution flow.
Array manipulation involves operations such as _______ and _______ to modify array elements.
- Concatenation, rotation
- Insertion, deletion
- Sorting, searching
- Traversal, deletion
Array manipulation involves operations such as insertion and deletion to modify array elements. Insertion adds elements at a specific position, and deletion removes elements from a given position, helping to manage the array's content dynamically.
Explain the difference between the coin change problem and the knapsack problem.
- Both problems are identical and interchangeable.
- The coin change problem involves finding the number of ways to make a specific amount using given denominations, without considering the quantity of each coin. The knapsack problem, on the other hand, considers the weight and value of items to maximize the total value in a knapsack with limited capacity.
- The coin change problem is a variation of the knapsack problem, with both focusing on maximizing the total value.
- The knapsack problem involves finding the number of ways to make a specific amount using given denominations, without considering the quantity of each coin. The coin change problem, on the other hand, considers the weight and value of items.
The main difference lies in their objectives. The coin change problem aims to find the number of ways to make a specific amount, while the knapsack problem focuses on maximizing the total value considering weight constraints.
Can BFS be used to find the shortest path between two nodes in an unweighted graph?
- It depends
- No
- Only in directed graphs
- Yes
Yes, BFS can be used to find the shortest path between two nodes in an unweighted graph. As BFS explores the graph level by level, the first time the destination node is reached, it guarantees the shortest path as it explores nodes in order of their distance from the source.
Can DFS be used to find the shortest path in a graph?
- No
- Only in acyclic graphs
- Only in weighted graphs
- Yes
No, DFS does not guarantee finding the shortest path in a graph. It can find a path, but it may not be the shortest. BFS is more suitable for finding the shortest path as it explores nodes level by level.
A hash table typically consists of an array of _______ and a hash function that maps _______ to indices in the array.
- Buckets, keys
- Elements, addresses
- Linked lists, keys
- Nodes, values
A hash table typically consists of an array of buckets and a hash function that maps keys to indices in the array. The array is divided into buckets, each capable of holding multiple key-value pairs. The hash function determines which bucket a key should go to.
Suppose you are faced with a scenario where the coin denominations are arbitrary and not necessarily sorted. How would you modify the dynamic programming solution to handle this situation?
- Convert the problem into a graph and apply Dijkstra's algorithm.
- Modify the dynamic programming approach to handle arbitrary denominations without sorting.
- Sort the coin denominations in descending order before applying dynamic programming.
- Use a different algorithm such as quicksort to sort the denominations during runtime.
To handle arbitrary and unsorted coin denominations, you would modify the dynamic programming solution by ensuring that the algorithm considers all possible denominations for each subproblem. Sorting is not necessary; instead, the algorithm dynamically adjusts to the available denominations, optimizing the solution for each specific scenario.
The time complexity of binary search is _______ due to its divide-and-conquer approach.
- O(1)
- O(log n)
- O(n)
- O(n^2)
The time complexity of binary search is O(log n) due to its divide-and-conquer approach. This is because with each comparison, the search space is effectively halved.
Selection sort's time complexity remains _______ regardless of the input sequence.
- O(log n)
- O(n log n)
- O(n)
- O(n^2)
The time complexity of selection sort is O(n^2), and it remains the same regardless of the input sequence. This is because it involves nested loops to iterate over the elements for comparisons and swaps, resulting in quadratic time complexity.
What is the difference between Dijkstra's algorithm and breadth-first search (BFS)?
- Dijkstra's is for finding connected components, BFS is for finding shortest paths
- Dijkstra's is for weighted graphs, BFS is for unweighted graphs
- Dijkstra's is only for directed graphs, BFS is for undirected graphs
- Dijkstra's uses a stack, BFS uses a queue
The main difference lies in their applications - Dijkstra's algorithm is designed for finding the shortest path in weighted graphs, while BFS is used for exploring and finding the shortest paths in unweighted graphs.
A dynamic programming approach to finding the Longest Palindromic Substring typically involves constructing a _______ to store intermediate results.
- Binary tree
- Hash table
- Memoization table
- Priority queue
A dynamic programming approach to finding the Longest Palindromic Substring typically involves constructing a memoization table to store intermediate results. This table is used to avoid redundant computations by caching and reusing previously computed results during the recursive process.