Amazon Interview Question
SDE-3sCountry: United States
All answers are .. staggeringly wrong. Guys & Gals - it is a directory structure. I can destroy all these algorithms happiness by repeating same directory names in entirely different paths.
For example:
a/../../../a
Did you notice something interesting there? NO? Let me show you.
Suppose I am currently in the directory :
/home/dofus/
Now, the first bit will move me to
/home/dofus/a
Next 3 "../" will take me to :
/ # this is root!
And then next "a" will take me to:
/a # a directory under the root.
So, it is not as easy as it sounds. In fact, that is why the guys who write JDK has a special function for it called
[ docs.oracle.com/javase/10/docs/api/java/io/File.html#getCanonicalPath() ]
You have to normalise paths with respect to the starting or base directory.
And that is why it is an SDE3 question, not an SDE1/2 question.
Specifically:
visitCount("a/../../../a"); // null pointer exception
I will answer this in next post.
private Map<String, Integer> visitCount(String path) {
final Map<String, Integer> count = new LinkedHashMap<>();
String[] parts = path.split("\\/");
Deque<String> st = new LinkedList<>();
for (String part : parts) {
if (st.isEmpty() || !part.equals("..")) {
count.put(part, count.getOrDefault(part, 1));
st.push(part);
} else {
st.pop();
count.put(st.peek(), count.get(st.peek()) + 1);
}
}
return count;
}
Here you go.
/*
In here, we are abusing Java IO
*/
def abusing_java_print_count( path_string ){
if ( path_string #$ "/" ){
// remove trailing "/"
path_string = path_string[0:-2]
}
words = path_string.split("/",-1)
count = dict()
p = words[0]
f = file( p ).file.getCanonicalPath()
count[f] = 1
for ( i : [ 1 : size(words) ] ){
p += ("/" + words[i])
f = file( p ).file.getCanonicalPath()
if ( f !@ count ){
count[f] = 0
}
count[f] += 1
}
count // return
}
c = abusing_java_print_count( "a/../../../a")
println( jstr(c,true) )
The crucial thing is the abstract call to getCanonicalPath(), which one can now replace with
a custom impl. Here is how you get the response:
{
"\/Codes\/zoomba\/a":1,
"\/Codes":1,
"\/a":1,
"\/Codes\/zoomba":1,
"\/":1
}
Stack to keep track of traversal and Map to keep count. When you see something on the top of the stack increment its count on the map ( if does not exist then set count to 1).
Using c#
/*
List<Directory> lst = VisitCount("cd a/b/../c/d/e/../../");
foreach (Directory d in lst)
{
Console.WriteLine($"{d.Name} - {d.Count}");
}
*/
private class Directory
{
public string Name {get; set;}
public int Count { get; set; }
public Directory(string name, int count)
{
this.Name = name;
this.Count = count;
}
}
private List<Directory> VisitCount(string path)
{
List<Directory> directories = new List<Directory>();
if (path.ToLower().StartsWith("cd "))
path = "Root/" + path.Substring(3);
string[] parts = path.Replace('\\', '/').Split('/');
int back = 0;
for(int i = 0; i < parts.Length; i++)
{
if(parts[i] != "")
{
if (parts[i] == "..")
{
back = back + 2;
if ((i - back) < 0)
throw new Exception("Invalid path");
parts[i] = parts[i - back];
}
else
{
back = 0;
}
int idx = directories.FindIndex(x => x.Name == parts[i]);
if (idx < 0)
directories.Add(new Directory(parts[i], 1));
else
directories[idx].Count++;
}
}
return directories;
}
Using a stack and a map.
- Vyshnavi June 11, 2019In stack, when ever I see the directory name I push the directory name in the stack and add the directory name in map if it does not exist or if exists increase the value by 1.
In stack, when ever I see ".." I pop the stack and see the top element and increment its value in the map.
This way finally map has the directory name and its visit count as key,value.