Which of the following is the time complexity of a find operation in Disjoint Set Union (DSU) with path compression?
A O(1)
B O(log n)
C O(n)
D O(log log n)
Path compression in DSU makes the trees flatter, resulting in nearly constant time complexity for the find operation. The time complexity is effectively O(log log n), making DSU very efficient for large datasets.
Which of the following is a feature of a doubly linked list?
A One pointer per node
B Fixed size
C Two pointers per node
D No next node
In a doubly linked list, each node contains two pointers: one pointing to the next node and another pointing to the previous node. This allows traversal in both directions, providing more flexibility compared to a singly linked list.
Which data structure is used to efficiently handle range sum queries and updates?
A Segment Tree
B Hash Table
C Binary Search Tree
D Fenwick Tree
A Segment Tree is specifically designed for efficiently handling range queries and updates, such as range sum queries. It allows updates and queries in O(log n) time, making it suitable for dynamic datasets where values change frequently.
In a Bloom Filter, which of the following is true?
A It guarantees no false positives
B It allows false positives
C It guarantees no false negatives
D It does not use any hash functions
Bloom Filters are probabilistic data structures that allow false positives but never false negatives. They provide a space efficient way to test set membership, although they may incorrectly report that an element is in the set.
Which of the following data structures supports efficient substring searches?
A Trie
B Hash Table
C Linked List
D Stack
A Trie is particularly well suited for substring searches and prefix matching. By storing each character of a string as a node, Tries allow efficient lookups, making them ideal for autocomplete and dictionary applications.
What is the main advantage of using a circular linked list?
A Fixed size
B Constant time traversal
C Continuous traversal
D Doubly linked
In a circular linked list, the last node points back to the first node, allowing for continuous traversal. This is useful in applications like round robin scheduling or in cases where a circular data structure is needed.
What is the space complexity of a Segment Tree?
A O(n)
B O(n log n)
C O(log n)
D O(nĀ²)
A Segment Tree requires O(n log n) space because it needs to store nodes for each segment of the array and its divisions. This space usage is necessary to allow efficient range queries and updates.
Which of the following is true about a Skip List?
A It is based on binary search
B It uses a hash table for quick lookups
C It is a layered linked list for faster search
D It is slower than binary search trees
A Skip List is a layered linked list that allows for faster search operations by “skipping” over multiple elements in each level. It provides O(log n) time complexity for search, insertion, and deletion, making it an alternative to balanced trees.
Which data structure is typically used in AI for representing decision trees?
A Trie
B Stack
C Tree
D Graph
In AI, decision trees are commonly used to model decisions and their possible consequences. Each node represents a decision or outcome, and the tree structure allows for efficient exploration of different decision paths.
What is the main advantage of a Red Black Tree over an AVL Tree?
A Simpler balancing rules
B More efficient searching
C Requires less memory
D More flexible structure
Red Black Trees have simpler balancing rules compared to AVL Trees. This makes them easier to implement and maintain, although AVL Trees tend to provide slightly better balancing, resulting in faster operations in some cases.
Which of the following operations can a Trie data structure perform efficiently?
A Searching for exact matches
B Sorting elements
C Range queries
D Merging trees
A Trie is highly efficient for searching for exact matches in a set of strings. It allows for fast retrieval of strings by storing characters as nodes and leveraging shared prefixes for faster searches.
Which of the following is a disadvantage of using a Fenwick Tree?
A High space complexity
B Slow updates
C Cannot handle range queries
D Limited to range sum queries
While Fenwick Trees are efficient for range sum queries and point updates, they are limited in that they do not support arbitrary range queries or more complex operations like range minimum queries without modifications.
Which of the following operations is the Disjoint Set Union (DSU) structure optimized for?
A Sorting
B Searching
C Union and Find
D Range queries
The Disjoint Set Union (DSU) structure is optimized for union and find operations. It efficiently manages the merging of sets and finding the root of an element, often used in algorithms for network connectivity or connected components in graphs.
Which memory allocation technique divides memory into equal sized blocks?
A Paging
B Segmentation
C Stack allocation
D Linked allocation
Paging divides memory into fixed size blocks called pages. This helps avoid external fragmentation and allows non-contiguous memory allocation, making it easier to manage memory and utilize space efficiently.
Which data structure would you use for implementing an autocomplete feature in a search engine?
A Stack
B Trie
C Queue
D Hash Table
A Trie is ideal for autocomplete features because it allows efficient prefix searches. Each node in a Trie represents a character in a word, making it easy to suggest completions based on user input in real-time.