Crawler folder log-coding question asked by Oracle, DE Shaw

Problem Statement:

Zepskill (subsidary of placewit) file system keeps a log each time some user performs a change folder operation.

The operations are described below:

“../” : Move to the parent folder of the current folder. (If you are already in the main folder, remain in the same folder).

“./” : Remain in the same folder.

“x/” : Move to the child folder named x (This folder is guaranteed to always exist).

You are given a list of strings logs where logs[i] is the operation performed by the user at the ith step.

The file system starts in the main folder, then the operations in logs are performed.

Return the minimum number of operations needed to go back to the main folder after the change folder operations

Input Format:

String containing logs

Output Format:

Number of operations needed to go to main folder

Sample Input 1:

["d1/","d2/","../","d21/","./"]

Sample Output 1:

2

Sample input 2:

["d1/","d2/","./","d3/","../","d31/"]

Sample output 2:

3

Sample Input 3:

["d1/","../","../","../"]

Sample Output 3:

0

Constraint:

• 1 <= logs.length <= 10^3
• 2 <= logs[i].length <= 10
• logs[i] contains lowercase English letters, digits, ‘.’, and ‘/’.
• logs[i] follows the format described in the statement.
• Folder names consist of lowercase English letters and digits.

Approach:

he problem can be easily solved by just keep tracking a depth variable which is basically showing that at what depth we are from root folder.
Each time we are going to a child folder, we are going far from the root folder by distance 1.( i.e. depth++ )
Each time we are going to a parent folder, we are decreasing coming nearer to root folder by distance 1. (i.e. depth–).
Note that we can only move to parent folder if we are not in the root folder.
So, we will start executing the commands from left to right in a for loop .

• If we will encounter “../” we will check if we are in root folder or not. If no then we will decrease depth by 1.
• Else if we will encounter “./” we have to stay in current folder, thus no change in depth variable.
• Else we have to move to one of our child folder. Thus, we will increase our depth by 1.

After all the commands, our depth variable is storing the distance from the root folder. We will return it as output.

Time complexity: O(n)

Space complexity: O(n)

Code:

Thanks for Reading

Placewit grows the best engineers by providing an interactive classroom experience and by helping them develop their skills and get placed in amazing companies.

Learn more at Placewit. Follow us on Instagram and Facebook for daily learning.