一亩三分地论坛

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

扫码关注一亩三分地公众号
查看: 1331|回复: 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的区别


zzgzzm 发表于 2016-10-28 08:39:27 | 显示全部楼层
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 | 显示全部楼层
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;. more info on 1point3acres.com
  4. };
  5. . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  6. string getExpression(Node* r) {
  7.   if (!r) return "";
  8.   if (!r->left && !r->right) return r->s;. From 1point 3acres bbs
  9.   return "(" + getExpression(r->left) + r->s + getExpression(r->right) + ")";
  10. }
复制代码
回复 支持 反对

使用道具 举报

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 ...

你说的完全正确,post order traversal,是full tree。不是深层先计算,这题不用计算,print出来,3/2*4就是从左到右print出来
回复 支持 反对

使用道具 举报

 楼主| caesarchen1995 发表于 2016-10-28 05:41:18 | 显示全部楼层
kin332026 发表于 2016-10-27 13:39
直接DFS, Bottom-up组合下?

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.1point3acres缃
你说的完全正确,post order traversal,是full tree。不是深层先计算,这题不用计算,print出来,3/2*4 ...

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

使用道具 举报

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

使用道具 举报

kevindx1120 发表于 6 天前 | 显示全部楼层
huai10 发表于 2016-10-28 08:12. visit 1point3acres.com for more.
为何post-oder? post-order 就变成reverse polish form 了

看代码,应该就是in order ?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-3 17:41

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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