Graph

Question 1

Fenwick tree - usage, complexity (create, update, search)

Answer 1

Usage: fast prefix sum

Space complexity: O(n)
Time complexity: create->O(nlogn), update all elements->O(logn), search->O(logn)

Question 2

Binary tree - traversal methods (three) and how

Time complexity?

Answer 2

1) pre order (visit - left - right) (usual one)
2) in order (L-V-R)
3) post order (L-R-V)

Time complexity: O(n)

Question 3

Binary tree - searching time (balanced/unbalanced)

Answer 3

Balance: O(logn)
Unbalanced: O(n)

Question 4

Binary tree - insertion time complexity (balanced/unbalanced)

Answer 4

Balance: O(logn)
Unbalanced: O(n)

Question 5

Topological sort - time complexity

Answer 5

Time: O(v+e)

Where v is the number of vertices and e is the number of edges

Question 6

Topological sort - how does it work?

Answer 6

Prepare: set, stack

1) choose a random node
2) Mark the node as visited and put it into the set
3) explore its children and continue with step 2
4) if the node has no children, put it into the stack and go back
5) the stack order from top to the bottom is the final state of topological sort

Question 7

Dijkstra’s algorithm - restriction

Answer 7

It can only work when there is no negative distance on edges.

Question 8

Dijkstra’s algorithm - usage

Answer 8

Given a source node

Find all shortest path from that node to every other node

Question 9

Dijkstra’s algorithm - space and time complexity

Answer 9

Time: O(elogv)
Space: O(e+v)
Where e is the number of edges and v is the number of vertices

Question 10

DFS (cycle detection (directed graph)) - time complexity

Answer 10

Time: O(e+v)

Where e is the number of edges and v is the number of vertices

Question 11

DFS (cycle detection (directed graph)) - how it works

Answer 11

Prepare: white set(not visit), grey set(visiting), black set(visited)

1) randomly pick a node from white set
2) do dfs while putting passed node into great set
3) if dfs find a node who is going to visit and also in the grey set, it is found
4) if not put the node in the black set so we are not going to visit again

Question 12

Edges list (graph representation) - space complexity

Answer 12

Space: O(v+e)

Where v is the number of vertices and e is the number of edges

Question 13

Edges list (graph representation) - how does it work?

Answer 13

1) create a class with starting and ending vertices and optionally adding value
2) store in a list..

struct edge {
   Int start;
   Int end;
   Int value;
};

Vector list(n);

Question 14

Edges list (graph representation) - time complexity of finding all adjacent node of given node

Answer 14

Time: O(n)

Where n is the size of edges list

Question 15

Edges list (graph representation) - what is it?

Answer 15

I can’t believe you forgot about this important thing!

Go Google for photo.

Question 16

Adjacency graph (graph representation) - space complexity

Answer 16

Space: O(v^2)

Where v is the number of vertices in the graph

Question 17

Adjacency graph (graph representation) - time complexity on finding adjacent node and check two node connectivity

Answer 17

1) O(v)

2) O(1)

Question 18

Graph representation - ways(3)

Answer 18

1) adjacency list - good
2) adjacency matrix - ok but consume space
3) vertices list- ok but time consuming on searching

Question 19

Disjoint set (cycle detection (undirected graph)) - how it works?

Answer 19

1) create a set for every element
2) start union two set by edges
3) if their representative is not the same, combine them
Else, that edge make a cycle on the graph

Question 20

Tree - root/node/leaf node/non-leaf node/ancestor/descendant/sibling/degree

Answer 20

Root - top of the tree/has no parent
Node - all other node except root
Leaf node - they don’t have child node
Non-leaf node - they have child node
Ancestor - all node from root to the given node (exclude given node)
Descendant - all node from given node to leaf node (exclude given node)
Sibling - two node having the same parent is called sibling
Degree - number of leaf node to the given node

Question 21

AVL tree (self balancing binary tree) - rotations (4)

Answer 21

• RR -> rotate left
• LL -> rotate right
• LR -> rotate left and then right
• RL -> rotate right and then left

Question 22

Binary tree - full / proper / strict binary tree

Answer 22

• each node has 0 or 2 children

Question 23

Binary tree - complete binary tree

Answer 23

• all level of node are completely filled (except last level)
• node from the last level are filled from left to right

Question 24

Binary tree - perfect binary tree

Answer 24

• all leaf node are on the same level

- all internal node has two children

Question 25

Binary tree - degenerated binary tree

Answer 25

- all node has only 1 child

Question 26

AVL tree (self balancing binary tree) - priorities

Answer 26

- the balancing factor of each node must be {-1,0,1} | - balancing factor = height of left subtree - height of right subtree

Question 27

Red black tree (self balancing binary tree) - priorities

Answer 27

- root node has to be black - there cannot be two consecutive red node - the number of black node of every path from the node to (the node after leaf node = null) should be the same

Question 28

Red black tree (self balancing binary tree) - insertion

Answer 28

if (tree == empty) { create a root node with color black; } else { follow the instructions of binary insertion to create a node with red colour; if (the parent of the created node == black) { return; } else { if (the sibling node of the parent of the created node == red) { the sibling node of the parent of the created node = black; the parent of the created node = black; if (the parent is above two node != root node) { the parent is above two node = red; recheck(); } } else { rotation(); recolour(); } } }

Question 29

Binary tree - deletion (with no child node / one child node / two children node)

Answer 29

No - just delete it One - replace the node with its child and delete the child node (recursively call until reach leaf node) Two - choose inorder predecessor / inorder successor and replace it Predecessor = the largest node from the left tree Successor = the smaller node from the right tree

Question 30

Spanning tree - what is spanning tree

Answer 30

- connected tree - no cycle - have same vertices as the original graph - have v-1 edges

Question 31

Prim’s algorithm (find minimum spanning tree) - how it works

Answer 31

1) remove loop and parallel 2) choose a random node to start with 3) choose the minimum edges connected to visited node 4) choose (|v|-1) edges and done

Question 32

Kruskals algorithm (find minimum spanning tree) - how it works

Answer 32

1) remove loop and parallel 2) create a list of edges with given weight in increasing order 3) choose edges and form a graph without any cycle 4) choose (|v|-1) edges

Question 33

Connected component - how to find

Answer 33

The number of call (dfs / bfs) to the graph = ans

Question 34

Bellman Ford algorithm (single source shortest path) - time complexity

Answer 34

Time: O(ev) | Where e is the number of edges and v is the number of vertices

Question 35

Bellman Ford algorithm (single source shortest path) - drawback

Answer 35

It cannot work on negative weighted cycle

Question 36

Bellman Ford algorithm (single source shortest path) - how it works

Answer 36

1) list all the edges 2) relax all the edges for (|v|-1) times Relax: d[u] = min(d[u], d[v]+c(u, v))

Question 37

Floyd Warshell algorithm (all pair shortest path) - time and space complexity

Answer 37

Time - O(v^3) Space - O(v^3) Where v is the number of vertices

Question 38

Floyd Warshell algorithm (all pair shortest path) - formula

Answer 38

Dk[i, j] = min(D(k-1)[i, k]+D(k-1)[k, j], D(k-1)[i, j])

Question 39

Segment tree - usage

Answer 39

Perform range quiet and range update in O(logn) time

Question 40

Segment tree - how to implement

Answer 40

1) create an array with 2n size 2) all leaf node are the original data 3) internal node will be the sum(or can be other with different situation) of theirs children

Question 41

Segment tree - update time (point/range)

Answer 41

O(logn)

Question 42

Last propagation (segment tree) - how

Answer 42

1) keep a tree with same size of the segment tree with 0 2) every time when the update range is not the leaf node - lazy tree will keep an pending update of the children 3) when every time reaches the node, the same node in lazy tree need to be checked 4) if 0 = no update, else update it with the (number x range) and pass the update to its children

Question 43

Strongly connected component - ?

Answer 43

Only exists in directed graph | When two arbitrary node is selected, they will have a path

Question 44

Tree - properties

Answer 44

Having only one connected component | Edges +1 = vertices