一亩三分地论坛

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

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

Google 10/5 电话面试

[复制链接] |试试Instant~ |关注本帖
JessieLyu 发表于 2015-10-6 13:33:06 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 本科 全职@Google - 校园招聘会 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
今天刚刚面试的,题目不难但面试不太好,发个帖求onsite!
面试是个印度大哥,在Google工作了10年了。啥background都没问。我还问了他要不要talk about resume结果他说不用==
第一题很简单,pairwise swap nodes in linkedlist,就是如果1-》2-》3-》4,return就是2-》1-》4-》3。我先就是swap里面的data,5分钟就写完了。后来他说data很大。。。所以要改pointer,好吧,又写了个改pointer的。大概总共用了10分钟。然后讨论了一下这个题,check了一下edge case。总的来说比就顺。但是昨晚这个题就过去30分钟了。。。
第二题他说写个pseudo code或者algorithm就可以了。就是L是个contain“(” 活着“)”的language,然后括号要balanced,就是说()()或者(())是可以的,但是)()(是不可以的。pass进去的是string length,return符合language的这个长度的string的个数。LeetCode原题,但我没写,哭死了。。。我说了一个用啥stack的,写了下pseudo code,但是巨麻烦而且不一定work。印度大哥也没说什么只是说应该可以work。后来看了leetcode知道了做法简直后悔死。。。总之希望过了给个onsite就好了,或者再给一个phone让我弥补一下T T。做了15分钟吧。然后又和大叔聊了一下Google,表达我超级喜欢Google啥的,估计要跪。。。求人品求人品,求onsite啊!

评分

2

查看全部评分

本帖被以下淘专辑推荐:

cjlm007 发表于 2015-10-6 14:02:46 | 显示全部楼层
祝拿到onsite。
两题都是原题。第二个就是leetcode的Unique Binary Search Trees吧。
回复 支持 反对

使用道具 举报

zxy_snow 发表于 2015-10-6 14:05:41 | 显示全部楼层
https://leetcode.com/problems/longest-valid-parentheses/ 这个题么?
回复 支持 反对

使用道具 举报

zxy_snow 发表于 2015-10-6 14:07:10 | 显示全部楼层
cjlm007 发表于 2015-10-6 14:02
祝拿到onsite。
两题都是原题。第二个就是leetcode的Unique Binary Search Trees吧。

咦,为什么是这个题
回复 支持 反对

使用道具 举报

cjlm007 发表于 2015-10-6 14:20:21 | 显示全部楼层
zxy_snow 发表于 2015-10-6 14:07
咦,为什么是这个题

https://zh.wikipedia.org/wiki/%E ... 4%E5%85%B0%E6%95%B0. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
应该就是这个吧
回复 支持 反对

使用道具 举报

zxy_snow 发表于 2015-10-6 15:29:09 | 显示全部楼层
cjlm007 发表于 2015-10-6 14:20
https://zh.wikipedia.org/wiki/%E5%8D%A1%E5%A1%94%E5%85%B0%E6%95%B0
应该就是这个吧
. 鍥磋鎴戜滑@1point 3 acres
是的,这个数好神奇。。
回复 支持 反对

使用道具 举报

darkwowgamer 发表于 2015-10-11 01:15:22 | 显示全部楼层
cjlm007 发表于 2015-10-6 14:02
祝拿到onsite。
两题都是原题。第二个就是leetcode的Unique Binary Search Trees吧。

想了很久也没想明白为什么可以这么算出结果, 能给点思路吗? 感谢!~
回复 支持 反对

使用道具 举报

hackenkreuz 发表于 2015-10-11 02:09:41 | 显示全部楼层
zxy_snow 发表于 2015-10-6 14:05
https://leetcode.com/problems/longest-valid-parentheses/ 这个题么?

感觉应该是这题的变种. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
https://leetcode.com/problems/generate-parentheses/

只是返回组合的数目. Waral 鍗氬鏈夋洿澶氭枃绔,
回复 支持 反对

使用道具 举报

darkwowgamer 发表于 2015-10-11 03:03:54 | 显示全部楼层
hackenkreuz 发表于 2015-10-11 02:09
感觉应该是这题的变种
https://leetcode.com/problems/generate-parentheses/

那个应该不满足时间复杂度
回复 支持 反对

使用道具 举报

airwindow 发表于 2015-10-12 00:23:02 | 显示全部楼层
我能想到的是用dfs搜索,统计出所有可能的组合...但我觉得那样时间复杂度明显达不到要求...
求大神们明示啊...
回复 支持 反对

使用道具 举报

坐看云起 发表于 2015-10-13 02:47:11 | 显示全部楼层
airwindow 发表于 2015-10-12 00:23.鐣欏璁哄潧-涓浜-涓夊垎鍦
我能想到的是用dfs搜索,统计出所有可能的组合...但我觉得那样时间复杂度明显达不到要求...
求大神们明示 ...

我的理解是。。。
OPT = OPT[0] * OPT[i-1] + OPT[1] * OPT[i-2] + ... + OPT[i-1] * OPT[0]
其中,OPT[0] = 1, OPT[1] = 1
回复 支持 反对

使用道具 举报

darkwowgamer 发表于 2015-10-13 05:37:38 | 显示全部楼层
坐看云起 发表于 2015-10-13 02:47. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
我的理解是。。。
OPT = OPT[0] * OPT + OPT[1] * OPT + ... + OPT * OPT[0]
其中,OPT[0] = 1, OPT[1] ...

能讲讲思路吗?
回复 支持 反对

使用道具 举报

坐看云起 发表于 2015-10-13 06:43:14 | 显示全部楼层

对于N个括号,可以分为两组,然后组成 __ (__)的形式。就是说一部分在括号里,一部分在括号外。两组括号总计用了N-1个括号
回复 支持 反对

使用道具 举报

darkwowgamer 发表于 2015-10-13 08:01:39 | 显示全部楼层
坐看云起 发表于 2015-10-13 06:43
对于N个括号,可以分为两组,然后组成 __ (__)的形式。就是说一部分在括号里,一部分在括号外。两组括 ...
. Waral 鍗氬鏈夋洿澶氭枃绔,
豁然开朗! 果然就是Unique Binary Search Trees, 感谢!
回复 支持 反对

使用道具 举报

坐看云起 发表于 2015-10-13 08:08:59 | 显示全部楼层
darkwowgamer 发表于 2015-10-13 08:01. more info on 1point3acres.com
豁然开朗! 果然就是Unique Binary Search Trees, 感谢!

客气啦~
楼上那个提出Unique BST的人太牛了!
回复 支持 反对

使用道具 举报

darkwowgamer 发表于 2015-10-13 08:19:10 | 显示全部楼层
坐看云起 发表于 2015-10-13 08:08
客气啦~. 鍥磋鎴戜滑@1point 3 acres
楼上那个提出Unique BST的人太牛了!

是啊, 后面那个wiki链接也是让人大开眼界
回复 支持 反对

使用道具 举报

genonashi 发表于 2015-10-14 06:48:21 | 显示全部楼层
lz貌似和我是同一个人,最后有结果了吗?
回复 支持 反对

使用道具 举报

aiweiwei 发表于 2015-10-14 09:56:52 | 显示全部楼层
坐看云起 发表于 2015-10-13 06:43
对于N个括号,可以分为两组,然后组成 __ (__)的形式。就是说一部分在括号里,一部分在括号外。两组括 ...

为什么我的理解是 比如 string长度是6,那么就有三对括号,拿“(”来看,那么如果它是中心,可以有如下几种情况:1, 有两个“(”在中心左边  2. 有一个“(”在中心左边 另一个“(”在中心右边  3. 有两个“(”都在中心右边    然后也是卡特兰数那个可以接出来

不知道我这样理解对吗?
回复 支持 反对

使用道具 举报

darkwowgamer 发表于 2015-10-15 06:09:34 | 显示全部楼层
aiweiwei 发表于 2015-10-14 09:56
为什么我的理解是 比如 string长度是6,那么就有三对括号,拿“(”来看,那么如果它是中心,可以有如下 ...

我认为本质上是一样的, 他给的例子里的(_)就是你所说的中心
回复 支持 反对

使用道具 举报

lyq0930 发表于 2015-10-15 15:19:50 | 显示全部楼层
坐看云起 发表于 2015-10-13 06:43
对于N个括号,可以分为两组,然后组成 __ (__)的形式。就是说一部分在括号里,一部分在括号外。两组括 ...

不是很理解 __ (__)的形式,求解具体什么意思?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 06:59

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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