一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 4147|回复: 49
收起左侧

google onsite 12/18 面经

[复制链接] |试试Instant~ |关注本帖
kklt92 发表于 2015-12-19 08:13:56 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 全职@Google - 猎头 - Onsite |Otherfresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
12/18 google onsite:
1. 一个1米的sidewalk, 一个水滴宽1cm, 每次水滴的位置是随机的.写一个模拟器来算出来需要多少次能把整个地面打湿.
2. code debug
3. 算出一个数是否是能被unique的fibonacci数给组成. 比如说9 能被set: 8,1组成. 8和1都是fibonacci数列. set里面数得是unqiue的, 比如说不能出现两个1什么的.
4. 括号配对, follow up: 对这个题目进行多线程优化.
. 1point3acres.com/bbs
目测可能跪了. 求人品...


评分

7

查看全部评分

本帖被以下淘专辑推荐:

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;. Waral 鍗氬鏈夋洿澶氭枃绔,
  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;.1point3acres缃
  22.                         }-google 1point3acres
  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.                 }. more info on 1point3acres.com
  28.                 return count;
  29.         }
  30. }
复制代码

评分

1

查看全部评分

回复 支持 2 反对 0

使用道具 举报

adiggo 发表于 2015-12-23 13:38:16 | 显示全部楼层
JohnsonMS 发表于 2015-12-23 09:32
第一题怎么做啊? 一点概念都没有

本质上是check interval. 记得leetcode应该有类似的题目。
回复 支持 1 反对 0

使用道具 举报

GatorAM 发表于 2015-12-23 13:00:30 | 显示全部楼层
fibonacci数的题我是用two sum的思想做的,大家评测一下。.鐣欏璁哄潧-涓浜-涓夊垎鍦

    private static boolean isFibonacci(int num){
        if(num <= 0){
            return false;
        }

        if(num == 2 || num == 1){
            return true;
        }

        Set<Integer> set = new HashSet<Integer>();

        int i = 1;
        int j = 1;

        List<Integer> list = new ArrayList<Integer>();
        list.add(0); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

. more info on 1point3acres.com        while(j <= num){
            list.add(j);
            int temp = i + j; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
            i = j;
            j = temp;
. Waral 鍗氬鏈夋洿澶氭枃绔,        }

        for(int l : list){
            //System.out.println(l);

            int temp = num - l;

            if(set.contains(temp)){
                return true;
            }else{
                set.add(l);
            }-google 1point3acres

        }

        return false;
    }
回复 支持 1 反对 0

使用道具 举报

yyyusa 发表于 2015-12-20 17:36:44 | 显示全部楼层
任何数字都是一组不同的斐波那契数之和,所以第三题永远返回true
http://www.maths.surrey.ac.uk/ho ... rep.html#section3.1

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

orangepie 发表于 2015-12-19 14:54:53 | 显示全部楼层
请问楼主 code debug是做什么呢;  面试官给你一段写在纸上的代码,然后你来找错?.1point3acres缃

大概是些什么类型的bug呢。
回复 支持 反对

使用道具 举报

 楼主| kklt92 发表于 2015-12-19 15:00:49 | 显示全部楼层
orangepie 发表于 2015-12-19 14:54. 1point3acres.com/bbs
请问楼主 code debug是做什么呢;  面试官给你一段写在纸上的代码,然后你来找错?

大概是些什么类型的b ...

对. 是有一张纸上都是打印好的代码. 然后要我来找哪些地方写的有问题, 不规范, 如何改进什么的. 没有明显的错误代码, 都是能跑但是不规范的代码. 然后跟面试官讨论如何改进
回复 支持 反对

使用道具 举报

cutesnoopy1993 发表于 2015-12-19 15:12:27 | 显示全部楼层
楼主面的是general hire嘛..
回复 支持 反对

使用道具 举报

xiaoniuona 发表于 2015-12-20 05:33:27 | 显示全部楼层
请问楼主第三题是怎么做的呢?譬如给个数n,是先把小于n的fib都算出来,然后再dp?但是dp好像不能保证unique

补充内容 (2015-12-20 11:36):
额,为什么感觉好像每个数都可以由unique fib相加得到啊。。。相加的fib数有限制嚒?楼主能不能给个反例哈,哪个数不行的
回复 支持 反对

使用道具 举报

googlerr 发表于 2015-12-21 03:29:36 | 显示全部楼层
For Question 3, can the set contain more than two unique Fibonacci numbers? For example, does 12 = 1+3+8 satisfy? If so, every positive integer can be expressed as a sum of unique Fibonacci numbers. This can be shown by induction.

We know 1 can be represented as a sum of unique Fibonacci numbers, i.e., 1 = 1, so let's assume every number up to F(n-1) can be represented as a sum of unique Fibonacci numbers for n>1. We then need to prove that all numbers between F(n-1) and F(n) can be represented as a sum of unique Fibonacci numbers. We already know that all numbers less than F(n-1) satisfy the requirement, so for a given number N in between F(n-1) and F(n), we know that N = F(n-1) + K, where K < F(n-2) and can be expressed as a sum of unique Fibonacci numbers less than F(n-2). Thus, N can be represented as a sum of unique Fibonacci numbers.

If the problem does not have any other requirement on the set, I don't see it has anything to do with programming...
回复 支持 反对

使用道具 举报

 楼主| kklt92 发表于 2015-12-21 13:30:03 | 显示全部楼层
cutesnoopy1993 发表于 2015-12-19 15:12
楼主面的是general hire嘛..

面的software engineer, tool and infrastructure.
回复 支持 反对

使用道具 举报

 楼主| kklt92 发表于 2015-12-21 13:30:50 | 显示全部楼层
xiaoniuona 发表于 2015-12-20 05:33
请问楼主第三题是怎么做的呢?譬如给个数n,是先把小于n的fib都算出来,然后再dp?但是dp好像不能保证uniqu ...

看见楼下的说貌似是这样, 但是不是返回true和false, 返回set.
回复 支持 反对

使用道具 举报

 楼主| kklt92 发表于 2015-12-21 13:32:44 | 显示全部楼层
yyyusa 发表于 2015-12-20 17:36
任何数字都是一组不同的斐波那契数之和,所以第三题永远返回true
http://www.maths.surrey.ac.uk/hosted-s ...

很有道理, 返回set就可以了, 不是返回bool
回复 支持 反对

使用道具 举报

cutesnoopy1993 发表于 2015-12-21 15:24:45 | 显示全部楼层
kklt92 发表于 2015-12-21 13:32
很有道理, 返回set就可以了, 不是返回bool

那是把小于n的都算出来放到hashset里用来lookup 然后逐个配对嘛..?不知道有没有更好的方法呢
回复 支持 反对

使用道具 举报

cutesnoopy1993 发表于 2015-12-21 15:25:38 | 显示全部楼层
kklt92 发表于 2015-12-21 13:30
面的software engineer, tool and infrastructure.

我几周前也面了这个 然后送进去hc了 recruiter说要等到明年初才有结果
回复 支持 反对

使用道具 举报

hulahu 发表于 2015-12-22 09:24:53 | 显示全部楼层
楼主, fibonacci 和 fibonacci 怎么做啊
回复 支持 反对

使用道具 举报

googlerr 发表于 2015-12-23 07:23:54 | 显示全部楼层
Algorithm for Fibonacci number:
.1point3acres缃
First, compute all Fibonacci numbers from 1 up to k, where k is the last Fibonacci number not greater than input n. Store all computed Fibonacci numbers into an array. Then scan the array from right to left and store the first one that is less than the target. The target is originally input n and get updated every time a Fibonacci number is found.

Java code:

        private List<Integer> generateFibonacci(int n) {
                List<Integer> list = new ArrayList<>();. from: 1point3acres.com/bbs
                int f1 = 0;
                int f2 = 1;       
                while(f1+f2<=n) {
                        int f = f1 + f2;
                        f1 = f2;-google 1point3acres
                        f2 = f;
                        list.add(f);
                }.鏈枃鍘熷垱鑷1point3acres璁哄潧
                return list;
        }
       
        public List<Integer> fibonacciSet(int n) {. visit 1point3acres.com for more.
                List<Integer> res = new ArrayList<>();
                List<Integer> list = generateFibonacci(n);
                for(int i=list.size()-1; i>=0; i--) {
                        int f_i = list.get(i);
                        if(f_i <= n) {
                                res.add(f_i);
                                n -= f_i;
                        }. 1point3acres.com/bbs
                }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                return res;-google 1point3acres
        }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

. from: 1point3acres.com/bbs 补充内容 (2015-12-23 07:28):
Just realized that the for loop in fibonacciSet can be updated to:
n>0 && i>=0
回复 支持 反对

使用道具 举报

 楼主| kklt92 发表于 2015-12-23 07:26:04 | 显示全部楼层
cutesnoopy1993 发表于 2015-12-21 15:25
我几周前也面了这个 然后送进去hc了 recruiter说要等到明年初才有结果
. 鍥磋鎴戜滑@1point 3 acres
我也是, hr说明年年初等结果, 祝好运.
回复 支持 反对

使用道具 举报

 楼主| kklt92 发表于 2015-12-23 07:27:40 | 显示全部楼层
cutesnoopy1993 发表于 2015-12-21 15:24
那是把小于n的都算出来放到hashset里用来lookup 然后逐个配对嘛..?不知道有没有更好的方法呢
.鏈枃鍘熷垱鑷1point3acres璁哄潧
我是暴力做的, 代码很简单, 就是跟求subset差不多, 但是后来和面试官讨论时间复杂度讨论了很久
回复 支持 反对

使用道具 举报

 楼主| kklt92 发表于 2015-12-23 07:28:57 | 显示全部楼层
hulahu 发表于 2015-12-22 09:24
楼主, fibonacci 和 fibonacci 怎么做啊

我是暴力做的, 先把整个需要的fib数列算出来, 再就和算subset差不多,
回复 支持 反对

使用道具 举报

JohnsonMS 发表于 2015-12-23 09:32:29 | 显示全部楼层
第一题怎么做啊? 一点概念都没有
回复 支持 反对

使用道具 举报

GatorAM 发表于 2015-12-23 12:55:45 | 显示全部楼层
yyyusa 发表于 2015-12-20 17:36. From 1point 3acres bbs
任何数字都是一组不同的斐波那契数之和,所以第三题永远返回true
http://www.maths.surrey.ac.uk/hosted-s ...

题目要求不能有重复的。
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-9 18:24

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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