一亩三分地论坛

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

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

google面经 intern. Feb1

[复制链接] |试试Instant~ |关注本帖
CraigHe 发表于 2016-2-2 04:05:02 | 显示全部楼层 |阅读模式

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

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

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

x
第一次发帖,回馈地里! 大家一起加油!. from: 1point3acres.com/bbs
本人博士二年级在读,找暑期实习,刚刚面试完。
题目感觉很简单。。。。但是我理解上出了点问题导致花了点时间。. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
第一个:
1.两个数组找intersection,两个数组是sorted.  
. visit 1point3acres.com for more.2. 一个binary tree, 有一个节点的child指向了 树中的另一个节点,把这个binary tree恢复成valid的binary tree.
这两个问题之前有一些很简单的复杂度的问题.

第二个:
1. 判断一个string是不是palindrome. 有空格和逗号之类的,都忽略。
2. 给一个string, 把它reoreder成一个palindrome. 我这道题煞笔了,我以为要返回所有的可能的palindrome.实际上只要一个.... 所以就很简单了,结果我把搜索的函数写完才发现其实只要一个。如果不能把它reorder成一个palindrome的话就return一个空string. 他给的例子. visit 1point3acres.com for more.
“220” -> “202”
“civic” -> “civic” or “icvci”
“hello” -> “”
“abbaaba” -> “aabbbaa” or “abababa”
这些都是可以的。
[size=13.3333px]然后就没什么时间了。。

评分

2

查看全部评分

本帖被以下淘专辑推荐:

sheepmiemies 发表于 2016-2-5 08:55:31 | 显示全部楼层
一岁上山采药 发表于 2016-2-5 04:15
请问楼主第一个第二问和第二个第二问怎么做呢?可不可以请楼主给点思路。谢谢楼主

以下是个人想法,仅供参考 :)
一轮二问:做一遍BFS,把每个node存在一个hashmap里。存之前先检查是否已经存在,已经存在说明这个异常的点找到了。(个人假设)如果只要求修复成valid binary tree,那其实并不用管是哪个异常,直接把后一个的异常child置为null即可;如果是BST,那就在check一下和子节点的大小关系再决定update哪一个。
.1point3acres缃
二轮二问:用一个hashmap保存每个字符出现的个数。然后扫描一遍hashmap,如果单数个的字符出现超过两个,则返回空;否则就可以开始构造了,奇数个的字符全放中间,然后两边依次放偶数个的字符。
回复 支持 1 反对 0

使用道具 举报

kinggarden2001 发表于 2016-2-2 06:38:01 | 显示全部楼层
第一个的第二题能再解释一下吗?
回复 支持 反对

使用道具 举报

sheepmiemies 发表于 2016-2-2 07:04:44 | 显示全部楼层
第二部分确实有点可惜。。不过没关系,下次别的面试先讨论清楚就没问题了!感觉LZ实力没问题,就是需要和面试官多交流,offer肯定滚滚来!
顺便想请问下LZ, 第一部分tree那道题,相当于是两个分支相交了吧,那是直接把异常的那个child的异常指针置为null么?
回复 支持 反对

使用道具 举报

johnjavabean 发表于 2016-2-2 08:17:17 | 显示全部楼层
全部都是lc原题...第一面第二题有点难是个hard....感觉phd intern问的题是比master要简单...可能主要是看中research经历,算法看的不是太重.1point3acres缃
回复 支持 反对

使用道具 举报

johnjavabean 发表于 2016-2-2 08:18:14 | 显示全部楼层
另外我是明天面...现在慌得不行....
回复 支持 反对

使用道具 举报

johnjavabean 发表于 2016-2-2 08:19:09 | 显示全部楼层
估计楼主第二面第二题做的快点会followup一个输出所有合法palindrome
回复 支持 反对

使用道具 举报

johnjavabean 发表于 2016-2-2 10:28:39 | 显示全部楼层
sheepmiemies 发表于 2016-2-2 07:04
第二部分确实有点可惜。。不过没关系,下次别的面试先讨论清楚就没问题了!感觉LZ实力没问题,就是需要和面 ...

这个题我有点没懂啊,如果一个child指针指到别处,那这个child不是永远找不到了么...还怎么还原
回复 支持 反对

使用道具 举报

 楼主| CraigHe 发表于 2016-2-2 12:22:24 | 显示全部楼层
sheepmiemies 发表于 2016-2-2 07:04
第二部分确实有点可惜。。不过没关系,下次别的面试先讨论清楚就没问题了!感觉LZ实力没问题,就是需要和面 ...

恩 其实第二部分也写完了 他要返回一个我就直接把search函数给注释掉了。。。然后跟他说如果要所有的话就跑一下search。  . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
对,tree的那道题就是两个分支相交,只要找到,然后把一个置为NULL就行了。
回复 支持 反对

使用道具 举报

 楼主| CraigHe 发表于 2016-2-2 16:04:11 | 显示全部楼层
sheepmiemies 发表于 2016-2-2 07:04
第二部分确实有点可惜。。不过没关系,下次别的面试先讨论清楚就没问题了!感觉LZ实力没问题,就是需要和面 ...

第二部分其实当时写完然后跟他说了 然后我就把那个search函数注释掉了...
tree这道题就是那样,只要找到了 然后把它置为NULL就行了

补充内容 (2016-2-2 16:05):
晕 我还以为我之前回的那个没回成功。。。好吧  两次。。
回复 支持 反对

使用道具 举报

 楼主| CraigHe 发表于 2016-2-2 16:06:49 | 显示全部楼层
johnjavabean 发表于 2016-2-2 10:28
这个题我有点没懂啊,如果一个child指针指到别处,那这个child不是永远找不到了么...还怎么还原

就是一个node的child指到另一个node了,你可以认为就是一个binary tree, 然后有两个node的child都指到了同一个点,然后你只要把其中一个置成NULL就行了
回复 支持 反对

使用道具 举报

johnjavabean 发表于 2016-2-2 16:11:01 | 显示全部楼层
CraigHe 发表于 2016-2-2 16:06
就是一个node的child指到另一个node了,你可以认为就是一个binary tree, 然后有两个node的child都指到了 ...
. 鍥磋鎴戜滑@1point 3 acres
楼主能详细讲讲怎么做吗,怎么找到指向相同节点的两个节点?
回复 支持 反对

使用道具 举报

sheepmiemies 发表于 2016-2-4 07:14:40 | 显示全部楼层
CraigHe 发表于 2016-2-2 16:04
第二部分其实当时写完然后跟他说了 然后我就把那个search函数注释掉了...
.鐣欏璁哄潧-涓浜-涓夊垎鍦tree这道题就是那样,只要找到 ...

哈哈,谢谢LZ的热心解答~
回复 支持 反对

使用道具 举报

sheepmiemies 发表于 2016-2-4 07:20:06 | 显示全部楼层
johnjavabean 发表于 2016-2-2 10:28. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
这个题我有点没懂啊,如果一个child指针指到别处,那这个child不是永远找不到了么...还怎么还原
. visit 1point3acres.com for more.
如果之前有人解释了就当我没说哈。
. From 1point 3acres bbs
这里题的意思应该是这个异常child node的某一个指针本来应该是null(如果是别的subtree现在已经找不到了额。。。。),但是现在被指向了某一个节点。我们的任务就是找到这个异常node并且把该指针置为null
回复 支持 反对

使用道具 举报

johnjavabean 发表于 2016-2-4 12:11:24 | 显示全部楼层
sheepmiemies 发表于 2016-2-4 07:20
如果之前有人解释了就当我没说哈。

这里题的意思应该是这个异常child node的某一个指针本来应该是null ...

我confuse的就是这一点...如果是这样那不是说这个应该一定是叶子节点吗...
回复 支持 反对

使用道具 举报

sheepmiemies 发表于 2016-2-4 14:29:39 | 显示全部楼层
johnjavabean 发表于 2016-2-4 12:11
我confuse的就是这一点...如果是这样那不是说这个应该一定是叶子节点吗...

不一定非要是叶子节点啊,他可能是一个中间节点,但原本只有一个child,另一个是null
回复 支持 反对

使用道具 举报

一岁上山采药 发表于 2016-2-5 04:15:22 | 显示全部楼层
请问楼主第一个第二问和第二个第二问怎么做呢?可不可以请楼主给点思路。谢谢楼主
回复 支持 反对

使用道具 举报

一岁上山采药 发表于 2016-2-5 10:11:31 | 显示全部楼层
sheepmiemies 发表于 2016-2-5 08:55
以下是个人想法,仅供参考 :)
一轮二问:做一遍BFS,把每个node存在一个hashmap里。存之前先检查是否已 ...

哦,有道理有道理,谢谢层主,感谢解答。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 01:46

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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