《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 8038|回复: 49
收起左侧

google onsite 12/18 面经

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

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

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

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

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

目测可能跪了. 求人品...

. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

评分

7

查看全部评分

本帖被以下淘专辑推荐:

googlerr 发表于 2016-1-8 05:26:40 | 显示全部楼层
lcl3356897 发表于 2016-1-5 13:41. visit 1point3acres.com for more.
第一题之前有发过面经. From 1point 3acres bbs
http://www.1point3acres.com/bbs/thread-147609-1-1.html

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

写了一个Java implementation,欢迎拍砖:
  1. public class WaterDrip {
  2.         private static final int SIZE = 100;. more info on 1point3acres.com
  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() {.鏈枃鍘熷垱鑷1point3acres璁哄潧
  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;. visit 1point3acres.com for more.
  26.                         }
  27.                 }
  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;
        }
. 1point3acres.com/bbs
        if(num == 2 || num == 1){
            return true;
        }

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

        int i = 1;-google 1point3acres
        int j = 1;

        List<Integer> list = new ArrayList<Integer>();
        list.add(0);
.鐣欏璁哄潧-涓浜-涓夊垎鍦
        while(j <= num){
            list.add(j);
            int temp = i + j;
            i = j;
            j = temp;
        }
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
        for(int l : list){
            //System.out.println(l);

            int temp = num - l;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
. 1point3acres.com/bbs
            if(set.contains(temp)){
                return true;
            }else{
                set.add(l);
            }
.鐣欏璁哄潧-涓浜-涓夊垎鍦
        }

        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是做什么呢;  面试官给你一段写在纸上的代码,然后你来找错?. 1point 3acres 璁哄潧

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

使用道具 举报

 楼主| kklt92 发表于 2015-12-19 15:00:49 | 显示全部楼层
orangepie 发表于 2015-12-19 14:54.鏈枃鍘熷垱鑷1point3acres璁哄潧
请问楼主 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.
. Waral 鍗氬鏈夋洿澶氭枃绔,
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. from: 1point3acres.com/bbs
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
. from: 1point3acres.com/bbs
那是把小于n的都算出来放到hashset里用来lookup 然后逐个配对嘛..?不知道有没有更好的方法呢
回复 支持 反对

使用道具 举报

cutesnoopy1993 发表于 2015-12-21 15:25:38 | 显示全部楼层
kklt92 发表于 2015-12-21 13:30. from: 1point3acres.com/bbs
面的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:

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<>();
                int f1 = 0;
                int f2 = 1;       
                while(f1+f2<=n) {. visit 1point3acres.com for more.
                        int f = f1 + f2;
                        f1 = f2;
                        f2 = f;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                        list.add(f);
                }
                return list;
        }
       
        public List<Integer> fibonacciSet(int n) {
                List<Integer> res = new ArrayList<>();. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                List<Integer> list = generateFibonacci(n);
                for(int i=list.size()-1; i>=0; i--) {. visit 1point3acres.com for more.
                        int f_i = list.get(i);
                        if(f_i <= n) {
                                res.add(f_i);. Waral 鍗氬鏈夋洿澶氭枃绔,
                                n -= f_i;
                        }
                }
                return res;. 1point3acres.com/bbs
        }
. visit 1point3acres.com for more.
补充内容 (2015-12-23 07:28):
Just realized that the for loop in fibonacciSet can be updated to: . Waral 鍗氬鏈夋洿澶氭枃绔,
n>0 && i>=0
回复 支持 反对

使用道具 举报

 楼主| kklt92 发表于 2015-12-23 07:26:04 | 显示全部楼层
cutesnoopy1993 发表于 2015-12-21 15:25
我几周前也面了这个 然后送进去hc了 recruiter说要等到明年初才有结果

我也是, hr说明年年初等结果, 祝好运.
回复 支持 反对

使用道具 举报

 楼主| kklt92 发表于 2015-12-23 07:27:40 | 显示全部楼层
cutesnoopy1993 发表于 2015-12-21 15:24
那是把小于n的都算出来放到hashset里用来lookup 然后逐个配对嘛..?不知道有没有更好的方法呢

我是暴力做的, 代码很简单, 就是跟求subset差不多, 但是后来和面试官讨论时间复杂度讨论了很久
回复 支持 反对

使用道具 举报

 楼主| kklt92 发表于 2015-12-23 07:28:57 | 显示全部楼层
hulahu 发表于 2015-12-22 09:24
楼主, fibonacci 和 fibonacci 怎么做啊
.1point3acres缃
我是暴力做的, 先把整个需要的fib数列算出来, 再就和算subset差不多,
回复 支持 反对

使用道具 举报

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

使用道具 举报

GatorAM 发表于 2015-12-23 12:55:45 | 显示全部楼层
yyyusa 发表于 2015-12-20 17:36.鏈枃鍘熷垱鑷1point3acres璁哄潧
任何数字都是一组不同的斐波那契数之和,所以第三题永远返回true
http://www.maths.surrey.ac.uk/hosted-s ...
. from: 1point3acres.com/bbs
题目要求不能有重复的。
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-11-22 17:25

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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