google onsite 12/18 面经

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

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

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

理论上来说好像每个数都是可以由unique fib组成的, 当时面试官没有很在意这个, 就随口一提如果不能组成就返回null. 我刚刚写了个程序跑了一下也没有发现...

关于dp, 我一开始是想做dp, 但是发现好像不是很容易做dp.,..跟你说的问题一样, 不能保证unique. 我觉得这题本质上就是打印所有subset, 但是check一下这个subset的sum是不是符合target number. 暂时没有想出来更好的办法去解

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

第一题就是跑一个循环, 不断的merge interval, 直到interval只有一个并且大于sidewalk就行

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

第一题就是跑一个循环, 不断的merge interval, 直到interval只有一个并且大于sidewalk就行

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

第一题就是跑一个循环, 不断的merge interval, 直到interval只有一个并且大于sidewalk就行.

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

第一题就是跑一个循环, 不断的merge interval, 直到interval只有一个并且大于sidewalk就行.

我贴个第一题，请大家拍砖。

import java.io.*;
import java.util.*;

public class Solution{

    public static void main(String[] args) {
        
        int num = oneTimeSimulator();
        
        System.out.println(num);
    }
   
    private static int oneTimeSimulator(){
        double lenS = 1;
        double lenD = 0.01;
        
        List<Interval> list = new LinkedList<Interval>(); // complexity of LinkedList and ArrayList
        
        Random rn = new Random();
        
        int count = 0;
        
        while(!coverAll(list)){
            double startPoint = rn.nextDouble();
            System.out.println(startPoint);
            System.out.println("Len is" + sysLen(list));
            Interval i1 = new Interval(startPoint - 0.005, startPoint + 0.005);
            list = mergeList(list, i1);
            count++;
        }
        
        return count;
    }
   
    private static double sysLen(List<Interval> list){
        if(list == null || list.size() <= 0){
            return 0;
        }
        
        double result = 0;
        for(int i = 0; i < list.size(); i++){
            Interval temp = list.get(i);
            result += temp.end - temp.start;
        }
        
        return result;
        
    }
   
    private static List<Interval> mergeList(List<Interval> list, Interval newInterval){
        List<Interval> result = new ArrayList<Interval>();
        
        for(int i = 0; i < list.size(); i++){
            Interval l = list.get(i);
            
            if(newInterval.end < l.start){
                result.add(newInterval);
                newInterval = l;
            }else if(newInterval.start > l.end){
                result.add(l);
            }else{
                newInterval = new Interval(Math.min(newInterval.start, l.start), Math.max(newInterval.end, l.end));
            }
        }
        
        result.add(newInterval);
        return result;
    }
   
    private static boolean coverAll(List<Interval> list){
        if(list != null && list.size() == 1 && list.get(0).start <= 0 && list.get(0).end >= 1){
            return true;
        }else{
            return false;
        }
   
    }

}

class Interval{
    double start;
    double end;
   
    Interval(double start, double end){
        this.start = start;
        this.end = end;
    }
}

GatorAM 发表于 2015-12-24 01:15
我贴个第一题，请大家拍砖。

import java.io.*;

你的Merge采用的是ArrayList，这样会不会导致增加没必要的重复操作？比如当前List是下面这种情况：
[0-1.5     3-4     5-6.5     7-8     9-10   ...   99-100]
新的Interval是[1.8 2.8]，原则上来说，只需要将1.8-2.8加入List，就完成了Merge，不需要处理(copy等)后续的。所以我想的是LinkedList来Merge，因为LinkedList添加新Interval和延长一个已有的Interval的复杂度都是1。但我遇到的问题是需要合并已有的两个Interval的时候，需要删除一个Interval，不知道如何快速删除。比如当新的Interval是[6.4 7.4]的时候，for loop运行到i=2时，发现i=2和i=3应该合并，我能想到的方法是：
intervals.get(2).end = 8;
intervals.remove(3);
但remove(i)的复杂度是O(n)，而实际上我们已经在i=2这个节点上了，应该有O(1)的方法来remove i=3这个节点的。

附件中是我的Code，欢迎拍砖。

楼主请问第四轮，多线程优化是怎么做呢？是不是在加左右括号的时候，不同的分支给不同的线程来做？

silenceleaf 发表于 2015-12-29 03:19
楼主请问第四轮，多线程优化是怎么做呢？是不是在加左右括号的时候，不同的分支给不同的线程来做？

这个我不知道最优解, 我当时给的解是仿照mapreduce做的一个算法, 花了很久才让面试官明白