이미지 파일로의 인쇄 경로

Question

나는 Google 인터뷰에서 질문을 받았다고하는 흥미로운 problem을 발견했으며 그에 대한 해결책이 궁금합니다. 문제는 여기에 길어서 조금 밖에 나오지 않으므로 여기에 발췌 부분을 포함 시키십시오. (전체 문제는 위 링크에 있습니다) :

파일에 디렉토리 및 파일 목록이 제공됩니다 체계. 각 디렉토리와 파일의 이름은 영숫자가 아닌 문자열입니다. 또한 각 파일의 이름에는 단일 점 문자가 포함됩니다. 점으로 시작하는 이름의 부분 을 확장자라고합니다. 디렉토리 이름에는 점들이 포함되지 않습니다. 모든 이름은 대문자입니다. 민감합니다. 각 항목은 별도의 행에 나열되어 있습니다. 모든 디렉토리 다음에는 내용이 한 칸 띄어 쓰여진 목록 문자가옵니다. 루트 디렉토리의 내용은 들여 쓰여지지 않습니다.

파일 시스템 목록의 형식은 this입니다. 본질적으로, 목표는 입력 파일을 검색하여 적어도 하나의 이미지 파일을 직접 포함하는 모든 디렉토리에 절대 경로의 모듈로 1,000,000,007 길이의 합계를 반환하는 것 같습니다.

파일 시스템은 본질적으로 나무이므로 입력 파일을 구문 분석하고 B- 트리와 같은 것을 만듭니다 (각 디렉토리는 다른 수의 하위 디렉토리/파일을 가질 수 있음). 그런 다음 트리의 심도 순서를 탐색하여 이미지 확장명을 가진 파일을 찾은 다음 경로를 인쇄 할 수 있습니다. 그러나 B/B + 트리를 사용하면 데이터베이스에서 정렬 된 인덱스를 유지하는 데 더 많은 역할을하지만 여기에서는 파일을 반드시 정렬 할 필요가 없습니다. 첫 번째 링크의 게시물에 대한 의견 중 일부는 입력 파일에서 나무를 만들지 않는 솔루션을 제공하지만 O (N) 시간 및 공간의 복잡성이 예상된다는 문제 때문에 나무를 구성하는 것처럼 보일 수 있습니다 오직 도움이 될 것입니다. 이는이 나무의 가장 좋은 유형의 것, 나무가이 상황에서 사용할 경우

1. 어떻게 문제를 해결하는 데 도움이 것 :

   그래서 여기에 질문이 있습니다?

2. 트리를 사용해서는 안되는 경우보다 효율적인 대안은 무엇입니까?

Answer 1

목표가 O (n) 인 경우 데이터를 한 번에 전달할 때 문제를 해결하기 위해 취해야 할 조치를 고려해야합니다.

이미지가있는 디렉토리를 찾기 위해 다음 단계 전에 B- 트리를 만드는 데 시간이 걸리기 때문에 O (n & middot; 로그 (n))입니다.

입력이 이미 트리처럼 배열되어있는 것처럼 보이므로 직접 활용할 수 있습니다. 자신의 트리를 만드는 대신 입력을 처리하는 동안 원하는 정보를 추적하십시오. 입력이 끝나면 답을 얻어야합니다.

내가 염두에두고있는 알고리즘은 재귀 함수에서 각 디렉토리를 처리하는 것입니다. 기능을 종료 할 때 이미지 파일이 발견되면 누적기에 경로 길이를 추가하십시오. 점없이 파일 이름을 발견하면 기능을 더 깊게 재연하십시오. 들여 쓰기 수준이 맞지 않을 때 돌아갑니다.

아래 알고리즘은 음수 값이 leading_spaces(EmptyLine)이라고 가정합니다.

process_directory(in path, in level, in-out accum) 
    has_image = false 
    while get_line(line) 
    invariant leading_spaces(line) <= level 
    if leading_spaces(line) < level 
     return line 
    while no_dot(line) 
     line = process_directory(path + '/' + trim(line), level + 1, accum) 
     if leading_spaces(line) < level 
     if has_image 
      accum = accum + length(path) 
     return line 
    has_image = extention_is_image(line) 
    if has_image 
    accum = accum + length(path) 
    return EmptyLine