Saturday, January 20, 2018

Connected components in a matrix - BFS

January 20, 2018


Introduction


It is 10:00 am mock interview, and I have chance to interview a super talented graduate student. He wrote the breath first search, since I ask him to write. He told me either BFS or DFS. I like to review BFS, so I asked him to write a BFS one.

Code review


I also told the peer that I like to learn C++ from him, so I write down each word he wrote, so I can stay current and then ask question. First question I asked in C++ why he declared a structure from line 7 to line 9 vec2i, why not int[]. And then he explained it to me. Later he also gave me a code snippet to explain the empty array shows the size 8 instead of zero in C++.

C++ code is here using BFS, queue.

And then I appraised that the BFS code is very readable and also very easy to follow. The peer changed the code to write DFS using stack as well, just a few lines of code change. And he explained to me using recursive function, it may stack overflow.

C++ code is here using DFS, stack.

No comments:

Post a Comment