google onsite 12/18 面经

12/18 google onsite:
1. 一个1米的sidewalk, 一个水滴宽1cm, 每次水滴的位置是随机的.写一个模拟器来算出来需要

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

p: 对这个题目进行多线程优化.

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

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. }

复制代码

JohnsonMS 发表于 2015-12-23 09:32
第一题怎么做啊？ 一点概念都没有

本质上是check interval. 记得leetcode应该有类似的题目。

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);

        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;

            if(set.contains(temp)){
                return true;
            }else{
                set.add(l);
            }

        }

        return false;
    }

请问楼主 code debug是做什么呢；  面试官给你一段写在纸上的代码，然后你来找错？

大概是些什么类型的bug呢。

orangepie 发表于 2015-12-19 14:54
请问楼主 code debug是做什么呢；  面试官给你一段写在纸上的代码，然后你来找错？

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

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

楼主面的是general hire嘛..

请问楼主第三题是怎么做的呢？譬如给个数n，是先把小于n的fib都算出来，然后再dp？但是dp好像不能保证unique

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

任何数字都是一组不同的斐波那契数之和，所以第三题永远返回true
http://www.maths.surrey.ac.uk/ho ... rep.html#section3.1

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...

cutesnoopy1993 发表于 2015-12-19 15:12
楼主面的是general hire嘛..

面的software engineer, tool and infrastructure.

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

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

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

很有道理, 返回set就可以了, 不是返回bool