Google电面挂经 + 求助

1个小时前结束的电面，开始时问了两次他的名字，仍然没有听清，只能作罢。

就问了句：你是PhD是吧，我说是ECE的PhD，然后就直接开始coding

题目是：
给你两个文件f1和f2，f1是10M的量级，f2是10G的量级。f1的每一行有三个东西：str1, str2, ratio，ratio代表str1和str2的比值，示例：

1. A, B, 0.5         // 解释：A / B = 0.5
   
2. A, E, 2.3         // 解释：A / E = 2.3
   
3. C, E, 1.5         // 解释：C / E = 1.5
   
4. C, D, 1.0         // 解释：C / D = 1.0
   
5. ...

复制代码

f2的每一行只存了str1, str2，示例：

1. C, B
   
2. A, D
   
3. ...

复制代码

需要返回一个新的文件叫f3，f3是在f2的基础上更新，并且和f1的格式一样，即你需要算出f2中每一行两个string的ratio，比如上面的例子的话，就是返回下面这样：

1. C, B, 0.33     // 即：C / B = C/E * E/A * A/B = 1.5*1/2.3*0.5 = 0.33
   
2. A, D, 1.53     // 即：A / D = A/E * E/C * C/D = 2.3*1/1.5*1 = 1.53

复制代码

电面具体结果：

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

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

(2016-3-29 08:15):
更准确地说不是weighted graph，只不过node的adj里面除了存node外，还要存一个ratio而以，所以为什么BFS就行，而不需要用bellman ford / dijkstra 之类的东西

补充内容 (2016-4-2 04:26):
今天HR告诉我加面，可能面试官没有fail我

leetcode 399
ORZ...ORZ....ORZ

bless 楼主

我也觉得union find应该比较好做：
可以分成两步:
union:
需要三个数据结构：
Edge: src, dest, ratio
HashSet<Edge>：从点到其root的dest，key是src和dest
HashMap<Node, Set<Node>>：点和他的root集，因为某个点可能有很多root，比如说A——C，B——C，c的root就是a和b
然后复杂度是O(n^2)
find：
直接在HashSet里面找就可以，总复杂度是O(N)

看了解释后直接写一次性跑通

1.        public void addEdge(String sa, String sb, double val, Map<String, Map<String, Double>> graph) {
   
2.             Map<String, Double> vertex = graph.get(sa);
   
3.             if (vertex == null) {
   
4.                 vertex = new HashMap<>();
   
5.                 graph.put(sa, vertex);
   
6.             }
   
7.             vertex.put(sb, val);
   
8.         }
   
9. 
   
10.         public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
    
11. 
    
12.             Map<String, Map<String, Double>> graph = new HashMap<>();
    
13. 
    
14.             for (int i  = 0; i < values.length; i++) {
    
15.                 String[] syms = equations[i];
    
16.                 String sym1 = syms[0];
    
17.                 String sym2 = syms[1];
    
18.                 addEdge(sym1, sym2, values[i], graph);
    
19.                 addEdge(sym2, sym1, 1 / values[i], graph);
    
20.             }
    
21. 
    
22. 
    
23.             double[] rt = new double[queries.length];
    
24.             for (int i = 0;i < queries.length; i++) {
    
25.                 String[] syms = queries[i];
    
26.                 String sym1 = syms[0];
    
27.                 String sym2 = syms[1];
    
28.                 Map<String, Double> vertexA = graph.get(sym1);
    
29.                 rt[i] = -1;
    
30.                 if (vertexA == null) {
    
31.                     continue;
    
32.                 }
    
33.                 rt[i] = countRatio(graph, sym1, sym2, new HashSet<>());
    
34.             }
    
35.             return rt;
    
36.         }
    
37. 
    
38.         private double countRatio(Map<String, Map<String, Double>> graph, String syma, String symb, Set<String> visited) {
    
39.             Map<String, Double> vertex = graph.get(syma);
    
40.             visited.add(syma);
    
41.             if (vertex == null) return -1;
    
42.             if (syma.equals(symb)) return 1;
    
43.             for (Map.Entry<String, Double> e : vertex.entrySet()) {
    
44.                 String sb = e.getKey();
    
45.                 Double ratio = e.getValue();
    
46.                 if (!visited.contains(sb)) {
    
47.                     double cr = countRatio(graph, sb, symb, visited);
    
48.                     if (cr != -1) {
    
49.                         double res = ratio * cr;
    
50.                         if (visited.contains(symb)) return res;
    
51.                     }
    
52.                 }
    
53.             }
    
54.             return -1;
    
55.         }

复制代码

更准确地说不是weighted graph，只不过node的adj里面除了存node外，还要存一个ratio而以，所以为什么BFS就行，而不需要用bellman ford / dijkstra 之类的东西

Map<Key1, Map<Key2, Ratio>> 没什么不对啊
这其实就是一个graph
Key 1 means start point
Key 2 means end point
ratio is cost of path

A -> B -> C -> A 这种情况 保留一个set 看 是否visit 过就可以了吗

F2 需要的path在f1中一定存在吗？F1和F2的量级的差别有什么说法？

ruokua 发表于 2016-3-29 09:05
Map 没什么不对啊
这其实就是一个graph
Key 1 means start point

具体就不知道了。我说这个说了半天，他后来让我换思路，于是就到了graph

yuan311 发表于 2016-3-29 09:15
F2 需要的path在f1中一定存在吗？F1和F2的量级的差别有什么说法？

不一定存在，如果两个Node没有连接，他让在两个Node后面写x

量级的差别的话，我的理解是，在你遍历f2的过程中，需要不断给graph添加edge，这样越到后面，BFS的时候越快

求助：这种情况怎么样向HR要求加面会增加被电面的可能性呢？

题目好难

好详实的面经。谢谢lz。
我有一些其他思路，但没有具体码出来。先抛砖引玉了。
首先可以对f1做Union Find。比如在f1中，从A点出发可以到达的点都在UnionA中， 所以可以自己写一个数据结构。和楼主的

Map<Key1, Map<Key2, Ratio>>类似。A{A, 1}即A点在集合A中，到A的R是1。只要任意一点X也在集合A中我们在处理f1文件是就算出他到A的R。
所以处理f2时候，就不用BFS，而是直接看点是否在一个集合中。如果在则直接R * 1/R。所以时间复杂度为O(1)。如果不在一个集合中，就为X。

按照图这个搞，45分钟写完还真不容易。。。
不过就是用图，还是得用map
bless lz！