Google电面面经

周一google电面，现在还在等消息，发发面经，攒攒RP，也希望得到大家的Bless。。。

第一题，水题，数组加一操作，fo

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

定一些这样的rule，问怎么rebuild the alphabet?

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

readman 发表于 2014-5-19 13:14
大概是这意思把..
添加的node是字母, 不是string, 添加前还要先找到位置 避免在字典中重复出现字母.
估 ...

Hi，根据lz的例子，简单地写了一下，监测结果是：
b
f
a
c
t
d

1. #define _USE_MATH_DEFINES
   
2. 
   
3. #ifdef ONLINE_JUDGE
   
4. #define FINPUT(file) 0
   
5. #define FOUTPUT(file) 0
   
6. #else
   
7. #define FINPUT(file) freopen(file,"r",stdin)
   
8. #define FOUTPUT(file) freopen(file,"w",stdout)
   
9. #endif
   
10. 
    
11. #include <iostream>
    
12. #include <cstdio>
    
13. #include <cstring>
    
14. #include <cstdlib>
    
15. #include <cmath>
    
16. #include <ctime>
    
17. #include <set>
    
18. #include <stack>
    
19. #include <string>
    
20. #include <map>
    
21. #include <vector>
    
22. #include <queue>
    
23. #include <algorithm>
    
24. #include <functional>
    
25. 
    
26. typedef long long ll;
    
27. static const int M = 300;
    
28. static const int N = 10;
    
29. static const int LEN = 1000010;
    
30. static const int MAX = 0x7fffffff;
    
31. static const int MIN = ~MAX;
    
32. static const double EPS = 1e-7;
    
33. char arr[N][M];
    
34. int indegree[N];
    
35. std::vector< std::map<int, int> > alphabet(27);
    
36. 
    
37. void topologic_sort(int n)
    
38. {
    
39.         std::queue<int> cur;
    
40.         std::vector<int> out;
    
41. 
    
42.         for (int i = 1; i<n; i++){
    
43.                 if (indegree[i] == 0 && alphabet[i].size() != 0){
    
44.                         cur.push(i);
    
45.                         out.push_back(i);
    
46.                 }
    
47.         }
    
48. 
    
49.         int ncount = 0;
    
50.         while (cur.empty() == false){
    
51.                 int tmp = cur.front();
    
52.                 cur.pop();
    
53.                 ncount++;
    
54.                 std::map<int, int>::iterator it = alphabet[tmp].begin();
    
55.                 for (it = alphabet[tmp].begin(); it != alphabet[tmp].end(); it++) {
    
56.                         if (--indegree[it->second] == 0){
    
57.                                 cur.push(it->second);
    
58.                                 out.push_back(it->second);
    
59.                         }
    
60.                 }
    
61.         }
    
62. 
    
63.         for (int i = 0; i < out.size(); i++) {
    
64.                 printf("%c\n", out[i] + 'a' - 1);
    
65.         }
    
66. }
    
67. 
    
68. 
    
69. void solve(int n, int m)
    
70. {
    
71.         for (int i = 0; i < m; i++) {
    
72.                 scanf("%s", arr[i]);
    
73.         }
    
74. 
    
75.         char *prev_str = arr[0];
    
76.         size_t prev_len = strlen(prev_str);
    
77.         for (int i = 1; i < m; i++) {
    
78.                 size_t len = std::min(prev_len, strlen(arr[i]));
    
79.                 for (int j = 0; j < len; j++) {
    
80.                         if (prev_str[j] != arr[i][j]) {
    
81.                                 int prev = prev_str[j] - 'a' + 1;
    
82.                                 int cur = arr[i][j] - 'a' + 1;
    
83.                                 if (alphabet[prev][cur] == 0) {
    
84.                                         alphabet[prev][cur] = cur;
    
85.                                         indegree[cur]++;
    
86.                                 }
    
87.                                 break;
    
88.                         }
    
89.                 }
    
90.                 prev_str = arr[i];
    
91.                 prev_len = len;
    
92.         }
    
93. 
    
94.         topologic_sort(27);
    
95. 
    
96.         for (int i = 0; i<n; i++){
    
97.                 alphabet[i].clear();
    
98.         }
    
99. 
    
100. }
     
101. 
     
102. int main()
     
103. {
     
104.         FINPUT("in.txt");
     
105.         FOUTPUT("out.txt");
     
106. 
     
107.         int n, m;
     
108.         while (scanf("%d %d ", &n, &m) != EOF) {
     
109.                 solve(n, m);
     
110.         }
     
111.         return 0;
     
112. }

复制代码

其实第二题本质是拓扑排序

谢谢楼主面经。。
G家发的面试准备清单里貌似没有提到“拓扑”。。。俺去复习复习。。

discoveryi 发表于 2014-5-15 01:39
谢谢楼主面经。。
G家发的面试准备清单里貌似没有提到“拓扑”。。。俺去复习复习。。

求面试准备清单。。。

第二题，我的理解是这样的：

fft和aac比较，按照f<a的规则，f在a前面。

既然是这样，那和拓扑排序有什么关系呢？

自定义std::sort规则，直接暴力排序，复杂度为O(nlog(n)*m)，其中m为字符串长度，n为字符串个数。

这样不能解决问题吗？

discoveryi 发表于 2014-5-15 01:39
谢谢楼主面经。。
G家发的面试准备清单里貌似没有提到“拓扑”。。。俺去复习复习。。

拓扑排序可以用depth-first，也可以用breadth-first

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies