Riverbed Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
Many systems model it as a tree, where each file is a node. Directories are then treated as a type of file that can hold other files (nodes in the tree that can be parent nodes to other nodes). All non-directories are leaf nodes in such a system. File systems are usually hierarchical, so a tree is a logical choice for such systems.
What are the filesystem scenarios? (Eg: single machine or distributed, Space optimized, what kind of API to provide etc).
No, don't need to deep into this problem, just describe a brief idea about what data structure used in the file system.
I would use composite patter.
interface Ifile{
byte getFile();
}
class File implements Ifile{
byte getFile(){
//return conten of file
};
}
class folder implements Ifile{
List<Ifile> files;
byte getFiles(){
List<Ifile> return = new ArrayList<Ifile>();
forach(Ifile file:files){
if(file instanseof Folder){
return.addAll(file.getFiles());
}else{
return.add(file.getFile());
}
}
}
}
It does not run but you get the idea.
This is just pattern, If you need datastructure, maybe tries. kinda folder->file relationship
folder
file folder
file file folder
file folder file
...
One of the implementation is to use a prefixTree, where PrefixTree starts with \ and every path node is deliminated by \ for example.
\c:\program files\a.txt
\c:\program files\b.txt
\
/
c:
/
Program files
/ \
a.txt b.txt
So, the lookup will be always O(n), where n is the nodes in the path.
Infact, windows NTFS uses this as internal structure to store their path.
An n-ary tree structure with the root being "/"?
- JustCoding September 27, 2012