Data Strucs

Question 1

Explain the different ways that graphs can be represented. What are the pros and cons of various ways of representing graphs.

Answer 1

Graphs can be represented in adjacency list/matrix.
List: Space-efficient. O(n) access. Good for sparse
Matrix: Access time O(1). O(n^2) space. Good for dense

Question 2

What are the steps for DFS on a graph?

Answer 2

1) Create a Stack
2) Start on a Node. Mark it as ‘Visited’ . Add it onto the Stack.
3) Check Top of Stack. Visit unvisited adjacent nodes
4) If there are no unvisited adjacent nodes, pop the stack
5) Repeat until Stack empty.

Question 3

Explain the Steps in a Topo sort

Answer 3

Kahn’s algo

1) Count the in-edges for every node
2) enqueue all the node’s with 0 in-edge
3) while queue is not empty. dequeue a node, decrease in-edges for all adjacent nodes. If the adjacent node’s in-edge count is 0, then enqueue it.

DFS approach

1) Create a stack
2) Mark node as ‘visited’
3) Visit their children/ If no children push into stack
4) Repeat