一亩三分地论坛

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

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

Poket gems

[复制链接] |试试Instant~ |关注本帖
zq13667243992 发表于 2014-12-6 06:27:52 | 显示全部楼层 |阅读模式

2014(10-12月) 码农类 硕士 全职@Poket Gems - 网上海投 - 技术电面 |Fail

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

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

x
Question: given a string that represents a ternary expression,
parse it into a tree comprised of Node objects and return the Node.鏈枃鍘熷垱鑷1point3acres璁哄潧
object that contains the pointer to the root node of the tree.

example:
a?b?c:d:e


        a. visit 1point3acres.com for more.
    /       \. from: 1point3acres.com/bbs
    b       e
/     \. visit 1point3acres.com for more.
c       d   

. 1point 3acres 璁哄潧
Also, you are given a Node class that holds a node in the. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
above-showed tree representation of an expression:

class Node {
    String variableName;
    Node left, right;
}
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
class Expression {
     Node getRootNodeOfExpressionTree (String expression) {
. 鍥磋鎴戜滑@1point 3 acres
    }

}


刚刚面完, 做了一个小时都没有做出来,求大神解答

.1point3acres缃
.鏈枃鍘熷垱鑷1point3acres璁哄潧

pro 发表于 2014-12-6 08:31:23 | 显示全部楼层
这就是用preorder traversal来构建二叉树吧……而且都给你用冒号把左子树和右子树分开了。另外应该需要用匹配左右括号(问号和冒号)类似的方法来找到root的问号对应的括号。
回复 支持 反对

使用道具 举报

adiggo 发表于 2014-12-6 09:10:33 | 显示全部楼层
楼主是第二轮phone interview么?
回复 支持 反对

使用道具 举报

 楼主| zq13667243992 发表于 2014-12-6 13:06:39 | 显示全部楼层
adiggo 发表于 2014-12-6 09:10. 鍥磋鎴戜滑@1point 3 acres
楼主是第二轮phone interview么?

第一轮上来就是这题
回复 支持 反对

使用道具 举报

Adeath 发表于 2014-12-6 13:37:46 | 显示全部楼层
这个解不唯一吧
example
a?b?c:d:e. 1point3acres.com/bbs

         a. 鍥磋鎴戜滑@1point 3 acres
        /
      b
     /
   c
     \
      d. more info on 1point3acres.com
        \
         e
还是要求尽量balanced ?
回复 支持 反对

使用道具 举报

adiggo 发表于 2014-12-7 14:04:49 | 显示全部楼层
zq13667243992 发表于 2014-12-6 13:06
第一轮上来就是这题

我面完他家一轮, 又让我面一轮。 也是醉了。
回复 支持 反对

使用道具 举报

wendychueng 发表于 2014-12-7 14:37:21 | 显示全部楼层
adiggo 发表于 2014-12-7 01:04
我面完他家一轮, 又让我面一轮。 也是醉了。
-google 1point3acres
终于看到有人面游戏公司了!请问他家要mobile experience吗
回复 支持 反对

使用道具 举报

adiggo 发表于 2014-12-8 10:30:48 | 显示全部楼层
wendychueng 发表于 2014-12-7 14:37
终于看到有人面游戏公司了!请问他家要mobile experience吗

haha, 他家跟我说好像没这个要求, 问题也很直接, 就是算法题。 而且题目好像不怎么变。
回复 支持 反对

使用道具 举报

LiamZhu 发表于 2014-12-8 10:44:48 | 显示全部楼层
Adeath 发表于 2014-12-6 13:37
这个解不唯一吧. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
example
a?b?c:d:e

你貌似没理解题意
这是一个ternary expression的嵌套
对于一个ternary expression a?b:c来说它的结构就是
  a
/  \. more info on 1point3acres.com
b   c.鏈枃鍘熷垱鑷1point3acres璁哄潧
加上嵌套的话就是相当于扩展叶子结点了
至于怎么parse一个嵌套的表达式,就跟ternary expression本身的性质有关了。
回复 支持 反对

使用道具 举报

Adeath 发表于 2014-12-8 11:10:26 | 显示全部楼层
LiamZhu 发表于 2014-12-8 10:44
你貌似没理解题意
这是一个ternary expression的嵌套.1point3acres缃
对于一个ternary expression a?b:c来说它的结构就 ...

哦哦 原来是root?left:right这样
感觉可以用stack做  stack记录?之前的节点(root)  ? 之后的节点直接匹配为左子树  : 之后的节点匹配为stack.pop()的右子树  这样就能把?:匹配到最近的root了
回复 支持 反对

使用道具 举报

 楼主| zq13667243992 发表于 2014-12-8 11:10:34 | 显示全部楼层
我把我后来想到的做法放上来吧,用一个堆栈就可以解决了。
  1.         public static TreeNode construct(String s) {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  2.                 if(s.length() == 0) return null;
  3.                 Stack<TreeNode> st = new Stack<TreeNode>();
  4.                 TreeNode root = new TreeNode(s.charAt(0));
  5.                 st.push(root);
  6.                 int i=1;
  7.                 while(i < s.length() && !st.isEmpty()) {
  8.                         TreeNode cur = null;
  9.                         if(s.charAt(i) == '?'){
  10.                                 cur = new TreeNode(s.charAt(++i));
  11.                                 TreeNode parent = st.peek();
  12.                                 parent.left = cur;. from: 1point3acres.com/bbs
  13.                                 st.push(cur);
  14.                         }else {
  15.                                 cur = new TreeNode(s.charAt(++i));
  16.                                 st.pop();
  17.                                 TreeNode parent = st.peek();
  18.                                 parent.right = cur; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  19.                         }
  20.                         i++;. From 1point 3acres bbs
  21.                 } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  22.                 return root;
  23.         }
复制代码
回复 支持 反对

使用道具 举报

LiamZhu 发表于 2014-12-8 11:31:11 | 显示全部楼层
Adeath 发表于 2014-12-8 11:10
哦哦 原来是root?left:right这样
感觉可以用stack做  stack记录?之前的节点(root)  ? 之后的节点直接匹 ...

对的!
楼下已经有人放代码啦~
回复 支持 反对

使用道具 举报

adiggo 发表于 2014-12-12 03:07:15 | 显示全部楼层
zq13667243992 发表于 2014-12-8 11:10
我把我后来想到的做法放上来吧,用一个堆栈就可以解决了。

hello, 您的代码有点小问题, 如果treenode 的val是int的话。
这里转换char到int, 如果是‘1’ 那么到int是49。 所以需要减去‘0’   
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 09:15

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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