Data Structure

Question 1

Disjoint set - operations and what they do(3)

Answer 1

1) make set - create a new set with one element (O(1))
2) Union - combine two set
3) find set - find which set is in for the given element and return the representative of that set

Question 2

Disjoint set - when to use (2 for now)

Answer 2

1) finding cycle in a undirected graph

2) Kruskal’s algorithm (fund minimum spanning forest)

Question 3

Stack - find next greater element of the whole array

Answer 3

1) push first element into the stack
2) iterate through all remaining elements
- if the stack is empty, push the current element
- else, keep popping the element when s.top() is less than the current element and mark the current element as answer for popped els
- push the current element
3) mark all remaining elements in the stack as not found