Solutions to 5 problems every software engineer should be able to solve (in less than 1 hour)

solutions_to_5_sw_problems.py

import re

# Problem 1
# ---------
# Write three functions that compute the sum of the numbers in a given list
# using a for-loop, a while-loop, and recursion.

input_1 = [1, 2, 3, 4, 5] #15
def p1_for(lst):
    c = 0
    for n in lst:
        c += n
    return c

def p1_while(lst):
    c = 0
    i = 0
    while (i < len(lst)):
        c += lst[i]
        i += 1
    return c

def p1_recur(lst, acc):
    if not lst:
        return acc
    else:
        head = lst[0]
        return p1_recur(lst[1:], acc + head)

print(p1_for(input_1,))
print(p1_while(input_1))
print(p1_recur(input_1, 0))

# Problem 2
# ---------
# Write a function that combines two lists by alternatingly taking elements.
# For example: given the two lists [a, b, c] and [1, 2, 3], the function
# should return [a, 1, b, 2, c, 3]

input_2_a =['a', 'b', 'c']
input_2_b =[1, 2, 3]

def merge(l1, l2):
    res = []
    for i in range(max(len(l1), len(l2))):
        if i < len(l1):
            res.append(l1[i])
        if i < len(l2):
            res.append(l2[i])
    return res

print(merge(input_2_a, input_2_b))

# Problem 3
# ---------
# Write a function that computes the list of the first 100 Fibonacci numbers.
# By definition, the first two numbers in the Fibonacci sequence are 0 and 1,
# and each subsequent number is the sum of the previous two. As an example,
# here are the first 10 Fibonnaci numbers: 0, 1, 1, 2, 3, 5, 8, 13, 21, and 34.

def fib(n):
    dp = [0] * n
    dp[0] = 0
    dp[1] = 1
    for i in range(2, n):
        dp[i] = dp[i-2] + dp[i-1]
    return dp

def fib_recur(n):
    acc = [-1] * (n + 1)
    def recur(n):
        if n < 2:
            acc[n] = n
            return acc[n]

        acc[n] = recur(n-1) + recur(n-2)
        return acc[n]
    recur(n)
    return acc

def fib_recur_memo(n):
    acc = [-1] * (n + 1)
    def recur(n, memo = {}):
        if n in memo:
            return memo[n]
        if n < 2:
            acc[n] = n
            memo[n] = n
            return acc[n]
        acc[n] = recur(n-1, memo) + recur(n-2, memo)
        memo[n] = acc[n]
        return acc[n]
    recur(n)
    return acc

#print(fib(100))
#print(fib_recur(100)) takes long
#print(fib_recur_memo(100))

# Problem 4
# ---------
# Write a function that given a list of non negative integers, arranges them
# such that they form the largest possible number. For example, given
# [50, 2, 1, 9], the largest formed number is 95021.

input_4 = [50, 2, 1, 9]

def largest_possible(lst):
    for i in range(len(lst)):
        lst[i] = str(lst[i])
    res = sorted(lst, reverse=True)
    for i in range(len(res)):
        res[i] = int(res[i])
    return res

print(largest_possible(input_4))

# Problem 5
# ---------
# Write a program that outputs all possibilities to put + or - or nothing
# between the numbers 1, 2, ..., 9 (in this order) such that the result is
# always 100. For example: 1 + 2 + 34 – 5 + 67 – 8 + 9 = 100.

def string_sum(s):
    if not s:
        return 0
    operators = re.findall(r"\+|\-", s)
    numbers = re.findall(r'\d+', s)
    sum = int(numbers[0])
    numbers = numbers[1:]
    zipped = zip(operators, numbers)
    for z in zipped:
        (o, n) = z
        if o == '+':
            sum += int(n)
        else:
            sum -= int(n)
    return sum

input_5 = [1,2,3,4,5,6,7,8,9]

def p5(s, target):
    def recur(s, target, soFar):
        sum = string_sum(soFar)
        result = []
        if not s:
            if sum == target:
                return [soFar]
            else:
                return result

        digit = str(s[0]) #head
        tail = s[1:]
        result += recur(tail, target, soFar + "+" + digit)
        result += recur(tail, target, soFar + "-" + digit)
        result += recur(tail, target, soFar + digit)

        return result

    return recur(s[1:], target, str(s[0]))

result = p5(input_5, target = 100)
print(len(result))