데이터 구조 문제

Question

이 흥미로운 데이터 구조 질문에 최적화 된 솔루션을 찾는데 도와주세요 :

약 1000 만 단어를 포함하는 파일을 감안할 때

1. , 데이터 구조를 설계 아나그램
2. 하는 프로그램을 작성을 찾기 위해 가장 복잡한 단어 10 개를 파일에 표시하여 프로그램이 모든 복잡성 측정에서 효율적이되도록하십시오.
3. 수백만 줄의 데이터가있는 파일이 있습니다. 두 줄만 동일합니다. 나머지는 모두 고유합니다. 각 라인은 길어서 메모리에 맞지 않을 수도 있습니다. 동일한 라인을 찾는 가장 효율적인 솔루션은 무엇입니까?

추가 몇 가지 추가 질문 :

4) (당신은 배열의 문자열 중 하나는 시작 문자열과 끝과 같은 다른 하나로 표시됩니다 3. 길이의 문자열의 배열을 제공됩니다) MS에 의해 요청 끈. 중간 문자열이 이전 문자열과 단 하나의 문자 만 달라야하고 문자열이 입력 배열에 있어야한다는 조건하에 시작 문자열을 종료 문자열로 변환해야합니다. 예. 입력

Array: {"fat", "tab", "eat", "see", "tub", "fab", "rat", "sel"} 
Start: "fat" 
End: "tub" 
Then the output should be 
fat -> fab -> tab -> tub 

경우 나는 세 번째를 해결하기 위해 노력했고, 두 가지 appraoches을 마련했다 : 1) 모든 라인의 첫 번째 단어를 읽은 후 그의 첫 번째 단어하지 않는 모든 라인을 제거 다른 줄의 첫 단어와 일치합니다. 이런 식으로 남은 줄의 연속적인 단어가 계속 나오게 될 때까지 두 줄만 남습니다. 너는 너의 대답을 얻었다! 2) 각 행을 더 작은 표현으로 변환하십시오. 이는 각 단어를 짧은 바이너리 형식으로 코딩 한 다음 각 행을 나타내는 비트를 XOR하는 방식으로 얻을 수 있습니다.

편집 : 이제는 데이터 구조 문제가 많았습니다. 누구든지 여기에서 토론하고 싶다면 좀 더 게시 할 수 있습니다.

Answer 1

네 번째 질문에서 제안한 솔루션은 배열의 모든 단어에 대한 그래프를 작성하는 것이 었습니다. 먼저 단어가 다른 단어로 직접 변환 될 수 있으면 값 1을 갖는 인접성 행렬을 만듭니다.

이제 깊이 우선 검색을 사용하여 시작 문자열에서 끝 문자열까지 경로를 찾고 찾으면 경로를 반환하십시오.

지금까지 트래버스 한 경로를 저장하려면 먼저 여기 깊이 검색을 수정해야합니다. 이를 위해, 방문중인 노드를 Stack으로 푸는 대신 스택 전체에 대한 전체 경로를 푸시 했으므로 요소가 발견되면 Start 문자열에서 End 문자열까지의 전체 경로가 생깁니다.

Answer 2

Q2에 대한 대답은 단어와 그 빈도를 저장하기 위해 Hashmap 또는 TRIE를 사용할 수 있다고 생각합니다. 이러한 구조는 모두 좋은 조회 순서를 제공합니다. 파일의 각 단어에 대해 단어가 이미 있는지 확인하십시오. 그렇다면 숫자를 늘리고 단어를 추가하고 개수를 1로 초기화하십시오.

이 질문은 최근에 Microsoft 인터뷰에서 내 친구 중 한 사람에게 요청되었습니다. 그가 제안한 해결책은 비슷했다. HashMap 및 이중 링크 목록을 유지 관리합니다. DLL은 단어 빈도에 따라 정렬됩니다. 새 단어가 문서에 추가 될 때마다 DLL은 현재 정렬 된 목록을 반영하도록 수정됩니다.

가장 효율적인 솔루션은 이중 연결 목록이있는 TRIE를 사용하는 것입니다.

Answer 3

제 4의 질문은 역 추적을 사용하여 해결할 수 있다고 생각하지만 그것이 최적 일지 확실하지 않습니다. 어제 해결책이 나에게 효과가있는 것 같습니다.

Answer 4

하이퍼 큐브를 사용하여 그래프 이론에서 4 번째 문제를 풀 수 있으므로 길이 3의 문자열을 시작 문자열을 '000'으로하여 Q3에 표현할 수 있으며 시작 문자열과 다른 문자열은 ' 001 ','100 '및'010 '이고, 끝 문자열은'111 '입니다.

하이퍼 큐브가 연결된 그래프이기 때문에 시작 문자열에서 끝 문자열까지 적어도 하나의 경로를 찾을 수 있습니다. 최단 경로를 찾으면 (즉, 정점이 없거나 문자열이 반복되지 않음을 의미 함) 문제를 해결할 수 있습니다.