Last active
June 28, 2024 08:40
-
-
Save dcalsky/3427f127efd9ea846e2ec5002b778531 to your computer and use it in GitHub Desktop.
Just some programming questions of interview and test of HKU
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# 给正整数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])) | |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# 给一组数和一个数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) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# 给个正整数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) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#找出数组的最大和次大值 | |
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) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# 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]) | |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# 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)) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# 给定一个集合和一个数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 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# 无序数组,返回乘积最大的三个数。 | |
# 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) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# 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) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# 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) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
For
HKU interview9
: You have to use natural language(English) to describe your sort algorithm.