Data Structures

Question 1

What is a stack?

Answer 1

A stack is a set with a LIFO policy.

The element deleted from the set is the one most recently inserted.

Question 2

What is a queue

Answer 2

A queue is a set with a FIFO policy.

The element deleted from the set is the one that has been in the set for the longest time.

Question 3

What is a linked list

Answer 3

A linked list is a data structure in which the object are arranged in a linear order.
Unlike an array, in which the linear order is determined by the array indices, the order in a linked list is determined by a pointer in each object.

Question 4

Complexity: Copy list

Answer 4

Average case: O(n)

Amortized worst case: O(n)

Question 5

Complexity: Append to list

Answer 5

Average case: O(1)

Amortized worst case: O(1)

Question 6

Complexity: Pop last from list

Answer 6

Average case: O(1)

Amortized worst case: O(1)

Question 7

Complexity: Pop intermediate from list

Answer 7

Average case: O(n)

Amortized worst case: O(n)

Question 8

Complexity: Insert into list

Answer 8

Average case: O(n)

Amortized worst case: O(n)

Question 9

Complexity: Get item from list

Answer 9

Average case: O(1)

Amortized worst case: O(1)

Question 10

Complexity: Set item in list

Answer 10

Average case: O(1)

Amortized worst case: O(1)

Question 11

Complexity: Delete item from list

Answer 11

Average case: O(n)

Amortized worst case: O(n)

Question 12

Complexity: List iteration

Answer 12

Average case: O(n)

Amortized worst case: O(n)

Question 13

Complexity: Get slice from list

Answer 13

Average case: O(k)
Amortized worst case: O(k)

k = Size of slice

Question 14

Complexity: Delete slice from list

Answer 14

Average case: O(n)

Amortized worst case: O(n)

Question 15

Complexity: Set slice in list

Answer 15

Average case: O(k+n)
Amortized worst case: O(k+n)

k = size of slize

Question 16

Complexity: Extend list

Answer 16

Average case: O(k)
Amortized worst case: O(k)

k = size of 2nd list

Question 17

Complexity: Sort list

Answer 17

Average case: O(n log n)

Amortized worst case: O(n log n)

Question 18

Complexity: Multiply list

Answer 18

Average case: O(n * k)

Amortized worst case: O(n * k)

Question 19

Complexity: x in list

Answer 19

Average case: O(n)

Question 20

Complexity: min() / max() of list

Answer 20

Average case: O(n)

Question 21

Complexity: Get length of list

Answer 21

Average case: O(1)

Amortized worst case: O(1)

Question 22

Complexity: Copy dequeue

Answer 22

Average case: O(n)

Amortized worst case: O(n)

Question 23

Complexity: Append to dequeue

Answer 23

Average case: O(1)

Amortized worst case: O(1)

Question 24

Complexity: Append left to dequeue

Answer 24

Average case: O(1)

Amortized worst case: O(1)

Question 25

Complexity: Pop from dequeue

Answer 25

Average case: O(1)

Amortized worst case: O(1)

Question 26

Complexity: Pop left from dequeue

Answer 26

Average case: O(1)

Amortized worst case: O(1)

Question 27

Complexity: Extend dequeue

Answer 27

Average case: O(k)
Amortized worst case: O(k)

k = number of items to extend

Question 28

Complexity: Extend left dequeue

Answer 28

Average case: O(k)
Amortized worst case: O(k)

k = number of items to extend

Question 29

Complexity: Rotate dequeue

Answer 29

Average case: O(k)
Amortized worst case: O(k)

k = Number of steps to rotate

Question 30

Complexity: Remove from dequeue

Answer 30

Average case: O(n)

Amortized worst case: O(n)

Question 31

Complexity: x in dict

Answer 31

Average case: O(1)

Amortized worst case: O(n)

Question 32

Complexity: Copy dict

Answer 32

Average case: O(n)

Amortized worst case: O(n)

Question 33

Complexity: Get item from dict

Answer 33

Average case: O(1)

Amortized worst case: O(n)

Question 34

Complexity: Set item in dict

Answer 34

Average case: O(1)

Amortized worst case: O(n)

Question 35

Complexity: Delete item from dict

Answer 35

Average case: O(1)

Amortized worst case: O(n)

Question 36

Complexity: Iterate dict

Answer 36

Average case: O(n)

Amortized worst case: O(n)

Question 37

How can k-ary trees represented memory efficiently?

Answer 37

By using a left-child right-sibling (LCRS) binary tree.

Each node contains at maximum two references: On to the leftmost direct child and on to its own right sibling.
In order to get the i-th child of a node it is necessary to access the left child and then iterate through its siblings.

This representation is very memory efficient, however accessing nodes may be slower.

Question 38

How does the division method for hash functions work?

Answer 38

A key k is mapped into one of m slots by taking the remainder of k divided by m:

h(k) = k mod m

Question 39

How does the multiplication method for hash functions work?

Answer 39

First, we multiply the key k by a constant A in the range 0 < A < 1 and extract the fractional part of kA.
Then, we multiply this value by m and take the floor of the result.

h(k) = floor (m (kA mod 1))

Question 40

Why is universal hashing used in favour of other hashing methods like division hashing?

Answer 40

If a malicious adversary chooses the keys to be hashed by some fixed hash function, then the adversary can choose n keys that all hash to the same slot, yielding an average retrieval time of O(n).

With universal hashing the hash function is chosen randomly. At the beginning of execution the hash function is selected randomly from a carefully designed class of functions.

Question 41

What is a universal hashing collection?

Answer 41

Let H be a finite collection of hash functions that map a given universe U of keys into the range {0, 1 , …, m-1}.

Such a collection is said to be universal if for each pair of distinct keys k,l ∈ U, the number of hash functions h ∈ H for which h(k) = h(l) is at most |H| / m.

With a hash function randomly chosen from H, the chance of a collision between distinct keys k and l is no more than the chance 1/m of a collision if h(k) and h(l) were randomly and independently chosen from the set {0, 1, …, m-1}

Question 42

Explain the difference between open addressing and chaining in hashing

Answer 42

In open addressing, keys are inserted at the specified hash position. If the slot is already occupied, the next slot is probed until an empty slot is found.
In accessing it works the same way: The slots are probed until the key is found, an empty slot is found or all slots have been probed. Since each slot can hold only one element, the load factor is <= 1

In chaining, keys hashed to the same slot are chained via linked lists. Since each slot can hold many elements, the load factor can grow beyond 1

Question 43

What is linear probing, quadratic probing & double hashing in open adressing?

Answer 43

Linear probing:

• Probing works by testing slot by slot in sequence
• Easiest to implement but susceptible for clustering
• h(k,i) = (h’ (k) + i) mod m

Quadratic probing:

• Probing uses two positive auxiliary constants, one of them in quadratic form
• Less susceptible for clustering than linear probing but still possible
• h(k,i) = (h’ (k) + c1 * i + c2 * i² ) mod m

Double hashing:

• Probing works by using two auxiliary hash functions
• The permutations produced have many of the characteristics of randomly chosen permutations
• h(k,i) = (h1 (k) + i * h2 (k)) mod m

Question 44

What is perfect hashing?

Answer 44

We call a hashing technique perfect hashing if O(1) memory accesses are required to perform a search in the worst case.

Two levels of hashing are used, with universal hashing at each level.

The first level is essentially the same as for hashing with chaining: We hash the n keys into m slots using a hash function h carefully selected from a family of universal hash functions.

Instead of making a linked list of the keys hashing to slot j, however, we use a small secondary hash table S_j with an associated hash function h_j. By choosing the hash functions h_j carefully, we can guarantee that there are no collisions at the secondary level.

Question 45

What are the prerequisites to create a static perfect hash table?

Answer 45

All keys are static: once the keys are stored in the table, the set of keys never changes.

Question 46

What is the worst-case running time of basic operations on a binary tree with n elements?

Answer 46

O( n )

Question 47

What is the basic structure of a binary tree?

Answer 47

A binary tree is a tree structure, in which each element (node) contains either 0, 1 or 2 children. The children are called left and right child. Each node has a reference to its parent node, except for the root node. Node referencing 0 or 1 children are called leaf-nodes.

Question 48

What is the binary-search-tree property?

Answer 48

Let x be a node in a binary search tree. If y is a node in the left subtree of x, then y.key <= x.key. If y is a node in the right subtree of x, then y.key >= x.key.

In other words: All values in the left subtree of node x are less than or equal to x.key. All values in the right subtree of node x are greater than or equal to x.key

Question 49

Implement the inorder_tree_walk procedure.

What is its complexity?

Answer 49

def inorder_tree_walk(node:Node):
if node.left:
inorder_tree_walk(node.left)

print(node.key)

if node.right:
    inorder_tree_walk(node.right)

Time complexity: O (n) (each element is visited once)

Question 50

Time complexity of search procedure on a binary tree

Answer 50

O(h), where h is the height of the binary tree

Question 51

Time complexity of min/max procedure on a binary tree

Answer 51

O(h), where h is the height of the binary tree

Question 52

Time complexity of min/max procedure on a binary tree

Answer 52

O(h), where h is the height of the binary tree

Question 53

Time complexity of predecessor/successor procedure on a binary tree

Answer 53

O(h), where h is the height of the binary tree,

since we either follow a simple path up the tree or follow a simple path down the tree

Question 54

Time complexity of binary tree insert node

Answer 54

O(h), where h is the height of the binary tree,

Question 55

Time complexity of binary tree delete node

Answer 55

O(h), where h is the height of the binary tree,

Question 56

Describe the deletion of a node from a binary tree

Answer 56

Deletion can be done in 3 different node states:

• Deleted node is leaf node: Just delete the node
• Deleted node has a single child: Replace the deleted node with its child
• Deleted node has 2 children: The trickiest state. We have to re-structure the tree. We are basically replacing the deleted node with its successor.
  
  • Option 1: Successor of deleted node is its right child: We can replace the deleted node with its successor node and re-assign the left child of the deleted node to the left child of the successor node (successor node is the minimum of the right subtree, so it won’t have a left node)
  • Option 2: Successor of deleted node is not its direct right child: The hardest part. First we replace the successor’s with its own right child. Secondly we set the successor to be the parent of the deleted node’s right child. Then, we set the successor to be the deleted node’s parent child and the parent of the deleted node’s left child.

Question 57

What is a red-black tree

Answer 57

A red-black tree is a binary search tree with one extra bit of storage per node: its color, which can be either red or black. By constraining the node colors on any simple path from the root to a leaf, red-black trees ensure that no such path is more than twice as long as any other, so that the tree is approximately balanced.

Question 58

What are the properties of a red-black tree?

Answer 58

1. Every node is either red or black
2. The root is black
3. Every leaf (NIL) is black
4. If a node is red, then both its children are black
5. . For each node, all simple paths from the node to descendant leaves contain the same number of black nodes

Question 59

What is the advantage of red-black tress compared to normal binary search trees?

Answer 59

On binary search trees the basic operations like search, min, max, successor, predecessor, insert & delete run in O(h). This is fine on balanced trees, however if the tree is unbalanced, the runtime becomes worse ( O(n) on a completely unbalanced tree).
Red-black trees keep the tree more or less balanced, so that we can guarantee to run the operations in O (lg n) time.

Question 60

What is the runtime of all basic operations on a red-black tree?

Answer 60

O( lg n )

Question 61

What is the runtime of a left or right rotation in a binary search tree?

Answer 61

O(1)

It runs in constant time as only a constant number of pointers are updated

Question 62

What is the difference between a binary tree and a binary search tree?

Answer 62

A binary search tree holds an additional condition: All left descendants <= n < all right descendants.

Question 63

What is a balanced tree?

Answer 63

In a balanced tree all branches have roughly the same height.

Question 64

What is a complete binary tree?

Answer 64

A complete binary tree is a binary tree in which every level of the tree is fully filled, except for perhaps the last level. To the extent that the last level is filled, it is filled left to right

Question 65

What is a full binary tree?

Answer 65

A full binary tree is a binary tree in which every node has either 0 or 2 children.

Question 66

What is a perfect binary tree?

Answer 66

A perfect binary tree is a binary tree that is both full and complete. All leave nodes will be at the same level, and this level has the maximum number of nodes.