Bài viết được sự cho phép của tác giả Huy Trần Show Tiếp tục với sê ri Algorithm in Frontend, kì này nói về một loại cấu trúc dữ liệu được dùng thường xuyên trên frontend, đó là Kiểu dữ liệu dạng cây (tree). Nhắc đến cây thì hẳn chúng ta nghĩ ngay đến DOM và các thao tác trên đó, ví dụ như tìm kiếm một element trên DOM, thêm/xóa element,… tuy nhiên các thao tác này chúng ta thường sử dụng DOM API có sẵn của trình duyệt và bài này cũng không có ý định nói đến phần đó Xem thêm tuyển dụng Front End lương cao trên TopDev 1. Bài toán cần giải quyếtThực ra đây là một câu hỏi phỏng vấn cho vị trí Frontend Engineer tại công ty G cũng khá là có tiếng tăm (vì họ bắt mình ký NDA không được tiết lộ nội dung buôi phỏng vấn, nhưng mà để viết bài này thì phải lộ đề rồi, nên thôi mình không tiết lộ tên công ty đó vậy hình như đây là lần thứ 2 mình nhắc đến NDA rồi, mấy cái công ty cứ thích dùng cái này để bịt miệng người ta quài). Đề bài như này. Cho một cục dữ liệu JSON có dạng: menu.json
Hãy xây dựng một component in ra một menu đa cấp (multi-level menu) dựa trên dữ liệu đã cho. Đối với dữ liệu mẫu ở trên thì cấu trúc của menu sẽ là:
Câu hỏi này gây ấn tượng mạnh với mình vì lúc đó là lần đầu tiên mình gặp một câu hỏi phỏng vấn núp bóng dưới dạng một ứng dụng thực tiễn rõ ràng như thế này. 2. Phân tích đề bàiMặc dù đề bài yêu cầu xây dựng một component in ra một menu đa cấp, nhưng bản chất bài toán vẫn là xây dựng thuật toán chuyển cục JSON kia về dạng cây. Nói thì dễ, đến lúc vào phỏng vấn thì mặt mình tái mét, dành hết 40 phút để implement cái cơ chế tạo và mount một custom component theo kiểu Angular Directive, trong khi không đả động gì đến cái đề bài, kết quả là fail dập mặt Nhìn vào dữ liệu input (tạm gọi là I) ta có thể thấy đây là một mảng “phẳng” (flat array), và mỗi phần tử của mảng này có thể có hoặc không có mối liên hệ nào với nhau. Nếu một phần tử Ij là “con” của Ii thì tên Ij.name sẽ có mặt trong mảng Ii.items. Nhiệm vụ của chúng ta sẽ biến mảng phẳng này thành một cây dữ liệu, dựa trên mối quan hệ vừa đề cập. 3. Cấu trúc dữ liệuOK, vậy thì đầu tiên ta phải nghĩ về cấu trúc dữ liệu của một Node trên cây, sẽ có dạng như sau: pseudo code
Với cấu trúc trên, một Node cha sẽ có các Node con nằm trong trường Như vậy, nếu Thinkpad là một Node lá, và cũng là con của Laptop thì cây của chúng ta sẽ có dạng:
4. Xây dựng thuật toánÝ tưởng của thuật toán sẽ gồm 2 công đoạn, giống như chơi xếp hình vậy:
Thuật toán đầy đủ được mô tả như sau:
Khác với các ngôn ngữ lập trình khác, vì JavaScript là dynamic typing, ta có thể dễ dàng thay đổi giữa nhiều kiểu dữ liệu cho một biến, chính vì thế, rất có khả năng bạn sẽ bị confuse khi đọc đến bước 3 và 3a Ở bước 3, một giá trị node=Ii.itemsj sẽ mang kiểu Nếu ngôn ngữ mà các bạn sử dụng không phải JavaScript mà là một ngôn ngữ strong typing nào đó ví dụ như Go hay Rust hay C/C++, thì thuật toán ở trên cần phải được sửa lại. Còn bây giờ thì implement thôi:
Chúng ta chạy thử và in kết quả dưới dạng một chuỗi JSON để thấy rõ cấu trúc dạng cây: Nội dung JSON của kết quả thu được5. Phức tạp quá, làm vậy chi cho cực?Đọc đến đây hẳn có bạn sẽ đặt ra câu hỏi: Tại sao ngay từ ban đầu lại dùng kiểu dữ liệu dạng như thế này trên frontend? Chẳng phải đây là việc của backend hay sao? Trên thực tế có ai làm vậy không? Câu trả lời nằm ở tính tiện lợi khi cần mở rộng menu dạng cây như thế này, ví dụ, với mảng I đã cho ở trên, khi chúng ta cần mở rộng, ví dụ thêm vào một loại laptop khác bên cạnh dòng Thinkpad, hoặc thêm vào một hãng xe ô tô mới, ta có thể thêm trực tiếp một hoặc nhiều item mới vào mảng I, ví dụ: menu.json
Nếu lưu dữ liệu trực tiếp dạng cây thì việc cả việc lưu trữ lẫn việc thêm/bớt này quả thực là một vấn đề không đơn giản. Hay nói cách khác thì giải pháp đó không scalable. 6. Bài viết này có giúp tôi được tăng lương không?Lưu ý: Bản quyền câu nói trên thuộc về blog Quần Cam, để đưa câu nói này vào bài viết, mình đã phải trả một khoản “tiền” khá lớn, mong các bạn đừng bắt chước. Chân thành mà nói thì việc tăng lương hay không phụ thuộc vào… sếp của bạn Tuy nhiên, là một frontend developer, bạn cũng là một phần rất quan trọng trong team, nếu phải lựa chọn giữa một giải pháp tiện lợi cho cá nhân mình nhưng sẽ tạo ra gánh nặng cho phần còn lại của team, và một giải pháp tạo ra vài thách thức nhỏ cho bản thân nhưng đem lại hiệu quả cho toàn bộ hệ thống, thì có lẽ hy sinh một chút thời gian và sự thoải mái của bản thân sẽ tốt hơn so với việc ngồi câu nệ xem việc này là của ai và ai phải làm gì. Rất cảm ơn các bạn đã đọc đến tận dòng này, hy vọng các bạn thích sê ri này, đừng ngại để lại comment nếu các bạn có bất kỳ góp ý hay gợi ý gì. Hẹn gặp lại các bạn trong các bài viết sắp tới. Bài viết gốc được đăng tải tại thefullsnack.com Có thể bạn quan tâm:
Xem thêm các việc làm CNTT hấp dẫn trên TopDev |