Week 5 - Data Structures

Question 1

What’s one of the biggest advantages of hash tables?

Answer 1

They combine the best of two worlds - arrays and linked lists

Question 2

What’s the biggest disadvantage of hash tables?

Answer 2

Huge memory consumption

Question 3

What’s the O of hash tables?

Answer 3

O(n)

Question 4

What’s a hash function?

Answer 4

It’s a function that sorts elements within a hash table

Question 5

What are tries?

Answer 5

Tries are data structures with trees, whose nodes are arrays

Question 6

What’s the O of tries?

Answer 6

O(1) - constant search time

Question 7

What’s the biggest disadvantage of tries?

Answer 7

Huge memory consumption

Question 8

What do structures do?

Answer 8

Structures provide a way to unify several vars. of different types into a single new var. type

Question 9

What structures are used for?

Answer 9

Structures are used to group elements of different data types that have a logical connection

Question 10

What’s the difference between “typedef struct” and “struct”?

Answer 10

“typedef” allows us to create an alias for the struct. This alias is then used later to define variables of that type without having to write the “struct” keyword

Question 11

Where are structures defined?

Answer 11

Structs are defined in separate .h files or atop of our programs, outside of any function

Question 12

How can elements (aka members) of structs be access?

Answer 12

Using the dot operator (.)

Question 13

How can we dynamically allocate structs?

Answer 13

Using the malloc function

Question 14

What’s an example of dynamically allocated struct using the arrow operator?

Answer 14

(*mycar).year = 2011; can be replaced by mycar → year = 2011;

Question 15

In how many directions can we move in a singly-linked list?

Answer 15

One direction only

Question 16

What’s the problem with singly-linked lists moving in one direction only?

Answer 16

We cannot delete a node

Question 17

In how many directions can we move on doubly-linked lists?

Answer 17

Two directions: foward and backward

Question 18

What’s the downside of doubly-linked lists moving in both directions (foward and backward)?

Answer 18

We need to add an extra pointer to the structure definition, so more memory will be consumed

Question 19

What are singly and doubly linked lists good for?

Answer 19

Insertion and deletion of elements

Question 20

What’s the time singly and doubly linked lists take to insert and delete elements respectively?

Answer 20

Constant time

Question 21

What’s the downside of singly and doubly linked lists?

Answer 21

We lose the ability to randomly access lists elements, so accessing elements will take linear time

Question 22

Why are tries considered the holy grail of data scructs?

Answer 22

That’s because they provide a way to insert, delete and lookup in constant time

Question 23

What do tries combine together to store data?

Answer 23

Structs and pointers

Question 24

What’s one of the biggest advantages of tries?

Answer 24

They have no collision risk (two pieces of data will never have the same path)

Question 25

What’s the downside of tries?

Answer 25

Memory consumption

Question 26

What’s the reason to use stacks?

Answer 26

Make sure that the last element to be added is the first one to be removed

Question 27

What do we need to consider before selecting a data struct?

Answer 27

How fast we want to:
* Insert data
* Delete data
* Look up data