Data Structures

Question 1

What is a dictionary?

Answer 1

An abstract data type made up of keys and values in pairs

Question 2

What are the 4 main operations of a dictionary?

Answer 2

CRUD: Create, Read, Update, Delete
1. Add a key-value pair
2. Delete a key-value pair
3. Update the value of a pair
4. Find the value of an associated key

Question 3

Explain why an array is a random-access data structure

Answer 3

Random-access means that you can access an arbitrary element as fast as any other element regardless of where it is in the array.

Question 4

How is the data of an array stored in RAM?

Answer 4

It’s stored in a contiguous block of memory where every element of the array has a fixed size known up front

Question 5

Given the offset of the array, element size and element index, how do you calculate the address of the element?

Answer 5

element_address = offset + (element_size * element_index)

Question 6

Explain how Python implements pointers to store values in arrays

Answer 6

Python uses pointers (integer numbers) in place of actual values in the array which reference the location of where the data is stored. That way, while the pointers are stored continguously for easy access, the actual values (with varying sizes) can be stored anywhere.

Pic

Question 7

What does a hash function do?

Answer 7

Turns any data into a fixed-size sequence of bytes, called a hash value or hash code

Question 8

T/F: a hash function with always return the same hash value for the same input, even if you exit and reopen Python

Answer 8

False, hash values are only immutable within the same Python session

Question 9

What is a hash collision, and why is it unavoidable?

Answer 9

It’s when a hash function will yield the same hash value for two different values. It’s unavoidable because the goal of a hash function is to project a potentially infinite number of values onto a finite space (e.g. the pigeonhole principle: Given m items and n containers, if m > n, then there’s at least one container with more than one item.)

Question 10

T/F: Good hash functions will distribute values evenly across available space

Answer 10

True

Question 11

T/F: Hash functions distribute values pseudo-randomly

Answer 11

True

Question 12

T/F: Hash functions are slow

Answer 12

False. They are lightning fast, hence why dictionaries are equally fast

Question 13

T/F: You can reverse-engineer a hash function’s value back to the original value

Answer 13

False, it’s virtually impossible

Question 14

T/F: Hash values from the same hash function can be different length numbers

Answer 14

False, they will always have a fixed-size

Question 15

What makes a hash table’s key-value pairs unordered?

Answer 15

The hash function, because by nature it will try to evenly distribute the key-value pair across the allocated memory space

Question 16

Briefly explain how to implement the 4 main operations of a hash table, given n fixed number of memory locations

Answer 16

1. Set up a simple method of assigning an index value from the key’s hash value, i.e. idx = hash(key) % n
2. Create: Use the index function on the key, then assign the key-value pair to the list of memory locations
3. Read: Use the index function on the key, return the value from the key-value pair
4. Update: Use the index function on the key, update the value from the key-value pair
5. Delete: Use the index function on the key, remove the key-value pair from the list

Question 17

Why do hash tables have an O(1) T.C for lookup, insert, update, and delete functions?

Answer 17

Because in order to find/update/add/delete any key-value pair from a hash table, you only need to calculate the index location from the key, e.g. idx = hash(key) % memory_size as a simple example.

Question 18

Explain how linear probing is used to solve hash collisions

Answer 18

1. Calculate the index of the key of a key-value pair

Question 19

T/F: For hash tables, you calculate the hash of the value in a key-value pair

Answer 19

False, you have to use the keys of the key-value pairs because they are guaranteed to be unique