Data Structures

Question 1

array

Answer 1

a collection of data elements, linear order is given by their physical placement in memory

Question 2

array: index (get)

Answer 2

O(1)

Question 3

array: insert/remove at the end

Answer 3

amortized O(1) (for dynamically resizing array)

Question 4

array: insert/remove at any position

Answer 4

O(n)

Question 5

array: insert/remove at the beginning

Answer 5

O(n)

Question 6

linked list

Answer 6

a collection of data elements not stored in adjacent physical memory. a group of nodes representing a sequence. each node is composed of data element itself and a pointer to the next node in the sequence.

Question 7

linked list: insert/remove at any position

Answer 7

O(1)

Question 8

linked list: index (get)

Answer 8

O(n)

Question 9

binary tree

Answer 9

a tree with each node having at most two children

Question 10

use cases of binary tree

Answer 10

• a way to access nodes based on value or label associated with each node. e.g. BST, binary heap (searching and sorting)
• as a representation of data with a relevant bifurcating structure where the particular arrangement of nodes under and/or to the left or right of other nodes is part of the information (that is, changing it would change the meaning).

Question 11

balanced tree

Answer 11

|height(left) - height(right)| <= 1 for any node

height = O(log n)

Question 12

binary tree: insert a leaf

Answer 12

O(1)

Question 13

binary tree: remove a zero/single child node

Answer 13

O(1)

Question 14

traversal of binary trees

Answer 14

pre-order, in-order, post-order
breath-first order
depth-first order

Question 15

implementation of binary trees

Answer 15

nodes and pointers

Question 16

binary search tree

Answer 16

sorted binary tree, node.val is greater or equal than all the nodes in the left subtree, node.val is less or equal than all the nodes in the right subtree

Question 17

binary search tree: height

Answer 17

balanced bst: O(log n); any bst: O(n)

Question 18

binary search tree: search

Answer 18

average O(log n), worst case O(n)

Question 19

binary search tree: insert

Answer 19

average O(log n), worst case O(n)

Question 20

binary search tree: remove

Answer 20

average O(log n), worst case O(n)

Question 21

self-balancing binary search tree

Answer 21

AVL and black-red tree

Question 22

AVL

Answer 22

Re-balance the tree by performing appropriate rotations on the subtree

Question 23

black-red tree

Answer 23

1) Every node has a color either red or black.
2) Root of tree is always black.
3) There are no two adjacent red nodes (A red node cannot have a red parent or red child).
4) Every path from a node (including root) to any of its descendant NULL node has the same number of black nodes.
In Red-Black tree, we use two tools to do balancing.
1) Recoloring
2) Rotation

Question 24

use case of binary search tree

Answer 24

lookup table, priority queue, dynamic sets

Question 25

hash table

Answer 25

map between key and value, a hash function hash(key) = index, pointing to a buckets/slots contains the corresponding value(s)

Question 26

collision of hash table

Answer 26

multiple key to the same index

Question 27

hash table: get

Answer 27

O(1)

Question 28

hash table: insert

Answer 28

amortized O(1)

Question 29

hash table: remove

Answer 29

amortized O(1)

Question 30

use case of hash table

Answer 30

associative arrays, database indexing, caches, and sets

Question 31

hash table: choice of hash function

Answer 31

uniform distribution

Question 32

hash table: collision resolution

Answer 32

- separate chaining: a linked list in each bucket - open addressing: all entry records are stored in the bucket array itself. When a new entry has to be inserted, proceed in some probe sequence, until an unoccupied slot is found. search is the same procedure

Question 33

hash table: dynamic resizing

Answer 33

copy all the entries to the new array when the size get bigger than a threshold, incremental resizing

Question 34

queue

Answer 34

FIFO, addition of entities to the rear terminal position, known as enqueue, and removal of entities from the front terminal position

Question 35

implementations of queue

Answer 35

``` circular buffer (big array with head and tail floating around) linked list with tail pointer deque ```

Question 36

queue: insert and delete (enqueue and dequeue)

Answer 36

O(1)

Question 37

stack

Answer 37

last-in-first-out

Question 38

stack: push

Answer 38

from top, O(1)

Question 39

stack: pop

Answer 39

from top, O(1)

Question 40

stack: peek

Answer 40

O(1)

Question 41

implementations of stack

Answer 41

array | linked list

Question 42

use cases of stack

Answer 42

expression evaluation and syntax parsing backtracking, depth-first-search memory

Question 43

what is stack overflow?

Answer 43

Parameters and local variables are allocated on the stack (with reference types, the object lives on the heap and a variable in the stack references that object on the heap). The stack typically lives at the upper end of your address space and as it is used up it heads towards the bottom of the address space (i.e. towards zero). Your process also has a heap, which lives at the bottom end of your process. As you allocate memory, this heap can grow towards the upper end of your address space. As you can see, there is a potential for the heap to "collide" with the stack.

Question 44

priority queue

Answer 44

Each element has a "priority" associated with it. In a priority queue, an element with high priority is served before an element with low priority. If two elements have the same priority, they are served according to their order in the queue.

Question 45

implementations of priority queue

Answer 45

heap: O(n) to build, O(log n) to insert and remove self-balanced BST: O(n log n) to build initially, O(log n) to insert and remove unordered array: O(n^2) ordered array: O(n^2)

Question 46

equivalence between priority queue and sorting

Answer 46

``` The semantics of priority queues naturally suggest a sorting method: insert all the elements to be sorted into a priority queue, and sequentially remove them; they will come out in sorted order. heap -------------------- heap sort self-balanced bst --- tree sort unordered array ---- selection sort ordered array -------- insertion sort ```

Question 47

priority queue: build

Answer 47

heap implementation O(n), self-balance bst implementation O(n log n)

Question 48

priority queue: push

Answer 48

O(n log n)

Question 49

priority queue: pop

Answer 49

O(n log n)

Question 50

use cases of priority queue

Answer 50

bandwidth management dijkstra’s algorithm hoffman coding best-first search

Question 51

heap

Answer 51

A specialized tree-based data structure which is essentially an almost complete tree that satisfies the heap property: max-heap: each parent is larger or equal than its children min-heap: each parent is smaller or equal than its children Visualized as a tree, but is usually linear in storage (array, linked list).

Question 52

heap: build

Answer 52

O(n)

Question 53

heap: insert top

Answer 53

O(n log n)

Question 54

heap: remove top

Answer 54

O(n log n)

Question 55

heapify

Answer 55

create a heap from an unsorted list of elements

Question 56

heap sort

Answer 56

sort a unsorted list of elements in place using max heap | min heap can not do in place

Question 57

use cases of heap

Answer 57

``` priority queue k-way merge selection algorithm graph algorithms (dijkstra) order statistics (get median/k-largest) ```