一亩三分地论坛

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

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

Zocdoc Intern Skype面试差点和面试官吵起来了

[复制链接] |试试Instant~ |关注本帖
cyx32524 发表于 2016-3-8 11:40:16 | 显示全部楼层 |阅读模式

2015(1-3月) 码农类 本科 实习@Zocdoc - 网上海投 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
Zocdoc是一家做web端和app端预约医生的公司。我应该是在网上海投的,然后前几天接到了hr面试,hr照例先介绍了一下公司情况和intern program,然后问了那个移除重复数字怎么办的问题(hashset),接着开始让我吹自己的project,快结束的时候让我问问题并且告诉我马上就可以和我约电面时间。于是,约到了今天。。
下午1点准时有人在Skype发消息,问我准备好了没有,答曰“sure”,然后Skype视频开始:

首先出现一个几乎无口音的印度小哥,他介绍了一下自己,又让我调试了一下摄像头,搞好了之后他突然往右边一坐,请出了一个ABC,从此再也没有说过一句话,后来我才知道原来印度哥是shadow。后面的流程先是abc介绍了一下公司,情况是成立了7、8年,用C#的,公司就两个产品:web和app,有70来个工程师,分15个team,其中只有6个team准备招有且只有1个实习生,也就是说,他们只招6个实习生。然后让我介绍了一下我的project,我没有吹逼,他们听了我蹩脚的英语以及转专业人做的freshmen level的project表示并不感兴趣,随便问了几个问题,cool了一下就进入coding。.1point3acres缃

coding只有一道题,题目背景(剧情)有点长,让他重讲了一遍才明白,输入是{"a.jpg", "b.jpg", "a.thb", "c.thb"},要求返回所有没有对应.jpg文件的.thb文件,因此这里要返回的就是{"c.thb"} (a.thb 有对应的 a.jpg,不用返回)。理解了题意就好说了,我说调用String.split把a.jpg分成name (a)和后缀 (jpg),用hashmap<name, Entry>存。其中class Entry { boolean hasJPG, boolean hasTHB }。先扫一遍list把数据存到map里面,再扫一遍map.keySet(),检查是否有Entry的hasJPG == false && hasTHB == true,有的话通过name + ".thb"重建出thb的文件名,放到arraylist里面返回。

写完代码之后问了时间复杂度,我说O(n),小哥让我解释,我就对着两个for loop逐行说了一下每个函数调用的时间复杂度。小哥又问了空间复杂度,我说O(n),然后他问我如何更快更小,我说不可能,至少要看一遍每一个输入吧,worst case就是全删,总要O(n)空间吧。然后他说其实你的时间复杂度是O(n+m),m是每个文件名的长度。我没想到还要考虑m,但是识破了他又在给我挖坑,于是我说应该是O(n*m),他假装恍然大悟,的确是O(n*m),然后说那你优化一下吧~
. 1point 3acres 璁哄潧

我不知道怎么优化,觉得这个面试官一点都不厚道,因为返回的Arraylist里面总要存一下名字吧,所有file都要返回就是n*m少不了了,于是我问那我能不能直接在输入的list里面删掉不需要返回的file,然后这个list里面的元素就都是要返回的东西,他奸猾地说好啊,那你试试吧。我靠,我当然知道list remove是O(n)的操作,他又想要看着我往坑里跳,然后我就说,我要assume输入的list是doubly linkedlist,我第一遍循环的时候把每个node的指针也存到map里面去,然后就可以O(1)的时间拿到这个节点,O(1)的时间remove。然后这个abc肯定没刷过LRU,不知道还能这样搞,他认真地想了一下,好像可行,说那你要这样写吗?这个方法有点麻烦,我担心我漏考虑了什么问题,这小哥又喜欢挖坑,于是我说万一输入不是doubly linkedlist我的解法就不行了,算了,我还是再想想别的方法吧。。。

想了一下,还是没有头绪,他开始提示Java的String是比较特殊的immutable,我表示对呀,String cancatenation的时候不是append而是创建了一个新String,但是我没懂你真正想说什么。然后他也没耐心了,直接说我通过name + ".thb"重建出thb的文件名这一行复杂度太高,这样深拷贝一个东西返回是O(n*m),而你要存指针。我说我印象中arraylist.add本身就是一个深拷贝的操作,你这样搞可能没用,能不能我要查一下document确认一下,他说assume你不用考虑add操作这个,我当时就要爆炸了,你让我优化居然是基于你的一个assumption。我说好啊,那来呗,Entry里面加一个String域thb,put的时候放进去,最后存结果的arraylist add的时候取这个Entry.thb,O(n)了。至此面了四十多分钟了,小哥说好的,时间差不多了,你有什么问题,我问了两个就结束了。


后来我试了一下,arraylist.add并不是深拷贝,小哥的方法是对的,是我学的不扎实太狂妄了。其实刷leetcode的时候dfs经常写的res.add(new ArrayList<>(tmp))就是要手动深拷贝一下,当时我比较生气我也没有想起来。


这次面试居然差点和面试官吵起来了,实在是太有趣了,哈哈哈哈,让我学到了一些道理,有理由记录一下。我生气主要是因为1. 我自以为处理corner case,封装helper函数,随手写注释都挺认真的,小哥对我这些处理却反应很冷淡。2. 老是给我挖坑 3. 我误以为其实不能优化,却非要让我优化。由于是摄像头,我生气他也看得出来,而我觉得他的情绪也不太好。其实这些都是芝麻大点事,何必太计较,45分钟面个试而已。。而且,看得出面试官还是比我厉害多了,以后要继续踏实学习,哈哈。

评分

2

查看全部评分

warriorbrant 发表于 2016-3-8 11:45:20 | 显示全部楼层
看标题进来的
回复 支持 反对

使用道具 举报

sz432 发表于 2016-3-8 12:46:43 | 显示全部楼层
说的太有道理了! 除了最后你感觉面试官比你厉害那里,全部赞同! 加油!
回复 支持 反对

使用道具 举报

mgnhjkl 发表于 2016-3-8 13:49:04 | 显示全部楼层
String那里我觉得他是暗示你用StringBuffer。。= =
回复 支持 反对

使用道具 举报

mclover 发表于 2016-3-8 14:12:29 | 显示全部楼层
同意楼上,小哥应该就是希望你用个StringBuilder而不是new一个String再放回去
回复 支持 反对

使用道具 举报

 楼主| cyx32524 发表于 2016-3-8 21:34:11 | 显示全部楼层
mgnhjkl 发表于 2016-3-8 13:49
String那里我觉得他是暗示你用StringBuffer。。= =

噢,我没描述好,应该是要用Entry里面存对象的方法的:
. from: 1point3acres.com/bbs
要想O(n)时间复杂度的话,就只能把输入list里面的对象存一下,然后返回那个对象,这样的存取一下“指针”是O(1)的时间。用StringBuilder的话,append和toString的时间都与字符串长度m有关吧,总的时间复杂度还是O(n*m)了。
回复 支持 反对

使用道具 举报

 楼主| cyx32524 发表于 2016-3-8 21:34:20 | 显示全部楼层
mclover 发表于 2016-3-8 14:12
同意楼上,小哥应该就是希望你用个StringBuilder而不是new一个String再放回去

噢,我没描述好,应该是要用Entry里面存对象的方法的:

要想O(n)时间复杂度的话,就只能把输入list里面的对象存一下,然后返回那个对象,这样的存取一下“指针”是O(1)的时间。用StringBuilder的话,append和toString的时间都与字符串长度m有关吧,总的时间复杂度还是O(n*m)了。
回复 支持 反对

使用道具 举报

 楼主| cyx32524 发表于 2016-3-8 21:35:12 | 显示全部楼层
sz432 发表于 2016-3-8 12:46
. visit 1point3acres.com for more.说的太有道理了! 除了最后你感觉面试官比你厉害那里,全部赞同! 加油!

66666666
回复 支持 反对

使用道具 举报

chuyahui 发表于 2016-3-8 22:04:34 | 显示全部楼层
其实楼主不用太激动,我看那个小哥没多少恶意。relax。。。
回复 支持 反对

使用道具 举报

wuashuai 发表于 2016-3-9 00:40:27 | 显示全部楼层
楼主很强啊
回复 支持 反对

使用道具 举报

william_gong 发表于 2016-3-9 04:02:09 | 显示全部楼层
鑫爷居然也有爆炸的时候。。。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 14:56

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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