一亩三分地论坛

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

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

推特的全职OA

[复制链接] |试试Instant~ |关注本帖
kolanery 发表于 2016-10-21 15:55:37 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 本科 全职@Twitter - 网上海投 - 在线笔试 |Otherfresh grad应届毕业生

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

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

x
刚做完Twitter OA,总共两题,第一题挺难的。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
1. Evaluate Expression Tree
Input: <expression tree> '/' <sequence of operations>

有两种Operations, reverse 'R'和simplify 'S'. 鍥磋鎴戜滑@1point 3 acres
The 'R' (reverse) operation means reverse the order of everything in the expression tree.
The 'S' (simplify) operation means remove the parenthesis around the very first element in the expression tree and in each of its sub-expression trees. The reason we would want to do this is typically the first element in an expression is a function, and the rest are its arguments, and its standard to consider an expression like '(f x) y' to mean the same thing as 'f x y'.

例子:
Input 1: (AB)C((DE)F)/S. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
Output 1: ABC(DEF)
Input 2: (AB)CDE/R. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
Output 2: EDC(BA)
注意可以有连续的Operation像RSR这样。

2. 和LC Unique path很像,可以走diagonally downward方向。

第一题最后一个case怎么也过不去求人品....



评分

2

查看全部评分

 楼主| kolanery 发表于 2016-10-24 16:43:26 | 显示全部楼层
pigeyes 发表于 2016-10-23 07:47
楼主能不能再解释下,
题目有指名给的String是expression tree的inorder traversal或preorder吗? 不然 ...

题目的input仅仅是一个String, 这题的题意是当你simplify的时候把它的sub-expression tree里第一个带括号的node去掉,比如上面这个例子:
(AB)C((DE)F) 可以根据括号分成
..|......\........\.鏈枃鍘熷垱鑷1point3acres璁哄潧
(AB) ... C... ((DE)F). 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
..................../.....\
.................(DE)....F. 1point 3acres 璁哄潧
然后simplify就去掉(AB)和(DE)的括号,结果是ABC(DEF)
我是去掉括号后递归加in-order重新建string
Reverse就是把树反过来. from: 1point3acres.com/bbs
额外两个例子:
Input: A(BC)/RSR   Output: A(BC) 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
Input: (AB)C(D((E)FG)H)   Output: ABC(D(EFG)H)

补充内容 (2016-10-24 16:45):
Sorry最后一行input是(AB)C(D((E)FG)H)/S.鏈枃鍘熷垱鑷1point3acres璁哄潧

补充内容 (2016-11-8 14:38):. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
Update: 没有过掉最后一个case就交了,然后就没有下文了...不过知道一个人也是这case没过却拿到了电面

评分

1

查看全部评分

回复 支持 3 反对 0

使用道具 举报

jiamuxeuer 发表于 2016-10-22 03:24:17 | 显示全部楼层
楼主您好,请问您是海投的,还是内推的呀?
回复 支持 反对

使用道具 举报

 楼主| kolanery 发表于 2016-10-22 05:34:47 | 显示全部楼层
jiamuxeuer 发表于 2016-10-22 03:24
楼主您好,请问您是海投的,还是内推的呀?
. from: 1point3acres.com/bbs
我是海投的
回复 支持 反对

使用道具 举报

jiamuxeuer 发表于 2016-10-22 22:37:37 | 显示全部楼层

谢谢您。可以再麻烦问一下,您是什么时候投的么?我在他家官网上没有找到new grad的职位啊?
回复 支持 反对

使用道具 举报

pigeyes 发表于 2016-10-22 23:06:40 | 显示全部楼层
Lz, 這input是个string?.1point3acres缃

补充内容 (2016-10-22 23:07):
第1道
回复 支持 反对

使用道具 举报

 楼主| kolanery 发表于 2016-10-23 00:10:21 | 显示全部楼层
pigeyes 发表于 2016-10-22 23:06
Lz, 這input是个string?

补充内容 (2016-10-22 23:07):
-google 1point3acres
是的 我是把它打散建树
回复 支持 反对

使用道具 举报

pigeyes 发表于 2016-10-23 07:47:39 | 显示全部楼层
kolanery 发表于 2016-10-23 00:10
是的 我是把它打散建树

楼主能不能再解释下,
题目有指名给的String是expression tree的inorder traversal或preorder吗? 不然怎么建树的呢?

还有如果只是要reverse和去除parenthesis, 为什么要建树呢? 直接从string处理不行吗?

谢谢lz!
回复 支持 反对

使用道具 举报

小雨嘀嗒 发表于 2016-10-26 07:59:45 | 显示全部楼层
kolanery 发表于 2016-10-24 16:43
题目的input仅仅是一个String, 这题的题意是当你simplify的时候把它的sub-expression tree里第一个带括号 ...

楼主你新增的例子里面:
Input: A(BC)/RSR   Output应该是ABC吧,不是有S操作吗?
另外,对于S操作,in each of its sub-expression trees 这句话的意思是每个sub tree都要去除吗?还是去除最里面的sub tree的括号呢 谢谢解答. 鍥磋鎴戜滑@1point 3 acres
回复 支持 反对

使用道具 举报

LunarManjusaka 发表于 2016-10-29 11:25:22 | 显示全部楼层
楼主你过了test case能看见测试数据吗?我case2 case4过不了想知道case2是什么数据。
回复 支持 反对

使用道具 举报

xu8431 发表于 2016-10-29 16:40:39 | 显示全部楼层
谢谢分享,只是暂时只是
回复 支持 反对

使用道具 举报

hyzl1sdo 发表于 2016-10-30 04:13:12 | 显示全部楼层
所以楼主最后一个testcase最终过了吗?
回复 支持 反对

使用道具 举报

yyang15 发表于 2016-10-30 04:52:06 | 显示全部楼层
麻烦问下楼主,我第一题有个test case (AB)C/RS 它的expected answer 是C(BA),这个有S,不是应该简化吗?
回复 支持 反对

使用道具 举报

上帝是童话 发表于 2016-10-30 05:56:02 | 显示全部楼层
求问这题有人最后一个testcase过了么 想看看testcase长啥样
回复 支持 反对

使用道具 举报

414337290 发表于 2016-10-30 09:46:44 | 显示全部楼层
同样最后一个case过不了。。。simplify的意思是包含第一个element的所有括号都去掉么?.1point3acres缃
比如 (((A))(B))C/S 变成 A(B)C
回复 支持 反对

使用道具 举报

EasonS 发表于 2016-10-30 11:42:43 | 显示全部楼层
414337290 发表于 2016-10-30 09:46
同样最后一个case过不了。。。simplify的意思是包含第一个element的所有括号都去掉么?. From 1point 3acres bbs
比如 (((A))(B))C/ ...

请问第二个case是什么呢~
回复 支持 反对

使用道具 举报

iammajian 发表于 2016-10-30 12:30:52 | 显示全部楼层
写了一下午,最后一个test过不了...
回复 支持 反对

使用道具 举报

xiaoling 发表于 2016-10-30 12:53:31 | 显示全部楼层
第二个和第四个case过不了。。。
回复 支持 反对

使用道具 举报

414337290 发表于 2016-10-30 21:51:06 | 显示全部楼层
EasonS 发表于 2016-10-30 11:42
请问第二个case是什么呢~

过了也看不到,不知道是什么
回复 支持 反对

使用道具 举报

414337290 发表于 2016-10-30 21:57:08 | 显示全部楼层
S的话我包住第一个element的括号全部都去,只去外圈和只去内圈都尝试过了,都不行。难道说有什么特殊的corner case,大家都努力挖掘一下 T.T
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 21:05

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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