[八我司] 介绍一下Uber tech stack和各个大组的情况

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 4729|回复: 11
收起左侧

请教pocket gems高频题ternary expression to bt的recursion写法

[复制链接] |试试Instant~ |关注本帖
yuxrose 发表于 2015-4-19 06:50:37 | 显示全部楼层 |阅读模式

2015(4-6月) 码农类General 硕士 全职@PoketGem - 网上海投 - 技术电面  | Other | 在职跳槽

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

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

x
这题好几个人报过面经, 请戳这个
http://www.1point3acres.com/bbs/ ... mp;highlight=pocket
和这里
http://www.1point3acres.com/bbs/ ... t=pocket&page=1

我写了个用stack的,但我觉得用recursion更intuitive一点,但怎么写也写不对,因为需要一个integer track现在在string的哪个位置了,但java的int是pass by value, 所以总是track不对,有小伙伴愿意交流一下这个题的写法吗?. 一亩-三分-地,独家发布
放上我这个错的写法
public static Node recursive(String s){
        int current = 0;
        return helper(s, current);
    }.1point3acres网
   
    public static Node helper(String s, int current){. 1point 3acres 论坛
        if(current >= s.length()){
            return null;
        }
        Node node = new Node(s.charAt(current));. from: 1point3acres
        current = current + 2;
        if(s.charAt(current - 1) == '?'){
            node.left = helper(s, current);
        }
        current = current + 2;
        if(s.charAt(current - 1) == ':'){. Waral 博客有更多文章,
            node.right = helper(s, current);. 1point3acres
        }
        return node;
    }

还请大家指教!

ryuichist 发表于 2015-4-19 07:15:51 | 显示全部楼层
昨天才面了他们的1面,可以加个好友一起讨论下,扣扣10805529
回复 支持 反对

使用道具 举报

 楼主| yuxrose 发表于 2015-4-19 07:23:52 | 显示全部楼层
ryuichist 发表于 2015-4-19 07:15
昨天才面了他们的1面,可以加个好友一起讨论下,扣扣10805529

不用QQ啊。。。有微信吗?
. visit 1point3acres for more.
补充内容 (2015-4-19 07:26):
. 一亩-三分-地,独家发布想起来你是那个面过L的大牛。。。天。。。赶快去加微信。这题有啥想法吗?
回复 支持 反对

使用道具 举报

ryuichist 发表于 2015-4-19 07:33:02 | 显示全部楼层
yuxrose 发表于 2015-4-19 07:23 来源一亩.三分地论坛.
不用QQ啊。。。有微信吗?

补充内容 (2015-4-19 07:26):

哈哈好像是加过微信,YUXROSE,你微信名字是什么,忘记啦
回复 支持 反对

使用道具 举报

yabay91 发表于 2015-4-19 08:19:30 | 显示全部楼层
这个是我当时的答案。很顺利的写出来了,但是不知道为什么还是挂了。面试官说有O(N)的解法
        public charNode parseTenary(String s){
                return parseHelp(s,0,s.length()-1);. Waral 博客有更多文章,
        }
        public charNode parseHelp(String s,int i,int j){
                if(i==j). 牛人云集,一亩三分地
                        return new charNode(s.charAt(i));. 1point 3acres 论坛
                charNode root=new charNode(s.charAt(i));
                LinkedList<Integer> stack=new LinkedList<Integer>();
                int move=i;
                int mark=0;
                while(move<=j){-google 1point3acres
                        if(s.charAt(move)=='?')
                                stack.push(move);
                        else if(s.charAt(move)==':'){
                                mark=stack.pop();
                                if(stack.isEmpty()){
. Waral 博客有更多文章,                                        break;
                                }
                        }
                        move++;        . visit 1point3acres for more.
                }
                root.left=parseHelp(s,mark+1,move-1);
                root.right=parseHelp(s,move+1,j);
                return root;. 牛人云集,一亩三分地
        }
祝你好运!!!
回复 支持 反对

使用道具 举报

nathanwong 发表于 2015-4-19 08:38:09 | 显示全部楼层
问了 招满了。。。无耻
回复 支持 反对

使用道具 举报

 楼主| yuxrose 发表于 2015-4-19 08:46:29 | 显示全部楼层
yabay91 发表于 2015-4-19 08:19
这个是我当时的答案。很顺利的写出来了,但是不知道为什么还是挂了。面试官说有O(N)的解法
        public charNo ...

非常感谢!!也祝你早日拿到大offer!
回复 支持 反对

使用道具 举报

 楼主| yuxrose 发表于 2015-4-19 08:57:40 | 显示全部楼层
nathanwong 发表于 2015-4-19 08:38
问了 招满了。。。无耻

全职也招满了是吗?那为啥不告诉我们。。还面个嘛劲儿啊。。。我们面试也有很多时间成本的。。。还得请假。
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

chm34 发表于 2015-4-19 09:39:29 | 显示全部楼层
我用递归写的,time complexity O(nlogn), space O(1). 时间复杂度高是因为要查找String的分割点,这个每次都要O(N),不知道有么有什么优化?
  1. public static TreeNode solve(String s)
  2.         {. 一亩-三分-地,独家发布
  3.                 if(s==null || s.length()==0) return null;
  4.                 if(s.length()==1)
  5.                         return new TreeNode(s.charAt(0));
  6.                 int flag=0; int mid=0;. more info on 1point3acres
  7.                 for(int i=2;i<=s.length()-1;i++)
  8.                 {
  9.                         if(s.charAt(i)=='?')
  10.                                 flag++;. 留学申请论坛-一亩三分地
  11.                         else if(s.charAt(i)==':'). Waral 博客有更多文章,
  12.                         {
  13.                                 if(flag==0)
  14.                                 {. 一亩-三分-地,独家发布
  15.                                         mid=i; break;
  16.                                 }
  17.                                 else flag--;
  18.                         }
  19.                 }-google 1point3acres
  20.                 TreeNode head=new TreeNode(s.charAt(0));
  21.                 TreeNode temp_left=solve(s.substring(2,mid));
  22.                 TreeNode temp_right=solve(s.substring(mid+1,s.length()));.1point3acres网
  23.                 head.left=temp_left;
  24.                 head.right=temp_right;
  25.                 return head;
  26.         }
复制代码
回复 支持 反对

使用道具 举报

sunfish 发表于 2015-4-19 11:20:01 | 显示全部楼层
这个题和serialize tree  差不多吧,pre oder build tree 就好了吧,因为一定是full tree, 所以只要注意代表这个字母有两个孩子,:代表没孩子就好了吧。自己想的,不知道对不对。. more info on 1point3acres

补充内容 (2015-4-19 11:21):
注意?代表这个字母有两个孩子,:代表没孩子
回复 支持 反对

使用道具 举报

wm_thu 发表于 2015-4-21 03:03:15 | 显示全部楼层
O(n)的思路是:
首先遍历一遍整个字符串,借助stack找出所有的?:匹配,存到一个hashmap里,key是?的index,value是:的index。这一趟是O(n)的。
然后再遍历一遍,建树。这时要递归,不过每个字符都只访问过一次,所以总的时间也是O(n)。
因此总时间O(n)。

补充内容 (2015-4-21 03:04):
由于用了hashmap,所以空间也是O(n)
回复 支持 反对

使用道具 举报

nathanwong 发表于 2015-4-22 14:39:55 | 显示全部楼层
yuxrose 发表于 2015-4-19 08:57. 留学申请论坛-一亩三分地
全职也招满了是吗?那为啥不告诉我们。。还面个嘛劲儿啊。。。我们面试也有很多时间成本的。。。还得请假 ...

我觉得一就是宣传公司 而是培训面试官,你看看之前有的人post的面经 无理由悲剧
回复 支持 反对

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

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

custom counter

GMT+8, 2018-5-25 15:17

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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