Amazon Interview Question Software Engineer in Tests
Country: India
Interview Type: Phone Interview
Consider a tree structure for the directory.
Read the input and while input string is not over do following for
each element after 'cd '
switch(ch)
current directory will be root.
when command is
case 1. cd a
two possibilities
a) There is a child directory a, you need to go to this node
b) No child directory called a stop and print error
case 2 cd .
Do nothing. '.' means current directory
case 3 cd ..
Go to parent
Going to parent will be expensive(Unless yiou modify a Tree to have parent pointer)..... We Should to use stack to first find out the path (i.e. without "." and "..") once we have the path we can follow Tree to go to the correct directory
I think you can make use of a doubly linked list while storing the ptr to the last element...
split the string based on '\'. When you find a char insert it at the end of the DLL if it's a valid path. When you encounter a '.' do nothing. When you encounter a ".." delete the last element in the DLL.
Does that make sense ?
Stack is the right data structure for this.
- Victor July 19, 2012