What is the main advantage of using a Segment Tree?
A Efficient range queries
B Simple to implement
C Fixed size structure
D Reduces space complexity
A Segment Tree is designed to efficiently answer range queries, such as sum, minimum, or maximum over a segment of an array. It provides O(log n) time complexity for both queries and updates, making it highly efficient for dynamic intervals.
What is the time complexity for querying a range sum in a Fenwick Tree (Binary Indexed Tree)?
A O(n)
B O(log n)
C O(n log n)
D O(1)
The Fenwick Tree (or Binary Indexed Tree) allows for efficient updates and range queries in O(log n) time. This makes it particularly useful for scenarios where frequent updates and queries are required on an array of data.
What is a Suffix Tree used for?
A Searching substrings
B Sorting elements
C Searching for patterns
D Memory optimization
A Suffix Tree is a powerful data structure that allows for fast searching of substrings within a string. It supports various operations like substring search, longest common substring, and more, all in linear time relative to the string length.
Which of the following is the primary operation supported by a Disjoint Set Union (DSU)?
A Find
B Merge
C Union
D All of the above
A Disjoint Set Union (DSU), also known as Union Find, supports three primary operations: find (to determine the set an element belongs to), union (to merge two sets), and path compression (to optimize future queries).
What is the space complexity of a Segment Tree?
A O(n)
B O(n log n)
C O(log n)
D O(1)
The space complexity of a Segment Tree is O(n log n) because it requires storing nodes for each segment and its splits. This space usage allows the tree to efficiently handle dynamic range queries and updates.
Which of the following operations can be performed efficiently by a Disjoint Set Union (DSU) with path compression?
A Sorting
B Range Queries
C Union of sets
D Finding the longest path
A Disjoint Set Union (DSU) with path compression efficiently supports union and find operations. Path compression ensures that trees are shallow, making future find operations faster, improving the performance of the DSU operations to nearly constant time.
Which of the following is a key feature of a Fenwick Tree?
A It stores the entire array
B It supports constant time queries
C It is used for range sum queries
D It has no space overhead
A Fenwick Tree (Binary Indexed Tree) is specifically designed for efficiently answering range sum queries. It allows updates and queries in O(log n) time, making it highly efficient for cumulative frequency tables and prefix sum calculations.
What is the main difference between a Segment Tree and a Binary Indexed Tree (Fenwick Tree)?
A Segment Tree supports both range queries and point updates
B Fenwick Tree is more efficient for range queries
C Segment Tree has O(n) space complexity
D Fenwick Tree is a tree based structure
A Segment Tree is more versatile than a Fenwick Tree as it can handle both range queries and point updates efficiently. Fenwick Tree, on the other hand, is typically used for cumulative frequency calculations and performs well with range sum queries.
What is the primary advantage of using path compression in a Disjoint Set Union (DSU)?
A Reduces time complexity for union operations
B Makes the tree shallow
C Increases memory usage
D Speeds up find operations
Path compression in DSU optimizes the find operation by flattening the structure of the tree, making future queries faster. It ensures that elements directly point to their root, reducing the height of the tree and improving performance.
Which operation does a Suffix Tree allow to perform in O(n) time?
A Finding the longest common prefix
B Finding the longest repeated substring
C Finding all occurrences of a substring
D All of the above
A Suffix Tree allows efficient querying in O(n) time for various operations, including finding the longest common prefix, longest repeated substring, and occurrences of substrings, making it a powerful tool for string analysis.
Which of the following operations is not supported efficiently by a Fenwick Tree?
A Point updates
B Range queries
C Range updates
D Range sum queries
A Fenwick Tree supports point updates and range sum queries efficiently in O(log n) time. However, it is not well suited for range updates. Segment Trees are more appropriate for problems involving range updates.
What is the worst-case time complexity of a find operation in a Disjoint Set Union (DSU) without path compression?
A O(1)
B O(log n)
C O(n)
D O(n log n)
Without path compression, the find operation in a Disjoint Set Union (DSU) can take O(n) time in the worst case. This happens when the tree is deep, and each find operation requires traversing the entire tree.
What type of data structure is used to implement a Suffix Tree?
A Trie
B Hash Map
C Binary Tree
D Array
A Suffix Tree is typically implemented as a specialized form of a Trie. It is a tree like structure where each edge represents a substring of the string, allowing efficient searches for patterns and substrings.
Which of the following is a drawback of a Segment Tree?
A It requires too much space
B It cannot handle range queries
C It is slower than a Fenwick Tree
D It is not suitable for dynamic datasets
A Segment Tree uses O(n log n) space, which can be inefficient for very large datasets. Although it is powerful for range queries and updates, its space usage may be excessive compared to simpler structures like Fenwick Trees.
What is the time complexity of the union operation in DSU with union by rank and path compression?
A O(1)
B O(log n)
C O(n)
D O(log log n)
With union by rank and path compression, the union operation in DSU is nearly constant time, with a time complexity of O(log log n). This is because the operations keep the trees flat and efficient for future queries.