一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1253|回复: 16
收起左侧

Google电面

[复制链接] |试试Instant~ |关注本帖
Violalee119 发表于 2016-4-1 02:39:35 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 硕士 全职@Google - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
刚刚电面大google,听起来像白人小哥,感觉要跪,做太久,各种写错。
给两个calender schedule, 要设定的meeting time interval, 返回最小的可设置schedule的起始时间。. 1point3acres.com/bbs
sched A: [0,10], [10, 15], [13, 20]
sched B: [0,5], [27, 33]
meeting_time = 5,. 1point 3acres 璁哄潧
return 20. more info on 1point3acres.com
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
求祝福,求人品,求on site.1point3acres缃



补充内容 (2016-4-2 01:47):
貌似没说明白。。
schedule内是busy time,也就是不可约的时间,meeting_time是希望约的meeting的时长。找出可以约的最早的时间点。如果都没有,比如例子中B的变成[0,5] [20,25] [27,33]就返回33。

评分

1

查看全部评分

本帖被以下淘专辑推荐:

  • · Google|主题: 54, 订阅: 45
zdhzh05 发表于 2016-4-3 08:51:27 | 显示全部楼层
参考leetcode 56 Merge Intervals

思路:
合并schedule A,B(或更多)
sort
merge intervals 返回新的interval list
线性扫描一遍,找到第一个符合meeting长度的gap

Time: O((m+n)log(m+n)) + O(m+n)
Space: O(m+n)
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
public int getMeetingStartTime(List<Interval> listA, List<Interval> listB, int limit) {
        if (listA == null && listB == null) return 0;
        List<Interval> list = new ArrayList<Interval>();
        if (listA != null) list.addAll(listA);
        if (listB != null) list.addAll(listB);
        if (list.size() == 0) return 0;
        Collections.sort(list, new Comparator<Interval>() {
                @Override
                public int compare(Interval i1, Interval i2) {
                        if (i1.start == i2.start) return i1.end-i2.end;
                        return i1.start-i2.start;
                }
        });
        Interval t = list.get(0);
        List<Interval> res = new ArrayList<Interval>();
        for (int i = 1; i < list.size(); i++) {
                Interval c = list.get(i);
                if (c.start <= t.end) {
                        t = new Interval(t.start, c.end);
                } else {
                        res.add(t);
                        t = c;
                }
        }
        res.add(t);
        for (int i = 1; i < res.size(); i++) {
                if (res.get(i).start-res.get(i-1).end >= limit) {
                        return res.get(i-1).end;
                }
        }
        return res.get(res.size()-1).end;
}

回复 支持 1 反对 0

使用道具 举报

say543 发表于 2016-4-1 14:46:52 | 显示全部楼层
LZ 题不是太懂 能把example 再说说吗?
回复 支持 反对

使用道具 举报

胡乱唱歌huge 发表于 2016-4-2 05:11:03 | 显示全部楼层
楼主这题你当时怎么做的啊,求分享 !!
回复 支持 反对

使用道具 举报

newbiee 发表于 2016-4-2 05:20:35 | 显示全部楼层
楼主你的补充说明里面
比如例子中B的变成[0,5] [20,25] [27,33]就返回33。
.鏈枃鍘熷垱鑷1point3acres璁哄潧
不是应该返回5吗? 如果只约5分钟的话
回复 支持 反对

使用道具 举报

 楼主| Violalee119 发表于 2016-4-2 05:39:35 | 显示全部楼层
newbiee 发表于 2016-4-2 05:20
楼主你的补充说明里面
比如例子中B的变成[0,5] [20,25] [27,33]就返回33。

A不可以呀,要找两个共同的free time slot
回复 支持 反对

使用道具 举报

 楼主| Violalee119 发表于 2016-4-2 06:36:27 | 显示全部楼层
有个条件忘记了,每个schedule都是按照开始时间sort过的。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
第一个想法是先找到A的可约的所有time slot, 存起来。再跟B的逐一进行比较,然后小哥问我有没有更好的,我说可以两个同时search,search的同时记录当前可以定schedule的时间。贴个code的图,电面的时候写的很混乱,这个是整理过的,估计还是会有问题,欢迎批评指正。


补充内容 (2016-4-2 06:46):
typo,最后一行参数是i,大家领会精神。。
回复 支持 反对

使用道具 举报

hayreddinluo 发表于 2016-4-2 07:45:56 | 显示全部楼层
如果A,B两个List不是很长的话,是不是可以先把短的list merge到长的list,然后从这个list里找第一个可选的interval?
回复 支持 反对

使用道具 举报

newbiee 发表于 2016-4-2 09:54:00 | 显示全部楼层
  1. import java.util.*;
    .鐣欏璁哄潧-涓浜-涓夊垎鍦
  2. import java.io.*;

  3. public class CalenderScheduler {. From 1point 3acres bbs
  4.     //find the first time slot that can schedule the work
  5.     public int find (int[][] schedule1, int[][] schedule2, int required) {. Waral 鍗氬鏈夋洿澶氭枃绔,
  6.         List<int[]> pos = new ArrayList<int[]>();
  7.         int lastStart = 0;
  8.         for (int[] job : schedule1) {
  9.             pos.add(new int[]{job[0], 1});
  10.             pos.add(new int[]{job[1], -1});
  11.         }.鐣欏璁哄潧-涓浜-涓夊垎鍦
  12.         for (int[] job : schedule2) {
  13.             pos.add(new int[]{job[0], 1});
  14.             pos.add(new int[]{job[1], -1});
  15.         }-google 1point3acres
  16.         Collections.sort(pos, (a, b) -> {
  17.             return a[0] - b[0];
  18.         });.鐣欏璁哄潧-涓浜-涓夊垎鍦
  19.         //System.out.println(pos.size() + "size #");
  20.         int count = 0;. From 1point 3acres bbs
  21.         int result = 0;
  22.         for (int i = 0; i <= pos.size(); i++) {
  23.             if (i == pos.size()) { // can only allocate after all is done;
  24.                 result = lastStart;
  25.                 break;
  26.             }
  27.             int[] now = pos.get(i);
  28.             if (count == 0) {  // no meeting ongoing
  29.                 if (now[0] - lastStart >= required) { // does the time slot > time required?
  30.                     result = lastStart;
  31.                     break;
  32.                 }
  33.             }
  34.             if (now[1] == 1)
  35.                 count++;
  36.             if (now[1] == -1) {  . 1point3acres.com/bbs
  37.                 count--;
  38.                 if (count == 0)
  39.                     lastStart = now[0]; // update the possible start time;. Waral 鍗氬鏈夋洿澶氭枃绔,
  40.             }
  41.         }
  42.         System.out.println(result);
  43.         return result;

  44.     }
  45. .鐣欏璁哄潧-涓浜-涓夊垎鍦
  46.         public static void main(String[] args) {
  47.                 CalenderScheduler test = new CalenderScheduler();
  48.                 int[][] a = {{0,10}, {10, 15}, {13, 20}};
  49.         int[][] b = {{0,5}, {27, 33}};. Waral 鍗氬鏈夋洿澶氭枃绔,
  50.         int[][] c = {{0,5}, {20, 25}, {27, 33}};
  51.         test.find(a, b, 5);
  52.         test.find(a, c, 5);.鐣欏璁哄潧-涓浜-涓夊垎鍦
  53.         }. 1point3acres.com/bbs
  54. }
复制代码
. 1point 3acres 璁哄潧
补充内容 (2016-4-2 09:55):
和meeting room 2类似,通过两个测试;. from: 1point3acres.com/bbs
lastStart 记录上一次开始可以约的时间,如果到下一次发生的时间 > required申请时间, 则可以
否则约最后一个结束时间;
回复 支持 反对

使用道具 举报

Sayings 发表于 2016-4-2 10:55:39 来自手机 | 显示全部楼层
newbiee 发表于 2016-4-2 05:20. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
楼主你的补充说明里面
比如例子中B的变成[0,5] [20,25] [27,33]就返回33。

.鏈枃鍘熷垱鑷1point3acres璁哄潧
还有sche A
回复 支持 反对

使用道具 举报

waver 发表于 2016-4-2 10:56:03 | 显示全部楼层
是时间吗?  怎么会有27   33。。。
回复 支持 反对

使用道具 举报

newFeeling 发表于 2016-4-3 04:45:01 | 显示全部楼层
leetcode 原题
回复 支持 反对

使用道具 举报

wyb_1221 发表于 2016-4-3 06:56:18 | 显示全部楼层
newFeeling 发表于 2016-4-3 04:45 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
leetcode 原题

可以给个leetcode连接吗?
回复 支持 反对

使用道具 举报

newFeeling 发表于 2016-4-4 08:20:12 | 显示全部楼层
wyb_1221 发表于 2016-4-3 06:56. Waral 鍗氬鏈夋洿澶氭枃绔,
可以给个leetcode连接吗?

253. Meeting Rooms II
回复 支持 反对

使用道具 举报

Alice0701 发表于 2016-4-4 08:27:50 | 显示全部楼层
谢谢楼主分享!!感觉楼上说的merge interval的方法估计算最优的了?
回复 支持 反对

使用道具 举报

sabrinalanlan 发表于 2016-4-6 15:39:42 | 显示全部楼层
merge Intervals,然后查找cur_start_time - last_end_time > meeting_time
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

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

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-5 19:04

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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