一亩三分地论坛

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

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

02/08 Google Pittsburgh Onsite 面经

[复制链接] |试试Instant~ |关注本帖
icyilo 发表于 2016-2-17 14:00:23 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 硕士 全职@Google - 内推 - Onsite |Passfresh grad应届毕业生

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

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

x
拿到offer回馈地里~匹兹堡果然全是白人哥哥姐姐们。。

第一轮:
Find Longest Increasing Sequence (nodes必须相邻)
比如[1, 2, 5, 3, 4] LIS 是 [1, 2, 5],[1, 2, 3, 4]不算。. visit 1point3acres.com for more.
考了四种数据结构:
1. Array: 扫一遍就好. more info on 1point3acres.com
2. Tree: BFS就好
3. Directed Acycle Graph: DFS从入度为0的nodes出发+记录已经找过的node的计算结果避免重复计算
4. Undirected Graph: 从每个node都要搜一遍,但是碰到decrease就可以停止了

第二轮:
Item[] findKLargest(Item[], k)
我说了heap方法和快排的partition方法,面试官喜欢partition就写了partition

第三轮:
1. 写一个class找一个window内sensor的均值
class Sensor{
        public Double smoothData(Double point);
}
还问了一个怎么处理wild number的问题
. more info on 1point3acres.com
2. 输出一个string所有可能的compress strings, compress之后必须比原string短
比如 abcdef => [a4f, ab3f, abc2f, a2def, a3ef] 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
第四轮:
给一串灯,要求返回所有光照重合区域的两个灯的组合。
List<Pair> getOverlap(List<Light> lights) {
}

class Light {
        int x; // x 坐标å. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
        int y; // y 坐标
        int r; // 发光半径
}

class Pair {. From 1point 3acres bbs
        Light l1;
        Light l2;
}

祝大家都offer多多!

本帖被以下淘专辑推荐:

qiuxuxing007 发表于 2016-2-18 01:52:16 | 显示全部楼层
第三轮 wild numbers是啥意思啦?谢啦
回复 支持 反对

使用道具 举报

yyyusa 发表于 2016-2-18 14:44:47 | 显示全部楼层
第四轮有小于O(n^2)的解法吗?
回复 支持 反对

使用道具 举报

yyyusa 发表于 2016-2-18 14:47:32 | 显示全部楼层
sensor题没看懂,smoothData的参数和返回值什么关系?
回复 支持 反对

使用道具 举报

aiwojiujiu 发表于 2016-2-18 15:44:22 | 显示全部楼层
请问楼主第四题解法!
回复 支持 反对

使用道具 举报

 楼主| icyilo 发表于 2016-2-18 16:29:01 | 显示全部楼层
qiuxuxing007 发表于 2016-2-18 01:52
第三轮 wild numbers是啥意思啦?谢啦

就是突然出现极高或者极低的数据怎么摒弃掉~
回复 支持 反对

使用道具 举报

 楼主| icyilo 发表于 2016-2-18 16:36:17 | 显示全部楼层
yyyusa 发表于 2016-2-18 14:44
第四轮有小于O(n^2)的解法吗?

后面有follow up问如果r都一样的话有什么优化,那么可以大概nlogn。
方法是把所有lights先排序一遍(比如先根据x再根据y),然后过一遍排好序的lights,用个queue存所有还有可能组成pair的灯,然后如果当前灯的x+queue首灯的x > 2 * r 的话就可以把queue首的灯扔出queue。
但其实这个算法跟r有关系,如果r特别大的话也没用。。。事实上是nlogn和nr之间比较大的那个吧~
回复 支持 反对

使用道具 举报

 楼主| icyilo 发表于 2016-2-18 16:37:24 | 显示全部楼层
yyyusa 发表于 2016-2-18 14:47
sensor题没看懂,smoothData的参数和返回值什么关系?

就是给一个data point的值,返回一个window内的data points的平均值~
回复 支持 反对

使用道具 举报

 楼主| icyilo 发表于 2016-2-18 16:37:40 | 显示全部楼层
aiwojiujiu 发表于 2016-2-18 15:44
请问楼主第四题解法!

请看上面~
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-2-18 22:09:14 | 显示全部楼层
请问楼主处理wild number是设置一个阈值吗?楼主第三题是写的双重循环还是dfs呢?
回复 支持 反对

使用道具 举报

xiaohl0913 发表于 2016-2-19 12:37:51 | 显示全部楼层
第四题 最坏的情况是n * (n -1) /2 对吧(其实n个圆都是一个圆),就是无论什么算法都得是O(n^2)。 对于一般的半径都相同的情况是不是可以用半径为 r 的 bucket做。
回复 支持 反对

使用道具 举报

 楼主| icyilo 发表于 2016-2-19 13:50:40 | 显示全部楼层
bobzhang2004 发表于 2016-2-18 22:09
请问楼主处理wild number是设置一个阈值吗?楼主第三题是写的双重循环还是dfs呢?

面试官说要动态的处理,问我什么想法,我就说要么给个百分比30%什么的,超过均值就说明是wild number就可以摒弃了~
回复 支持 反对

使用道具 举报

 楼主| icyilo 发表于 2016-2-19 13:51:13 | 显示全部楼层
bobzhang2004 发表于 2016-2-18 22:09
请问楼主处理wild number是设置一个阈值吗?楼主第三题是写的双重循环还是dfs呢?

泥问的是哪个第三题?
回复 支持 反对

使用道具 举报

 楼主| icyilo 发表于 2016-2-19 13:53:46 | 显示全部楼层
xiaohl0913 发表于 2016-2-19 12:37
第四题 最坏的情况是n * (n -1) /2 对吧(其实n个圆都是一个圆),就是无论什么算法都得是O(n^2)。 对于一 ...

对的我一开始就是写了个双重for循环~不太懂半径为r的bucket的意思。。。
回复 支持 反对

使用道具 举报

xiaohl0913 发表于 2016-2-19 14:35:57 | 显示全部楼层
就是(x/r, y/r)是一个bucket,然后每个bucket里面的圆都会两两相交。然后只用比周围的8个bucket里的圆是不是相交。
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-2-19 14:42:49 | 显示全部楼层
icyilo 发表于 2016-2-19 13:51
泥问的是哪个第三题?

第三轮第二题,谢谢
回复 支持 反对

使用道具 举报

 楼主| icyilo 发表于 2016-2-20 01:59:54 | 显示全部楼层
xiaohl0913 发表于 2016-2-19 14:35
就是(x/r, y/r)是一个bucket,然后每个bucket里面的圆都会两两相交。然后只用比周围的8个bucket里的圆是不 ...

哦哦懂你的意思了~是种好解法~
回复 支持 反对

使用道具 举报

 楼主| icyilo 发表于 2016-2-20 02:09:07 | 显示全部楼层
bobzhang2004 发表于 2016-2-19 14:42
第三轮第二题,谢谢

我写的一个for循环,相当于用counter i把string切成两半,然后看左右两个substring,如果长度比2大就可以被压缩:. 1point3acres.com/bbs
List<String> getCompressedStrings(String input) {
    List<String> res = new ArrayList<>();. Waral 鍗氬鏈夋洿澶氭枃绔,
    if (input == null || input.length() < 3) {. more info on 1point3acres.com
        return res;
    }
    for (int i = 1; i < input.length() - 1; i++) {
        String left = input.substring(0, i);
        String right = input.substring(i);
        if (left.length() > 2) {
            String compressed = left.charAt(0) + (left.length() - 1) + right;
            res.add(compressed);.鐣欏璁哄潧-涓浜-涓夊垎鍦
        }.鐣欏璁哄潧-涓浜-涓夊垎鍦
        if (right.length() > 2) {
            String compressed = left + (right.length() - 1) + right.charAt(right.length() - 1);
            res.add(compressed);
        }
    }
    return res;. Waral 鍗氬鏈夋洿澶氭枃绔,
}

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

xiaobao9 发表于 2016-2-20 04:17:22 | 显示全部楼层
xiaohl0913 发表于 2016-2-19 14:35
就是(x/r, y/r)是一个bucket,然后每个bucket里面的圆都会两两相交。然后只用比周围的8个bucket里的圆是不 ...

感觉不对啊,比如r=10,  (5, 0) 和 (22, 0)是相交的,但其中一个并不在另外一个的周围8个buckets里
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 08:32

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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