[CareerCup] 10.2 Data Structures for Large Social Network 대형 소 셜 네트워크 의 데이터 구조

10.2 How would you design the data structures for a very large social network like Facebook or Linkedln? Describe how you would design an algorithm to show the connection, or path, between two people (e.g., Me -> Bob -> Susan -> Jason -> You).
 
이 문 제 는 우리 로 하여 금 대형 소 셜 네트워크 서비스의 데이터 구 조 를 실현 하 게 한다. 먼저 사용자 류 Person 은 친구 와 다른 정 보 를 포함 해 야 한다. 그리고 대형 사 이 트 는 보통 수백 만 명의 사용자 가 있 을 수 있다. 우 리 는 모든 데 이 터 를 기계 에 존재 할 수 없 기 때문에 우 리 는 친 구 를 찾 을 때 친구 가 있 는 기 계 를 먼저 찾 은 다음 에 기계 에서 친 구 를 조회 해 야 한다.모든 친구 나 기 계 는 자신의 번 호 를 가지 고 있 습 니 다. 빠 른 검색 을 위해 해시 표를 사용 하여 맵 을 만 들 었 습 니 다. 코드 는 다음 과 같 습 니 다.
 

class Person {
public:
    Person(int id): _personID(id) {}
    int getID() { return _personID; }
    void addFriend(int id) { _friendIDs.push_back(id); }
    
private:
    vector<int> _friendIDs;
    int _personID;
};

class Machine {
public:
    unordered_map<int, Person*> _persons;
    int _machineID;
    Person* getPersonWithID(int personID) {
        if (_persons.find(personID) == _persons.end()) {
            return nullptr;
        }
        return _persons[personID];
    }
};

class Server {
public:
    unordered_map<int, Machine*> _machines;
    unordered_map<int, int> _personToMachineMap;
    Machine* getMatchineWithId(int machineID) {
        if (_machines.find(machineID) == _machines.end()) {
            return nullptr;
        }
        return _machines[machineID];
    }
    int getMachineIDForUser(int personID) {
        if (_personToMachineMap.find(personID) == _personToMachineMap.end()) {
            return -1;
        }
        return _personToMachineMap[personID];
    }
    Person* getPersonWithID(int personID) {
        if (_personToMachineMap.find(personID) == _personToMachineMap.end()) {
            return nullptr;
        }
        int machineID = _personToMachineMap[personID];
        Machine *machine = getMatchineWithId(machineID);
        if (machine == nullptr) return nullptr;
        return machine->getPersonWithID(personID);
    }
};

 
최적화: 기계 점프 감소
기계 간 의 점프 비용 이 많이 든다. 우 리 는 보통 기계 간 에 무 작위 점프 를 하지 않 는 다. 보통 내 가 많은 친구 들 이 같은 기계 에 있 으 면 그들 을 함께 방문 할 것 이다.
최적화: 스마트 한 분류 자 와 기계
사람들 은 그들 과 같은 나라 에서 온 사람 을 추가 할 가능성 이 높 기 때문에 같은 도시, 주, 국가의 사람들 은 모두 가능 한 한 같은 기계 에 저장 해 두 어야 한다. 이렇게 찾 을 때 기계 의 도약 을 줄 일 수 있다.
질문: BFS 검색 은 읽 은 것 으로 점 을 표시 해 야 합 니 다. 여 기 는 어떻게 처리 합 니까?
여러 검색 이 동시에 진 행 될 수 있 기 때문에 데 이 터 를 직접 표시 하 지 는 않 지만, 데이터 가 방 문 했 는 지 여 부 를 표시 하기 위해 해시 표를 사용 합 니 다.
또 다른 문 제 는 고려 할 수 있다.
1. 현실 에서 서버 가 무 너 지면 어떻게 하나 요?
2. 캐 시 기능 을 어떻게 잘 활용 합 니까?
3. 그림 의 끝 을 찾 을 수 있 습 니까? 언제 검색 을 중단 할 지 어떻게 결정 합 니까?
4. 실제 적 으로 모든 사람의 친구 수가 다 릅 니 다. 어떤 사람 은 당신 과 다른 사람 사이 에 친구 체인 을 만 들 고 싶 어 합 니 다. 이 데 이 터 를 어떻게 사용 하여 어디서 옮 겨 다 니 는 지 확인 해 야 합 니까?