Python cho người Việt

Python cho người Việt

Phỏng vấn: Sắp xếp lắc lư

written by Nguyễn Thành Nam, on May 5, 2015 7:05:39 AM.

Câu hỏi

Cho một mảng A các số nguyên a[i], tìm cách sắp xếp mảng sao cho phần tử thứ nhất nhỏ hơn phần tử thứ hai, phần tử thứ hai lớn hơn phần tử thứ ba, phần tử thứ ba nhỏ hơn phần tử thứ tư v.v... Tức là:

  a[0] <= a[1] >= a[2] <= a[3] >= a[4] ...

Ta gọi một mảng có thứ tự như vậy là một mảng đã được sắp xếp lắc lư (wiggly sorted).

Phân tích

Ta nhận xét rằng yêu cầu thứ tự chỉ áp dụng vào hai phần tử lân cận của phần tử đang xét. Ví dụ, phần tử a[1] chỉ cần lớn hơn hai phần tử a[0]a[2], ngoài ra không còn quan hệ với phần tử nào nữa. Điều đó dẫn đến ý tưởng giải sẽ rất có thể ở dạng tham ăn (greedy algorithm).

Giả sử như ta đã có mảng A' có độ dài 2n (chẵn) thỏa mãn điều kiện. Phần tử kế tiếp (2n + 1) vì ở vị trí lẻ nên sẽ phải nhỏ hơn phần tử cuối cùng trong mảng, đồng thời cũng phải đảm bảo nhỏ hơn phần tử sau đó (2n + 2). Vì ta không biết phần tử (2n + 2) sẽ có giá trị bao nhiêu nên cách an toàn nhất để thỏa mãn hai điều kiện cho phần tử 2n + 1 là chọn phần tử nhỏ nhất trong số các phần tử còn lại của A.

Lập luận tương tự cho thấy rằng phần tử ở vị trí chẵn nên có giá trị lớn nhất trong số các phần tử còn lại.

Tóm lại, cách giải câu hỏi này sẽ bao gồm hai bước chính:

  1. Sắp xếp mảng A theo thứ tự tăng dần.
  2. Lần lượt gán a[0] = min(A), và a[1] = max(A[1 : ]), và a[2] = min(A[2 : ]), v.v...

Dĩ nhiên là ta không cần gọi min hay max mà chỉ cần giữ hai biến chỉ mục từ đầu, và cuối mảng A để tìm ngay giá trị cực tiểu hay cực đại vì A đã được sắp xếp ở bước đầu tiên.

Độ phức tạp thực thi của cách giải này phụ thuộc vào thuộc toán sắp xếp sử dụng ở bước đầu tiên.

Vấn đề cài đặt cách giải xin được để lại cho bạn đọc. Diễn đàn là nơi tốt nhất để trao đổi về các yếu tố liên quan đến cài đặt.

Tổng kết

Qua loạt bài Phỏng vấn, tác giả hy vọng rằng bạn đọc nhận ra được sự quan trọng của bộ kiến thức nền tảng, đặc biệt là các cấu trúc dữ liệu phổ biến. Từ các kiến thức nền tảng này, chúng ta có thể giải quyết được rất nhiều những vấn đề khác.

Python cùng với phương châm kèm cả pin đem đến cho chúng ta một loạt các cấu trúc dữ liệu qua các kiểu, hoặc mô-đun có sẵn. Python thật sự là một công cụ mạnh mẽ và hữu ích.

Phỏng vấn: Tìm 1 triệu số nhỏ nhất trong 1 tỷ số

written by Nguyễn Thành Nam, on Apr 30, 2015 11:56:00 AM.

Câu hỏi

Cho 1 tỷ số thực, tìm 1 triệu số nhỏ nhất trong 1 tỷ số đấy.

Phân tích

Cách giải đơn giản nhất là sắp xếp từ bé đến lớn 1 tỷ số đầu vào, sau đó chọn ra 1 triệu số đầu tiên. Độ phức tạp của cách giải này phụ thuộc vào độ phức tạp của thuật toán sắp xếp. Cách này có hai nhược điểm lớn: 1. là tốn bộ nhớ để chứa 1 tỷ số đầu vào để sắp xếp, 2. là nếu số lượng đầu vào không có giới hạn thì cách giải này không dùng được.

Giả sử ta chỉ có 1 triệu số đầu vào, thì rõ ràng kết quả sẽ chính là 1 triệu số đó. Khi có thêm 1 số mới, số mới này sẽ nằm trong kết quả nếu như nó nhỏ hơn số lớn nhất trong 1 triệu số kết quả hiện tại.

Với nhận xét đó, ta có cách giải thứ hai, tối ưu hơn cách đầu tiên. Ta sẽ tạo một max heap với 1 triệu phần tử. Với mỗi phần tử đầu vào, ta sẽ:

  1. Đưa vào heap nếu heap chưa có đủ 1 triệu số
  2. Nếu heap đã có đủ một triệu số thì lấy từ đỉnh heap ra (tức lấy phần tử lớn nhất trong heap) so sánh với phần tử đầu vào, và đưa lại vào heap phần tử nhỏ hơn trong phép so sánh đó.

Độ phức tạp thực thi của cách giải này là O(nlogn) nhưng chỉ tốn bộ nhớ tỷ lệ với số phần tử đầu ra.

Cài đặt

Ta có thể dùng mô-đun heapq có sẵn để trả lời câu hỏi này. Mô-đun này giúp ta quản lý một min heap. Tuy nhiên, vì ta cần max heap nên các giá trị đầu vào sẽ được đổi thành số bù 0 - x.

# encoding: utf-8
import heapq

def solve(inp, n=1000000):
    heap = []
    for i in inp:
        i = -i
        if len(heap) < n:
            heapq.heappush(heap, i)
        else:
            m = heap[0]
            if m < i:
                heapq.heapreplace(heap, i)
    return [-x for x in heap]

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

Mô-đun heapq cũng có sẵn hàm nsmallest để giải quyết câu hỏi này ;).

Phỏng vấn: Số nhân viên cấp dưới

written by Nguyễn Thành Nam, on Apr 10, 2015 11:56:00 AM.

Câu hỏi

Cho một từ điển từ chuỗi sang chuỗi, khoá là tên nhân viên, và giá trị là tên của người quản lý. Nhân viên cấp cao nhất báo cáo cho chính họ. Tìm số nhân viên cấp dưới của một nhân viên nào đó.

Ví dụ: Trong từ điển sau, A và B cùng báo cáo cho C, C và E báo cáo cho F, D báo cáo cho E, và F là nhân viên cấp cao nhất.

{
    "A": "C",
    "B": "C",
    "C": "F",
    "D": "E",
    "E": "F",
    "F": "F",
}

Số lượng nhân viên cấp dưới của A là 0, B là 0, C là 2, D là 0, E là 1, và F là 5.

Phân tích

Giả sử A là nhân viên cấp dưới của B, và B là nhân viên cấp dưới của C.

Cách nhìn trực tiếp từ trên xuống theo câu hỏi này là C có 2 nhân viên cấp dưới, và B có một nhân viên cấp dưới. Nếu nhìn ngược lại, ta sẽ nói rằng A "đội" B lên 1, đội tiếp C lên 1, và B đội C lên thêm 1. Tức là mỗi nhân viên sẽ đội tất cả các nhân viên cấp trên của họ lên 1 (A đội B và C, B đội C).

Do đó, cách giải câu hỏi này là duyệt hết các phần tử trong danh sách, với mỗi phần tử, lần lượt đội (cộng 1) vào kết quả của các nhân viên cấp trên của phần tử đấy.

Độ phức tạp thực thi là O(n^2) và tốn O(n) bộ nhớ.

Nếu bạn có cách giải tốt hơn xin hãy cùng chia sẻ tại diễn đàn.

Cài đặt

def solve(employees):
    subordinate_count = {}
    for emp, boss in employees.iteritems():
        if emp not in subordinate_count:
            subordinate_count[emp] = 0
        while emp != boss:
            try:
                subordinate_count[boss] += 1
            except KeyError:
                subordinate_count[boss] = 1
            emp, boss = boss, employees[boss]
    return subordinate_count

inp = {"A": "C", "B": "C", "C": "F", "D": "E", "E": "F", "F": "F"}
exp = {"A": 0, "B": 0, "C": 2, "D": 0, "E": 1, "F": 5}
assert(solve(inp) == exp)

Phỏng vấn: Cộng chuỗi ít tốn nhất

written by Nguyễn Thành Nam, on Mar 23, 2015 2:08:53 AM.

Câu hỏi

Cho n chuỗi, tìm cách cộng các chuỗi này lại theo một thứ tự nào đó sao cho ít tốn bộ nhớ nhất.

Ví dụ: Cho chuỗi A="abc", B=wxyz, C=g, và xét hai cách cộng chuỗi sau:

  1. Cộng AB trước, sau đó cộng với C. A + B sẽ tốn 3 + 4 = 7. Sau đó cộng thêm C sẽ tốn 7 + 1 = 8. Tổng cộng tốn 7 + 8 = 15.
  2. Cộng AC trước, sau đó cộng với B. A + C tốn 3 + 1 = 4. Sau đó cộng thêm B sẽ tốn 4 + 4 = 8. Tổng cộng tốn 4 + 8 = 12.

Cách cộng chuỗi thứ 2 đỡ tốn bộ nhớ hơn cách thứ 1, và cũng là cách tốn ít bộ nhớ nhất.

Phân tích

Việc cộng n chuỗi với nhau luôn luôn tốn n-1 phép cộng chuỗi, và tạo ra chuỗi cuối cùng với độ lớn không đổi. Do đó, lý do tốn bộ nhớ không phải là vì kết quả cuối cùng, mà là do các mảng nhớ tạm ta phải sử dụng để chứa kết quả của các phép cộng chuỗi này.

Xét ba chuỗi bất kỳ với độ lớn x <= y <= z. Ta cần thực hiện 2 phép cộng chuỗi, và độ lớn của chuỗi cuối cùng sẽ là tổng của x + y + z không đổi. Độ lớn của chuỗi tạm sẽ là tổng này trừ đi độ lớn của chuỗi gốc trong phép cộng chuỗi thứ 2. Dễ thấy rằng nếu ta để dành chuỗi có độ lớn z để cộng cuối cùng, thì độ lớn của chuỗi tạm sẽ là nhỏ nhất, x + y.

Do đó, ta sẽ để dành chuỗi có chiều dài lớn nhất cho các phép cộng sau cùng, chuỗi có độ dài lớn thứ hai cho phép cộng kế cuối... Vì vậy, cách giải bài toán này chỉ đơn giản là sắp xếp các chuỗi đã cho theo thứ tự tăng dần về độ lớn chuỗi.

Phần cài đặt xin được để dành làm một thử thách nhỏ cho bạn đọc. Diễn đàn là nơi phù hợp để trao đổi thêm về những vấn đề tương tự.

Phỏng vấn: In ra phần tử nhỏ thứ n trong cây nhị phân

written by Nguyễn Thành Nam, on Mar 19, 2015 11:19:23 AM.

Câu hỏi

Cho một cây nhị phân tìm kiếm (binary search tree), in ra phần tử nhỏ thứ n trong cây này.

Ví dụ: Với cây nhị phân như sau:

                7
           5         9
        3     6         10

Phần tử nhỏ nhất (n=1) là 3, phần tử nhỏ thứ 2 là 6, phần tử nhỏ thứ 3 là 5.

Phân tích

Vì đây là cây nhị phân tìm kiếm nên ta luôn có điều kiện bất biến là các đỉnh bên trái luôn luôn nhỏ hơn hoặc bằng, và các đỉnh bên phải luôn luôn lớn hơn hoặc bằng giá trị của đỉnh đang xét.

Do đó, phần tử nhỏ nhất thứ n cũng là phần tử thứ n trong quá trình duyệt cây theo thứ tự trái, giữa, phải, tức là theo cách tìm kiếm ưu tiên chiều sâu (depth first search).

# encoding: utf-8
def solve(root, n):

    def traverse(node, nr_seen):
        '''Trả về (số đỉnh đã qua, và kết quả).'''
        if node is None:
            return nr_seen, None

        # Tìm trong nhánh trái
        nr_seen, answer = traverse(node.left, nr_seen)
        if answer is not None:
            # Tìm thấy kết quả bên nhánh trái.
            return nr_seen, answer

        nr_seen += 1
        if nr_seen == n:
            # Đỉnh hiện tại chính là đỉnh cần tìm.
            return nr_seen, node.value

        # Tìm trong nhánh phải
        nr_seen, answer = traverse(node.right, nr_seen)
        return nr_seen, answer

    nr_seen, answer = traverse(root, 0)
    return answer


class Node(object):

    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right


root = Node(7, Node(5, Node(3), Node(6)), Node(9, None, Node(10)))
assert(solve(root, 1) == 3)
assert(solve(root, 2) == 5)
assert(solve(root, 3) == 6)
assert(solve(root, 4) == 7)
assert(solve(root, 5) == 9)
assert(solve(root, 6) == 10)

Phỏng vấn: Tìm các từ cùng bộ ký tự

written by Nguyễn Thành Nam, on Mar 16, 2015 9:05:00 AM.

Câu hỏi

Cho một quyển từ điển D, và một từ W trong từ điển, yêu cầu xuất ra tất cả các từ có trong từ điển với cùng bộ ký tự như từ W.

Ví dụ từ mary có bộ ký tự là một chữ m, một chữ a, một chữ r và một chữ y, từ army cũng có cùng bộ ký tự như vậy.

Phân tích

Mối quan hệ giữa từ, và bộ ký tự là 1-n, tức là một từ sẽ có một bộ ký tự, nhưng một bộ ký tự có thể có nhiều từ. Do đó, cách giải bài này là thể hiện mối quan hệ giữa từ và bộ ký tự của nó.

Với mỗi từ X trong từ điển, ta sẽ tìm ra bộ ký tự K tương ứng của từ đó, và lưu X vào danh sách các từ có bộ ký tự K. Để trả lời câu hỏi, ta chỉ việc in ra danh sách các từ có bộ ký tự tương ứng với W.

Độ phức tạp thực thi của cách giải này là O(1) với O(n) bước xử lý trước (preprocessing), và tốn O(n) bộ nhớ.

from collections import defaultdict

def get_alphabet(word):
    count = defaultdict(int)
    for c in word:
        count[c] += 1
    # vì kiểu dict là khả biến, nên ta phải
    # chuyển "count" thành kiểu string để
    # có thể dùng làm khóa trong một dict khác
    r = []
    for k in sorted(count.keys()):
        r.append('%c%d' % (k, count[k]))
    return ''.join(r)

assert(get_alphabet('aaabb') == 'a3b2')

def solve(D, W):
    alpha_to_words = defaultdict(list)
    for word in D:
        alpha = get_alphabet(word)
        alpha_to_words[alpha].append(word)
    return alpha_to_words[get_alphabet(W)]

assert(solve(['mary', 'army', 'vithon'], 'mary') == ['mary', 'army'])

Cách giải trên sẽ áp dụng tốt nếu ta cần trả lời cho một loạt các từ W bởi vì ta chỉ tốn thời gian xử lý trước một lần, và sau đó có thể truy vấn alpha_to_words cho mỗi từ W sau đó. Tuy nhiên, nếu ta chỉ cần trả lời câu hỏi cho duy nhất một từ W thì việc tốn thêm O(n) bộ nhớ cho alpha_to_words là không cần thiết. Trong trường hợp đó, ta chỉ việc xét từng từ trong D, nếu nó có cùng bộ ký tự như W thì ta xuất nó ra ngay.

Phỏng vấn: Số lượng số chính phương ít nhất để có tổng là n

written by Nguyễn Thành Nam, on Mar 14, 2015 10:53:00 PM.

Câu hỏi

Cho một số nguyên dương n, tìm số lượng số chính phương ít nhất có tổng là n.

Ví dụ: Với n là 9, thì đáp án là 1 (vì 9 là số chính phương), với n là 10 thì đáp án là 2 (9 + 1), với n là 11, đáp án là 3 (9 + 1 + 1), với n là 12 thì đáp án là 3 (4 + 4 + 4).

Phân tích

Giả sử như ta đã có đáp án cho tất cả các giá trị từ 1 đến n-1, đáp án cho n sẽ là min(1 + đáp án của (n-x)) với x là một số chính phương. Nói một cách khác, với mỗi số chính phương x nhỏ hơn hoặc bằng n, số lượng số chính phương cần để có tổng là n sẽ là số lượng số chính phương cần để tạo ra tổng là n-x thêm 1 (chính là x). Do đó, đáp án cho n sẽ chính là min của các cách tạo ra tổng n từ các số chính phương nhỏ hơn hoặc bằng n.

Như vậy, ta có thể giải bài toán này bằng cách điền vào bảng trả lời (đặt tên là ans) cho các giá trị từ 0 đến n. Kết quả cuối cùng sẽ là giá trị của ans[n].

Cách giải các bài toán mà đáp án cho giá trị cuối cùng có thể được tính từ đáp án của các giá trị trước, và ta có thể tính các giá trị này bằng cách từ từ điền vào bảng, được gọi là quy hoạch động (dynamic programming).

def solve(n):
    ans = [n] * (n + 1)
    ans[0] = 0
    ans[1] = 1
    for i in xrange(2, n + 1):
        x = 0
        while True:
            x += 1
            x2 = x * x
            if x2 > i:
                break
            ans[i] = min(ans[i], 1 + ans[i - x2])
    return ans[n]

assert(solve(9) == 1)
assert(solve(10) == 2)
assert(solve(11) == 3)
assert(solve(12) == 3)

Độ phức tạp thực thi của cách giải này là O(n * sqrt(n)), và tốn O(n) bộ nhớ.

Phỏng vấn: Cài đặt "ngăn xếp" với thao tác "min/max"

written by Nguyễn Thành Nam, on Mar 11, 2015 10:07:20 AM.

Câu hỏi

Cài đặt cấu trúc dữ liệu ngăn xếp với thao tác trả về phần tử nhỏ (hay lớn) nhất hiện tại của ngăn xếp.

Phân tích

Ngăn xếp (stack) là cấu trúc dữ liệu vào sau ra trước (Last In, First Out). Nói đến ngăn xếp ta phải nhớ ngay đến hai tác vụ quan trọng nhất là đẩy vào (push) và lấy ra (pop). Khi push dữ liệu vào, dữ liệu sẽ nằm trên cùng của ngăn xếp (top of stack). Khi pop, dữ liệu trên cùng của ngăn xếp sẽ được lấy ra khỏi ngăn xếp.

Ngoài hai tác vụ trên, ta còn có thể kể thêm một số tác vụ truy vấn cấu trúc dữ liệu này ví dụ như số lượng dữ liệu có trong ngăn xếp, liệu ngăn xếp có dữ liệu hay không, hay xem dữ liệu trên cùng của ngăn xếp (mà không lấy nó ra khỏi ngăn xếp).

Câu hỏi này yêu cầu ta cài đặt hai tác vụ push, pop, và thêm tác vụ min (hoặc max) để cho biết dữ liệu nhỏ nhất (hay lớn nhất) hiện tại trong ngăn xếp mà không lấy nó ra.

Cách giải dễ nhất

Điều đầu tiên ta nghĩ đến sẽ là tạo một biến để chứa giá trị cực tiểu (hay cực đại). Khi push vào, ta sẽ cập nhật lại biến này nếu cần. Khi hỏi min thì ta chỉ cần trả về giá trị này.

Vấn đề phức tạp là khi pop ra, làm sao để ta cập nhật lại biến cực tiểu đó? Một cách rất đơn giản là ta sẽ duyệt lại toàn bộ các dữ liệu đang có trong ngăn xếp để đưa ra giá trị cực tiểu mới.

Cách giải này dẫn đến độ phức tạp O(1) cho push, O(1) cho minO(n) cho pop.

class Stack(object):

    def __init__(self):
        self.store = []
        self.min = None

    def push(self, value):
        self.store.append(value)
        if self.min is None or self.min < value:
            self.min = value

    def pop(self):
        r = self.store[-1]
        del self.store[-1]
        if not self.store:
            self.min = None
        else:
            self.min = min(self.store)
        return r

    def min(self):
        return self.min

Cách giải O(1) cho pop

Ta nhận thấy rằng tác vụ pop có độ phức tạp O(n) là bởi vì ta phải duyệt lại toàn bộ các phần tử hiện tại của ngăn xếp để xác định phần tử cực tiểu.

Một phương pháp thường được sử dụng để tăng tốc tác vụ là sử dụng bộ nhớ tạm (cache). Ta sẽ tráo đổi giữa thời gian chạy, và không gian nhớ. Nếu như ở mỗi lần push, ta lưu giá trị cực tiểu của các phần tử trong ngăn xếp này vào trong một ngăn xếp thứ hai, thì khi trả lời min, ta chỉ việc nhìn vào (peek) ngăn xếp thứ hai là sẽ có ngay kết quả. Và khi pop thì ta chỉ việc pop ở cả hai ngăn xếp. Các tác vụ này đều có độ phức tạp O(1), nhưng ta sẽ tốn thêm O(n) bộ nhớ cho ngăn xếp thứ hai.

class StackBase(object):

    def __init__(self):
        self.store = []

    def push(self, value):
        self.store.append(value)

    def pop(self):
        r = self.store[-1]
        del self.store[-1]
        return r

    def peek(self):
        return self.store[-1]

    def __bool__(self):
        return bool(self.store)


class StackWithMin(object):

    def __init__(self):
        self.store = StackBase()
        self.mins = StackBase()

    def push(self, value):
        self.store.push(value)
        if not self.mins or self.mins.peek() < value:
            self.mins.push(value)
        else:
            self.mins.push(self.min.peek())

    def pop(self):
        self.mins.pop()
        return self.store.pop()

    def min(self):
        return self.mins.peek()

Cách giải O(1) cho pop cải tiến

Cách giải trên tráo đổi O(1) bộ nhớ và O(n) thời gian cho O(n) bộ nhớ và O(1) thời gian.

Vấn đề dẫn đến O(n) bộ nhớ là do ở mỗi lần push ta cũng lưu lại giá trị cực tiểu của các phần tử hiện tại. Nếu như ta chỉ lưu vị trí của phần tử cực tiểu, thì ta sẽ tiết kiệm được bộ nhớ một chút. Ta chỉ cần lưu lại vị trí của phần tử cực tiểu mới, nếu vị trí này khác với vị trí hiện tại. Khi pop ra, nếu số lượng phần tử hiện tại ít hơn vị trí của phần tử cực tiểu thì ta cũng pop luôn vị trí này ra khỏi ngăn xếp thứ hai. Điều này đảm bảo điều kiện bất biến vị trí của phần tử cực tiểu luôn luôn nhỏ hơn số lượng phần tử trong ngăn xếp.

Cài đặt này xin được để dành làm một thử thách nhỏ cho bạn đọc. Diễn đàn là nơi tốt nhất để bạn đọc trao đổi thêm.

Phỏng vấn: Tìm tích của mọi phần tử trừ phần tử hiện tại

written by Nguyễn Thành Nam, on Mar 8, 2015 2:05:00 PM.

Câu hỏi

Cho một danh sách các số thực A, trả về một danh sách trong đó phần tử tại vị trí i có giá trị là tích của các phần tử không phải ở vị trí i trong danh sách A.

Phân tích

Trường hợp ngoại lệ

Nếu A chỉ có một phần tử thì giá trị trả về sẽ là gì? Người đi phỏng vấn phải hỏi ngược lại được người phỏng vấn trường hợp này.

Cách giải đơn giản

Cách giải đơn giản nhất là ta thực hiện hai vòng lặp để tính giá trị của từng phần tử của danh sách B.

def solve(A):
  B = [1] * len(A)
  for i in xrange(len(A)):
    for j in xrange(len(A)):
      if i != j:
        B[i] *= A[j]
  return B
assert(solve([1, 7, 3, 4]) == [84, 12, 28, 21])

Cách giải này có độ phức tạp là O(n^2).

Cách giải O(n)

Có hai nhận xét đơn giản sau:

  1. Nếu như trong số phần tử còn lại có giá trị 0, thì tích số cũng sẽ là 0.
  2. Giá trị của B[i] sẽ là tích của toàn bộ các phần tử trong A, chia cho A[i]. Ta có thể tính tích của toàn bộ các phần tử trong A qua một vòng lặp, và dùng một vòng lặp khác để tính từng giá trị của B.
def solve(A):
  nr_zeros = 0
  product = 1
  for i in xrange(len(A)):
    if A[i] == 0:
      nr_zeros += 1
    else:
      product *= A[i]
  if nr_zeros >= 2:
    return [0] * len(A)
  B = [0] * len(A)
  for i in xrange(len(B)):
    if A[i] == 0:
      B[i] = product
    elif nr_zeros != 1:
      B[i] = product / A[i]
  return B
assert(solve([1, 7, 3, 4]) == [84, 12, 28, 21])

Cách giải không dùng phép chia

Ta nhận thấy rằng B[i] là tích của các phần tử từ 0 đến i-1 và từ i+1 đến n của A (với n là số phần tử trong A). Nói một cách khác, giá trị trong Btích của hai phần liên tục từ bên trái, và từ bên phải của A . Do đó, ta sẽ sử dụng hai danh sách tạm left_productright_product để chứa tích các phần tử trong A từ bên trái, và từ bên phải, loại trừ phần tử đang xét.

def solve(A):
  left_product = [1] * len(A)
  right_product = [1] * len(A)
  for i in xrange(1, len(A)):
    left_product[i] = left_product[i - 1] * A[i - 1]
  for i in xrange(len(A) - 2, -1, -1):
    right_product[i] = right_product[i + 1] * A[i + 1]
  B = [1] * len(A)
  for i in xrange(len(A)):
    B[i] = left_product[i] * right_product[i]
  return B
assert(solve([1, 7, 3, 4]) == [84, 12, 28, 21])

Khi đọc kỹ đoạn mã trên, ta sẽ thấy rằng có lẽ danh sách left_product là thừa. Thay vào đó, trong quá trình tính B, ta có thể giữ một biến tạm cho biết tích từ A[0] đến A[i - 1]. Phần này xin được dành làm một thử thách nhỏ cho bạn đọc. Nếu bạn giải ra, xin hãy cùng trao đổi trong diễn đàn.

Phỏng vấn: Cách mua và bán lời nhất

written by Nguyễn Thành Nam, on Mar 6, 2015 11:47:00 AM.

Câu hỏi

Giả sử như bạn có thông tin về giá của một món hàng trong một khoảng thời gian nào đó. Tìm ngày bạn sẽ mua, và ngày bạn sẽ bán món hàng đó để đạt được lợi nhuận cao nhất.

Đầu vào: một danh sách các giá trị thực là giá của món hàng từng ngày.

Đầu ra: hai chỉ mục trong danh sách là ngày mua, và ngày bán.

Ví dụ: với dữ liệu vào [10, 13, 9, 10, 11], thì kết quả là (0, 1) ý là mua ngày 0 với mức giá 10, bán ra ngày 1 với mức giá 13, lợi nhuận cao nhất là 3 đơn vị.

Phân tích

Gọi danh sách đầu vào là A. Câu hỏi này yêu cầu chúng ta tìm hai chỉ mục xy trong A sao cho A[y] - A[x] lớn nhất, với điều kiện x < y.

Đặt min_x là chỉ mục của giá thấp nhất trong danh sách A. Khi xét đến phần tử i trong danh sách A, ta sẽ gặp một số trường hợp sau:

  1. Giá giảm: A[i] < A[min_x] Đây là cơ hội mua vào nên ta sẽ đặt min_x = i.
  2. Giá tăng: A[i] >= A[min_x] Đây là cơ hội bán ra nên ta sẽ phải xét thêm A[i] - A[min_x] > A[y] - A[x], tức là bán vào lúc này có lời hơn lúc trước không. Nếu có, ta sẽ cập nhật y, x = i, min_x.

Cài đặt

def solve(A):
  x = y = min_x = 0
  for i in xrange(1, len(A)):
    if A[i] < A[min_x]:
      min_x = i
    elif A[i] - A[min_x] >= A[y] - A[x]:
      x, y = min_x, i
  return (x, y)

assert(solve([10, 13, 9, 10, 11]) == (0, 1))