Phỏng vấn Câu hỏi: Cấu trúc dữ liệu cho một mạng xã hội lớn

Question

Một câu hỏi phỏng vấn thú vị mà tôi stumbled khi -

Thiết kế các cấu trúc dữ liệu cho một mạng xã hội rất lớn (Facebook, LinkedIn, vv)?

Ngoài ra, thiết kế một thuật toán để hiển thị các kết nối, hoặc con đường, giữa hai người (ví dụ ME> foo-> bar-> rob-> ron)

Answer 1

tôi có lẽ sẽ xem xét một đồ thị vô hướng của một số loại , có thể được lưu trữ dưới dạng ma trận kề phụ thưa thớt. Theo như tìm ra con đường ngắn nhất giữa hai người, vì chi phí của các cạnh là thống nhất, tôi sẽ xem xét đi với một tìm kiếm hai chiều.

Về cơ bản, hãy đi vòng tròn đồng tâm xoay quanh mỗi người, mỗi vòng tròn là chính người đó, sau đó bạn bè của anh ấy, sau đó bạn bè của anh ấy, v.v., ở mỗi bước kiểm tra nếu có người nào ở cả hai vòng tròn. Đi theo con đường từ người đầu tiên bạn tìm thấy bên trong về phía trung tâm của mỗi người, và bạn đã tìm thấy con đường ngắn nhất.

Bạn có thể thử các thuật toán đường dẫn ngắn nhất khác, nhưng nói chung, hầu hết các thuật toán đường dẫn ngắn nhất chỉ cung cấp cho bạn khoảng cách chứ không phải đường dẫn thực tế.

Answer 2

Tôi sẽ lo lắng về điều đó là không thể với một cấu trúc dữ liệu - bạn có thể nói về sturcture cơ sở dữ liệu ở đây. Rất lớn là xxx triệu (100+), và tôi không nghĩ rằng điều này có thể được xử lý hiệu quả trong bộ nhớ.

Answer 3

Khi chúng tôi có một lượng lớn dữ liệu, chúng tôi không thể giữ tất cả dữ liệu của chúng tôi trên một máy. Điều đó có nghĩa là đối với mỗi người chúng ta cần lưu trữ một id máy. Chúng tôi cần phải chăm sóc các khía cạnh sau -

1. Đối với mỗi ID người bạn: machine_id = lookupMachineForUserID (id);
2. Đi tới machine machine_id
3. friend = lookupBạn bè (machine_id);

Có thể có rất nhiều tối ưu hóa được thực hiện ở đây. Một trong số đó là giảm số lần nhảy từ máy này sang máy kia vì nó đắt. Chúng ta có thể làm điều này bằng cách nhóm những người cùng thuộc cùng một quốc gia/thành phố lại với nhau. Có nhiều cơ hội tìm bạn bè trong cùng một thành phố. Tương tự như vậy có thể có những cách khác để tối ưu hóa.

Tôi sẽ cố gắng thực hiện rất cơ bản về cách cấu trúc dữ liệu của chúng tôi trông như thế nào. Ofcourse trong thực tế chúng ta phải xem xét rất nhiều yếu tố như những gì nếu trên của các máy đi xuống, bộ nhớ đệm dữ liệu, vv

public class Server 
{ 
ArrayList<Machine> machines = new ArrayList<Machine>(); 
} 

public class Machine 
{ 
public ArrayList<Person> persons = new ArrayList<Person>(); 
public int machineID; 
} 

public class Person 
{ 
private ArrayList<Integer> friends; 
private int ID; 
private int machineID; 
private String info; 
private Server server = new Server(); 
} 

Tôi sẽ cố gắng giải pháp để truy tìm con đường giữa bạn bè sau này.

Answer 4

Mẫu tổng hợp? Chúng tôi có thể không cần phải kéo tất cả "bạn bè của bạn" của mình để nói chuyện, với bộ nhớ.
Các DB bảng thiết kế là một vấn đề khác nhau

Answer 5

Về thuật toán:

Tôi thích câu trả lời @sxeraverx trừ phần ma trận thưa thớt. Một danh sách điều chỉnh hoặc đồ thị đối tượng đơn giản sẽ là một lựa chọn tốt hơn ở đây. Ma trận phải cấp phát bộ nhớ cho mỗi kết nối có thể là là O (n^2) trong đó n là số lượng người dùng.Một danh sách hoặc đồ thị đối tượng sẽ chỉ cấp phát bộ nhớ trên O (e) trong đó e là số lượng kết nối, đó là thưa thớt.

Tôi sẽ sử dụng tìm kiếm chuyên sâu với đánh dấu để tìm bạn bè. Đánh dấu các nút mà bạn đã duyệt qua là điều cần thiết vì chu kỳ của bạn bè sẽ tồn tại. Với DFS, việc tìm kiếm đường dẫn gần như là tầm thường bởi vì chồng bạn đang sử dụng để thực hiện DFS là đường dẫn. Vì vậy, khi bạn tìm thấy người bạn, bạn chỉ cần bật toàn bộ ngăn xếp và bạn đã hoàn tất.

Tìm kiếm hơi thở đầu tiên không có thuộc tính đẹp vì hàng đợi được sử dụng để duyệt biểu đồ sẽ có các nút chưa được khám phá, vì vậy bạn sẽ cần phải theo dõi đường dẫn bằng cách sử dụng một số cấu trúc khác. Một tìm kiếm đầu tiên chiều rộng có thể thích hợp nếu chúng ta mong đợi chức năng được chạy với những người trong cùng một "khu phố" của bạn bè và thực sự quan tâm đến hiệu suất.

Một đặc tính hay khác của DFS là nó có thể được song song. Khi gặp phải một nút mới, người ta có thể tạo ra các quy trình/chủ đề DFS mới/bất cứ thứ gì để xử lý các nút con. Các chủ đề mới phải có khả năng chia sẻ thông tin đánh dấu thông qua một số loại hệ thống nhắn tin. Điều này có thể là một chút tối ưu hóa sớm bây giờ mà tôi nghĩ về nó một số chi tiết. Dưới đây là một paper về đề tài này trong trường hợp bất cứ ai đang quan tâm đến

Answer 6

Bạn có thể sử dụng một cơ sở dữ liệu đồ thị như neo4j