一亩三分地论坛

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

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

两周前的Google onsite,攒个人品

[复制链接] |试试Instant~ |关注本帖
sldsg123 发表于 2015-4-7 12:33:45 | 显示全部楼层 |阅读模式

2015(1-3月) 码农类 硕士 全职@Google - 网上海投 - Onsite |Failfresh grad应届毕业生

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

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

x
先介绍一下背景,LZ是中部完全没名水校毕业,这次Google的onsite是HR在数据库里找到了我的简历,联系我的,莫名其妙过了电面,拿到了onsite。

onsite时候我的LeetCode也就刷了十几道easy的题目,之前准备Epic OA时做了面经的题目,基本准备也就这些,所以其实没有报希望,就是去旅游的。

前一天抵达,Google帮租的车,订的酒店还是蛮豪华的。吃了个中餐,又看了几道题就睡了。第二天早上9点半左右到的Google,在大厅check in,等了一下就带去面试。

一共四轮面试+午餐,因为签了保密协议,虽然已经被拒了,但还是要注意一下人品的,大概说一下题目吧。

有一轮是国人阿姨,YouTube组的,问了一个关于视频的音频视频轨道找sync point的,基本就是说每个轨道都是一块一块的,每块时间长度不一样,要找到sync point,能够让所有轨道都正好在一个音频或视频块结束。后来又加了一道题,大意是一共5个task,然后有很多的项目,每个项目包括了5个task中的一个或几个,每个项目有对应的盈利。问如果系统资源只能完成2个task,怎么找完成哪两个。

还有一轮是个小哥,问的是BFS的问题,就是棋盘给定一个点,往外扩散看能否找到含有特定值的block,不难。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

还有一轮是设计一个API,输入是三个地方传来的stream,输出是每个值在这些stream中出现的次数。我感觉这轮我没有明白题目是什么意思,再加上不知道API该怎么写,又不知道stream是怎么个工作方式,所以答得乱七八糟的……

还有一轮是一个游戏,貌似网上有,因为跟别人聊时别人说见过,就是一个String,加减号组成,每一步可以将两个连续减号变成加号,遇到没有可走的了,就赢了。第一步是给一个String,写个方法返回所有可能的下一步,很简单。Follow-up是给你一个String,写一个方法来决定先走好还是后走好。这一问就难了很多,和面试官讨论了很久,感觉和他的理解有些偏差,最后我按照我的想法写了个解法,也跟他解释了我的想法,貌似他是同意了我的看法。
. 1point3acres.com/bbs
午餐就不用说了,吃吃饭聊聊天,不过我被带去的是个印度餐为主的,再加上一上午用脑子,其实没有什么食欲,也没有觉得很好吃……

总体来说我的四轮题目都不难,不过总共只答了算是四道半题目,从答题数量上还是有差距的,而且自己确实准备得不好,比如BFS那道,被问了之后才发现自己平时都是用的DFS,BFS是现场提示了下现写的,有点囧……

周四面试的,下一周的周三接到电话拒了。被拒了的话果然很快……现在在等Epic的最后结果,回头再写下Epic onsite的面经,我竟然被问了一道关于算法的题目,给跪……攒人品求offer啊!. 鍥磋鎴戜滑@1point 3 acres

评分

2

查看全部评分

本帖被以下淘专辑推荐:

eric108 发表于 2015-4-10 10:16:12 | 显示全部楼层
谢楼主分享 祝后面好运
回复 支持 反对

使用道具 举报

sonicgu 发表于 2015-4-10 11:10:47 | 显示全部楼层
祝楼主后面好运,顺便求++--题目细节,可以一起讨论一下
回复 支持 反对

使用道具 举报

hotIce 发表于 2015-4-13 08:00:15 | 显示全部楼层
sonicgu 发表于 2015-4-10 11:10. 1point 3acres 璁哄潧
祝楼主后面好运,顺便求++--题目细节,可以一起讨论一下

我觉得++--的题目是用recusion做 你有啥更好的想法吗
回复 支持 反对

使用道具 举报

sonicgu 发表于 2015-4-13 08:04:23 | 显示全部楼层
hotIce 发表于 2015-4-13 08:00
我觉得++--的题目是用recusion做 你有啥更好的想法吗

我不知道到底是什么题,你帮忙给说下题目,我想想
回复 支持 反对

使用道具 举报

hotIce 发表于 2015-4-13 10:38:33 | 显示全部楼层
sonicgu 发表于 2015-4-13 08:04
我不知道到底是什么题,你帮忙给说下题目,我想想
.鐣欏璁哄潧-涓浜-涓夊垎鍦
第二题设计一个两人玩的游戏,"--"变成"++"是一个valid move,赢得条件是一方不能move, 给一个String比如“---++----++-+", 写一个函数返回所有valid move, 然后写一个函数判断当前是否赢了,再写一个函数判断接下去是否会赢
回复 支持 反对

使用道具 举报

sonicgu 发表于 2015-4-13 10:43:20 | 显示全部楼层
hotIce 发表于 2015-4-13 10:38
第二题设计一个两人玩的游戏,"--"变成"++"是一个valid move,赢得条件是一方不能move, 给一个String比如 ...
. 1point 3acres 璁哄潧
哦,就是如果你移动一次后,再没有一个valid move,你就赢了,是这意思吧
回复 支持 反对

使用道具 举报

sonicgu 发表于 2015-4-13 10:43:31 | 显示全部楼层
hotIce 发表于 2015-4-13 10:38
第二题设计一个两人玩的游戏,"--"变成"++"是一个valid move,赢得条件是一方不能move, 给一个String比如 ...

哦,就是如果你移动一次后,再没有一个valid move,你就赢了,是这意思吧
回复 支持 反对

使用道具 举报

sonicgu 发表于 2015-4-13 10:43:36 | 显示全部楼层
hotIce 发表于 2015-4-13 10:38. 鍥磋鎴戜滑@1point 3 acres
第二题设计一个两人玩的游戏,"--"变成"++"是一个valid move,赢得条件是一方不能move, 给一个String比如 ...
. 1point 3acres 璁哄潧
哦,就是如果你移动一次后,再没有一个valid move,你就赢了,是这意思吧
回复 支持 反对

使用道具 举报

sonicgu 发表于 2015-4-13 10:43:56 | 显示全部楼层
hotIce 发表于 2015-4-13 10:38. 鍥磋鎴戜滑@1point 3 acres
第二题设计一个两人玩的游戏,"--"变成"++"是一个valid move,赢得条件是一方不能move, 给一个String比如 ...

哦,就是如果你移动一次后,再没有一个valid move,你就赢了,是这意思吧
回复 支持 反对

使用道具 举报

hotIce 发表于 2015-4-13 10:52:04 | 显示全部楼层
sonicgu 发表于 2015-4-13 10:43
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴哦,就是如果你移动一次后,再没有一个valid move,你就赢了,是这意思吧

是的 感觉返回所有valid move可以用recursion 先走好还是后走好貌似比较复杂 不知道该咋解
回复 支持 反对

使用道具 举报

hotIce 发表于 2015-4-13 10:52:12 | 显示全部楼层
sonicgu 发表于 2015-4-13 10:43
哦,就是如果你移动一次后,再没有一个valid move,你就赢了,是这意思吧

是的 感觉返回所有valid move可以用recursion 先走好还是后走好貌似比较复杂 不知道该咋解
回复 支持 反对

使用道具 举报

sonicgu 发表于 2015-4-13 10:57:58 | 显示全部楼层
hotIce 发表于 2015-4-13 08:00
我觉得++--的题目是用recusion做 你有啥更好的想法吗

我看的第一眼感觉就是recursion+记忆状态,类似于dp吧,不知道有没有必胜解
回复 支持 反对

使用道具 举报

adaromu 发表于 2015-4-15 14:45:21 | 显示全部楼层
hotIce 发表于 2015-4-13 10:52
是的 感觉返回所有valid move可以用recursion 先走好还是后走好貌似比较复杂 不知道该咋解

如果当前字符串永远只有奇数次valid move的解法的话,是不是就是必胜解了?
回复 支持 反对

使用道具 举报

superlvyou 发表于 2015-4-15 15:23:14 | 显示全部楼层
初步想了一下,大概这么个思路: 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
Step 1 把输入string分割成若干连续减号的字段,因为每一次move必在其中一个字段内,所以分别查看每个字段是先走赢还是先走输,最后如果先走赢的字段数量是奇数,则整个游戏是先走赢,反之就是先走输。
Step 2 对于每个字段来判断是否先走赢。用数学归纳法。
-先走输
--先走赢
---先走赢
----先走赢
-----先走输. more info on 1point3acres.com
因为每次move只能转换两个连续的减号,所以用每两个连续减号split字段,若某一种分割后左右的子字段若都为先走赢,则此字段为先走赢,否则就是先走输。

步骤2算是个1维dp吧,每个字段的结果按照步骤1最后统计游戏的输赢。

请问,这个思路有问题么?

补充内容 (2015-4-15 15:26):
积分太少连搜索都用不了。。。拜托能给加点米么?谢谢!
回复 支持 反对

使用道具 举报

hotIce 发表于 2015-4-16 01:28:19 | 显示全部楼层
superlvyou 发表于 2015-4-15 15:23
初步想了一下,大概这么个思路:
Step 1 把输入string分割成若干连续减号的字段,因为每一次move必在其中 ...

似乎有一定的道理, 你能把dp的公式写出来看看吗?看了公式才能知道对错
回复 支持 反对

使用道具 举报

tracywade 发表于 2015-4-20 09:49:56 | 显示全部楼层
hotIce 发表于 2015-4-13 10:52
是的 感觉返回所有valid move可以用recursion 先走好还是后走好貌似比较复杂 不知道该咋解

我觉得既然找到所有可能 就可以知道到底走了奇数步还是偶数步多 奇数步多先走好 偶数步多 后走好
回复 支持 反对

使用道具 举报

celtspirit 发表于 2015-4-21 12:08:22 | 显示全部楼层
superlvyou 发表于 2015-4-15 15:23
初步想了一下,大概这么个思路:
Step 1 把输入string分割成若干连续减号的字段,因为每一次move必在其中 ...

这不是求最小最大的问题,没看出来dp啊。能麻烦把转移方程写一下么。多谢了!
回复 支持 反对

使用道具 举报

wild_ricky_0221 发表于 2015-4-21 13:42:18 | 显示全部楼层
lz能细说一下音频轨道那个题吗,不是很理解
回复 支持 反对

使用道具 举报

宝贝忆彼岸 发表于 2015-9-9 05:43:21 | 显示全部楼层
那个++--的题试着写了一下也不知道对不对,使用recursion做的 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
public boolean canWin(String s){
        if(s == null || s.length() < 2){
                return false;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
        }
        int length = s.length();
        for(int i=0;i<length-1;i++){
                if(s.charAt(i) == '-' && s.charAt(i+1) == '-'){
                        char[] temp = s.toCharArray();
                        temp[i] = '+';
                        temp[i+1] = '+';. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                        if(!canWin(String.valueOf(temp))){
                                return true; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                        }
                        temp[i] = '-';
                        temp[i+1] = '-';
                }
        }
.鐣欏璁哄潧-涓浜-涓夊垎鍦        return false;
}
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-3 04:22

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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