Amazon Interview Question
Software Engineer / DevelopersSince File System is like a tree structure, I would say using Composite Pattern works here. Where the Component node will be directory and file will be a root node.
The base class which is composite node has methods like
-vector<Component_Class> child.
+addFile()
+removeFile()
-_lastmodified
_creationtime
Just had an interview with Amazon..and first two questions were..
What are the classes and data structures you would use for a file
system
What kind of data structure would you use to implement a map (not a
location map... But rather a mapping from a key to a value).
Both of these questions were mentioned under Gayle's tips. I think I bombed...in the interview...
Any insight about the second question...?
if you mean a mapping from the logical address to the physical one, then file systems usually use an Extensible Hash Table. Even a B-Tree isn't such a bad answer :)
Just had an interview with Amazon..and first two questions were..
What are the classes and data structures you would use for a file
system
What kind of data structure would you use to implement a map (not a
location map... But rather a mapping from a key to a value).
Both of these questions were mentioned under Gayle's tips. I think I bombed...in the interview...
Any insight about the second question...?
Map is usually implemented using a hash table or balanced binary tree (Red Black Tree is the popular tree data structures). If you know ahead of time how many elements are to be inserted and the number is small, an array would do the job. A Splay Tree would be a good data structures if there are some accessing pattern.
Go through and solve all the questions on this website. This is the best preparation. I don't know any other good interview books. I recommend reading data structures and algorithms and design patterns books. I recommend Algorithms in C++ by SedgeWick, Effective C++ and More Effective C++ by Scott Meyers. The Algorithm Design Manual by Steven Skienna and the classic Introductions to Algorithms(CLR). Mark Weiss Data Structures and Algorithms book is very useful. If you read all these books and and solve all the questions on Gayle's website, I think you would have an easier time with these interview questions.
To answer this question I would probably go into B-Trees and it's variants (B+ and B-) for the data structures of file systems. Not sure as far as classes go, but I imagine it's a little more complicated than having a list of files for a directory, and a tree/map of directories for a filesystem.
As far as data structures for maps (ie. associative arrays), Red-Black trees is a good answer as well.
Both of these are basically self-balancing binary trees, the knowledge of which is what I think what they are really after.
I am also looking for Gayle's website that everyone is refering to here. Can someone please post a link or some more info about it.
Thanks.
Just to get the ball rolling:
- Vader May 06, 2006class File{
permissions user;
permissions group;
permissions other;
char * owner;
char *group
int size;
date created;
date modified;
char * name;
char * extension;
}
class Directory:public File{
List <File> filesInTheDirectory[];
}
class FileSystem{
Tree <Directory> fileSystem;
}