google onsite 12/18 面经

aiwojiujiu 发表于 2016-1-6 07:48
请问小伙伴们 第4题有啥容易的想法吗？

java里有个callable
用这个可以实现多线程并且返回数据

lcl3356897 发表于 2016-1-5 13:41
第一题之前有发过面经
http://www.1point3acres.com/bbs/thread-147609-1-1.html

嗯，这个方法的确好得多，之前用LinkedList太弱了。。。

写了一个Java implementation，欢迎拍砖：

1. public class WaterDrip {
   
2.         private static final int SIZE = 100;
   
3.         private static final double RATIO = 0.5;
   
4.        
   
5.         // implement algorithm posted here: http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=147609&page=1#pid2058631
   
6.         private int simulatorImproved() {
   
7.                 int count = 0;
   
8.                 Random rm = new Random();
   
9.                 double[][] states = new double[SIZE][2];
   
10.                 for(int i=0; i<SIZE; i++) states[i][1] = 1;
    
11.                 int countFilled = 0;
    
12.                 while(countFilled<100) {
    
13.                         ++count;
    
14.                         double center = rm.nextDouble()*SIZE;
    
15.                         double left = center - RATIO;
    
16.                         double right = center + RATIO;
    
17.                         int leftId = (int)left;
    
18.                         int rightId = (int)right;
    
19.                         if(leftId>=0 && states[leftId][1]>states[leftId][0] && left-leftId<states[leftId][1]) {
    
20.                                 states[leftId][1] = left-leftId;
    
21.                                 if(left-leftId<=states[leftId][0]) ++countFilled;
    
22.                         }
    
23.                         if(rightId<100 && states[rightId][0]<states[rightId][1] && right-rightId>states[rightId][0]) {
    
24.                                 states[rightId][0] = right-rightId;
    
25.                                 if(right-rightId>=states[rightId][1]) ++countFilled;
    
26.                         }
    
27.                 }
    
28.                 return count;
    
29.         }
    
30. }

复制代码

googlerr 发表于 2016-1-7 13:26
嗯，这个方法的确好得多，之前用LinkedList太弱了。。。

写了一个Java implementation，欢迎拍砖：

没有看懂呀， 能稍微讲一下吗？
states[i][0]和state[i][1]是什么关系？

lcl3356897 发表于 2016-1-7 12:13
java里有个callable
用这个可以实现多线程并且返回数据

请问有参考资料介绍吗？

哗啦啦 发表于 2016-4-3 23:49
请问有参考资料介绍吗？

唔。。没啥

我在网上搜的

yyyusa 发表于 2015-12-20 17:36
任何数字都是一组不同的斐波那契数之和，所以第三题永远返回true
http://www.maths.surrey.ac.uk/hosted-s ...

他说两个之和吧

GatorAM 发表于 2015-12-23 13:00
fibonacci数的题我是用two sum的思想做的，大家评测一下。

    private static boolean isFibonacci(int ...

fibonacci 是个递增数组，用two sum刚刚好

多线程哪个大家有好方法吗

xiaoniuona 发表于 2015-12-20 05:33
请问楼主第三题是怎么做的呢？譬如给个数n，是先把小于n的fib都算出来，然后再dp？但是dp好像不能保证uniqu ...

DP可以unique吧？
DP function就是取当前fibonacci数字或者不取；如果取，就从目标和里面减去当前数字

kklt92 发表于 2015-12-23 07:27
我是暴力做的, 代码很简单, 就是跟求subset差不多, 但是后来和面试官讨论时间复杂度讨论了很久

DP可以unique吧？
DP function就是取当前fibonacci数字或者不取；如果取，就从目标和里面减去当前数字