一亩三分地论坛

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

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

TripAdvisor面经 OA+phone

[复制链接] |试试Instant~ |关注本帖
jacgraphy 发表于 2014-11-22 05:47:03 | 显示全部楼层 |阅读模式

2014(10-12月) 码农类 硕士 全职@TripAdvisor - 网上海投 - 技术电面 在线笔试 |Fail

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

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

x
10月份开始面的,当时直接网申的, 投的是daodao.com组的职位。先在codility上做了OA,然后两轮电面。其实很早就被拒了,一直很忧桑,今天想想还是把题发上来说不定对大家有用。

OA 两道题:.1point3acres缃
1. longest left or right path
鏉ユ簮涓浜.涓夊垎鍦拌鍧.     在codility上做过OA的应该都挺熟悉的,经常出现,就是返回二叉树中最长的单向路径的长度。
2. SQL query. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
    具体不太记得了,需要用到group by,order by
. 1point3acres.com/bbs
电面第一轮:. Waral 鍗氬鏈夋洿澶氭枃绔,
1. java里,String s = "abc" 和 String s = new String("abc") 有什么区别
2. boolean isSubstring(String s, String p)
    检查p是不是s的字串,p中可能会有 “*”,“*”表示0个或多个任意字符

电面第二轮:
CountingSquares.jpg
.1point3acres缃
如图的网格,会少掉一些边,要求其中正方形的个数。对于这个图的情况有16个正方形。自定义网格作为输入数据的结构。


补充内容 (2014-11-21 17:19):
非常抱歉!电面第一轮第二题,输入参数应该是char[] s和char[] p,其实就是不能用String的方法

评分

2

查看全部评分

本帖被以下淘专辑推荐:

  • · TA|主题: 9, 订阅: 0
hno3 发表于 2015-1-2 04:25:21 | 显示全部楼层
问问 楼主第二题是什么图啊,没有权限打不开。。。
回复 支持 反对

使用道具 举报

 楼主| jacgraphy 发表于 2015-1-2 05:39:28 | 显示全部楼层
hno3 发表于 2015-1-1 15:25
问问 楼主第二题是什么图啊,没有权限打不开。。。

这个可以吗? http://smilepls.com/pictures/fil ... mber_of_squares.jpg
回复 支持 反对

使用道具 举报

hno3 发表于 2015-1-2 07:46:11 | 显示全部楼层
jacgraphy 发表于 2015-1-2 05:39
这个可以吗? http://smilepls.com/pictures/files/2013/01/count_the_number_of_squares.jpg

可以了 谢谢楼主啦!!!
回复 支持 反对

使用道具 举报

hno3 发表于 2015-1-2 07:59:07 | 显示全部楼层
第二题好难啊,一点思路都没有,除了BF,楼主是怎么做的啊?
回复 支持 反对

使用道具 举报

 楼主| jacgraphy 发表于 2015-1-2 09:16:04 | 显示全部楼层
hno3 发表于 2015-1-1 18:59
-google 1point3acres第二题好难啊,一点思路都没有,除了BF,楼主是怎么做的啊?

面试的时候只想到硬搜,后来才知道应该是DP。. more info on 1point3acres.com
输入网格的表示方法我用的是有个二位数组,每个数表示一个格子,然后相连的格子用同一个数。
大致就是建一个boolean数组 dp[n][n][n][2],然后 dp[j][k][0] 表示以(i, j)为右端点,(i, k)为左端点的边能否作为一个正方形的上边;dp[j][k][1]就表示以(i, j)为下端点,(k, j)为上端点的边能否作为一个正方形的左边。转移方程就是 dp[j-1][k][0] -> dp[j][k][0],dp[i-1][j][k][1] -> dp[j][k][1],O(n^3) 。
然后再扫一边所有格子,以每个格子作为正方形的右下顶点,看能找到多少个正方形,O(n^3) 。.鏈枃鍘熷垱鑷1point3acres璁哄潧
所以总共时间O(n^3),空间O(n^3),如果原来的硬搜的话时间就要O(n^4)了。

补充内容 (2015-1-1 20:17):
好像有些【i】都被吞了= =
dp【i】[j-1][k][0] -> dp【i】[j][k][0],dp[i-1][j][k][1] -> dp【i】[j][k][1]
回复 支持 反对

使用道具 举报

hno3 发表于 2015-1-4 13:51:20 | 显示全部楼层
jacgraphy 发表于 2015-1-2 09:16. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
面试的时候只想到硬搜,后来才知道应该是DP。
输入网格的表示方法我用的是有个二位数组,每个数表示一个 ...

慢慢体会一下,没想到电面出这么难得题目,谢谢楼主码了这么多,嘿嘿!
回复 支持 反对

使用道具 举报

nibuxing 发表于 2015-3-11 06:34:30 | 显示全部楼层
请问楼主daodao组面你的是谁啊,听说他们组面人都用中文。。。还有是不是主要就考算法。。。
回复 支持 反对

使用道具 举报

 楼主| jacgraphy 发表于 2015-3-11 11:24:07 | 显示全部楼层
nibuxing 发表于 2015-3-10 17:34
请问楼主daodao组面你的是谁啊,听说他们组面人都用中文。。。还有是不是主要就考算法。。。

具体谁已经不太记得了。一面直接是中文,二面好像是ABC,用的英语。应该基本上都是算法题吧。
回复 支持 反对

使用道具 举报

nibuxing 发表于 2015-3-11 11:37:27 | 显示全部楼层
jacgraphy 发表于 2015-3-11 11:24
具体谁已经不太记得了。一面直接是中文,二面好像是ABC,用的英语。应该基本上都是算法题吧。

好的,谢谢,我马上也要面了,也是这个组。。。希望能过
回复 支持 反对

使用道具 举报

 楼主| jacgraphy 发表于 2015-3-11 11:43:58 | 显示全部楼层
nibuxing 发表于 2015-3-10 22:37
好的,谢谢,我马上也要面了,也是这个组。。。希望能过

加油,祝好运!
回复 支持 反对

使用道具 举报

nibuxing 发表于 2015-3-13 03:49:32 | 显示全部楼层
我醉了,两道题和楼主一模一样。.1point3acres缃
问一下一面两道题楼主都怎么答的。. 1point 3acres 璁哄潧
我第二题当场写了一个方法。。。自己都觉得不对。。。考官都惊呆了我的递归写法。。。
回复 支持 反对

使用道具 举报

 楼主| jacgraphy 发表于 2015-3-13 11:33:56 | 显示全部楼层
nibuxing 发表于 2015-3-12 14:49
我醉了,两道题和楼主一模一样。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
问一下一面两道题楼主都怎么答的。
我第二题当场写了一个方法。。。自己 ...

第一问我记得好像是s = "abc" 是保存在一个叫intern pool的区域里的,然后所有用这种方式申明的"abc"都实际指向这同一个字符串,如果用new的话就算字符串内容一样但每一个都不是同一个。
第二问我当时写得也不顺。基本上就是拿模式串里每一段不带"*"的子串和上一次匹配剩下的目标串比较找匹配的字串。后来想了下,还可以用kmp优化下。
回复 支持 反对

使用道具 举报

nibuxing 发表于 2015-3-13 11:53:04 | 显示全部楼层
jacgraphy 发表于 2015-3-13 11:33. more info on 1point3acres.com
第一问我记得好像是s = "abc" 是保存在一个叫intern pool的区域里的,然后所有用这种方式申明的"abc"都实 ...

这个pool我没答出来,其他都一样。
第二问你的方法也和我很类似,哈哈,等结果吧~
楼主现在有哪家offer了不
回复 支持 反对

使用道具 举报

 楼主| jacgraphy 发表于 2015-3-13 15:19:51 来自手机 | 显示全部楼层
nibuxing 发表于 2015-3-12 22:53
这个pool我没答出来,其他都一样。
第二问你的方法也和我很类似,哈哈,等结果吧~
楼主现在有哪家offer ...

其实我已经入职了…
回复 支持 反对

使用道具 举报

nibuxing 发表于 2015-3-13 22:34:58 | 显示全部楼层
jacgraphy 发表于 2015-3-13 15:19
其实我已经入职了…

棒棒的
TA的二面楼主是多少天后收到通知的啊
回复 支持 反对

使用道具 举报

苏DsL 发表于 2015-3-14 05:52:35 | 显示全部楼层
请问lz,第一面第二题是不是跟leetcode里面正则表达式匹配得题差不多呀?
回复 支持 反对

使用道具 举报

 楼主| jacgraphy 发表于 2015-3-14 06:28:25 来自手机 | 显示全部楼层
nibuxing 发表于 2015-3-13 09:34
棒棒的. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
TA的二面楼主是多少天后收到通知的啊

大概一周左右吧
回复 支持 反对

使用道具 举报

 楼主| jacgraphy 发表于 2015-3-14 06:30:01 来自手机 | 显示全部楼层
苏DsL 发表于 2015-3-13 16:52
请问lz,第一面第二题是不是跟leetcode里面正则表达式匹配得题差不多呀?

应该比那个简单吧。这个只有"*",而且是找子串不需要全匹配
回复 支持 反对

使用道具 举报

nibuxing 发表于 2015-3-14 06:38:42 | 显示全部楼层

好的,谢谢回答!坐等
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-3 08:56

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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