인터뷰 패널에서 질문하는 질문. 웹 응용 프로그램 사용자가 즐겨 찾는 스포츠를 선택할 수 있습니다. 한 명의 사용자는 즐겨 찾는 스포츠를 많이 사용합니다 .e.g 사용자 John은 축구, 축구, 테니스와 같은 즐겨 찾기 스포츠를 제공합니다. 사용자 Alen은 BaseBall, BasketBall과 같은 즐겨 찾는 스포츠를 가지고 있습니다.데이터 구조 검색 기록
수백만 명의 사용자를 고려하십시오. 데이터 구조에서 어떤 알고리즘을 사용하여 풋볼이나 scoccer와 관련된 사용자를 검색합니다.
처음으로 해쉬 맵 (HashMap)으로 답을했지만 인터뷰 패널에서 이진 검색 트리를 사용할 수있는 또 다른 방법 인 메모리 문제를 일으켰다 고 말했지만 대답에 만족하지 않습니다. 누구나 DS 알고리즘을 사용하여 좋아하는 스포츠를 가진 모든 사용자를 얻는 좋은 방법이 무엇인지 설명해 주실 수 있습니까?
가장 쉬운 해결책은 위에서 설명한대로 사용자를 키와 스포츠 목록으로 매핑하여 HashMap을 사용하는 것입니다. 인터뷰에서 가장 먼저이 솔루션을 사용하여 인터뷰 담당자를 만족하는지 확인합니다.
더 나은 해결책은 스포츠 아이템 노드, 즉 축구에서 사용자 노드, 즉 foo, bar까지 단방향 에지가있는 사용자 및 스포츠의 그래프를 만드는 것일 수 있습니다. 스포츠 상품 (예 : 축구)에 대한 쿼리의 경우 소스 노드로 football을 고려하여 그래프를 탐색 할 수 있습니다. 탐색 할 모든 노드는 가장 좋아하는 스포츠 중 하나가 축구 인 사용자 목록입니다. 이렇게하면 효율적으로 공간을 확보 할 수 있습니다.
그래프 탐색의 시간 복잡도가 O(E) 인 각 쿼리에 대해 그래프를 탐색하는 시간 복잡도를 고려하면 최악의 경우에는 E = all users입니다. 따라서 우리는 HashMap을 사용하여 자주 질의 결과를 캐싱 할 수 있습니다. 다시 공간에 대처하기 위해 HashMap을 사용하여 LRU 캐시를 시뮬레이션 할 수 있습니다.
희망이 있습니다.
당신은 자식 노드 (userid)와 연결된 각 부모 노드 (게임)의 이진 검색 트리를 생성하는 것을 의미합니다. 축구는 부모 노드이며 하위 노드는 축구를 좋아하는 사용자입니다. – user3795493
HashMap은 풋볼 - {user1, user2 ....}과 같은 매핑 원인 메모리 문제를 의미합니까? –
사용자를 스포츠 사용자가 좋아하는 키와 값으로 입력하십시오. – user3795493