Microsoft Interview Question
Software Engineer in TestsCountry: United States
Easy using recursive methods but checking circle is tricky...
void FindPaths(const string& source, const string& dest, list<string>& path)
{
path.push_back(source);
if(source == dest)
{
PrintPath(path);
path.pop_back();
return;
}
list<string> destList = RetriveDestinations(source);
for(list<string>::const_iterator iter = destList.begin(); iter != destList.end(); ++iter)
{
if(find(path.begin(), path.end(), *iter) != path.end())
{
continue;
}
else
{
FindPaths(*iter, dest, path);
}
}
path.pop_back();
}
BFS algorithm should work for this.
- Anonymous November 16, 2011