Google & Microsoft
Java Interview Questions
Amazon Interview Question
Compaq Interview Question
You have to get from point A to point B. You donâ€™t know if you can get there. What would you do?
The two most common ways to tackle a problem like this are using Depth-First Search (DFS), and Breadth-First Search (BFS). In the example above, you drive and drive around while you hope to find the destination. Have you reached a deadend? Turn around and go back to where you came from. It might not be the shortest way, but if you tried every possible road, you would know that you canâ€™t get to China from New York. Understanding this leads you to more exotic things like A* Search, and itâ€™s a fundamental exploring algorithm. Too many things can be reduced into a graph, and knowing the best way to search a graph will come in handy. DFS is basically a stack-based implementation, while BFS is a queue-based implementation, each with its own strengths and weaknesses..
Â© 2006 - 2011 Technical-Interview.com . All rights reserved