Graph Topological Sorting - Build System Order Example
Graph Topological Sorting This is a well known problem in graph world…
October 03, 2020
The Leetcode 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.
Example
Input: logs = ["d1/","d2/","../","d21/","./"]
Output: 2
Explanation: Use this change folder operation "../" 2 times and go back to the main folder.
Input: logs = ["d1/","d2/","./","d3/","../","d31/"]
Output: 3
Input: logs = ["d1/","../","../","../"]
Output: 0
This is fairly simple problem. The only complexity in this problem is that for ../
. If you are in the main folder, and you do a ../
, you should remain in the same folder.
If you see, the problem is asking you to calculate how far you have gone, or the distance. Because, that is how many steps you will require to come back to original main folder.
Lets try to calculate the distance from the main folder.
./
, Just keep the counter as it is../
, you need to check if you are in the current folder or not. If you are in the current folder, your distance
counter will be zero. So if its zero, do nothing else decrement the counterabc/
, just increment the counter.Lets look at the code
public int minOperations(String[] logs) {
int distance = 0;
for (int i=0; i<logs.length; i++) {
if (logs[i].equals("./")) {
continue;
}
else if (logs[i].equals("../")) {
if (distance == 0) {
//do nothing
continue;
}
else {
distance --;
}
}
else {
// folder/
distance ++;
}
}
return distance;
}
Its simple O(n)
where n is the length of array
Your runtime beats 100% of java submissions. Memory usage beats 80% of java submissions.
Graph Topological Sorting This is a well known problem in graph world…
Problem Statement There are two sorted arrays nums1 and nums2 of size m and n…
Problem Statement Given a linked list, swap every two adjacent nodes and return…
Problem Statement Given an array of integers, find if the array contains any…
This is kind of preliminary technique of sorting. And, this is the first…
Problem Statement The string “PAYPALISHIRING” is written in a zigzag pattern on…
In this post, we will see some of the frequently used concepts/vocabulary in…
System design interview is pretty common these days, specially if you are having…
Introduction You are given an array of integers with size N, and a number K…
Graph Topological Sorting This is a well known problem in graph world…
Problem Statement Given a Binary tree, print out nodes in level order traversal…
Problem Statement Given an array nums of n integers and an integer target, are…