打印图像文件的路径

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