一亩三分地论坛

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

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

Dropbox已跪OA

[复制链接] |试试Instant~ |关注本帖
lijing2441 发表于 2015-9-9 09:44:44 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 全职@Dropbox - 网上海投 - 在线笔试 |Failfresh grad应届毕业生

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

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

x
刚刚跪了Dropbox。。。上来发一下,攒攒人品
从来木有见过的一道题。上来有点慌,后来发现是Word Search的变种。题目叫做Frenemy,就是说一坨n个关系有点复杂的人,有的一对人是Enemy,有的一对人是Friend,两个人不能又是朋友又是敌人。。然后他们之间的关系以一个Matrix来表示。然后给一个关系的string,问能不能从matrix中找出来,能找到返回1,不能找到返回0.

Example:
. more info on 1point3acres.com
Frenemy:
"-FE"
"F-E"
"EE-"

people: 0 and 2
relation: "FF"
output: 1

题目老大一坨,然后慌了七八分钟之后发现是Word Search, 就开始写。写完了还有不到二十分钟,很开心的放到IDE里面run了一下,跑通!答案对!
. more info on 1point3acres.com
然后交,然后发现12个test cases,最后两个过不去。。显示是Time Limit Exceeded,应该是两个大的dataset过不去,然后也不知道是什么dataset。然后加了各种优化,什么加boolean[][],把string转成char[],各种剪枝。。。都没用。然后还有40秒,放弃了。。。
. 1point 3acres 璁哄潧
上午做的,下午就来了一封没有Congrats的信 攒人品攒人品。。。



评分

5

查看全部评分

g56422 发表于 2015-12-24 10:36:27 | 显示全部楼层
完整題目:
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
Given a matrix of friend/enemy relationship between a group of people, your goal is to figure out if two individuals have a particular relationship chain (;friend of a friend;, ;enemy of a friend;) For example, consider when you have the following matrix of relationships, where F means ;friend of; and E means ;enemy of;, and an entry at (x,y) is the relationships between individual x and individual y: -FE F-F EF- In this example, individual 0 and individual 2 have a relationship chain E (eg. 0;;2), but they also have the relationship chains FF (0;;1;;2) and EFFE (0;;2;;1;;0;;2)l that is cycles of relationships are possible. These relationships have the following properties: 1. Being friends and enemies are symmetric, so if person A is friend with person B that implies that person B is also friends with Person A, similarly with enemies 2. A person cannot have a relationship to themself and so no relationshp chain will include 0;;0 3. The only valid relationships are F, E, or - (friend, enemy, or neither) Given a matrix of size n x n, the indices for 2 individuals, and a relationshp chain as a string, return 1 this relationshp exists between 2 people and 0 if otherwise. This is the boilerplate function, I had to write the code for: n = number of people frenemy is the relationship type x = index of person A y = index of person B relationship = def is_Frenemy(n, frenemy, x, y, relationship):

求解答 多謝
回复 支持 2 反对 0

使用道具 举报

leixiang5 发表于 2015-9-9 10:40:27 | 显示全部楼层
楼主的OA和我的不一样啊。。楼主节哀。。我之前看了你的帖子。今天面试uber考sudoku verifier.。。可惜没仔细看你的答案。。结果面试一堆傻逼。。累了。
回复 支持 反对

使用道具 举报

 楼主| lijing2441 发表于 2015-9-9 10:57:12 | 显示全部楼层
leixiang5 发表于 2015-9-9 10:40
楼主的OA和我的不一样啊。。楼主节哀。。我之前看了你的帖子。今天面试uber考sudoku verifier.。。可惜没仔 ...

这个题,貌似最近挺常考的。。
回复 支持 反对

使用道具 举报

leixiang5 发表于 2015-9-9 10:58:56 | 显示全部楼层
lijing2441 发表于 2015-9-9 10:57
这个题,貌似最近挺常考的。。
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
好吧。。只求再接再厉。。明天dropbox电面顺利。
回复 支持 反对

使用道具 举报

iorisli 发表于 2015-9-11 12:53:05 | 显示全部楼层
楼主我马上要做这个OA了。。能不能说详细点呢?0 和 2 的关系为什么是“FF” ? 这里为什么是两个F? 另外按照例子给的matrix, 0 和2 应该是 E 才对啊。。
回复 支持 反对

使用道具 举报

kelvinzhong 发表于 2015-9-12 02:33:48 | 显示全部楼层
iorisli 发表于 2015-9-11 12:53
楼主我马上要做这个OA了。。能不能说详细点呢?0 和 2 的关系为什么是“FF” ? 这里为什么是两个F? 另外 ...

楼上已经做了这题了吗? 求问问题目是怎么样子的呀?
回复 支持 反对

使用道具 举报

 楼主| lijing2441 发表于 2015-9-12 02:58:18 | 显示全部楼层
iorisli 发表于 2015-9-11 12:53
楼主我马上要做这个OA了。。能不能说详细点呢?0 和 2 的关系为什么是“FF” ? 这里为什么是两个F? 另外 ...

也可能是我记错了。。。不可以copy/paste的
回复 支持 反对

使用道具 举报

iorisli 发表于 2015-9-12 03:07:37 | 显示全部楼层
lijing2441 发表于 2015-9-12 02:58. from: 1point3acres.com/bbs
也可能是我记错了。。。不可以copy/paste的

楼主, 求问, matrix是给出了每个人和每个人之间的关系(F 或者 E), 那么这个问题具体是什么呢? 是给一串关系比如 FFFFEEEE, 然后问能不能从一个人出发, 经过若干个人(若干个关系), 满足这个关系序列?

这样就是dfs了, 超时很虚啊。。
回复 支持 反对

使用道具 举报

kelvinzhong 发表于 2015-9-12 04:01:53 | 显示全部楼层
iorisli 发表于 2015-9-12 03:07
楼主, 求问, matrix是给出了每个人和每个人之间的关系(F 或者 E), 那么这个问题具体是什么呢? 是给一 ...

我也感觉楼主是这个意思
回复 支持 反对

使用道具 举报

 楼主| lijing2441 发表于 2015-9-12 05:11:05 | 显示全部楼层
iorisli 发表于 2015-9-12 03:07.鏈枃鍘熷垱鑷1point3acres璁哄潧
楼主, 求问, matrix是给出了每个人和每个人之间的关系(F 或者 E), 那么这个问题具体是什么呢? 是给一 ...

. 鍥磋鎴戜滑@1point 3 acres是的。。。所以我也不知道为什么。。也可能是需要用DP之类的,或者pre-processing什么的吧。我至今未懂。
回复 支持 反对

使用道具 举报

 楼主| lijing2441 发表于 2015-9-12 05:11:27 | 显示全部楼层
kelvinzhong 发表于 2015-9-12 04:01
我也感觉楼主是这个意思

嗯嗯。没错。就是这个意思。。然后关系可以circle
回复 支持 反对

使用道具 举报

huanghe0828 发表于 2015-9-12 07:56:31 | 显示全部楼层
楼主啊
这道题要用bfs或者dp啊
boolean[][] dp = new dp[n][s.length()+1];
dp[start][0] = true;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
for (int j = 0; j <= s.length(); j++) {. Waral 鍗氬鏈夋洿澶氭枃绔,
   for (int i = 0; i < n; i++) {
      ....鏈枃鍘熷垱鑷1point3acres璁哄潧
   }
}
return dp[end][s.length()];
回复 支持 反对

使用道具 举报

kelvinzhong 发表于 2015-9-12 09:33:41 | 显示全部楼层
huanghe0828 发表于 2015-9-12 07:56
楼主啊
这道题要用bfs或者dp啊. 1point3acres.com/bbs
boolean[][] dp = new dp[n][s.length()+1];

bfs会比dfs快吗?不见得吧
回复 支持 反对

使用道具 举报

kelvinzhong 发表于 2015-9-12 09:52:50 | 显示全部楼层
lijing2441 发表于 2015-9-12 05:11
嗯嗯。没错。就是这个意思。。然后关系可以circle

有限制说经过的人必须是和上一个人是相邻的吗?
因为感觉如果不相邻而且可以circle的话,我觉得只要判断E是偶数还是奇数我就知道关系成不成立的啦?因为中间的过程是不影响的。
回复 支持 反对

使用道具 举报

huanghe0828 发表于 2015-9-12 11:34:34 | 显示全部楼层
kelvinzhong 发表于 2015-9-12 09:33
bfs会比dfs快吗?不见得吧

当然咯
bfs每一个level可以用HashSet储存可能的points
complexity是O(m*n)
dfs能达到吗?
回复 支持 反对

使用道具 举报

开水蛙 发表于 2015-10-3 12:41:00 | 显示全部楼层
有没有人能给出一个具体的代码啊?dfs之类的还是属于穷举,有没有更快的方法?
回复 支持 反对

使用道具 举报

ningo 发表于 2015-10-3 17:41:43 | 显示全部楼层
leixiang5 发表于 2015-9-9 10:40. Waral 鍗氬鏈夋洿澶氭枃绔,
楼主的OA和我的不一样啊。。楼主节哀。。我之前看了你的帖子。今天面试uber考sudoku verifier.。。可惜没仔 ...

有些题目就是初始解很容易写,一进入优化流程就各种蛋疼
回复 支持 反对

使用道具 举报

leixiang5 发表于 2015-10-4 00:33:24 | 显示全部楼层
ningo 发表于 2015-10-3 17:41
有些题目就是初始解很容易写,一进入优化流程就各种蛋疼

鏉ユ簮涓浜.涓夊垎鍦拌鍧. 其实他没要我优化。我只是没好好准备而已。学到了教训。。
回复 支持 反对

使用道具 举报

vivaroma 发表于 2015-12-19 14:39:13 | 显示全部楼层
楼主,这个跟word search不一样吧?

我觉得可以一个一个字母检查,比如“FF”,就从0开始,先让j循环一下,查 matrix[0][j]里面有没有F

然后把可能的j都加入queue,下一个“F”, 就查matrix[j][k]有没有F的

这样循环下去直到字符串最后一个字符能够配上2,return 1

楼主是这么做的么。。。
回复 支持 反对

使用道具 举报

yhfyhf 发表于 2015-12-23 11:36:17 | 显示全部楼层
huanghe0828 发表于 2015-9-12 07:56
楼主啊. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
这道题要用bfs或者dp啊
. 鍥磋鎴戜滑@1point 3 acresboolean[][] dp = new dp[n][s.length()+1];
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
能详细讲讲for循环里应该怎么写嘛?谢谢!
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 22:47

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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