Data Structures and Algorithms

Question 1

What is “asymptotic amortized worst case analysis”

Answer 1

TBD

Question 2

Insert time of Unsorted List

Answer 2

O(n)

Question 3

Delete time of Unsorted List

Answer 3

O(n)

Question 4

Get value at Index of Unsorted List

Answer 4

O(1)

Question 5

Search Value for Unsorted List

Answer 5

O(n)

Question 6

Find Max/Min in Unsorted List

Answer 6

O(n)

Question 7

Space usage of Unsorted List

Answer 7

O(n)

Question 8

Insert time of Sorted List

Answer 8

O(n)

Question 9

Delete time of Sorted List

Answer 9

O(n)

Question 10

Get value at Index Sorted List

Answer 10

O(1)

Question 11

Search Value for Sorted List

Answer 11

O(log n)

Question 12

Find Max/Min in Sorted List

Answer 12

O(1)

Question 13

Space usage of Sorted List

Answer 13

O(n)

Question 14

Insert into Unsorted Linked List

Answer 14

O(1) if the pointer to the next location is available. O(n) otherwise

Question 15

Delete from Unsorted Linked List

Answer 15

O(1) if the pointer to the next location is available. O(n) otherwise

Question 16

Get value at index in Unsorted Linked List

Answer 16

O(n)

Question 17

Search for value in Unsorted Linked List

Answer 17

O(n)

Question 18

Find Max/Min in Unsorted Linked List

Answer 18

O(n)

Question 19

Space usage of Unsorted Linked List

Answer 19

O(n)

Question 20

Insert into Sorted Linked List

Answer 20

O(1) if the pointer to the next location is available. O(n) otherwise

Question 21

Delete from Sorted Linked List

Answer 21

O(1) if the pointer to the next location is available. O(n) otherwise

Question 22

Get value at index for Sorted Linked List

Answer 22

O(n)

Question 23

Search for value in Sorted Linked List

Answer 23

O(n)

Question 24

Find Max/Min in sorted Linked List

Answer 24

O(n)

Question 25

Space usage for sorted Linked List

Answer 25

O(n)

Question 26

Insert in Self-balancing Binary Search Tree

Answer 26

O(log n)

Question 27

Delete in Self-Balancing Binary Search Tree

Answer 27

O(log n)

Question 28

Get value at index in Self-Balancing Binary Search Tree

Answer 28

N/A – No direct index

Question 29

Search for a key in Self-Balancing Binary Search Tree

Answer 29

O(log n)

Question 30

Find Min/Max in Self-Balancing Binary Search Tree

Answer 30

O(log n)

Question 31

Space usage in Self-Balancing Binary Search Tree

Answer 31

O(n)

Question 32

Insert into Heap

Answer 32

O(log n)

Question 33

Delete from Heap

Answer 33

O(log n) is value is min or max, O(n) for arbit element

Question 34

Get value at index in Heap

Answer 34

N/A – No direct index

Question 35

Search value in Heap

Answer 35

O(n)

Question 36

Find Min/Max in Heap

Answer 36

O(1)

Question 37

Space usage in Heap

Answer 37

O(n)

Question 38

Insert in HashTable

Answer 38

O(1)

Question 39

Delete from HashTable

Answer 39

O(1)

Question 40

Get value at index in HashTable

Answer 40

N/A

Question 41

Search for value in HashTable

Answer 41

O(1)

Question 42

Find Max/Min in HashTable

Answer 42

O(n)

Question 43

Space Usage in HashTable

Answer 43

O(n)

Question 44

What is the difference between Abstract Data Types and Data Structures

Answer 44

ADT is the mathematical model, or concept– describes the working– E.g stacks, queues,
A data structure is the implementation.
E.g. A stack can be implemented using an array or a linked list