Crawler Log Folder — Solution in Python, Java & C++
Crawler Log Folder solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem on arrays and strings.
Crawler Log Folder is an easy coding problem on arrays, strings and stack, asked in Amazon and Adobe interviews.
- Difficulty: Easy
- Topics: Arrays, Strings, Stack
- Asked at: Amazon, Adobe
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
The file system starts in the main folder. You are given a change-folder log where each entry is one of:
"../"— move to the parent folder, or stay put if already in the main folder;"./"— stay in the current folder;"x/"— move into the child folder namedx.
Return the minimum number of "../" operations needed to get back to the main folder.
Example 1
Input: logs = ["d1/","d2/","../","d21/","./"]
Output: 2
Example 2
Input: logs = ["d1/","d2/","./","d3/","../","d31/"]
Output: 3
Example 3
Input: logs = ["d1/","../","../","../"]
Output: 0
Constraints
1 <= logs.length <= 30Each entry is "../", "./", or a folder name followed by "/".
Hints for Crawler Log Folder
Hint 1
Only the current depth matters, not the folder names.
Hint 2
"x/"increases the depth,"../"decreases it,"./"leaves it alone.Hint 3
The depth can never go below zero —
"../"in the main folder does nothing.
How to solve Crawler Log Folder
Only the depth matters: x/ adds one, ../ subtracts one (floored at zero), ./ does nothing.
Approach
- Walk the log updating
depth. - Return
depth.
Why it works
The number of ../ needed to return to the root equals the current depth, and the floor at zero models ../ at the root being a no-op.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Folder names are irrelevant.
Reference solution
Python
def minOperations(logs) -> int:
depth = 0
for op in logs:
if op == "../":
depth = max(0, depth - 1)
elif op != "./":
depth += 1
return depthJava
public static int minOperations(String[] logs) {
int depth = 0;
for (String op : logs) {
if (op.equals("../")) {
if (depth > 0) depth--;
} else if (!op.equals("./")) {
depth++;
}
}
return depth;
}C++
int minOperations(vector<string>& logs) {
int depth = 0;
for (const string& op : logs) {
if (op == "../") {
if (depth > 0) depth--;
} else if (op != "./") {
depth++;
}
}
return depth;
}JavaScript
var minOperations = function(logs) {
let depth = 0;
for (let i = 0; i < logs.length; i++) {
const op = logs[i];
if (op === "../") {
if (depth > 0) depth--;
} else if (op !== "./") {
depth++;
}
}
return depth;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.