Data Structures Flashcards
What is direct addressing?
It is an alternative way to solve collision by having distinct array positions for every possible key. Direct addressing is possible only when we can afford to allocate an array that has one position for every possible key.
When I create a linked list, what should I store?
Typically, a pointer to its head is stored. Sometimes also a pointer to the tail.
Deque: definition, possible implementations, insert policy, remove policy, contiguity in memory, time complexity
- Definition: a queue with two ends
- Possible implementations: dynamic array, linked list
- Insert policy: both ends
- Remove policy: both ends
- Contiguity in memory: yes
- Time complexity: implementation dependent
What is the search complexity in direct addressing?
O(1), since every key has a unique array position, searching takes a constant time.
What is collision in a hash table?
Multiple keys might have the same hash code, or two different hash codes can map to the same index. This is because we operate two mappings from higher to lower dimensional spaces.
What is a common way of mapping the hash code into an index?
Using the modulo function
idx = hash_code % array_length
How can I add an element in a min-heap?
To insert an element in a min-heap, we start from the bottom and compare the new node added with its parent. If it is smaller, we swap parent and child, and continue until we find the right spot for the node we want to add.
What is chaining?
Chaining is a technique to solve the collision problem in a hash table which is based on the use of a linked list and an array. Each element of the array is a linked list, which allows multiple elements to be mapped into the same index.
What is a leaf in a tree?
A node without children is called leaf.
What is primary clustering? How can I solve it?
Primary Clustering is the tendency for a collision resolution scheme such as linear probing to create long runs of filled slots near the hash position of keys.
I can solve it with quadratic probing.
What is a binary tree?
A tree is a binary tree if all its nodes have up to two children.
What is rehashing? When is it necessary?
When the load factor increases to more than a desired value (usually 0.75) we can perform a rehashing: the array is increased in size (double), the elements are rehashed and the load factor is therefore decreased.
What is the search complexity in direct addressing?
O(1), Since every key has a unique array position, searching takes a constant time.
Draw a complete, a full and a perfect binary tree
DRAW…
What is the difference between ordered and unordered set/map?
The elements in the std::map/std::set are ordered by the key, and the std::unordered_map/std::unordered_set are not ordered based on their key, but are placed into “buckets” based on a hash value computed for their key.
What is a perfect binary tree?
A complete and full binary tree.
How can I solve collisions in a hash table?
- Chaining
- Open addressing
What’s the runtime complexity of removing in a linked list?
O(1) for the head, O(N) for the middle, O(N) for the last element (even if we have the tail pointer, because we have to go through the entire list to find the new last element)
What is a singly-linked list?
A singly-linked list is a data structure composed of pairs {key, next}
- Key: is the value stored by the element (e.g., an int, a float, or whatever)
- Next: is a pointer to the next element in the list.
Is there a difference between hash code and index?
It is important to highlight that the hash code is NOT the index in the array. Indeed, we can potentially have much more hash codes than indices in the array.
What is a min-heap?
In a min-heap, each node is smaller than its children. It follows that the root is the smallest element of the tree.
How does a ring buffer work?
When an element is written, the pointer to the next element to write is increased. If the maximum capacity of the buffer is reached, then the pointer goes to the beginning of the data structure and keeps writing from there.
When an element is read, the pointer to the next element to read it increased. If the end of the buffer is reached, the pointer is moved to the begin of the buffer. Clearly, the read pointer cannot be ahead of the write pointer.
What is a complete binary tree?
A binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible. In other words, it is totally filled, other than the rightmost elements of the last level.
In simple chaining, what data structure is appropriate?
Linked-lists. Doubly linked lists are better because deletion becomes easier.
Binary heap: runtime complexity for search, insert, remove
- Search: to look for a generic element is O(N), to look for the smallest is O(1)
- Insert: average O(1), since the elements are added at the bottom and “bubbled-up”
- Remove: O(log N)
What is a doubly-linked list?
A doubly-linked list extends a singly-linked list by adding another pointer to the previous element. Therefore, each element in the list is a triplet {key, previous, next}.
Map: definition, what’s composed of, insert policy, remove policy, contiguity in memory, time complexity
- Definition: Sets are a type of associative containers storing pairs {key,value}. Each element is identified by its key. Keys are unique (i.e., cannot add the same key twice).
- Possible implementations: binary search tree
- Ordering: if ordered, then elements are sorted by value. If unordered, elements are organized in buckets based on their hash value.
- Contiguity in memory: contiguous if unordered, otherwise do not know
- Time complexity: logarithmic
How can I traverse a binary tree?
- In-order: we visit the left branch, then current node, then right branch;
- Pre-order: we visit the current node first, then left, then right;
- Post-order: we visit the left branch, then right, then current node.
What’s the most common way to implement a hash table?
A common way is the use of an array of linked lists and a hash function. Given a key, we can compute its hash code, which corresponds to an index of the array. nce we know to which element of the array the key is mapped, we have access to the linked list stored in such an element and we can do the operation that we want (for example, store the pair {key,value}).
What is the difference between a binary heap (e.g., a min-heap) and a binary search tree?
A binary heap only guarantees order among a parent and its children. For example, it guarantees that each node is smaller (min-heap) than its childeren. However no overall order is guaranteed.
In a binary search tree, all the elements in the left subtree of a node are smaller than any element in the right subtree. Therefore, a binary search tree has stronger order property than a binary heap.
