Olivier Langlois's blog

Graph breadth-first traversal algorithm C++ implementation

08/24/10

08:53:31 pm, by lano1106

, 97 words, 2059 views

Categories: General, C++

Graph breadth-first traversal algorithm C++ implementation

I have posted on my website a small C++ program that I have been asked to write during an interview with Facebook at Fall 2009. One of their interview was related to graph theory and the problem was to find the the shortest distance between to nodes in a graph. The best algorithm to use to solve this problem is the breadth-first traversal algorithm.

You can look at the source code here at:
http://www.olivierlanglois.net/archive/graph_cpp.htm

and you can read more about the breadth-first traversal algorithm in Robert Sedgewick excellent book on algorithms.

Permalink 3 comments

Comments, Pingbacks:

Comment from: Stephen Reis [Visitor] · http://www.terminalserverprinting.org/

Never had any interview where I was asked to write a program. Did that take you long to create Olivier; if ever it did facebook paid your time? Just asking out of curiosity.

Permalink 10/11/10 @ 15:01

Comment from: lano1106 [Member]

Stephen,

You have about 30 minutes, maybe less than that to produce the program. That being said, I am not even sure that I had a working program during the alloted time. and no, they do not pay you for your time like any interviews in any company that I know and IMO, this is the right thing to do.

I have considerably embellished the program once I decided that I would publish it on my website. With all the comments, and all the cool STL usages within the program, I would say that I spent a good evening to bring the program as it is now.

Permalink 10/11/10 @ 19:18

Comment from: stephen [Visitor]

Cool, I thought the interview was an all day affair hence my question about payment.

Permalink 10/12/10 @ 06:10

This post has 325 feedbacks awaiting moderation...

I want you to find in this blog informations about C++ programming that I had a hard time to find in the first place on the web.

Sun	Mon	Tue	Wed	Thu	Fri	Sat
<< <				> >>
			1	2	3	4
5	6	7	8	9	10	11
12	13	14	15	16	17	18
19	20	21	22	23	24	25
26	27	28	29

Olivier Langlois's blog

Graph breadth-first traversal algorithm C++ implementation

08/24/10

Graph breadth-first traversal algorithm C++ implementation

Comments, Pingbacks:

Leave a comment:

Olivier Langlois's blog

Search

Categories

Olivier Langlois's blog

Archives

Misc

XML Feeds

Who's Online?