Data structures

Question 1

List/array complexity

Answer 1

Build: n
Insert, delets, find: n
Case: worst
Strengths: Fast look ups, fast appends
Weakness: Fixed inserts and deletes

Question 2

Sorted array

Answer 2

Build: nlogn
Insert delete, find: log n
case: worst

Question 3

Stack, queue, deque

Answer 3

Build: n
IDF: 1
case: worst
Strength: Fast operations
Uses: BFS (Queue) DFS(Stack)

Question 4

Dynamic array

Answer 4

BUild: n
ID: 1
find: log n
case: average
Strengths: Fast lookups, variable size
Weaknesses: Slow worst-case appends. Costly insert and deletes

Question 5

Heap/Priority queue

Answer 5

Build: n logn
idf: log n
case: worst
Strength: Heap used to implement a priority queue

Question 6

Hash table

Answer 6

build: n
idf: 1 but in fact m
case: expected
Strengths: Fast Lookups, flexible keys
Weaknesses: Unordered

Question 7

Skip list

Answer 7

Build: nlogn
idf: logn
case expected

Question 8

BST

Answer 8

idf: n
case: worst
Strength: Sorted
Weakness: Poor performance if unbalanced.

Question 9

AVL, Red-Black,B-tree

Answer 9

Build: nlogn
idf: log n
case: worst

Question 10

Adj list

Answer 10

Build: n_m
id: deg(v)
find vertex: n
find edge(v,w): deg(v)
case: worst

Question 11

Graph adjacency matrix

Answer 11

: Find vertex: log n
Find edge: n
Case: worst

Question 12

k-d tree

Answer 12

Build: nlogn
idfL logn
case: worst
Range queries in k-dimensional space

Question 13

Union-find/disjoin-set

Answer 13

Build: n log n
case: worst
Useful for tracking items that can be partitioned into disjoint sets

Question 14

Trie

Answer 14

Build: n
idf: m

Question 15

2d array

Answer 15

Build: nm
case: worst

Question 16

adaptable/Location-aware heap

Answer 16

Build: nlog n

Question 17

Why would you use any tree?

Answer 17

Store information that is hierarchical in nature: Library file system
Tree traversall making searching specific data reasonable.