Which data structure is used to implement a Skip List?
A Linked List
B Array
C Tree
D Hash Table
A Skip List is a probabilistic data structure built on top of multiple levels of linked lists. It allows for faster search, insertion, and deletion operations by skipping over some elements in each level, providing logarithmic time complexity for search operations.
What is the main advantage of using a Bloom Filter?
A Space efficiency
B Exact matches
C Fast search
D Balanced structure
Bloom Filters are space efficient probabilistic data structures used to test whether an element is a member of a set. They allow for fast membership testing with a trade off: they can have false positives but no false negatives.
Which operation is most commonly associated with a Trie data structure?
A Searching for a prefix
B Sorting elements
C Merging trees
D Traversing nodes
Tries are primarily used for searching prefixes in a set of strings. Each node represents a character, and traversing the trie allows for efficient prefix matching, making it ideal for applications like autocomplete and spell checking.
In which of the following cases would a Bloom Filter be used?
A Exact membership queries
B Set intersection
C Estimating set membership
D Sorting large datasets
Bloom Filters are used to estimate set membership efficiently with a risk of false positives. They are particularly useful in situations like network routing, web caching, and distributed databases, where space efficiency is critical.
What is the space complexity of a Bloom Filter?
A O(n)
B O(log n)
C O(1)
D O(m)
The space complexity of a Bloom Filter is O(m), where m is the size of the bit array used to store the data. The space used depends on the number of elements expected to be stored and the false positive rate.
Which of the following best describes the performance of a Trie?
A O(log n) for search
B O(n) for search
C O(1) for search
D O(n²) for search
In a Trie, searching for a string or prefix takes O(n) time, where n is the length of the string. Each character in the string corresponds to a traversal through a node in the Trie, making it efficient for prefix searches.
What is the primary drawback of a Bloom Filter?
A It cannot be resized
B It requires too much memory
C It allows false positives
D It cannot be used for set operations
The primary drawback of a Bloom Filter is the potential for false positives. It may incorrectly indicate that an element is part of the set, but it will never incorrectly state that an element is not part of the set.
In a Trie, what does each node represent?
A A full string
B A character in a string
C The entire dataset
D A prefix of a string
In a Trie, each node represents a character in a string. The path from the root to a leaf node corresponds to a complete string, and the structure allows for efficient searching and prefix matching.
What is the time complexity of inserting an element into a Trie?
A O(1)
B O(n)
C O(log n)
D O(n²)
The time complexity of inserting an element into a Trie is O(n), where n is the length of the string being inserted. Each character in the string requires a traversal through the Trie to add the corresponding node.
Which of the following algorithms is used to construct a Skip List?
A Linear Search
B Merge Sort
C Probabilistic methods
D Depth-First Search
A Skip List is constructed using probabilistic methods, where each node has multiple levels that are chosen randomly. This allows the Skip List to achieve O(log n) time complexity for search, insert, and delete operations on average.
What is the main difference between a Trie and a Binary Search Tree (BST)?
A Tries are unordered
B Tries store entire strings in each node
C Tries store characters as nodes
D BSTs support prefix matching
In a Trie, each node stores a single character, while a Binary Search Tree (BST) stores a full string or value in each node. Tries allow for efficient prefix searches, unlike BSTs that focus on whole data items.
What is the typical use case of a Bloom Filter in a web application?
A To store session data
B To verify if a user has visited a page
C To check if a URL exists in a set of URLs
D To rank search results
Bloom Filters are commonly used in web applications for tasks like checking if a URL is part of a large set of known URLs (e.g., for checking URL presence in a blacklist or a cache). They offer fast membership testing at the cost of occasional false positives.
Which of the following operations is most efficient in a Skip List compared to a regular linked list?
A Search
B Insert
C Delete
D All of the above
A Skip List is more efficient than a regular linked list for all major operations (search, insert, delete) due to its multi-level structure, which allows for skipping over nodes and achieving O(log n) time complexity on average.
In a Bloom Filter, what happens when you try to insert an element already present in the filter?
A The filter rejects the element
B The filter is reset
C The filter’s probability of false positives increases
D The element is added normally
Bloom Filters do not track the exact presence of elements, so inserting an element that is already present does not affect the filter. However, this can increase the probability of false positives.
What is the main advantage of using a Trie in an autocomplete system?
A Lower memory usage
B Faster insertion
C Efficient prefix search
D Reduced space complexity
A Trie is ideal for autocomplete systems because it allows efficient prefix searches. Each node in the Trie represents a character, enabling fast retrieval of all possible completions for a given prefix.