Random data structures

Question 1

Skip lists (idea)

Answer 1

Have a number of linked lists, reducing search operation times. The top most level will have just two nodes and will gradually be more until you reach the lowest level with all the nodes. Each node will be put in a higher level with a 0.5 probability.

Question 2

Skip lists put method

Answer 2

Add the key to the correct spot in the lowest level. Then each Time put it also in the upper level with a 0.5 probability. Do this until you randomly pick to not put it in then higher level or you add a new level.

Question 3

Skip lists (size and time)

Answer 3

On average each key will be in two lists, meaning that the size is 2n = O(n). Height O(logn). Time for all operations O(logn)

Question 4

Bloom filter (idea)

Answer 4

Initialize an array to be all zeroes. Each time you insert a new key, pass it through k different hash functions each give you an index. increment the value of the array at them indices by one. know for sure if a key is not in the filter but not the opposite.

Question 5

Bloom filter (mistake rate)

Answer 5

𝜀=(1−(1−1/𝑚)^𝑘𝑛 )^𝑘≈(1−𝑒^((−𝑘𝑛)/𝑚) )^𝑘 .
m - size of array
k - number of hash functions
n - number of inserted elements

Question 6

Bloom filter (best results n,k,m)

Answer 6

For best results: larger array (higher m), lower inserted elements (lower n). Number of hash functions has mixed effect.