Huy's Blog Theo dõi blog này

Algorithm in Frontend - Kỳ 2: Tree và Menu

Published: 10/6/2017 5:38:18 PM

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 đó

Bài toán cần giải quyết

Thự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

[
  {
    "name": "Electronics",
    "items": ["Laptop", "Headphones"]
  },
  {
    "name": "Headphones",
    "items": ["Shure", "Bose", "JLB"]
  },
  {
    "name": "Cars",
    "items": ["SUV", "Sedan", "Sports"]
  },
  {
    "name": "SUV",
    "items": ["Honda", "Ferrari"]
  },
  {
    "name": "Laptop",
    "items": ["Thinkpad"]
  }
]

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à:

  |- Electronics
  |    |- Headphones
  |    |   |- Shure
  |    |   |- Bose
  |    |   |- JLB
  |    |- Laptop
  |    |   |- Thinkpad
  |- Cars
  |    |- SUV
  |    |   |- Honda
  |    |   |- Ferrari
  |    |- Sedan
  |    |- Sports

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.

Phân tích đề bài

Mặ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ử $I_j$ là "con" của $I_i$ thì tên $I_j\texttt{.name}$ sẽ có mặt trong mảng $I_i\texttt{.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.

Cấu trúc dữ liệu

OK, 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

struct Node {
  name: String,
  items: Array<Node>
}

Với cấu trúc trên, một Node cha sẽ có các Node con nằm trong trường items, và với một Node lá, không có Node con nào, thì trường items chỉ là một mảng rỗng.

Như vậy, nếu $\texttt{Thinkpad}$ là một Node lá, và cũng là con của $\texttt{Laptop}$ thì cây của chúng ta sẽ có dạng:

Node {
  name: "Laptop",
  items: [
    Node {
      name: "Thinkpad",
      items: []
    }
  ]
}

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 33a :see_no_evil:

Ở bước 3, một giá trị $\texttt{node} = I_i\texttt{.items}_j$ sẽ mang kiểu string, đến bước 3a ta lại gán $\texttt{node}$ thành một giá trị $I_t$ (là một cây).

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:

const buildTree = (nodes) => {
  for (let i = 0; i < nodes.length; i++) {
    for (let j = 0; j < nodes[i].items.length; j++) {
      let node = nodes[i].items[j];
      let found = nodes.find(n => n.name == node);
      if (found) {
        nodes[i].items[j] = Object.assign({}, found);
        found.removed = true;
      } else {
        nodes[i].items[j] = {
          name: node,
          items: []
        };
      }
    }
  }

  return nodes.reduce((arr, item) => {
    if (!item.removed) {
      arr.push(item);
    }
    return arr;
  }, []);
}

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:

let list = require('./menu.json');
let result = buildTree(list);
console.log(JSON.stringify(result, null, '  '));
Nội dung JSON của kết quả thu được
[
  {
    "name": "Cars",
    "items": [
      {
        "name": "SUV",
        "items": [
          {
            "name": "Honda",
            "items": []
          },
          {
            "name": "Ferrari",
            "items": []
          }
        ]
      },
      {
        "name": "Sedan",
        "items": []
      },
      {
        "name": "Sports",
        "items": []
      }
    ]
  },
  {
    "name": "Electronics",
    "items": [
      {
        "name": "Laptop",
        "items": [
          {
            "name": "Thinkpad",
            "items": []
          }
        ]
      },
      {
        "name": "Headphones",
        "items": [
          {
            "name": "Shure",
            "items": []
          },
          {
            "name": "Bose",
            "items": []
          },
          {
            "name": "JLB",
            "items": []
          }
        ]
      }
    ]
  }
]

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

[
  ...,
  {
    "name": "Laptop",
    "items": ["Thinkpad"]
  },
  {
    "name": "Thinkpad",
    "items": ["X220", "T450"]
  },
  {
    "name": "X220",
    "items": ["New", "Second Hand"]
  },
  ...
]

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.

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.

Gõ xong nhấn Ctrl + Enter để gửi.