Gần đây tôi đã tham dự Cuộc phỏng vấn của Microsoft.Làm cách nào để triển khai danh sách được liên kết với 1 triệu nút?
Tôi được yêu cầu triển khai danh sách được liên kết với 1 triệu nút? Bạn sẽ truy cập vào nút 999999 như thế nào?
Chiến lược và triển khai thiết kế tối ưu cho câu hỏi như vậy là gì?
Danh sách được liên kết có khá ít biến thể, bởi vì nhiều biến thể có nghĩa là nó sẽ khác với danh sách được liên kết.
Bạn có thể thay đổi nó bằng cách liên kết đơn hoặc kép. Liên kết đơn là nơi bạn có một con trỏ tới đầu (nút đầu tiên, A say) trỏ đến B trỏ tới C, v.v. Để biến nó thành danh sách được liên kết đôi, bạn cũng sẽ thêm liên kết từ C đến B và B Nếu bạn có một danh sách liên kết kép thì có nghĩa là giữ một con trỏ đến đuôi danh sách (nút cuối) cũng như phần đầu, có nghĩa là truy cập phần tử cuối cùng là rẻ và các phần tử gần cuối rẻ hơn, bởi vì bạn có thể làm việc ngược lại hoặc tiến lên ... NHƯNG ... bạn sẽ cần phải biết bạn muốn gì ở cuối danh sách ... VÀ vào cuối ngày, danh sách liên kết vẫn là như vậy, và nếu nó sẽ trở nên rất lớn và đó là một vấn đề vì bản chất của ca sử dụng của nó, thì một cấu trúc lưu trữ khác với một danh sách liên kết có lẽ nên được chọn.
Bạn có thể lai danh sách liên kết của khóa học, vì vậy bạn có thể lập chỉ mục hoặc ví dụ, và không có gì sai với lý thuyết đó, nhưng nếu bạn lập chỉ mục TẤT CẢ các nút thì tính chất danh sách được liên kết không còn giá trị nữa và nếu bạn chỉ lập chỉ mục, thì các nút ở giữa các nút được lập chỉ mục phải được sắp xếp hoặc thứ gì đó để bạn có thể tìm thấy nút đóng và làm việc hướng tới nút đích ... có thể điều này sẽ không bao giờ tối ưu và cấu trúc dữ liệu tốt hơn đã chọn.
Thực sự danh sách được liên kết nên được sử dụng khi bạn không muốn làm những việc như nhận được một nút cụ thể, nhưng muốn lặp lại các nút bất kể.
Và có lẽ loại lý do này là những gì người phỏng vấn mong đợi, hơn là một giải pháp rõ ràng cho vấn đề – Trompa
Tôi đồng ý, tôi đã phỏng vấn rất nhiều người và tôi không thể nghĩ ra loại câu trả lời nào khác Tôi có thể mong đợi từ một ứng viên, tôi có hỏi họ một câu hỏi như thế không. – Michael
Nó cũng đáng nhắc đến về Danh sách bỏ qua nếu bạn đang cố gắng giữ cho các mục được lưu trữ theo thứ tự (thứ tự sắp xếp, thứ tự chèn, vv), thường là trường hợp với các tập dữ liệu rất lớn. Bỏ qua Danh sách giống như danh sách được liên kết nhưng thay vào đó là đa cấp với các cấp cao hơn bỏ qua một nửa số nút (trên mức trung bình) so với danh sách được liên kết cấp thấp hơn. – Tuxdude
Tôi không có ý tưởng về những gì tôi sẽ nói, nhưng, ở đây đi:
Bạn có thể conceptually chia danh sách trong sqrt(1000000)khối, theo cách như vậy mà bạn sẽ phải "gợi ý tham khảo" mỗi 1000 yếu tố.
Hãy nghĩ về việc có 1000 linked lists mỗi số có 1000 elements đại diện cho danh sách của bạn với 1000000 elements.
Đây là những gì bạn nghĩ đến!
Khái quát khái niệm này và bạn nhận được [danh sách bỏ qua] (https://en.wikipedia.org/wiki/Skip_list). –
Cool !! Tôi không biết về điều này :) –
Như Michael nói bạn nên trình bày trước hai biến thể cổ điển của danh sách được liên kết. Điều tiếp theo bạn nên làm là hỏi về chèn, tìm kiếm và xóa các mẫu.
Các mẫu này sẽ hướng dẫn bạn hướng tới cấu trúc dữ liệu phù hợp hơn, vì không ai muốn danh sách được liên kết đơn giản hoặc kép với một triệu nút.
Tôi không thể không suy nghĩ ngay lập tức "nó phụ thuộc, cái gì?". Tuy nhiên, đừng trả lời câu hỏi đó tại một cuộc phỏng vấn. Dù sao, bạn đang yêu cầu một giải pháp "tối ưu", vì vậy ... Nó phụ thuộc. Đối với một cuộc phỏng vấn, nó là nhiều hơn một đặt cược cho những gì người phỏng vấn mong đợi cho vị trí, chứ không phải là một vấn đề SO ... –
Tôi có thể sẽ hỏi việc sử dụng một danh sách liên kết cho một bộ sưu tập 1 triệu nút và không phỏng vấn vì đây là microsoft chúng ta đang nói về.cho biết trường hợp xấu nhất của danh sách liền kề khi triển khai biểu đồ là một danh sách liên kết duy nhất – UmNyobe