一亩三分地论坛

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

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

Pocket Gems summer intern一面

[复制链接] |试试Instant~ |关注本帖
wm_thu 发表于 2015-3-14 12:06:27 | 显示全部楼层 |阅读模式

2015(7-9月) 码农类 硕士 实习@Pocket Gems - 网上海投 - 技术电面 |Pass

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

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

x
今天的新鲜面经:phone screen面试,一共问了两道题:
1. leetcode上的原题 strStr(). 然后问了时间复杂度(还问你这是最好,平均,还是最坏?),然后要给出一个能触发最坏运行时间的例子。以往的两篇面经中都能见到这个题,不多解释。
2. parse一个字符串表示的三元表达式,输出一个树结构。三元表达式中不含括号,每个变量名都是一个字母,并且保证合法。例如:
a?b:c a?b?c:d:e a?b:c?d:e  
   a / \. From 1point 3acres bbs
b   c
     a   / \
  b   e
/ \
c   d
    a  / \
b   c
    / \
   d   e
其实一开始蒙圈了。。因为从没见过,所以很慌,总感觉跟上学期编译原理里讲的parser是一样的,努力回忆parser算法。。。。后来什么也没想起来,因为当初编程实现都是用yacc做的==
于是这才开始真正用心思考这个题目本身。很快想到得用递归了,然后有两个要点:
第一,字符串的开头一个字母一定是root。
第二,去掉root后,剩下的怎么切分成左子树和右子树呢?这里的关键是找到和第一个"?"相匹配的":"。后来发现其实就是很括号匹配一样的道理:见到"?"压栈;见到":"弹栈,弹出来的"?"和这个":"对应。
于是呼隆呼隆写完,然后interviewer要分析最坏时间复杂度。首先列出最坏情况:. 1point3acres.com/bbs
a ? (...) : b
再列出最坏情况的递归表达式 T(n) = 2 * T(n - 4),因为中间括号部分长度是n - 4,而且匹配":"时遍历了一遍,然后递归又遍历了一遍。这时 T(n) = O(2^n)。
然后问能不能优化,这才发现中间部分遍历了两次,所以应该一开始遍历就用hash table存下所有的 ? : 匹配关系,然后再遍历一遍,常数时间就能找到每个子树的起止点了。这样总复杂度是O(n)。这里就没让写代码,因为来不及了,只这样说了下思路。


最后一点时间介绍了一下公司情况。这家是做ios端手游的,一个游戏有一个team。然后还有一个team管后端服务器,虽然用python但是框架都是很老掉牙的,不是很有前途的样子。尽管我说没有ios开发经验,但是面试官还是鼓励说确实很多实习生没有Objective-C的经验,但是来学一学很容易上手的,我也顺势表示很喜欢学新东西((⊙o⊙)…swift才是新版不是吗==)。


==============================
第二题是我第一次在面试里遇到没见过的题,之前面过的都是leetcode上有的题。
这次经验告诉我,遇到没做过的题目,千万不要胡乱联想然后精力投入到回忆当中不可自拔==静下心来研究题目本身,有任何思路有先讲出来,实在不行问interviewer要hint,上面我说的第二个要点就是和interviewer讨论的时候忽然想清楚的。总之,don't panic。
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
==============================
下午四点(EDT)的面试,结果晚上六点就收到二面通知了。二面不知道会不会更难。希望自己好运,也祝各位看到这篇面经的人好运。
这个时候还没有实习Offer的小伙伴(我也是其中一员)可能都很焦急,但是别丧气,继续努力一定会有结果。一句话与大家共勉:不是因为有希望才去坚持,而是因为坚持才有希望。




-google 1point3acres




评分

2

查看全部评分

xianliang 发表于 2015-3-20 02:02:20 | 显示全部楼层
楼主,intern需要onsite么?
回复 支持 反对

使用道具 举报

 楼主| wm_thu 发表于 2015-3-20 05:56:48 | 显示全部楼层
xianliang 发表于 2015-3-20 02:02
楼主,intern需要onsite么?

他们说的第二轮或者是电面或者onsite。
我不住加州,所以第二轮是电面。
回复 支持 反对

使用道具 举报

bsbcarter 发表于 2015-3-29 01:15:56 | 显示全部楼层
楼主二面怎么样了啊 面完之后求面经啊!!
回复 支持 反对

使用道具 举报

bsbcarter 发表于 2015-3-29 01:54:06 | 显示全部楼层
以及他们家intern满了吗?我下周一轮电面 他通知我的时候并没有说是intern
回复 支持 反对

使用道具 举报

 楼主| wm_thu 发表于 2015-3-29 07:55:45 | 显示全部楼层
bsbcarter 发表于 2015-3-29 01:15
楼主二面怎么样了啊 面完之后求面经啊!!
-google 1point3acres
二面的两题在其他同学的帖子里提到了~ Sort Colors 和 find next largest node in BST
后来两面都结束了,recruiter跟我打电话,我犯傻拒掉了他家。。所以现在的情况就不知道了。
回复 支持 反对

使用道具 举报

bsbcarter 发表于 2015-3-29 10:25:02 | 显示全部楼层
wm_thu 发表于 2015-3-29 07:55
二面的两题在其他同学的帖子里提到了~ Sort Colors 和 find next largest node in BST
后来两面都结束了 ...

楼主是说这两面之后就是要给你offer了是吗?
回复 支持 反对

使用道具 举报

 楼主| wm_thu 发表于 2015-3-30 23:40:59 | 显示全部楼层
bsbcarter 发表于 2015-3-29 10:25. 1point 3acres 璁哄潧
楼主是说这两面之后就是要给你offer了是吗?

应该是的
回复 支持 反对

使用道具 举报

黑眼豆豆 发表于 2015-4-10 08:47:14 | 显示全部楼层
请问楼主是两面之后是多久收到结果的呢~~~

补充内容 (2015-4-10 13:35):.1point3acres缃
intern就两面吗?
回复 支持 反对

使用道具 举报

黑眼豆豆 发表于 2015-4-10 13:32:55 | 显示全部楼层

请问楼主是两面之后是多久收到结果的呢~~~
回复 支持 反对

使用道具 举报

aloncgo 发表于 2015-4-10 14:08:13 | 显示全部楼层
黑眼豆豆 发表于 2015-4-10 13:32
请问楼主是两面之后是多久收到结果的呢~~~
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
你才面了Pocket gems二面呀?  我这周一面,   一面题目和LZ一模一样。。。  求二面面筋呀
回复 支持 反对

使用道具 举报

gaohannk 发表于 2015-4-11 02:50:31 | 显示全部楼层
第二题是用Node构建一个Tree, 还是要print出树的形状。如果是构建树,要用两个stack,同时把结点压进去吧。
回复 支持 反对

使用道具 举报

gaohannk 发表于 2015-4-11 03:05:22 | 显示全部楼层
gaohannk 发表于 2015-4-11 02:50. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
第二题是用Node构建一个Tree, 还是要print出树的形状。如果是构建树,要用两个stack,同时把结点压进去吧 ...

代码是怎么写的呢?
回复 支持 反对

使用道具 举报

黑眼豆豆 发表于 2015-4-11 23:07:11 来自手机 | 显示全部楼层
aloncgo 发表于 2015-4-10 14:08
你才面了Pocket gems二面呀?  我这周一面,   一面题目和LZ一模一样。。。  求二面面筋呀

面了 和地里一样 就是sort color和bst 所有的代码应该都对了 面试官也很high的一直说correct 然后behavior还问了一下为什么选做游戏之类的 能看出面试官蛮高兴 但是隔了一天就发据信了 就是周五 好像周五晚上发了好多据信
回复 支持 反对

使用道具 举报

aloncgo 发表于 2015-4-13 02:17:26 | 显示全部楼层
黑眼豆豆 发表于 2015-4-11 23:07
面了 和地里一样 就是sort color和bst 所有的代码应该都对了 面试官也很high的一直说correct 然后behavio ...

我这里好几个同学也是周五Rej的

二面还没面就rej了  说招到人了
回复 支持 反对

使用道具 举报

liokumo 发表于 2015-4-13 02:34:43 | 显示全部楼层
aloncgo 发表于 2015-4-12 13:17. Waral 鍗氬鏈夋洿澶氭枃绔,
我这里好几个同学也是周五Rej的
.鐣欏璁哄潧-涓浜-涓夊垎鍦
二面还没面就rej了  说招到人了

都是面intern么?
回复 支持 反对

使用道具 举报

aloncgo 发表于 2015-4-13 02:47:04 | 显示全部楼层
liokumo 发表于 2015-4-13 02:34
都是面intern么?

我是intern
回复 支持 反对

使用道具 举报

 楼主| wm_thu 发表于 2015-4-13 06:16:13 | 显示全部楼层
黑眼豆豆 发表于 2015-4-10 13:32
请问楼主是两面之后是多久收到结果的呢~~~

大概一两天的样子就说会有HR跟我电聊了~
回复 支持 反对

使用道具 举报

wrj5518 发表于 2015-4-13 07:39:20 | 显示全部楼层
aloncgo 发表于 2015-4-10 14:08
你才面了Pocket gems二面呀?  我这周一面,   一面题目和LZ一模一样。。。  求二面面筋呀

这个逗比公司面了我一个读程序题,各种槽点,http://www.1point3acres.com/bbs/ ... 9&fromuid=39275

PS:你还在面intern?
回复 支持 反对

使用道具 举报

stevenlordiam 发表于 2015-4-14 09:13:32 | 显示全部楼层
请问建tree, a?b:c 这题怎么test的呢? 输入string 然后一行一行的打印出tree么?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 00:37

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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