楼主: kklt92
跳转到指定楼层
上一主题 下一主题
收起左侧

google onsite 12/18 面经

🔗
adiggo 2015-12-23 13:38:16 | 只看该作者
全局:
JohnsonMS 发表于 2015-12-23 09:32
第一题怎么做啊? 一点概念都没有

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

使用道具 举报

🔗
 楼主| kklt92 2015-12-23 14:22:33 | 只看该作者
全局:
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. 暂时没有想出来更好的办法去解
回复

使用道具 举报

🔗
 楼主| kklt92 2015-12-23 14:24:20 | 只看该作者
全局:
JohnsonMS 发表于 2015-12-23 09:32
第一题怎么做啊? 一点概念都没有

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

使用道具 举报

🔗
 楼主| kklt92 2015-12-23 14:24:26 | 只看该作者
全局:
JohnsonMS 发表于 2015-12-23 09:32
第一题怎么做啊? 一点概念都没有

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

使用道具 举报

🔗
 楼主| kklt92 2015-12-23 14:24:32 | 只看该作者
全局:
JohnsonMS 发表于 2015-12-23 09:32
第一题怎么做啊? 一点概念都没有

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

使用道具 举报

🔗
 楼主| kklt92 2015-12-23 14:24:39 | 只看该作者
全局:
JohnsonMS 发表于 2015-12-23 09:32
第一题怎么做啊? 一点概念都没有

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

使用道具 举报

🔗
GatorAM 2015-12-24 01:15:19 | 只看该作者
全局:
我贴个第一题,请大家拍砖。

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





回复

使用道具 举报

🔗
googlerr 2015-12-26 08:45:52 | 只看该作者
全局:
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,欢迎拍砖。

本帖子中包含更多资源

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
回复

使用道具 举报

🔗
silenceleaf 2015-12-29 03:19:31 | 只看该作者
全局:
楼主请问第四轮,多线程优化是怎么做呢?是不是在加左右括号的时候,不同的分支给不同的线程来做?
回复

使用道具 举报

🔗
 楼主| kklt92 2015-12-30 11:45:37 | 只看该作者
全局:
silenceleaf 发表于 2015-12-29 03:19
楼主请问第四轮,多线程优化是怎么做呢?是不是在加左右括号的时候,不同的分支给不同的线程来做?

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

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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