針對面試中常見的Python技巧做練習並記錄相關延伸知識。

演算法

氣泡排序法

請用氣泡排序法(Bubble sort)將數列由小到大排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def bubble_sort(seq):
    # Time complexity: O(n^2)
    # Space complexity: O(1)
    size = len(seq)
    if size <= 1:
        return seq

    i, j = 0, 0
    while i < size:
        j = i + 1
        while j < size:
            if seq[i] > seq[j]:
                seq[i], seq[j] = seq[j], seq[i]  # swap(n, n+1)
            j += 1
        i += 1

    return seq


assert bubble_sort([]) == []
assert bubble_sort([1]) == [1]
assert bubble_sort([2, 1]) == [1, 2]
assert bubble_sort([5, 1, 3, 2, 4]) == [1, 2, 3, 4, 5]

快速排序法

Write your quick sort code here.
請用快速排序法(Quick sort)將數列由小到大排序。
圖示演算法流程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def quick_sort(sequence):
    # Time complexity: O(nlogn)
    # Space complexity: O(n)
    if len(sequence) <= 1:
        return sequence

    pivot = sequence[0]
    left = []
    right = []
    for i in sequence[1:]:
        if i < pivot:
            left.append(i)
        else:
            right.append(i)

    return quick_sort(left) + [pivot] + quick_sort(right)


assert quick_sort([]) == []
assert quick_sort([1]) == [1]
assert quick_sort([2, 1]) == [1, 2]
assert quick_sort([5, 1, 3, 2, 4]) == [1, 2, 3, 4, 5]

合併排序法

Write your merge sort code here.
請用合併排序法(Merge sort)將數列由小到大排序。
圖示演算法流程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def merge_sort(sequence):
    # Time complexity: O(nlogn)
    # Space complexity: O(n)
    if len(sequence) <= 1:
        return sequence

    mid = len(sequence) // 2
    left = merge_sort(sequence[:mid])
    right = merge_sort(sequence[mid:])

    return merge_sort(left, right)


assert merge_sort([]) == []
assert merge_sort([1]) == [1]
assert merge_sort([2, 1]) == [1, 2]
assert merge_sort([5, 1, 3, 2, 4]) == [1, 2, 3, 4, 5]

找出數列中第二大的數字

Find second largest number in a list.
找出數列中第二大的數字。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def find_second_largest(sequence):
    # Time complexity: O(n)
    # Space complexity: O(1)
    first, second = 0, 0
    for i in sequence:
        if i in (first, second):
            continue

        if i > second:
            second = i

        if second > first:
            first, second = second, first

    return second


assert find_second_largest([3]) == 0
assert find_second_largest([3, 3, 2, 1]) == 2
assert find_second_largest([3, 3, 3, 3, 3, 2, 2, 1]) == 2
assert find_second_largest([-1, 2, 3, 5, 3, 1, 2, 4]) == 4

找出Target的兩個數字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
def two_sum(nums, target):
    """
    思路:
    假設 nums = [2, 7, 11, 15], target = 13 => x+y = target
    1. 逐一檢查 nums 中的元素 x, 並檢查 target-x 是否在 dict 中
       loop 1: nums[i] = nums[0] = x = 2 , target-x = 13 - 2  = 11, 11 not in dict => False, dict = {2: 0}
       loop 2: nums[i] = nums[1] = x = 7 , target-x = 13 - 7  = 6 , 6 not in dict  => False, dict = {2: 0, 7: 1}
       loop 3: nums[i] = nums[2] = x = 11, target-x = 13 - 11 = 2 , 2 in dict      => True,
               => return [dict[target - nums[i]], i]
               => return [dict[target - nums[2]], 2]
               => return [dict[13-11], 2]
               => return [dict[2], 2]
               => return [0, 2]
    """
    # Time complexity: O(n)
    # Space complexity: O(n)
    dict_ = {}
    for i in range(len(nums)):
        if target - nums[i] in dict_:
            return [dict_[target - nums[i]], i]
        elif target == nums[i]:
            return [i]
        else:
            dict_[nums[i]] = i

    return []


assert two_sum([2, 7, 11, 15], target=13) == [0, 2]
assert two_sum([2, 7, 11, 15], target=15) == [3]
assert two_sum([2, 7, 11, 15], target=20) == []


Python技巧

技巧一

請繼承Rectangle類別改寫成Square類別，請使用最小改動方式進行實作。

1
2
3
4
5
6
7
8
9
10
11
# 題目
class Rectangle(object):
    def __init__(self, width, height):
        self.width = width
        self.height = height

    def area(self):
        return self.width * self.height

    def perimeter(self):
        return 2 * self.width + 2 * self.height
1
2
3
4
5
6
7
8
9
10
# 作答
class Square(Rectangle):
    # Write your inheritance code here.
    def __init__(self, width):
        super().__init__(width, width)


square = Square(10)
assert square.area() == 100
assert square.perimeter() == 40

技巧二

Write some examples with *args, **kwargs here.
請嘗試使用 *args, **kwargs實作一個函式。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def calculate(*args, **kwargs):
    # kwargs: keyword arguments
    result = 0
    exp = kwargs.get('exp', '+')

    for idx, val in enumerate(args):
        if idx == 0:
            result = val
        elif exp == '+':
            result += val
        elif exp == '-':
            result -= val
        elif exp == '*':
            result *= val
        elif exp == '/':
            result = round(result / val, 2)

    return result


assert calculate(4, 3, 2, 1, exp='*') == 24
assert calculate(4, 3, 2, 1, exp='+') == 10
assert calculate(4, 3, 2, 1) == 10
assert calculate(4, 3, 2, 1, exp='-') == -2
assert calculate(4.0, 3.0, 2.0, 1.0, exp='/') == 0.67
assert calculate(100, 10, 2, 1, exp='/') == 5

技巧三

Write some examples using python lambda here.
請嘗試使用lambda實作一個函式。

1
2
swap = lambda x, y: (y, x)
assert swap(1, 2) == (2, 1)

技巧四

Write some examples using python comprehension here.
請嘗試使用comprehension實作一個函式。

1
2
3
4
5
6
# Python comprehension:
# List Comprehension: [i for i in range(10)]
# Set & Dictionary Comprehension: {i: i for i in range(10)}
# Generator Comprehension: (i for i in range(10))
square = lambda x: x * x
assert [square(i) for i in (1, 2, 3, 4, 6) if not i % 2] == [4, 16, 36]

技巧五

Write some examples using python decorator here.
請嘗試使用decorator實作一個函式。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def skill(skill_name=None):
    def decorator(func):
        def wrapper():
            skills = func()
            skills.append(skill_name)
            return skills

        return wrapper

    return decorator


@skill('swift.')
@skill('kotlin,')
@skill('python,')
def i_have_skills():
    return ["My skills have:"]


print(" ".join(i_have_skills()))
# Output: My skills have: python, kotlin, swift.

技巧六

Write some examples using python generator here.
請嘗試使用generator實作一個函式。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
# Explain the benefit of generators:
# 1. Save memory: 
#    - Only generate the next value when needed.
#    - 不用一次性產生所有的數據，而是一次產生一個，這樣就不會有內存溢出的問題。
# 2. Lazy evaluation:
#    - only evaluate when needed.

tasks = [
    'task A',
    'task B',
    'task C',
]


def pop_tasks():
    for task in tasks:
        print(f'pop task: {task}')
        yield task


print("===Example 1===")
for task in pop_tasks():
    print(f'{task} is done.')

print()
print("===Example 2===")
print(">pop task and add new task at the same time.")
for idx, task in enumerate(pop_tasks()):
    print(f'idx:{idx}, {task} is done.')
    if idx < 5:
        print(f'add new task {idx}')
        tasks.append(f'task {idx}')

# Output:
# ===Example 1===
# pop task: task A
# task A is done.
# pop task: task B
# task B is done.
# pop task: task C
# task C is done.
# 
# ===Example 2===
# >pop task and add new task at the same time.
# pop task: task A
# idx:0, task A is done.
# add new task 0
# pop task: task B
# idx:1, task B is done.
# add new task 1
# pop task: task C
# idx:2, task C is done.
# add new task 2
# pop task: task 0
# idx:3, task 0 is done.
# add new task 3
# pop task: task 1
# idx:4, task 1 is done.
# add new task 4
# pop task: task 2
# idx:5, task 2 is done.
# pop task: task 3
# idx:6, task 3 is done.
# pop task: task 4
# idx:7, task 4 is done.

技巧七

Write some examples using python context manager here.
請嘗試使用context manager實作一個函式。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# Explain the benefit of context manager:
# 常用於某種資源需開啟並關閉動作，例如open('file.txt')檔案，常常忘記呼叫file.close()導致文本被鎖，使用context manager可以自動關閉資源。

class ContextManager:
    def __init__(self):
        print('1->init method called')

    def __enter__(self):
        # 當進入with區塊時，會自動調用__enter__方法
        print('2->enter method called')
        return self

    def __exit__(self, exc_type, exc_value, exc_traceback):
        # 當離開with區塊時，會自動調用__exit__方法
        print('4->exit method called')


with ContextManager() as manager:
    print('3->with statement block')

# Output:
# 1->init method called
# 2->enter method called
# 3->with statement block
# 4->exit method called

技巧八

Write some examples using python magic methods here.
請嘗試使用magic methods實作一個函式。
更多Magic Methods的使用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class MagicExample(object):
    def __init__(self, value):
        self.value = value

    def __str__(self):
        # 常用於顯示 django model object
        return f'__str__:{self.value}'

    def __add__(self, other):
        return f'__add__:{self.value + other}'

    def __sub__(self, other):
        return f'__sub__:{self.value - other}'

    def __mul__(self, other):
        return f'__mul__:{self.value * other}'

    def __truediv__(self, other):
        return f'__truediv__:{self.value / other}'

    def __floordiv__(self, other):
        return f'__floordiv__:{self.value // other}'


magic = MagicExample(100)
print(magic)
print(magic + 100)
print(magic - 100)
print(magic * 100)
print(magic / 80)  # 取餘數保留小數點
print(magic // 50)  # 取餘數去除小數點

# Output:
# __str__:100
# __add__:200
# __sub__:0
# __mul__:10000
# __truediv__:1.25
# __floordiv__:2

Keyword

1
2
3
4
演算法, Algorithm, al - go - rithm
技巧, Skill, skill
練習, Practice, pra - ct - ice
延伸知識, Knowledge, knowl - edge
1