一亩三分地论坛

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

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

TripAdvisor phone interview

[复制链接] |试试Instant~ |关注本帖
oneshot 发表于 2015-12-16 05:50:35 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 全职@TripAdvisor - 网上海投 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
  TripAdvisor的店面,最开始HR说用Skype面,告诉我名字看是个中国人。面试前五分钟面试官发来一封邮件,是一个白板的链接。 然后电话就打来了,一直电话聊的,没用Skype。
  面试官感觉很严肃的样子,问了一些背景之后就给了我一道题:http://matchstickpuzzles.blogspo ... w-many-squares.html,就是这道在一堆火柴摆成的矩形里面找一共有多少个矩形。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴


  我做的方法是把这个图形转换成了二元矩阵,int[][] matrix, 输入矩形的左下角在matrix[0][0]点,并且假设如果(i, j)是横竖两根火柴的交点,那么matrix[j] = 1, 其他的点都设为0。

  然后就开始DFS做的,对于每一个matrix[j]等于1的点,这个点可以组成矩形的条件是(i + len, j), (i, j + len), (i + len, j + len)这三个点的值同时都是1.

  大概写了半小时给他最终的答案,最开始我理解为数所有的矩形,所以len的长度写成(i + lenX, j), (i, j + lenY), (i + lenX, j + lenY), 他说了半天我才明白他想要的是四边相等的正方形,然后我就赶紧改,但是还是感觉他不是很开心......然后又问我这个方法的时间复杂度,我说是O(m * n^2), m是这个矩形里面一共有多少个交点,也就是matrix[j] = 1的个数,然后他问我那这个m, 矩形里面一共有多少个点啊,我当时脑袋一晕,直接告诉他有n平方的点,然后他发觉说,那你的时间复杂度就是n^4了。然后我居然没反应过来,也默认这个方法是n的4次方的time complexity了,就回了他一句,maybe......好想哭......


  后来又问了问有关的问题,具体在哪个组啊,每天的工作啊是什么的之类的,他还是好严肃的口气回答了我一下,= =,然后就挂电话了...

  印象中有人说这道题可以再加上DP的解法,当时就扫了一眼也没认真看,现在又找了一下那个帖子,然后没有找到...有没有哪位大神可以帮帮忙看下这道题如何做最好哎?也希望对后面的人如果面到这道题的话有所帮助,谢谢 !

  最后祝大家和我都好运多多,offer多多!

zhouyoung1124 发表于 2015-12-18 03:51:09 | 显示全部楼层
这题我上周贴过面经和O(N^3)的解法。。。。。。。。。。。
http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=158358&highlight=tripadvisor
回复 支持 反对

使用道具 举报

 楼主| oneshot 发表于 2015-12-18 03:52:39 | 显示全部楼层
zhouyoung1124 发表于 2015-12-18 03:51
这题我上周贴过面经和O(N^3)的解法。。。。。。。。。。。. From 1point 3acres bbs
http://www.1point3acres.com/bbs/forum.php?mo ...

噢对!之前还给你留言来着!谢谢大神啦!
回复 支持 反对

使用道具 举报

zhouyoung1124 发表于 2015-12-18 03:54:35 | 显示全部楼层
oneshot 发表于 2015-12-18 03:52
噢对!之前还给你留言来着!谢谢大神啦!

不客气 :-)
回复 支持 反对

使用道具 举报

 楼主| oneshot 发表于 2015-12-18 03:59:16 | 显示全部楼层

请问这周onsite了吗?进行的怎么样?我上周发了封邮件问HR然后告诉我电面没过杯具了...
回复 支持 反对

使用道具 举报

zhouyoung1124 发表于 2015-12-18 04:08:02 | 显示全部楼层
oneshot 发表于 2015-12-18 03:59
请问这周onsite了吗?进行的怎么样?我上周发了封邮件问HR然后告诉我电面没过杯具了...

明天onsite...惊慌中。。。求过求过
回复 支持 反对

使用道具 举报

 楼主| oneshot 发表于 2015-12-18 04:17:37 | 显示全部楼层
zhouyoung1124 发表于 2015-12-18 04:08
明天onsite...惊慌中。。。求过求过

哈哈,加油加油!!!offer属于你!!!
回复 支持 反对

使用道具 举报

zhouyoung1124 发表于 2015-12-18 04:31:32 | 显示全部楼层
oneshot 发表于 2015-12-18 04:17
哈哈,加油加油!!!offer属于你!!!
. more info on 1point3acres.com
借你吉言了
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 02:02

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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