[Leetcode] 388. Longest Absolute File Path

Suppose we abstract our file system by a string in the following manner:

The string "dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext" represents:

dir
    subdir1
    subdir2
        file.ext

The directory dir contains an empty sub-directory subdir1 and a sub-directory subdir2 containing a file file.ext.

The string "dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext" represents:

dir
    subdir1
        file1.ext
        subsubdir1
    subdir2
        subsubdir2
            file2.ext

The directory dir contains two sub-directories subdir1 and subdir2. subdir1 contains a file file1.ext and an empty second-level sub-directory subsubdir1. subdir2 contains a second-level sub-directory subsubdir2 containing a file file2.ext.

We are interested in finding the longest (number of characters) absolute path to a file within our file system. For example, in the second example above, the longest absolute path is "dir/subdir2/subsubdir2/file2.ext", and its length is 32 (not including the double quotes).

Given a string representing the file system in the above format, return the length of the longest absolute path to file in the abstracted file system. If there is no file in the system, return 0.

Note:

• The name of a file contains at least a . and an extension.
• The name of a directory or sub-directory will not contain a ..

Time complexity required: O(n) where n is the size of the input string.

Notice that a/aa/aaa/file1.txt is not the longest file path, if there is another path aaaaaaaaaaaaaaaaaaaaa/sth.png.

---

I solved this problem about 7 months ago - when I first started to tackle these Leetcode problems. Back then, I wasn't proficient in any algorithms. But somehow, I managed to solve this problem with an extremely messy code. Ever since I got that job offer, I thought I should re-do some of the problems or focus those problems that require some modeling (i.e., Google problems).

This problem is on the easier side of this kind. It is very obvious files and folders are organized in tree structure. Only if we have a well-organized tree structure, then we can basically use backtracking to find out the answers. However, the input is a string. But, by looking at the string, we can see that the number of '\t' in the element is the same as the level of that elements. For example, '\tsubdir1', '\t\tfile.txt' are in the first, second level of the file organization, respectively.

We can't easily do a tree traverse on this type of string input, but hey, the elements order after input.split('\n') is similar to the  in-order traversal of the directory tree (here might be a forest).

Therefore, the abstraction of the problem will be:

Given the in-order traversal of a tree and each element's level, reconstruct the maximum length path from root to leaf where we only considers those leaves that contain '.' (file). 

Well, then we just use a stack, when the level is higher than the current level, meaning that the incoming element will be the children of current element; when lower, meaning that the incoming one is the parent; the same, siblings.

class Solution(object):
    def lengthLongestPath(self, input):
        """
        :type input: str
        :rtype: int
        """
        stack = []
        current_level = 0
        res = 0
        for name in input.split('\n'):
            #print stack, current_level
            tabs = name.split('\t')
            if len(tabs) - 1 == current_level:
                if stack:
                    stack.pop()
                stack.append(tabs[-1])
            elif len(tabs) -1 > current_level:
                stack.append(tabs[-1])
            else:
                for _ in range(current_level - len(tabs) + 2):
                    if stack: stack.pop()
                stack.append(tabs[-1])
            if '.' in tabs[-1]:
                res = max(res, len('/'.join(stack)))
            current_level = len(tabs) - 1
        return res

[Leetcode] Course Schedule

This is a classical graph problem - the key is to detect cycle in a directed graph. This is usually done by flagging a node by 0, 1, 2, where 0 represents never visited, 1 in the stack, 2 visited. If at any time, we visited a node which status is 1, that it is in stack yet we visited it again, then it means that there is a cycle.

There are a total of n courses you have to take, labeled from 0 to n - 1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

For example:

2, [[1,0]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.

2, [[1,0],[0,1]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

Code: 

class Solution(object):
    def canFinish(self, numCourses, prerequisites):
        """
        :type numCourses: int
        :type prerequisites: List[List[int]]
        :rtype: bool
        """
        g = [[] for _ in range(numCourses)]
        for a, b in prerequisites:
            g[b].append(a)
            
        visited = [0 for _ in range(numCourses)]
        
        def dfs(node, visited):
            visited[node] = 1
            for v in g[node]:
                if visited[v] == 1:
                    return False
                elif visited[v] == 0:
                    if not dfs(v, visited):
                        return False
            visited[node] = 2
            return True
            
        for i in range(numCourses):
            if visited[i] == 0:
                if not dfs(i, visited):
                    return False
        return True

[Leetcode] Combination sum II

Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

Each number in C may only be used once in the combination.

Note:

• All numbers (including target) will be positive integers.
• The solution set must not contain duplicate combinations.

For example, given candidate set [10, 1, 2, 7, 6, 1, 5] and target 8,
A solution set is: 

[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]

This is not a hard problem - it's quite standard to think a recursion solution. However, the recursion solution sometimes doesn't work as I expected - it turns out the "exit" condition is quite important.

One little aspect: when there is repeated elements and order doesn't matter, sort always helps to remove the duplicates.

class Solution(object):
    def combinationSum2(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        res = []
        candidates.sort()
        res = self.helper(candidates, target)
        return res
    
    def helper(self, candidates, target):
        if len(candidates) == 0: return []
        output = []
        for i, can in enumerate(candidates):
            if can > target: continue
            if i > 0 and can == candidates[i-1]: continue
            tmp_res = self.helper(candidates[i+1: ], target-can)
            if len(tmp_res) > 0:
                for tr in tmp_res:
                    output.append(tr+[can])
            if len(tmp_res) == 0: # important to determine if there is a solution or not
                if can == target:
                    output.append([can])
        return output

[CodeFights] ClimbingStaircase

You need to climb a staircase that has n steps, and you decide to get some extra exercise by jumping up the steps. You can cover at most k steps in a single jump. Return all the possible sequences of jumps that you could take to climb the staircase, sorted.

Example

For n = 4 and k = 2, the output should be

climbingStaircase(n, k) =
[[1, 1, 1, 1],
 [1, 1, 2],
 [1, 2, 1],
 [2, 1, 1],
 [2, 2]]

There are 4 steps in the staircase, and you can jump up 2 or fewer steps at a time. There are 5 potential sequences in which you jump up the stairs either 2 or 1 at a time.

This problem is in the section of backtracking. It's very straightforward regarding to the "tree"-construction: we start from step 1 (which is the root), and each parent has k children, which represent 1, 2, ..., k steps. 

To me, I always want to practice the framework of doing backtrack. It should be straightforward, but somehow I got confused of how to frame the program. But I think this one is good:

def climbingStaircase(n, k):
    output = []
    steps = []
    helper(output, steps, k, n)
    return output
        
def helper(output, steps, k, left):
    if left == 0:
        output.append(list(steps)) # notice hard copy here
    else:
        for i in range(1, k+1):
            if i <= left:
                steps.append(i)
                helper(output, steps, k, left-i)
                steps.pop()