Amazon Interview Question
Software Engineer / DevelopersCould do this-
1. Generate a graph using the Grid. Can use Adjacency List or Grid as is (i.e. adjacency Matrix)
2. Define these functions -
-> gen_words(startchar, endchar)
{ /*BFS traversal of the graph*/ }
-> gen_all_words()
{
for(i=A to Z)
for(j=A to Z)
gen_words(i,j)
}
-> construct_graph(grid[][]){/* graph construction to be done only once at start*/}
-> main(){ construct_graph();
gen_all_words();
}
We need to maintain a Visited[n][n] flags.. so that we don't loop around.. once this is done the algorithm is simple.. check for boundary conditions and for visited flags.. if not recurse in all 4 direction (i, j) - > (i-1, j), (i, j-1), (i+1, j), (i, j+1).. print the words as we traverse.. remember to reset the flag as we recurse out..
fuck
- john February 09, 2011