Câu hỏi yêu thích phỏng vấn thuật toán của các công ty công nghệ

Bài toán "Two sum" trên LeetCode là một bài toán thông dụng được các công ty công nghệ sử dụng trong vòng phỏng vấn của mình nhằm mục đích kiểm tra kiến thức cơ bản của người lập trình về xử lý mảng và bảng băm. Bài toán phát biểu:

Cho một mảng số nguyên nums và một số nguyên target, trả về chỉ mục của hai số sao cho tổng của chúng bằng giá trị target.

Đường dẫn đề bài: https://leetcode.com/problems/two-sum/

Đây là lời giải Python:

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # Tạo một từ điển trống
        d = {}
        # Lặp qua mảng
        for i, num in enumerate(nums):
            # Kiểm tra xem số bù của số hiện tại có trong từ điển không - tức là cộng vào số hiện tại có bằng target hay không
            if target - num in d:
                # Nếu có, trả về chỉ số của số bù và số hiện tại
                return [d[target - num], i]
            # Ngược lại, thêm số hiện tại và chỉ số của nó vào từ điển
            d[num] = i

Cách này sử dụng bảng băm (công nghệ đằng sau một từ điển trong Python) để lưu trữ các số trong mảng và chỉ mục của chúng. Cho mỗi số trong mảng, nó kiểm tra xem số bù của số đó (target - num) đã có trong bảng băm hay chưa.

• Nếu có tức là là chúng ta đã tìm thấy một cặp số mà chúng có tổng bằng target, sau đó chúng ta trả về chỉ mục của những số đó.

• Nếu không chúng ta thêm số hiện tại và chỉ mục của nó vào bảng băm và tiếp tục với số tiếp theo.

Trong trường hợp này, giải pháp sử dụng bảng băm để lưu trữ các số và chỉ mục, vì vậy độ phức tạp thời gian lấy giá trị khỏi từ điển là O(1) vì ta không cần sắp xếp hoặc duyệt qua toàn bộ các phần tử. Tổng độ phức tạp thời gian là O(n), với n là số phần tử trong mảng.

Xem thêm về độ phức tạp về thuật toán nếu bạn chưa hiểu các công thức BigO.

Luyện tập thêm Leetcode tại lớp học Leetcode 200 - Luyện thuật toán với chuyên gia