Amazon Interview Question for SDE-3s


Country: United States




Comment hidden because of low score. Click to expand.
1
of 1 vote

Using a stack and a map.

In 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.

- Vyshnavi June 11, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

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.

- NoOne June 13, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Given output is wrong :
Root - 1
a - 2
b - 1
c - 2
d - 2
e - 1

- code reviewer June 10, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Updated

- neer.1304 June 12, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
	}

- Saravana June 12, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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
}

- NoOne June 13, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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).

- Mukul June 14, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can you help understand me the question. What does directory count mean and how is it even calculated ?

- ajaysingh9022 June 20, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
        }

- shaunmey June 20, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

it should use stack to solve

- lixx3527 July 27, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Stack is the right data structure for thsos

- anshuman101 February 12, 2020 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More