Google Onsite 10/26

第一题follow up的这个算法好像概率并不平均啊？

zhouyoung1124 发表于 2015-11-15 01:39
第一题follow up的这个算法好像概率并不平均啊？

我当时也觉得不平均，但是最后算了一下的确是能保证在任意时刻你找出来的K个都是等可能的。话说大神你也去Google了吗？求加微信

夜行码农耗子 发表于 2015-11-15 02:10
我当时也觉得不平均，但是最后算了一下的确是能保证在任意时刻你找出来的K个都是等可能的。话说大神你也 ...

并没有。。。google onsite 跪了，，，
仔细看了下，楼主应该想说的是reservoir sampling,,,之前读帖子没读明白，还是平均的

anyway, 恭喜楼主！

恭喜楼主！第一题的follow up楼主可以说得更清楚一些么 sream？

fdecayed 发表于 2015-11-15 04:16
恭喜楼主！第一题的follow up楼主可以说得更清楚一些么 sream？

请问上一楼的大神具体细节，我记不太清了因为当时不是自己做出来的是人家提示做出来的~~

zhouyoung1124 发表于 2015-11-15 02:19
并没有。。。google onsite 跪了，，，
仔细看了下，楼主应该想说的是reservoir sampling,,,之前读帖子 ...

能说说概率的算法吗? 也是觉得怪怪的

say543 发表于 2015-11-18 09:33
能说说概率的算法吗? 也是觉得怪怪的

http://www.cnblogs.com/HappyAngel/archive/2011/02/07/1949762.html
这个帖子解释的蛮好

写了下LongestCommonPath的代码，欢迎指教

1. public class LongestCommonPath {
   
2. 
   
3.         public static void main(String[] args) {
   
4.                 String[] strs = {"/abc/def/g", "/abc/def/h"};
   
5.                 String res = findLongestCommonPath(strs);
   
6.                 System.out.println(res);
   
7.         }
   
8.         public static String findLongestCommonPath(String[] strs) {
   
9.                 if (strs == null || strs.length == 0) {
   
10.                         return "";
    
11.                 }
    
12.                 String commonPath = strs[0];
    
13.                 for (int i = 1; i < strs.length; i++) {
    
14.                         String[] strs1 = commonPath.split("/");
    
15.                         String[] strs2 = strs[i].split("/");
    
16.                         StringBuilder sb = new StringBuilder();
    
17.                         for (int j = 0; j < strs1.length && j < strs2.length; j++) {
    
18.                                 if (strs1[j].equals(strs2[j])) {
    
19.                                         if (strs1[j].length() != 0) {
    
20.                                                 sb.append("/" + strs1[j]);
    
21.                                         }
    
22.                                 } else {
    
23.                                         break;
    
24.                                 }
    
25.                         }
    
26.                         if (sb.length() == 0) {
    
27.                                 return "/";
    
28.                         } else {
    
29.                                 commonPath = sb.toString();
    
30.                         }
    
31.                 }
    
32.                
    
33.                 return commonPath;
    
34.         }
    
35. }
    

复制代码