h*********d
发帖数: 336 | 1 phone interview, 实现一个in-memory filesystem. 刚开始面试，还没有摸到门路，
请大牛指点
Write an in memory filesystem! This is a simplified file system that only
supports directories. Your code needs to read from a file and parse the
commands listed below.
cd - Changes the current working directory. The working
directory begins at '/'. The special characters '.' should not modify the
current working directory and '..' should move the current working directory
to the parent.
mkdir - Creates a new directory with the current working directory as
the parent.
rmdir - Removes a directory from the current working directories's
children. This is only allowed if the directory you are removing contains no
children.
pwd - Prints the current working directory's path from the root. Example: /
school/homework
ls - Lists the children of the current working directory. These are printed
on a single line with a single space character separating them. Example:
math history spanish
When started the only directory in your virtual filesystem should be the
root directory, '/', the current working directory should also point here.
Example Input file:
mkdir school
cd school
pwd
mkdir homework
cd homework
mkdir math
mkdir lunch
mkdir history
mkdir spanish
rmdir lunch
ls
pwd
cd ..
mkdir cheatsheet
ls
rmdir cheatsheet
cd ..
pwd
Example output from the above file:
/school
math history spanish
/school/homework
homework
cheatsheet
/
以下是我的code，时间比较紧，所以validation & exception 都没怎么做，
public class FileSystem {
private static FileSystem fileSystem;
private Directory root;
private HashMap dirMap;
private Directory current;
/*
* use Singleton Design pattern to keep global configuration in
FileSystem instance
*/
private FileSystem() {
root = new Directory("", null);
dirMap = new HashMap();
current = root;
}
public static FileSystem getInstance(){
if (fileSystem==null) fileSystem = new FileSystem();
return fileSystem;
}
/*
* for command "mkdir"
*/
public boolean createDirctory(String name) {
if (isValidDirName(name)) {
Directory d = new Directory(name, current);
boolean res = current.add(name, d);
if (res) {
dirMap.put(name, d) ;
return true;
}
return false;
}
return false;
}
/*
* for command "cd"
*/
public void changeWorkingDir(String dir) {
if (dir.equals(".")) return ;
if (dir.equals("..")) {
current = current == root ? root : current.parent;
} else {
Directory res = current.goSubDir(dir);
if (res!=null) current = res;
}
}
/*
* for command "pwd"
*/
public void getCurrentPath(){
if (current==root) System.out.println("/");
else System.out.println(current.getPath());
}
/*
* for command "ls"
*/
public void listDirs() {
if (current.isEmptyDir()) {
System.out.println("it is a empty directoyr");
} else {
Set res = current.getChildren();
for (String name : res) {
System.out.print(name + " ");
}
System.out.println();
}
}
/*
* for command "rmdir"
*/
public void removeDir(String name) {
if (!dirMap.containsKey(name)) return;
else {
boolean res = current.removeSubDir(name);
if (res) dirMap.remove(name);
}
}
/*
* directory name must be 0-9 and A-Z or a-z
*/
private boolean isValidDirName(String name){
if (!Pattern.matches("[a-zA-Z0-9-_]{1,200}", name)) {
System.out.println(name + " is not valid. Please use a valid
name for directory" );
return false;
}
return true;
}
}
public class Directory {
private String name;
private String path;
protected Directory parent;
private HashMap children;
public Directory(String n, Directory d) {
name = n;
path = d==null ? "" : d.getPath() + "/" + name;
parent = d;
children = new HashMap();
}
/*
* get path for this directory
*/
public String getPath() {
return path;
}
/*
* get name for this directory
*/
public String getName() {
return name;
}
/*
* check whether is directory is empty
*/
public boolean isEmptyDir() {
return children.size()==0;
}
/*
* remove sub dircetory
*/
public boolean removeSubDir(String name) {
if (children.containsKey(name)) {
Directory dir = children.get(name);
if (dir.isEmptyDir()) {
children.remove(name);
return true;
}
return false;
}
return false;
}
/*
* return a set for all sub directory name
*/
public Set getChildren(){
return children.keySet();
}
/*
* add a new directory
*/
public boolean add(String name, Directory child){
if (children.containsKey(name)) return false;
children.put(name, child);
return true;
}
/*
* go to sub directory
*/
public Directory goSubDir(String child){
if (children.containsKey(child)) {
return children.get(child);
} else {
return null;
}
}
} |
h*********d
发帖数: 336 | 2 另外， 我写了个main to do test, 写的比较糙，是不是这样parse command不好啊?
public static void main(String[] args){
FileSystem fs = FileSystem.getInstance();
File file = new File("C:/JobHunting/input.txt");
try {
BufferedReader br = new BufferedReader(new FileReader(file));
String line = new String();
while ((line = br.readLine()) != null) {
String[] command = line.split(" ");
if (command[0].equals("mkdir")) {
fs.createDirctory(command[1]);
} else if (command[0].equals("cd")) {
fs.changeWorkingDir(command[1]);
} else if (command[0].equals("pwd")) {
fs.getCurrentPath();
} else if (command[0].equals("rmdir")) {
fs.removeDir(command[1]);
} else if (command[0].equals("ls")) {
fs.listDirs();
}
}
br.close();
} catch (IOException e) {
e.printStackTrace();
} finally {
}
}
directory
as
【在 h*********d 的大作中提到】
: phone interview, 实现一个in-memory filesystem. 刚开始面试，还没有摸到门路，
: 请大牛指点
: Write an in memory filesystem! This is a simplified file system that only
: supports directories. Your code needs to read from a file and parse the
: commands listed below.
: cd - Changes the current working directory. The working
: directory begins at '/'. The special characters '.' should not modify the
: current working directory and '..' should move the current working directory
: to the parent.
: mkdir - Creates a new directory with the current working directory as
|
A*****i
发帖数: 3587 | 3 不用考虑多线程么？如果多个线程access同一个dir怎么办？ |
h*********d
发帖数: 336 | 4 我没想到啊,平时很少用multi threading，如果这样需要加synchronized for
FileSystem 的 instance, 但这会影响 performance 吧
您能不能说说还有没有其他有效的方法
【在 A*****i 的大作中提到】
: 不用考虑多线程么？如果多个线程access同一个dir怎么办？
|
A*****i
发帖数: 3587 | 5 当设计题做的话多线程必须要考虑的，如果就是个电面题应该不用。
【在 h*********d 的大作中提到】
: 我没想到啊,平时很少用multi threading，如果这样需要加synchronized for
: FileSystem 的 instance, 但这会影响 performance 吧
: 您能不能说说还有没有其他有效的方法
|
h*********d
发帖数: 336 | 6 是电话面试最后给我发过来一道题，不知道算不算system design。 让我做完发过去，
不能多于2小时。
您能不能和我说说您认为的有效考虑多线程的方法，应如何code？我能想到的就是加
synchronized 在instance of FileSystem.
望大牛指点
【在 A*****i 的大作中提到】
: 当设计题做的话多线程必须要考虑的，如果就是个电面题应该不用。
|
A*****i
发帖数: 3587 | 7 java的话问古德霸吧，或者赵策也行。基本上思路就这些 |
h*********d
发帖数: 336 | 8 谢谢，您能告诉我古德霸的id吗。我在版上搜不到，赵策的信箱满了，发不过去信。
【在 A*****i 的大作中提到】
: java的话问古德霸吧，或者赵策也行。基本上思路就这些
|
|
A*****i
发帖数: 3587 | 9 goodbug
你发个帖题目叫“java难用的跟屎一样”他就自动出现了
【在 h*********d 的大作中提到】
: 谢谢，您能告诉我古德霸的id吗。我在版上搜不到，赵策的信箱满了，发不过去信。
|
