tree

Chắc ai cũng từng nghe một lần câu nói “Cấu trúc dữ liệu rất quan trọng trong quá trình sự nghiệp của một lập trình viên” vậy tại sao lại thế? Áp dụng nó như nào trong thực tế thì chúng ta hãy cùng đi đến một bài toán mà mình gặp trong quá trình làm việc ngay sau đây nhé.

Đặt Vấn Đề

Đây có thể là một câu hỏi khi bạn đi phỏng vấn hoặc một bài toán trong thực thế mà bạn có thể gặp phải:
Ta có 2 UIView ở trong hệ thống phân cấp của View trong ứng dụng IOS. Làm như nào để có thể phát hiện được superview chung của 2 UIView gần nhất ?

Hiểu vấn đề

Nhìn qua bài toán chúng ta sẽ cùng tìm hiểu và giải quyết vấn đề này nhé !
Bài toán này giống như chúng ta đang tìm kiếm điểm chung gần nhất trong cây nhị phân ví dụ:

tree

Điểm số 5 và số 8 thì có điểm chung gần nhất trong hệ thống cây là điểm số 6. Hệ thống phân cấp View trong IOS cũng tương tự như thế, chúng ta cần phải tìm được Superview chung gần nhất của 2 UIView. Mục tiêu để nhận dạng là superview gần nhất trong hệ thống phân cấp của 2 view là view đó phải chứa cả 2 UIView trên.

Chiến lược giải quyết vấn đề

Để giải quyết được bài toán trên ta sẽ chia cách giải quyết thành 2 bước.
Bước 1: Truy tìm đến Root View trong mỗi view
Bước 2: Ta sẽ so sánh 2 hệ thống phân cấp với nhau để tìm ra UIView chung gần nhất.

Cách làm sơ bộ đã có. Chúng ta bắt đầu đi giải quyết thực tế nhé !

1. Truy tìm đến Root View

Cho mỗi UIView chúng ta sẽ tạo 1 Array để lưu lại danh sách các UIView ( Từ root view đến nó ) . Để làm điều này chúng ta cần Di chuyển từ nó đến từng superview rồi thêm vào danh sách.

   var path: [UIView] = []
   var currentView: UIView? = view
    while let view = currentView {
        path.append(view)
        currentView = view.superview
    }

2. Nhận diện View chung gần nhất của 2 UIView

Để làm được bước này thì ta cần biến đổi 1 danh sách các view trong hệ thống phân cấp view thành hash table để tìm kiếm được nhanh hơn.


    let hashTable = Set(path1)

Sau đó thông qua danh sách view còn lại để để tìm kiếm trong hashTable parent view gần nhất của 2 view trên.

func findClosestCommonParent(view1: UIView, view2: UIView) -> UIView? {
    var path1 = [UIView]()
    var path2 = [UIView]()

    // Trace path for view1
    var currentView: UIView? = view1
    while let view = currentView {
        path1.append(view)
        currentView = view.superview
    }

    // Trace path for view2
    currentView = view2
    while let view = currentView {
        path2.append(view)
        currentView = view.superview
    }

    // Convert path2 into a hash table
    let hashTable = Set(path2)

    // Find the closest common ancestor
    for ancestor in path1 {
        if hashTable.contains(ancestor) {
            return ancestor
        }
    }

    return nil // No common ancestor found
}

Phân tích độ hiệu quả của giải pháp trên

Time Complexity: Đây là phương thức có hiệu quả cùng độ phức tạp thuật toán là 0(n), Việc tạo hashTable giúp thuật toán tìm kiếm sẽ nhanh và hiệu quả hơn trong quá trình tìm kiếm.

Space Complexity: Trong giải pháp trên thì chúng ta sử dụng 2 path để lưu trữ danh sach các UIView và một hashTable, mỗi biến lưu trữ d phần tử trong đó d là số phần tử tối đa trong hệ thống phân cấp view. Vì thế kết quả Space Complexity là 0(d).

Kết luận

Vậy biết cấu trúc dữ liệu và giải thuật có thể giúp chúng ta tối ưu và giải quyết nhanh gọn các bài toán trong thực tế.
Đây cũng là một trong nhưng câu hỏi phỏng vấn để xem kiến thức giải thuật và cách xử lý một vấn đề của một lập trình viên nói chung còn với lập trình viên IOS nói riêng thì để xem độ hiểu biết của bạn về UIView.

Cảm ơn các bạn đã đọc bài viết của mình ! Nếu có gì sai sót hay có vấn đề gì cần hỏi hoặc thảo luận vui lòng các bạn comment xuống dưới bài viết giúp mình nhé.