包子君听小伙伴说最近面试market僧多肉少(不过貌似资深程序员需求既然强烈。In May, U.S. employers added 28,000 technology workers, according to tech trade group CompTIA’s analysis of government jobs data.)，被雷的，骑驴找马的，公司抄底好员工，同时也有了更多的议价lowball资本。
面试本来就难，除了基本功扎实手刃leetcode hard question bug free code, 又能30分钟同时design netflix，youtube 和facebook，video面试有什么需要注意的事项吗？
文章和图片来源：https://www.theinformation.com/articles/how-to-find-a-new-job-during-the-pandemic，基本一堆废话没有什么营养😒
其实video面试和in person并没有什么太大不同，永远记住面试你面得是人，不是题。
一些小tip：
- 花点钱网速快一点
- 注意一些礼貌，有可能他家网慢，等一会再说话，让人家把话说完你再说
- 微笑，看镜头，背景弄得干净整洁一点。
- 注意下自己对于公司culture的理解，尽量focus在技术和而不是对当下时局美国革命小将的高谈阔论。
Blogger: http://blog.baozitraining.org/2020/06/leetcode-solution-200-number-of-islands.html
Youtube: https://youtu.be/E5_ivrrLVFQ
博客园: https://www.cnblogs.com/baozitraining/p/12963010.html
B站: https://www.bilibili.com/video/BV1oz4y1X71Y
Problem Statement
Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example 1:
Input:
11110
11010
11000
00000Output: 1
Example 2:
Input:
11000
11000
00100
00011Output: 3
Problem link
Video Tutorial
You can find the detailed video tutorial here
- Youtube BFS & DFS solution in 2015
- Youtube Disjoint Solution
- B站
Thought Process
I have recorded a video back in 2015 (5 years ago, Geez time flies) using BFS and DFS. The essential idea is every time we see a land (i.e., “1”), we would trigger a BFS or DFS search to mark all the connected grids and increase the island counts to 1.
Another solution is to use Disjoint Set (aka Union Find). There is a generic solution where we could implement a DisjointSet data structure and perform “union” steps first to assign each grid a “parent”. In the 2nd iteration we can perform “find” step to count how many distinct “parents”, which is the number of islands.
A quick summary of some classic use cases
- Disjoint Set / Union Find (Disjoint set is the data structure while union find is the algorithm, people normally use it interchangeably) can often be used to solve if a graph is connected or not, such as phone contact problem (who knows who, how many isolated groups are there)
- To detect if a directed graph has cycle, use Kahn’s algorithm for topological sort
- To detect if a un-directed graph has cycle
- We could use normal BFS or DFS
- We should use Union Find with edge list graph representation
Solutions
Use BFS
1 public class Block {
2 public int x;
3 public int y;
4
5 public Block(int x, int y) {
6 this.x = x;
7 this.y = y;
8 }
9 }
10
11 public int numIslandsBFS(char[][] grid) {
12 if (grid == null || grid.length == 0 || grid[0].length == 0) {
13 return 0;
14 }
15
16 int m = grid.length;
17 int n = grid[0].length;
18
19 boolean[][] visited = new boolean[m][n];
20 int count = 0;
21
22 for (int i = 0; i < m; i++) {
23 for (int j = 0; j < n; j++) {
24 if (grid[i][j] == '0' || visited[i][j]) {
25 continue;
26 }
27
28 count++;
29 visited[i][j] = true;
30
31 Queue<Block> q = new LinkedList<>(); // queue just uses LinkedList, ArrayList doesn't implement it
32
33 // remind myself what's the diff between offer and add,
34 // some implementation it's the same, some add throws while offer return true/false if the queue is
35 // full while you still trying to add
36 q.offer(new Block(i, j));
37
38 while (!q.isEmpty()) {
39 Block b = q.poll();
40
41 for (int k = 0; k < 4; k++) {
42 int x = b.x + xDirection[k];
43 int y = b.y + yDirection[k];
44 if (this.shouldExplore(x, y, m, n, grid, visited)) {
45 visited[x][y] = true;
46 q.offer(new Block(x, y));
47 }
48 }
49 }
50 }
51 }
52 return count;
53 }
54
55 private boolean shouldExplore(int x, int y, int row, int col, char[][] grid, boolean[][] visited) {
56 if (x >= 0 && x < row && y >= 0 && y < col && grid[x][y] == '1' && !visited[x][y]) return true;
57
58 return false;
59 }Time Complexity: O(M*N), where M and N is row and col of grid matrix. Each grid is visited once
Space Complexity: O(M*N) since we have to track the visited grid
Use DFS
1 private final int[] xDirection = {1, 0, -1, 0};
2 private final int[] yDirection = {0, -1, 0, 1 };
3
4 public int numIslands(char[][] grid) {
5 if (grid == null || grid.length == 0 || grid[0].length == 0) {
6 return 0;
7 }
8
9 int m = grid.length;
10 int n = grid[0].length;
11 int islandCount = 0;
12 boolean[][] visited = new boolean[m][n];
13
14 for (int i = 0; i < m; i++) {
15 for (int j = 0; j < n; j++) {
16 if (grid[i][j] == '0' || visited[i][j]) {
17 continue;
18 }
19 explore(i, j, m, n, grid, visited);
20 islandCount++;
21 }
22 }
23
24 return islandCount;
25 }
26
27 private void explore(int x, int y, int row, int col, char[][] grid, boolean[][] visited) {
28 if (!this.shouldExplore(x, y, row, col, grid, visited)) return;
29
30 visited[x][y] = true;
31 for (int i = 0; i < 4; i++) {
32 explore(x + this.xDirection[i], y + this.yDirection[i], row, col, grid, visited);
33 }
34 }Time Complexity: O(M*N), where M and N is row and col of grid matrix. Each grid is visited once
Space Complexity: O(M*N) since we have to track the visited grids
Use Disjoint Set / Union Find
1 private class DisjointSet {
2 private Map<String, String> lookup = new HashMap<>();
3
4 public void init(int row, int col) {
5 for (int i = 0; i < row; i++) {
6 for (int j = 0; j < col; j++) {
7 String key = i + "," + j;
8 // initially key value is the same, meaning the parent of the disjoint set is itself, i.e., isolated or not initialized
9 this.lookup.put(key, key);
10 }
11 }
12 }
13
14 /**
15 * @param key "row,col" is the key in the mastrix
16 * @return String, "row,col" of the parent of this key
17 */
18 public String find(String key) throws Exception {
19 if (key == null || key.length() == 0 || !this.lookup.containsKey(key)) {
20 throw new Exception(String.format("Invalid input key %s", key));
21 }
22
23 while (!key.equals(this.lookup.get(key))) {
24 key = this.lookup.get(key);
25 }
26
27 return key;
28 }
29
30 public void union(String key1, String key2) throws Exception {
31 if (key1 == null || key1.length() == 0 || key2 == null || key2.length() == 0) {
32 throw new Exception(String.format("key1 %s or key2 %s not valid", key1, key2));
33 }
34
35 String parent1 = this.find(key1);
36 String parent2 = this.find(key2);
37
38 if (!parent1.equals(parent2)) {
39 this.lookup.put(parent1, parent2);
40 }
41 }
42
43 }
44
45 public int numIslandsDisjoinSet(char[][] grid) {
46 if (grid == null || grid.length == 0 || grid[0].length == 0) {
47 return 0;
48 }
49
50 int row = grid.length;
51 int col = grid[0].length;
52 // key: row,col, val: row,col
53 DisjointSet ds = new DisjointSet();
54 ds.init(row, col);
55 Set<String> islands = new HashSet<>();
56
57 try {
58 for (int i = 0; i < row; i++) {
59 for (int j = 0; j < col; j++) {
60 if (grid[i][j] == '1') {
61 String key = i + "," + j;
62 // union right grid
63 if (j + 1 < col && grid[i][j + 1] == '1') {
64 ds.union(key, i + "," + (j + 1));
65 }
66 // union the below grid
67 if (i + 1 < row && grid[i + 1][j] == '1') {
68 ds.union(key, (i + 1) + "," + j);
69 }
70 }
71 }
72 }
73
74 for (int i = 0; i < row; i++) {
75 for (int j = 0; j < col; j++) {
76 if (grid[i][j] == '1') {
77 islands.add(ds.find(i + "," + j));
78 }
79 }
80 }
81 } catch (Exception e) {
82 System.err.println(e);
83 }
84 return islands.size();
85 }Time Complexity: O(M*N), where M and N is row and col of grid matrix. Each grid is visited once
Space Complexity: O(M*N) since we have to track the visited grids using a map
References
- Leetcode official solution
