一亩三分地论坛

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

一亩三分地官方iOS手机应用下载
查看: 1785|回复: 11
收起左侧

Google phone

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

2016(10-12月) 码农类 本科 全职@Google - 网上海投 - 技术电面 |Failfresh grad应届毕业生

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

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

x
问了hash是啥,然后一堆java的概念. 题目是给一个expression tree,leaf node都是数字,其他的node有符号+ - * /,最后要你print出来这个表达式,最好的情况是如果有加号减号要括起来,乘法除法不用扩,比如tree看起来这样           *
     +       -
8      3    5   4
print(8+3)* (5-4),最后是问了java和Python的区别

. visit 1point3acres.com for more.

本帖被以下淘专辑推荐:

zzgzzm 发表于 2016-10-28 08:39:27 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
huai10 发表于 2016-10-28 08:12
为何post-oder? post-order 就变成reverse polish form 了

Post-order traversal是为了先打印底层的计算,然后才能打印外层的,并不是说运算符在参与运算的operands之后打印(polish form)。在打印任意一个内部node的时候,打印顺序还是:left expression + operator + right expression.
回复 支持 1 反对 0

使用道具 举报

zzgzzm 发表于 2016-10-27 12:52:39 | 显示全部楼层
关注一亩三分地微博:
Warald
LZ这个题的tree node的定义有给定吗?我是用一个string来统一表示数值node或运算符node. 用post-order traversal递归。而且一个给定的tree要合法的话必须是full tree (i.e., each internal node must have 2 children)
另外我觉得应该不论任何运算符都应该用括号,因为从这个tree的形式上来说应该是深层的必须先计算,然后浅层的再算。例如 3/2*4和3/(2*4)还是不同的。从tree的结构看显然是需要后者表达式,因为2和4都在tree的最深层,应该先计算。
  1. struct Node {
  2.   string s;
  3.   Node* left, *right;
  4. };

  5. string getExpression(Node* r) {
  6.   if (!r) return "";
  7.   if (!r->left && !r->right) return r->s;
  8.   return "(" + getExpression(r->left) + r->s + getExpression(r->right) + ")";. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  9. }
复制代码
回复 支持 反对

使用道具 举报

kin332026 发表于 2016-10-27 13:39:51 | 显示全部楼层
直接DFS, Bottom-up组合下?
回复 支持 反对

使用道具 举报

 楼主| caesarchen1995 发表于 2016-10-28 05:40:57 | 显示全部楼层
zzgzzm 发表于 2016-10-27 12:52
LZ这个题的tree node的定义有给定吗?我是用一个string来统一表示数值node或运算符node. 用post-order trav ...
.鏈枃鍘熷垱鑷1point3acres璁哄潧
你说的完全正确,post order traversal,是full tree。不是深层先计算,这题不用计算,print出来,3/2*4就是从左到右print出来
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 反对

使用道具 举报

 楼主| caesarchen1995 发表于 2016-10-28 05:41:18 | 显示全部楼层
kin332026 发表于 2016-10-27 13:39
直接DFS, Bottom-up组合下?
. 1point3acres.com/bbs
post order traversal
回复 支持 反对

使用道具 举报

jolesiawu 发表于 2016-10-28 07:54:40 | 显示全部楼层
哎不是很熟悉java 会不会被问一开始那些题目呀?楼主面的时候是选择用java面的吗?或者是在简历里面说了自己熟悉java 和python?
回复 支持 反对

使用道具 举报

huai10 发表于 2016-10-28 08:12:57 | 显示全部楼层
为何post-oder? post-order 就变成reverse polish form 了
回复 支持 反对

使用道具 举报

 楼主| caesarchen1995 发表于 2016-10-28 08:21:47 | 显示全部楼层
jolesiawu 发表于 2016-10-28 07:54
哎不是很熟悉java 会不会被问一开始那些题目呀?楼主面的时候是选择用java面的吗?或者是在简历里面说了自 ...

我说了最proficient with java
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-10-28 08:42:40 | 显示全部楼层
caesarchen1995 发表于 2016-10-28 05:40
你说的完全正确,post order traversal,是full tree。不是深层先计算,这题不用计算,print出来,3/2*4 ...

OK, I see. 原来题意就是这样规定的。谢谢。
回复 支持 反对

使用道具 举报

美女的 发表于 2016-10-30 01:35:26 | 显示全部楼层
parse tree 就一道题目么
回复 支持 反对

使用道具 举报

kevindx1120 发表于 2016-11-27 13:22:36 | 显示全部楼层
huai10 发表于 2016-10-28 08:12
为何post-oder? post-order 就变成reverse polish form 了
. 1point 3acres 璁哄潧
看代码,应该就是in order ?. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-2-24 23:43

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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