A Brief Reflection on my Interviews
I have been doing interviews for a while now, companies I interviewed with range from big names to small inspiring start-ups. Here is a little murmuring of my reflections on it.
In the data structure class, we know we could traverse a tree in two basic fashion, depth-first and breadth-first, each of the traversing methods has recursive and iterative two ways to implement(well I think every recursive implementation has its iterative way to implement), in the iterative way depth-first traverse we usually use a stack as a helping data structure to traverse through the tree, while in breadth-first, we use a queue (a FIFO first in first out structure).
#include <iostream>
using std::cout;
breadth_first_traversal(Node* croot){
queue<Node*> q;
Node* level;
int height;
if (!croot){
q.enqueue(croot);
q.enqueue(level);
while (!q.empty()){
Node* temp = q.dequeue();
if (temp==level){
height++;
q.enqueue(level);
temp = q.dequeue();
}
cout<<temp->value<<' ';
if(!temp->left) q.enqueue(temp->left);
if(!temp->right) q.enqueue(temp->right);
}
}
}
The brief code showed how powerful breadth-first search could be, it
could help you traverse through each node of a tree, while help you keep
track of the height of the tree. In my recent interview questions, I
also encountered a question that ask me to implement an iterator for a
general tree class, given by the short timing, I also found that the
same breadth-first traverse philosophy could apply to the problem, using
a queue structure as iterator, checking if the queue is empty to see if
this iterator ‘hasNext’. And in another question, where a brief Facebook
Member class is defined, which includes a name and a email address of
the user, and a list of his friends (List
Comments
comments powered by Disqus