Created
January 9, 2018 07:31
-
-
Save jianminchen/83719f890e05343923851b64dd2ed490 to your computer and use it in GitHub Desktop.
Union find algorithm - Julia asked the peer to give a different question to ask - January 8, 2018 - 10:00 PM mock interview
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
In this problem, a tree is an undirected graph that is connected and has no cycles. | |
The given input is a graph that started as a tree with N nodes (with distinct values 1, 2, ..., N), | |
with one additional edge added. The added edge has two different vertices chosen from 1 to N, and | |
was not an edge that already existed. | |
The resulting graph is given as a 2D-array of edges. Each element of edges is a pair [u, v] with u < v, | |
that represents an undirected edge connecting nodes u and v. | |
Return an edge that can be removed so that the resulting graph is a tree of N nodes. If there are multiple | |
answers, return the answer that occurs last in the given 2D-array. The answer edge [u, v] should be in the | |
same format, with u < v. | |
Example 1: | |
Input: [[1,2], [1,3], [2,3]] | |
Output: [2,3] | |
Explanation: The given undirected graph will be like this: | |
1 | |
/ \ | |
2 - 3 | |
third edge -> | |
Example 2: distinct 5, 5 distinct edge, 4 distinct edge | |
Input: [[1,2], [2,3], [3,4], [1,4], [1,5]] | |
Output: [1,4] | |
Explanation: The given undirected graph will be like this: | |
Note: | |
The size of the input 2D-array will be between 3 and 1000. | |
Every integer represented in the 2D-array will be between 1 and N, where N is the size of the input array. | |
---- Discussion starts from here --- | |
Julia's idea and the discussion with the peer: | |
Determine if there is a cycle. How to determine if there is a cycle? | |
Tree, graph, using depth first search. | |
Union find algorithm - one group | |
The peer asked Julia what is the base case. | |
What is the base case? | |
1 | |
/ \ | |
2 - 3 | |
3 -> 2 -> 1 | |
base case: | |
4 | |
/ \ | |
1 3 | |
/\ | |
5 2 | |
Hint given by the peer: | |
Example 1: Hint given by peer: | |
[1,2] | |
set(1,2) | |
[1,3] | |
set(1,2,3) | |
[2,3] | |
Example 2: | |
set(1), set(2), set(3), set(4), set(5) | |
1. [1,2] | |
set(1, 2) | |
2. [2,3] | |
set(1, 2, 3) | |
3. [3,4] | |
set(1,2,3,4) | |
4. [1,4] | |
It is called union-find merge disjointed groups. | |
5 - 1 - 2 | |
| | | |
4 - 3 | |
[1, 4] in part of cycle | |
detect the cycle | |
5 -> 1 -> 2 -> 3 -> 4 -> 1, there is cycle | |
4 -> 1 -> 5 | |
*/ |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment