Google电面面经

您好！
本帖隐藏的内容需要积分高于 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. }

复制代码

discoveryi 发表于 2014-5-19 11:49
***************************************************************
GOOGLE PHONE TECHNICAL INTERVIEW  ...

碉堡，谢拉兄台！

想问一下第二题  数组最后一个数据 tdf 感觉会造成图里有环呀 这样还能拓扑排序么？ 还是lz手抖打错啦？

下周可能要电面G 图相关的还有点弱。。好好准备了。。

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

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

可以简单解释一下怎么做吗

topological sort正解

mark 一个~

littlecoolblaxk 发表于 2014-9-21 02:57
想问一下第二题  数组最后一个数据 tdf 感觉会造成图里有环呀 这样还能拓扑排序么？ 还是lz手抖打错啦？

...

我也觉得楼主打错了， 这里面有环

如果没有tdf  这条路径（排除环）的话，应该是 afctbpk（在没给全所有node的条件下算的）当然 Topological Sorting答案不唯一

补充内容 (2015-6-18 13:20):
应该是['a', 'f', 'c', 't', 'p', 'b', 'd', 'k']， 如果没有tdf的话