打印圖像文件的路徑

Question

我發現一個有趣的problem據說在Google面試中被問到，我很好奇它的解決方案。這個問題陳述很長並且有一點點抽象，所以我只在這裏包括它的摘錄（完整的問題在上面的鏈接中）：

給你一個文件中的目錄和文件的列表系統。每個目錄和文件都有一個名稱，該名稱是由字母數字字符組成的非空 字符串。此外，每個文件的名稱都包含一個點號字符;名稱以點開頭的部分 稱爲擴展名。目錄名稱不包含任何點。所有的名字都是這種情況 - 敏感。 每個條目在一個單獨的行中列出。每個目錄後面跟着一個空格 字符的內容列表。根目錄的內容不縮進。

文件系統列表的格式似乎是this。本質上，目標似乎是搜索輸入文件，並將絕對路徑的總長度（以字符爲單位）以模1,000,000,007爲單位返回到所有直接包含至少一個圖像文件的目錄。由於文件系統本質上是樹，我正在考慮將輸入文件讀入解析它的函數，並創建類似B-Tree的東西（因爲每個目錄可以有不同數量的子目錄/文件）。然後，您可以對樹進行深度遍歷來查找帶有圖像擴展名的文件，然後打印它們的路徑。但是，使用B/B +樹更適合在數據庫中維護排序索引，而在這裏，文件不一定需要排序。對帖子的一些評論（來自第一個鏈接）提供了不會在輸入文件中創建樹的解決方案，但是由於該問題指出預期O（N）時間和空間複雜性，似乎構建樹只會有所幫助。

所以這裏的問題是：

1. 如果樹是在這種情況下使用，這將是樹的最佳類型以及它將如何解決問題幫助？

2. 如果不應該使用樹，那麼更有效的替代方法是什麼？

Answer 1

如果目標是O（n），那麼您應該考慮在數據的一次傳遞中解決問題的方式。

您的建議方法是O（n＆middot; log（n）），因爲您需要時間在隨後的傳遞之前創建B樹以查找包含圖像的目錄。

由於輸入似乎已經像樹一樣排列，所以您可以直接利用它。不要構建自己的樹，只需跟蹤處理輸入時所需的信息。當你到達輸入結尾時，你應該有你的答案。

我想到的算法是在遞歸函數中處理每個目錄。離開函數時，如果遇到圖像文件，請將路徑長度添加到累加器。如果遇到沒有點的文件名，則深入該函數。當您遇到縮進級別低於應該出現的級別時返回。

以下算法假定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