Google电面 10/1

donnice 发表于 2015-10-2 11:22
好吧= =求问这道题和N叉树之间的关系？

楼主的意思是“1.”只是讨论project而已，不算题。所以“第一题”是从“2.”开始算的。

stellari 发表于 2015-10-2 11:31
楼主的意思是“1.”只是讨论project而已，不算题。所以“第一题”是从“2.”开始算的。

不不，我问的是第二题，就是我说sort的那个

donnice 发表于 2015-10-2 11:33
不不，我问的是第二题，就是我说sort的那个

……我知道啊。我想表达的是：“找第一个缺失的整数”这道题和N叉树没有任何关系，楼主也没有说这道题和N叉树有关系。楼主说的“第二题”是“打印文件系统”那道题。

stellari 发表于 2015-10-2 11:49
……我知道啊。我想表达的是：“找第一个缺失的整数”这道题和N叉树没有任何关系，楼主也没有说这道题和N ...

原来如此＝＝难怪我看不懂

求问第一题的思路～

补充内容 (2015-10-2 12:53):
懂了＝＝谢谢，HashSet的contains是多少复杂度？可以用List吗？

gp89757 发表于 2015-10-2 11:07
第一题用hash_set存一下 然后从1开始往上找吗？

对，我是这么写的，她也没说啥…可能她啥都懒得说吧…

第二道题不知道是不是这个意思。。。

1. # Suppose we have the following API available
   
2. # isFile(), isDirectory(), getFileOrDirectory()
   
3. # input: the original position in the file system, e.g. ~/
   
4. # output: None, just print the file system hierarchy under the input path
   
5. class Solution:
   
6.     def printHierarchyIterative(self, path):
   
7.         if not path: return
   
8.         stack = [(path, 1)]
   
9.         while stack:
   
10.             node, indentation = stack.pop()
    
11.             print '-' * indentation + node
    
12.             if node.isFile():
    
13.                 continue
    
14.             if node.isDirectory():
    
15.                 for fileOrDir in node.getFileOrDirectory():
    
16.                     stack.append((fireOrDic, indentation + 1))
    
17. 
    
18.     def printHierarchyRecursive(self, path):
    
19.         if not path: return
    
20.         self.helper(path, 1)
    
21.         return
    
22. 
    
23.     def helper(self, node, indentation):
    
24.         print '-' * indentation + node
    
25.         if node.isDirectory():
    
26.             for fileOrDir in node.getFileOrDirectory():
    
27.                  self.helper(fileOrDir, indentation + 1)
    
28.         return

复制代码

donnice 发表于 2015-10-2 12:50
求问第一题的思路～

补充内容 (2015-10-2 12:53):

contains是O(1)

donnice 发表于 2015-10-2 11:22
好吧= =求问这道题和N叉树之间的关系？

我觉得，直接把元素替换到对应数组下标的位置（1换到num[1]），然后找到第一个不对应的位置即可

坐看云起 发表于 2015-10-3 03:03
我觉得，直接把元素替换到对应数组下标的位置（1换到num[1]），然后找到第一个不对应的位置即可

那如果是[100, 99, 1, 2], 100要怎么换到num[100]？