Just some programming questions of interview and test of HKU

hku-interview.py

# 给正整数N,分解成1和3的组合,比如N=4,分解为1111,13,31(递归)

N = 5
res = []

def helper(left, arr=[]):
    if left == 0: 
        res.append(arr)
        return
    if left < 0:
        return
    helper(left - 1, arr + [1])
    helper(left - 3, arr + [3])

helper(N)

for i in res:
    print(''.join([str(j) for j in i]))
    

hku-interview10.py

# 给一组数和一个数x，求一组数中哪三个数相乘结果为x，返回这三个数。可能有多个结果哦

N = 16
arr = [1, 3, 4, 2, 2, 4]

res = []

def helper(left, index = 0, current=[]):
    if left == 1 and len(current) == 3:
        res.append(current)
        return
    if left < 1:
        return
    
    for i in range(len(arr)):
        if i <= index: continue
        helper(left / arr[i], i, current + [arr[i]])

helper(N)
print(res)

hku-interview2.py

# 给个正整数N,判断是否有7位并且第4位是0
N = 423450789

# 1
def judge1(n):
    n = str(n)
    return len(n) >= 7 and n[-4] == '0'

def judge2(n):
    return n // 10**6 >= 1 and (n // 1000) % 10 == 0

f1 = judge1(N)
f2 = judge2(N)
print(f1, f2)

hku-interview3.py

#找出数组的最大和次大值
from heapq import heappush, heappop

arr = [89, 19203, 1, 3, 35671, 423, 42, 66, 3289, 11111, 0, 11]

def find_max1(arr):
    h = []
    for i in arr:
        heappush(h, -i)
    return -heappop(h), -heappop(h)


def find_max2(arr):
    m1 = max(arr)
    arr.remove(m1)
    m2 = max(arr)
    return m1, m2

f1 = find_max1(arr)
f2 = find_max2(arr)
print(f1, f2)

hku-interview4.py

# N级台阶，每次可以上一步或两步，返回可能的所有方法的个数（考虑顺序）。

N  = 20
res = [0] * (N + 1)

for i in range(N+1):
    if i == 0: 
        res[0] = 0
    elif i == 1:
        res[1] = 1
    else: 
        res[i] = res[i - 1] + res[i - 2]

print(res[N])
  

hku-interview5.py

# gcd, egcd

vals = (24, 16)

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a%b)

def egcd(a, b):
    if b == 0:
        return 1, 0
    x2, y2 = egcd(b, a%b)
    return y2, x2 - (a/b)*y2

print(gcd(*vals))
print(egcd(*vals))

hku-interview6.py

# 给定一个集合和一个数N，让集合的子集中的元素和为N
# Leetcode: https://leetcode.com/problems/combination-sum/submissions/
"""
Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

The same repeated number may be chosen from candidates unlimited number of times.

Note:

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

Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
  [7],
  [2,2,3]
]
Example 2:

Input: candidates = [2,3,5], target = 8,
A solution set is:
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]
"""

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        res = []
        candidates.sort()
        def helper(left, current_val=float('-inf'), arr=[]):
            if left == 0:
                res.append(arr)
                return
            if left < 0:
                return
            
            for val in candidates:
                if val >= current_val:
                    helper(left - val, val, arr+[val])
        helper(target)
        return res

hku-interview7.py

# 无序数组，返回乘积最大的三个数。
# Leetcode: https://leetcode.com/problems/maximum-product-of-three-numbers/

class Solution:
    def maximumProduct(self, nums: List[int]) -> int:
        min1 = min2 = float('inf')
        max1 = max2 = max3 = float('-inf')
        
        for val in nums:
            if val < min1:
                min2 = min1
                min1 = val
            elif val < min2:
                min2 = val
            
            if val > max1:
                max3 = max2
                max2 = max1
                max1 = val
            elif val > max2:
                max3 = max2
                max2 = val
            elif val > max3:
                max3 = val
        return max(min1 * min2 * max1, max1 * max2 * max3)

hku-interview8.py

# bubble sort

arr = [312893, 12, 6, 123, 0, -213, 4, 742, -3, 13, 777, 12356, 4234]


def bubble(arr):
    n = len(arr)
    for i in range(n):
        for j in range(n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]


bubble(arr)

hku-interview9.py

# Two sort algorithms

arr = []


def reset_arr():
    global arr
    arr = [312893, 12, 6, 123, 0, -213, 4, 742, -3, 13, 777, 12356, 4234]


# bubble sort
def bubble(arr):
    n = len(arr)
    for i in range(n):
        for j in range(n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]


# quick sort
def quick(arr, l, r):
    i, j = l, l+1
    if l >= r:
        return
    k = arr[l]
    while j <= r:
        if arr[j] < k:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
        j += 1
    arr[l], arr[i] = arr[i], k
    quick(arr, i+1, r)
    quick(arr, l, i-1)


reset_arr()
bubble(arr)
reset_arr()
quick(arr, 0, len(arr) - 1)

For HKU interview9: You have to use natural language(English) to describe your sort algorithm.