Monthly Archives: September 2021

python coding question

String Calculator

String Calculator without parenthesis

def calculate(s):
    return helper(s)

def helper(s, index):
    ops = {"+", "-", "/", "*", "#"}
    sign = '+'
    num = 0
    stack = []
    i = index
    s = s + "#"
    while i < len(s):
        if s[i].isdigit():
            num = num*10 + int(s[i])
        if s[i] in ops:

            if sign == "+":
                stack.append(num)
            elif sign == '-':
                stack.append(-num)
            elif sign == "*":
                tmp = stack.pop()
                print(tmp, num, tmp * num)
                stack.append(tmp*num)
            elif sign == "/":
                tmp = stack.pop()
                stack.append(tmp // num)
            sign = s[i]
            # mistake
            num = 0
        i += 1
    return sum(stack)

String Calculator with parenthesis

def calculate(s):
    s = s + "#"
    _, _sum = helper(s, 0)
    return _sum

def helper(s, i):
    stack = []
    sign = "+"
    num = 0
    while i < len(s):
        if s[i] == " ":
            pass
        elif s[i].isdigit():
            num = num*10 + int(s[i])
        elif s[i] == "(":
            i, num = helper(s, i + 1)
        else:
            if sign == "+":
                stack.append(num)
            elif sign == "-":
                stack.append(-num)
            elif sign == "*":
                prev = stack.pop()
                stack.append(prev * num)
            elif sign == "/":
                prev = stack.pop()
                stack.append(prev / num)
            if s[i] == ")":
                return i, sum(stack)
            sign = s[i]
            num = 0
        i += 1
    return i, sum(stack)
python coding question

Leetcode 388. Longest Absolute File Path

Recursion Problem

Time Complexity: O(N) N is number of words in input

def lengthLongestPath(input):
    filepathes = []
    path = []
    foo(input.split("\n"), 0, path, filepathes)
    if len(filepathes) == 0:
        return 0
    lens = map(lambda path: len(path), filepathes)
    print(filepathes)
    return max(lens)

def foo(arr, index, path, filepathes):
    if len(arr) == index:
        return
    depth = arr[index].count("\t")
    dirname = arr[index].strip("\t")
    if path:
        rootpath = path[:depth]
    else:
        rootpath = []

    if arr[index].find(".") != -1:
        filename = arr[index].strip("\t")
        rootpath.append(filename)
        filepathes.append('/'.join(rootpath))
        rootpath.pop()
        foo(arr, index + 1, rootpath, filepathes)
        #return

    else:
        rootpath.append(dirname)
        foo(arr, index + 1, rootpath, filepathes)

input = "dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext" # 20
print(lengthLongestPath(input))

input = "dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext" # 32
print(lengthLongestPath(input))

input = "file1.txt\nfile2.txt\nlongfile.txt" # 12
print(lengthLongestPath(input))

input ="dir\n        file.txt"
print(lengthLongestPath(input)) # 16