楼主: kklt92
跳转到指定楼层
上一主题 下一主题
收起左侧

google onsite 12/18 面经

🔗
lcl3356897 2016-1-7 12:13:21 | 只看该作者
全局:
aiwojiujiu 发表于 2016-1-6 07:48
请问小伙伴们 第4题有啥容易的想法吗?

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

使用道具 举报

🔗
googlerr 2016-1-8 05:26:40 | 只看该作者
全局:
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. }
复制代码

评分

参与人数 1大米 +3 收起 理由
xiaoniqiuqiu + 3 感谢分享!

查看全部评分

回复

使用道具 举报

🔗
liutr90 2016-1-31 14:36:40 | 只看该作者
全局:
googlerr 发表于 2016-1-7 13:26
嗯,这个方法的确好得多,之前用LinkedList太弱了。。。

写了一个Java implementation,欢迎拍砖:

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

使用道具 举报

🔗
哗啦啦 2016-4-3 23:49:40 | 只看该作者
全局:
lcl3356897 发表于 2016-1-7 12:13
java里有个callable
用这个可以实现多线程并且返回数据

请问有参考资料介绍吗?
回复

使用道具 举报

🔗
lcl3356897 2016-4-4 13:30:00 | 只看该作者
全局:
哗啦啦 发表于 2016-4-3 23:49
请问有参考资料介绍吗?

唔。。没啥

我在网上搜的
回复

使用道具 举报

🔗
tcomein2009 2016-4-4 13:57:25 | 只看该作者
全局:
yyyusa 发表于 2015-12-20 17:36
任何数字都是一组不同的斐波那契数之和,所以第三题永远返回true
http://www.maths.surrey.ac.uk/hosted-s ...

他说两个之和吧
回复

使用道具 举报

🔗
tcomein2009 2016-4-4 13:59:59 | 只看该作者
全局:
GatorAM 发表于 2015-12-23 13:00
fibonacci数的题我是用two sum的思想做的,大家评测一下。

    private static boolean isFibonacci(int ...

fibonacci 是个递增数组,用two sum刚刚好
回复

使用道具 举报

🔗
jy_121 2016-4-26 10:53:56 | 只看该作者
全局:
多线程哪个大家有好方法吗
回复

使用道具 举报

🔗
tcomein2009 2016-4-26 12:27:53 | 只看该作者
全局:
xiaoniuona 发表于 2015-12-20 05:33
请问楼主第三题是怎么做的呢?譬如给个数n,是先把小于n的fib都算出来,然后再dp?但是dp好像不能保证uniqu ...

DP可以unique吧?
DP function就是取当前fibonacci数字或者不取;如果取,就从目标和里面减去当前数字
回复

使用道具 举报

🔗
tcomein2009 2016-4-26 12:28:19 | 只看该作者
全局:
kklt92 发表于 2015-12-23 07:27
我是暴力做的, 代码很简单, 就是跟求subset差不多, 但是后来和面试官讨论时间复杂度讨论了很久

DP可以unique吧?
DP function就是取当前fibonacci数字或者不取;如果取,就从目标和里面减去当前数字
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表