《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 1602|回复: 12
收起左侧

Poket gems

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

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

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

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

x
Question: given a string that represents a ternary expression,. more info on 1point3acres.com
parse it into a tree comprised of Node objects and return the Node
object that contains the pointer to the root node of the tree.

example:
a?b?c:d:e

. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
        a
    /       \
    b       e
/     \. from: 1point3acres.com/bbs
c       d   


Also, you are given a Node class that holds a node in the
above-showed tree representation of an expression:

class Node {
-google 1point3acres    String variableName;
    Node left, right;
}

class Expression {
     Node getRootNodeOfExpressionTree (String expression) {

    }

}


刚刚面完, 做了一个小时都没有做出来,求大神解答
. from: 1point3acres.com/bbs
. 1point3acres.com/bbs

.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
楼主是第二轮phone interview么?

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

使用道具 举报

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

         a
        /
      b
     /
   c
     \
      d
        \
         e. 1point 3acres 璁哄潧
还是要求尽量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
我面完他家一轮, 又让我面一轮。 也是醉了。

终于看到有人面游戏公司了!请问他家要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
这个解不唯一吧.鏈枃鍘熷垱鑷1point3acres璁哄潧
example
a?b?c:d:e
. from: 1point3acres.com/bbs
你貌似没理解题意
这是一个ternary expression的嵌套.1point3acres缃
对于一个ternary expression a?b:c来说它的结构就是
  a
/  \
b   c. 鍥磋鎴戜滑@1point 3 acres
加上嵌套的话就是相当于扩展叶子结点了
至于怎么parse一个嵌套的表达式,就跟ternary expression本身的性质有关了。
回复 支持 反对

使用道具 举报

Adeath 发表于 2014-12-8 11:10:26 | 显示全部楼层
LiamZhu 发表于 2014-12-8 10:44
你貌似没理解题意
这是一个ternary expression的嵌套
对于一个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));. 鍥磋鎴戜滑@1point 3 acres
  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;
  13.                                 st.push(cur);-google 1point3acres
  14.                         }else {
  15.                                 cur = new TreeNode(s.charAt(++i));
  16.                                 st.pop();
  17.                                 TreeNode parent = st.peek();
  18.                                 parent.right = cur;
  19.                         }
  20.                         i++;
  21.                 }.1point3acres缃
  22.                 return root;-google 1point3acres
  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’   
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-11-20 12:24

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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