google onsite 12/18 面经

kklt92 发表于 2015-12-21 13:32
很有道理, 返回set就可以了, 不是返回bool

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

kklt92 发表于 2015-12-21 13:30
面的software engineer, tool and infrastructure.

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

楼主， fibonacci 和 fibonacci 怎么做啊

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) {
                        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--) {
                        int f_i = list.get(i);
                        if(f_i <= n) {
                                res.add(f_i);
                                n -= f_i;
                        }
                }
                return res;
        }

补充内容 (2015-12-23 07:28):
Just realized that the for loop in fibonacciSet can be updated to:
n>0 && i>=0

cutesnoopy1993 发表于 2015-12-21 15:25
我几周前也面了这个 然后送进去hc了 recruiter说要等到明年初才有结果

我也是, hr说明年年初等结果, 祝好运.

cutesnoopy1993 发表于 2015-12-21 15:24
那是把小于n的都算出来放到hashset里用来lookup 然后逐个配对嘛..?不知道有没有更好的方法呢

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

hulahu 发表于 2015-12-22 09:24
楼主， fibonacci 和 fibonacci 怎么做啊

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

第一题怎么做啊？ 一点概念都没有

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

题目要求不能有重复的。

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