一亩三分地论坛

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

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

Google两次电面面经求Onsite

[复制链接] |试试Instant~ |关注本帖
sauceforge 发表于 2016-11-4 01:33:52 | 显示全部楼层 |阅读模式

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

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

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

x

. 鍥磋鎴戜滑@1point 3 acres
发面经求onsite貌似很有用,面了2个狗家电面,来求Onsite.

一面:
1. 给n个集合比如{a, b}, {1}, {x, y}. 从每个集合里面去一个数组成新的集合,输出所有这种集合,比如例子就是:{{a, 1, x}, {a,1,y}, {b,1,x}, {b,1,y}}. 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
2. 写完后开始聊多线程,聊完就说你写个死锁吧,然后就写了2个线程和2个锁来读写文件的死锁情况,他也很满意,然后问怎么解死锁,我说用一个锁就是了。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
.1point3acres缃
以为面得很好,结果一周后hr打电话通知二面!感觉被三哥黑了!!

二面:
又是一个三哥!全程没说任何闲话都在做题。
1. 给你n个coins和一个value比如1000,输出这些coins能组成多少种value小于1000, 每种coin可以用无限次。直接完全背包秒杀了。
2. 给你1,000,000个数,求有多少个pair的和小于给定的数K, 直接排序加二分做的。follow up: 找三个数怎么办,我没多想就说对于排序后对每个数做一遍前面的问题。
以为没有了,说完test case还有15分钟的样子,结果就来第三题了:
3. 给你两个string s和t, 问s是否能删除小于N个字符,使得结果是t的一个子串,比如 "book, aook", N = 1, return true;.鐣欏璁哄潧-涓浜-涓夊垎鍦
看完直接懵了,因为最近做two points太多了,就朝那个方向想,一直想去用O(N),最后他说不行,我也发现不行,然后45分钟一到,直接就说拜拜了。
第三个题真的太紧张了,下来一想就是一个二维的dp也不难。

求人品吧,3天了都还没消息。


补充内容 (2016-11-10 02:44):
电面8天后终于收到Onsite通知,人品还是有点好

评分

2

查看全部评分

本帖被以下淘专辑推荐:

willians512 发表于 2016-11-10 15:36:03 | 显示全部楼层
xiangminxufsu 发表于 2016-11-8 03:02
我靠显示确实有问题啊!
. from: 1point3acres.com/bbs
补充内容 (2016-11-8 16:04):

我明白你的意思了 ,但 当 s != t[j] 的时候,这个i不一定要删除吧?有一种情况是 i 匹配[0 : j -1]里面的字符,所以 d (i+1)(j+1) = 最小的 d(i)(j+1)+1, d(i+1)(j)。 比如 s= boo t = aook  当 i= 最后一个o j 等于k的时候  这时候o 就没必要删除吧?

补充内容 (2016-11-10 02:37):
不打方括号就行  d(i)(j)
回复 支持 1 反对 0

使用道具 举报

gmixy 发表于 2016-11-10 08:24:45 | 显示全部楼层
楼主太强了,有几个问题同时也给上面所有回复的朋友

1. coins那个题目跟combination sum完全一样啊,dp不是最优解。如果给的比如是1,5,20的coins,那么跳跃非常大,dp是差劲的解

2. 楼主二面最后一个题,跟edit distance有点像,但是简单太多了,我不知道为什么要用dp,因为是要求subarray,而且只有删除一个操作,直接把s里面不满足t的全都删除掉,看次数是不是小于N就行了,我粗略举了个例子,idea就是把t的char和indices读一遍,存到map<char, minHeap<index>>里面,然后对s线性走一遍,如果不在map,删,如果在map,poll掉minHeap的top,这样average情况就是线性的

我感觉好多题目dp都是实在没有解法的时候才考虑的
回复 支持 1 反对 0

使用道具 举报

xiangminxufsu 发表于 2016-11-5 09:07:22 | 显示全部楼层
楼主加油!我觉得凭楼主实力就算被黑了也肯定能拿到其他公司offer, 只不过我建议楼主在没把握的情况下,不要上来就奔着最优解去,像你说的,一卡住就很容易紧张,面试官也不了解你的思路也只能在旁边干看着,最后他就完全有理由给你个negtive feedback. 另外我想了一下第三题,跟LC的edit distance有点类似,写了下代码还请指正。 不得不说这俩面试官确实够狠。。。

  1. def solve(s,t):
  2.         ls = len(s)
  3.         lt = len(t)
  4.         dp = [[ls for j in xrange(lt+1)] for i in xrange(ls+1)]
  5.         #max value is ls as empty always be substring of other strings

  6.         for i in xrange(ls+1):
  7.                 dp[i][0] = i # when t is empty, we need make s empty too
  8.         for j in xrange(lt+1):
  9.                 dp[0][j] = 0 #when s is empty, s is substring of any string. Waral 鍗氬鏈夋洿澶氭枃绔,
  10. . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  11.         for i in xrange(ls):
    鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  12.                 for j in xrange(lt):
  13.                         .1point3acres缃
  14.                         if s[i] == t[j]:
  15.                                 dp[i+1][j+1] = min(dp[i+1][j+1],dp[i][j])
  16.                         else:
  17.                                 dp[i+1][j+1] = min(dp[i+1][j+1],dp[i][j+1]+1)

  18.         ans = ls
  19.         for x in dp[ls]:
  20.                 ans = min(ans,x)
  21.        return ans. 1point 3acres 璁哄潧
  22. . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  23. print solve('okok','okok')
  24. print solve('book','aooksbooks')
复制代码
回复 支持 1 反对 0

使用道具 举报

 楼主| sauceforge 发表于 2016-11-4 16:45:50 | 显示全部楼层
sixtysix 发表于 2016-11-4 16:35
第二题没思路啊 排序二分怎么想的?

排序后对于a, 二分找到最大的数小于K-a 如果index是j, 那么以a作为第二个数的pair就有j+1个。处理所有a, 就是nlogn了
回复 支持 1 反对 0

使用道具 举报

syjohnson 发表于 2016-11-4 05:47:01 | 显示全部楼层
lz秒了三题,onsite一定没问题!
回复 支持 反对

使用道具 举报

zhan1612 发表于 2016-11-4 11:44:56 | 显示全部楼层
麻烦问一下楼主那个硬币怎么搞的

补充内容 (2016-11-4 11:51):
我想的是加入value x可以被组合成, 那么x+cion0, x+coin1,....都可以。 可是这个复杂度是o(nk)  想问一下楼主是什么方法。
回复 支持 反对

使用道具 举报

 楼主| sauceforge 发表于 2016-11-4 16:14:44 | 显示全部楼层
zhan1612 发表于 2016-11-4 11:44
麻烦问一下楼主那个硬币怎么搞的. 1point 3acres 璁哄潧
. 1point 3acres 璁哄潧
补充内容 (2016-11-4 11:51):

就是这个思路,dp实现,完全背包,复杂度就是这样了
回复 支持 反对

使用道具 举报

sixtysix 发表于 2016-11-4 16:35:27 | 显示全部楼层
第二题没思路啊 排序二分怎么想的?
回复 支持 反对

使用道具 举报

yangqqh 发表于 2016-11-5 04:51:29 | 显示全部楼层
二面第三题什么思路啊?是随便删吗?还是只能从前面删?
回复 支持 反对

使用道具 举报

hezhifeng850207 发表于 2016-11-7 05:21:50 | 显示全部楼层
楼主太强了。。。肯定会有好消息的
回复 支持 反对

使用道具 举报

 楼主| sauceforge 发表于 2016-11-8 02:21:19 | 显示全部楼层
xiangminxufsu 发表于 2016-11-5 09:07
楼主加油!我觉得凭楼主实力就算被黑了也肯定能拿到其他公司offer, 只不过我建议楼主在没把握的情况下,不 ...

谢谢回复,确实还是容易紧张,这题我后面我也写了,就是这个思路,其实不难,就是当时只有10分钟了还问这个题确实有点懵。两次都是阿三,被黑得不轻,Bloomberg面试也是阿三,也是3个题,但是最后一个题不难,也直接秒了,然后拿了Onsite
回复 支持 反对

使用道具 举报

willians512 发表于 2016-11-8 13:40:56 | 显示全部楼层
xiangminxufsu 发表于 2016-11-4 20:07
楼主加油!我觉得凭楼主实力就算被黑了也肯定能拿到其他公司offer, 只不过我建议楼主在没把握的情况下,不 ...

可以帮忙解释一下  状态方程的含义吗  就是 if 和 else  里面的 式子。为什么要包含 dp[i+1][j+1]呢   你的dp定义的含义是什么呢  不好意思 dp掌握的还不是很熟练  谢谢啦

补充内容 (2016-11-8 01:09):
比如  dp[1][1] 的值 按照楼主的逻辑 应该得0吧 但 如果 s = "book" t = "aook" 从b 到 a 应该删除1吧

补充内容 (2016-11-8 01:26):.鐣欏璁哄潧-涓浜-涓夊垎鍦
我的是
if s == t[j]:
                                dp[i+1][j+1] = min (dp[j],dp[j]+1)
                        else
                                dp[i+1][j+1] = min(dp[j+1]+1,dp[i+1][j].鐣欏璁哄潧-涓浜-涓夊垎鍦
. visit 1point3acres.com for more.
补充内容 (2016-11-8 01:27):
笔误: 第一个if 成立的式子是 dp[i+1][j+1] = min (dp[j],dp[j]+1). 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

补充内容 (2016-11-8 01:28):
不知道为什么 显示总是错误 是 i 和 j , dp[j],dp[j]+1
回复 支持 反对

使用道具 举报

xiangminxufsu 发表于 2016-11-8 16:01:45 | 显示全部楼层
willians512 发表于 2016-11-8 13:40
可以帮忙解释一下  状态方程的含义吗  就是 if 和 else  里面的 式子。为什么要包含 dp[j+1]呢   你的dp ...

我对这题的理解就是,我们需要求出s 变成 t的substring 所需要删除的最小数量, 如果这个数量n<=N,那么条件成立,反之不成立。
这里我们用dp[i+1][j+1]来表示s[0:i](包含i) 变成t[0:j](包含j)的substring所需要的删除数量,如果s == t[j]那么这个s是不需要删除的,只需要让其等于dp[j],如果s != t[j],那么这个i是需要删除的,删除之后我们就看下s[0:i-1]和t[0:j]的匹配情况就好了,所以就等于dp[j+1]
最后我们需要找的值就是dp最后一行里面的最小值,dp[-1][j]表示的就是s成为t[0:j]的substring所需要删除最小值。
我的这种解法可能不是最优解。。有可能存在O(m+n).... 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
另外我以前也不太会dp,我都是把里面东西全部打印出来,体会每一个dp[j]是怎么来的,很有用。
我看不太懂你写的啊,怎么会有 dp[i+1][j+1] = min (dp[j],dp[j]+1)这种语法呢?
回复 支持 反对

使用道具 举报

xiangminxufsu 发表于 2016-11-8 16:02:39 | 显示全部楼层
willians512 发表于 2016-11-8 13:40
可以帮忙解释一下  状态方程的含义吗  就是 if 和 else  里面的 式子。为什么要包含 dp[j+1]呢   你的dp ...
. more info on 1point3acres.com
我靠显示确实有问题啊!
. 鍥磋鎴戜滑@1point 3 acres
补充内容 (2016-11-8 16:04):
显示有问题,你就看下我的理解就好了。
回复 支持 反对

使用道具 举报

zjswhhh 发表于 2016-11-8 18:38:32 | 显示全部楼层
楼主玩过ACM吗,这说话的语气好像是同道中人
回复 支持 反对

使用道具 举报

 楼主| sauceforge 发表于 2016-11-10 02:41:23 | 显示全部楼层
zjswhhh 发表于 2016-11-8 18:38
楼主玩过ACM吗,这说话的语气好像是同道中人

本科水过一段时间,但是比较弱,不然本科毕业就上班了
回复 支持 反对

使用道具 举报

zjswhhh 发表于 2016-11-10 13:32:22 | 显示全部楼层
gmixy 发表于 2016-11-10 08:24
楼主太强了,有几个问题同时也给上面所有回复的朋友

1. coins那个题目跟combination sum完全一样啊,dp ...

你是说矩阵快速幂吧 或者这东西应该是个多项式,插值就行了
回复 支持 反对

使用道具 举报

fengwang 发表于 2016-11-10 16:41:32 | 显示全部楼层
willians512 发表于 2016-11-10 15:36
我明白你的意思了 ,但 当 s != t[j] 的时候,这个i不一定要删除吧?有一种情况是 i 匹配[0 : j -1]里面 ...

对啊,非常同意你这个改法,只要在每一次对(i + 1, j + 1)取min的时候同时考虑(i + 1, j)就可以了,这样最后的dp(i + 1, j + 1)直接跟N比就是要的结果了,没有必要再扫一遍s
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 21:57

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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