---
# System prepended metadata

title: 2024 / 08/ 20 mock interview

---

// 2024/08/20
// interviewer: Nathan
// interviewee: Ted

261. Graph Valid Tree
2077. Paths in Maze That Lead to Same Room


### Q1 ----------------------------------
start time: 15:01

Input: n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]

0 -> 1, 2, 3
1 -> 4
1 -> 2

TC: O(n)
SC: O(1)

```cpp!
class UnionFind {
public:
    UnionFind(int size): root(size), rank(size) {
        for (int i = 0; i < size; i++) {
            root[i] = i;
            rank[i] = 1;
        }
    }
    
    int find(int x) {
        if (x == root[x]) {
            return x;
        }
        return root[x] = find(root[x]);
    }
    
    void UnionSet(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            if (rank[rootX] > rank[rootY]) {
                root[rootY] = root[rootX];
            } else if (rank[rootX] < rank[rootY]) {
                root[rootX] = root[rootY];
            } else {
                root[rootY] = root[rootX];
                rank[rootX] += 1;
            }
        }
    }
    
    bool isConnect(int x, int y) {
        return find(x) == find(y);
    }
    
private:
    vector<int> root;
    vector<int> rank;
}


bool isNoCycle(int n, vector<vecotor<int>>& edges) {
    UnionFind uf(n);
    for (vector<int>& edge: edges) {
        if (uf.isConnect(edge[0], edge[1])) {
            return false;
        } else {
            uf.unionSet(edge[0], edge[1]);
        }
    }
    return true;
}
```

finish time: 15:16


### Q2 ----------------------------------
start time: 15:18
Q:the number of different cycles of length 3?
Input: n = 5, edges = [[1,2],[5,2],[4,1],[2,4],[3,1],[3,4]]

edges = [[4,1],[3,1],[3,4]]

graph: {1: [3, 4], 3: [1, 4], 4: [1, 3]}
i = 1
path: [1]

dfs(graph, [], 1) -> dfs(graph, [1], 3), dfs(graph, [1], 4)

dfs(graph, [1], 3) -> dfs(graph, [1, 3], 1), dfs(graph, [1, 3], 4)

dfs(graph, [1, 3], 4) -> dfs(graph, [1, 3, 4], 1), dfs(graph, [1, 3, 4], 3)

dfs(graph, [1, 3, 4], 1) -> dfs(graph, [1, 3, 4, 1], 3), dfs(graph, [1, 3, 4, 1], 4) 

TC: O(n^2)
OC: O(n^2)

edges = [[4,1],[3,1],[3,4]]

3: 1
4: 1 3



```cpp!
class Solution {
    int cnt = 0;

public:
    void dfs(unordered_map<int, vector<int>>& graph, vector<int>& path, int nodeVal){
        path.push_back(nodeVal);
        for (int nextVal: graph[nodeVal]) {
            if (path.size() == 3) {
                if (path[0] == nextVal) {
                    cnt++;
                }
                continue;
            }
            dfs(graph, path, nextVal);
        }
    }
    
    int cycleCnt(int n, vector<vector<int>> edges) {
        unordered_map<int, vector<int>> graph;
        for (vector<int>& edge: edges) {
            graph[edge[0]].push_back(edge[1]);
            graph[edge[1]].push_back(edge[0]);
        }
        
        for (int i = 1; i < n + 1; i++) {
            vector<int> path;
            dfs(graph, path, i);
        }

        return (cnt / 6);
    }
}
```



finish time: 15:55

Q3
aa??bb
=> aababb
aa?
=>aab
b?
=>bb ba
### feedback
1.
2.
