Crawler Log Folder - codepath/compsci_guides GitHub Wiki

• 🔗 Leetcode Link: Crawler Log Folder
• 💡 Problem Difficulty: Easy
• ⏰ Time to complete: 15 mins
• 🛠️ Topics: Recursion
• 🗒️ Similar Questions: Valid Palindrome, Shortest Distance to a Character, Check Distances Between Same Letters

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Established a set (2-3) of test cases to verify their own solution later.
• Established a set (1-2) of edge cases to verify their solution handles complexities.
• Have fully understood the problem and have no clarifying questions.
• Have you verified any Time/Space Constraints for this problem?

Be sure that you clarify the input and output parameters of the problem:

• How should I handle an empty log file?
  • All log files will have at least one input
• What are the time and space constraints?
  • Time should be O(N) and space should be O(1) including the recursive stack, N being the length of the logs

Run through a set of example cases:

HAPPY CASE
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

EDGE CASE 
Input: logs = ["../"]
Output: 0

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

• Sort
  • Not helpful, we need to maintain the relative order of the logs
• Two pointer solutions (left and right pointer variables)
  • Not helpful, we need to move in one direction
• Storing the elements of the array in a HashMap or a Set
  • Not helpful, how does the hashmap help us find the distance between characters
• Traversing the array with a sliding window
  • Not helpful, we are not looking for a window size
• Stack
  • When dealing with file system traversal, stack is a good choice

Plan the solution with appropriate visualizations and pseudocode.

General Idea: We will recursively find the depth of the file traversal logs and that will be the minimum operations to return to root.

1. Write a recursive function to drill into the file system.
    a. Set the basecase: Out of bound.
    b. Update depth base on log function string
    c. Call recursive function on next log item
2. Call the recursive function 
3. Return the result.

General Idea: We will iteratively find the depth of the file traversal logs and that will be the minimum operations to return to root.

1. Create a stack
2. Add/Remove items from stack 
3. Return the size of stack.

⚠️ Common Mistakes

• Using iterative approach will work here, however the interviewer wants the recursive solution.

Implement the code to solve the algorithm.

Recursive

class Solution:
    def minOperations(self, logs: List[str]) -> int:
      depth = 0
      # Write a recursive function to drill into the file system
      def helper(i):
        # Set the basecase: Out of bound
        if i > len(logs) - 1:
          return 

        # Update depth base on log function string
        nonlocal depth
        if logs[i] == "../":
          if depth > 0:
            depth -= 1
        elif logs[i] == "./":
          pass
        else:
          depth  += 1
        
        # Call recursive function on next log item
        helper(i + 1)

      # Call the recursive function 
      helper(0)

      # Return the result
      return depth

class Solution {
  int depth = 0;
  public int minOperations(String[] logs) {
    // Call the recursive function 
    helper(logs, 0);
    // Return the result
    return depth;
  }
  // Write a recursive function to drill into the file system
  private void helper(String[] logs, int i) {
    // Set the basecase: Out of bound
    if (i > logs.length - 1) return;

    // Update depth base on log function string
    if (logs[i].equals("../")) {
      if (depth > 0) {
        depth--;
      }
    } else if (logs[i].equals("./")) {
      ;
    } else {
      depth++;
    }

    // Call recursive function on next log item
    helper(logs, i+1);
  }
}

Iterative

class Solution:
  def minOperations(self, logs: List[str]) -> int:
    # Create a stack
    stack = []

    # Add/Remove items from stack
    for log in logs:
      if log == "../":
        if stack:
          stack.pop()
      elif log == "./":
        continue
      else:
        stack.append(log)
    
    # Return the size of stack
    return len(stack)

class Solution {
  public int minOperations(String[] logs) {
    // Create a stack
    var stack = new Stack<String>();
    //Add/Remove items from stack
    for(var log : logs){
      if(log.equals("../")){
          if(!stack.empty())
              stack.pop();
      }else if(log.equals("./")){

      }else{
          stack.push(log);
      }
    }
    // Return the size of stack.
    return stack.size();
  }
}

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

• Trace through your code with an input to check for the expected output
• Catch possible edge cases and off-by-one errors

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume N represents the size of array

• Time Complexity: O(N) because we will run the algorithm once to process all logged commands
• Space Complexity: O(1) because the recusive call does not need to be stored in memory. Technically this called Tail recursion, a recursion of a function where it does not consumes stack space and hence prevents stack overflow.