Google OA 试题讨论

Mr.111 发表于 2016-8-23 05:52
电面也需要做题吗？大神一共面试了几轮？希望大神和大家分享一下经验

OA, 然后一轮电面， 然后onsite

huai10 发表于 2016-8-23 10:46
OA, 然后一轮电面， 然后onsite

好的，谢谢分享！

根据@stellari 大神的指点，今天花时间研究了一下，然后自己写了一个C#版本。目前测试一切正常，代码如下，希望和大家共同进步，如果有不正确的地方真心求正

1. public int solution(String S)
   
2. {
   
3.     string[] input = S.Split('\n');
   
4. 
   
5.     string[] isImage = { ".jpeg", ".gif", ".png" };
   
6.     int rezult = 0;
   
7.     Stack<int> holder = new Stack<int>();
   
8. 
   
9.     for (int i = 0; i < input.Length; i++)
   
10.     {
    
11.         string currentNode = input[i].Replace(" ", "");
    
12.         int currentLength = currentNode.Length; //The length with the "/"
    
13.         int currentLevel = input[i].Length - currentLength; //Find the level
    
14.         
    
15.         while (currentLevel < holder.Count) //Find the full path length of current node's last parent
    
16.         {
    
17.             holder.Pop();
    
18.         }
    
19. 
    
20.         if (holder.Any()) //Add the full path length of current node, if the node is not in the 1 level
    
21.         {
    
22.             holder.Push(holder.Peek() + currentLength + 1);
    
23.         }
    
24.         else //Add the full path length of current node, if the node is in the 1 level
    
25.         {
    
26.             holder.Push(currentLength + 1);
    
27.         }
    
28. 
    
29.         if (isImage.Any(n => currentNode.Contains(n))) //Add the full path length of current node to the rezult, if the current node is image file
    
30.         {
    
31.             rezult += holder.Peek();
    
32.         }
    
33.     }
    
34. 
    
35.     return rezult;
    
36. }

复制代码

写了一个基于递归的parser，求交流。。。
我的想法是：首先把输入转化成一个string list其中每个元素对应一行。在递归调用_build_subtree会对当前节点及其子树进行分析，返回下一个待分析的（对于这棵子树的中间结果，文件名的index）

1. class Solution:
   
2.     dic = {'.jpeg', '.png', '.gif'}
   
3. 
   
4.     @staticmethod
   
5.     def _is_pic(name):
   
6.         for ext in Solution.dic:
   
7.             if len(name) > len(ext) and name[-len(ext):] == ext:
   
8.                 return True
   
9.         return False
   
10. 
    
11.     @staticmethod
    
12.     def _level(name):
    
13.         return len(name) - len(name.strip())
    
14. 
    
15.     @staticmethod
    
16.     def _build_subtree(strings, start):     # return the (total length, next position)
    
17.         root = strings[start]
    
18.         this_level = Solution._level(root)
    
19.         count = 0
    
20.         next_file = start + 1
    
21. 
    
22.         # base case: leaf node
    
23.         if next_file < len(strings) and Solution._level(strings[next_file]) <= this_level or next_file == len(strings):
    
24.             # leaf node
    
25.             if Solution._is_pic(root):
    
26.                 return 1 + len(root.strip()), next_file
    
27.             else:
    
28.                 return 0, next_file
    
29. 
    
30.         while next_file < len(strings) and Solution._level(strings[next_file]) > this_level:
    
31.             tmp, next_file = Solution._build_subtree(strings, next_file)
    
32.             if tmp > 0:
    
33.                 count += (tmp + len(root.strip()) + 1)
    
34.         return count, next_file
    
35. 
    
36.     @staticmethod
    
37.     def build_tree(string):
    
38.         strings = string.split('\n')
    
39.         next_file = 0
    
40.         res = 0
    
41.         while next_file < len(strings):
    
42.             tmp, next_file = Solution._build_subtree(strings, next_file)
    
43.             res += tmp
    
44.         return res
    
45. 
    
46. 
    
47. 
    
48. if __name__ == "__main__":
    
49.     directory = 'dir1\n dir11\n dir12\n  picture.jpeg\ndir121\n file1.txt\ndir2\n file2.gif'
    
50.     print(Solution.build_tree(directory))
    

复制代码