Python cho người Việt

Python cho người Việt

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.