一亩三分地论坛

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

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

Bloomberg跪经 Mar 23

[复制链接] |试试Instant~ |关注本帖
fmy9209 发表于 2016-3-24 04:31:44 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 硕士 全职@Bloomberg - 网上海投 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
怀着极其沉重的心情发这条面经。。。interviewer: 印度小哥,冷漠,口语还行
1. why BBG?interesting project
2. 只有一道题  其实和flatten tree一样不过是linkedList 每个node都有一个next和一个down
1->2->3->4->5
    |
     6->7->8. from: 1point3acres.com/bbs
     |
     9
要flatten变成126978345
楼主第一次面试吓尿了。。用的DFS stack找的,中间解释的磕磕巴巴。。。
然后分析time space
然后他说能不能用o(1)的space
然后我想了半天,他提醒了说用recursive的方法,他问recursive有什么弊端,解释了几句。
然后就问问题了,也没让我写代码。。。. 1point3acres.com/bbs
. 1point3acres.com/bbs
他迟到了15分钟,然后又提前结束了,总共面了30 分钟。。。
挂不挂到是无所谓,但是作为第一次面试经历太糟糕了。。。觉得自己好挫啊,稍微遇到一点变动的题目就吓得要死。。。

评分

1

查看全部评分

1peter 发表于 2016-3-25 11:58:01 | 显示全部楼层
我怎么感觉把down替换成left,next替换成right,这就是一道pre order traversal 呢。不就是换了个variable 那么吗?
回复 支持 1 反对 0

使用道具 举报

碇真嗣 发表于 2016-3-24 04:52:18 | 显示全部楼层
recursive能是O(1)的space麽。。。
回复 支持 反对

使用道具 举报

 楼主| fmy9209 发表于 2016-3-24 06:26:48 | 显示全部楼层
碇真嗣 发表于 2016-3-24 04:52
recursive能是O(1)的space麽。。。
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
所以O(1)应该是什么呀?他自己提醒我用recursive的。。。
回复 支持 反对

使用道具 举报

ok123 发表于 2016-3-24 06:55:18 | 显示全部楼层
既然recursive了就不能是space O(1)吧
如果每一个都有down,recursive很难。5 的down会先打出来,然后才是4 的down. from: 1point3acres.com/bbs
DFS 用stack 不也有这个问题吗?求解释

跟树的level order traverse一样,用一个queue,把第一level的node放就去。. 鍥磋鎴戜滑@1point 3 acres
loop q里的node有没有down,有就把down指的那一level 的node全放到q里去
然后从头打印这个Q的node
回复 支持 反对

使用道具 举报

KlausQi 发表于 2016-3-24 06:56:56 | 显示全部楼层
这印度小哥简直在逗我……我觉得worst case是一定要O(n)的,你可以看能不能找到那个三哥的邮箱然后给他发邮件说他在扯淡……
回复 支持 反对

使用道具 举报

g3chenyi 发表于 2016-3-24 07:07:09 | 显示全部楼层
recursion的stack不要钱么lol。。。
回复 支持 反对

使用道具 举报

houqingniao 发表于 2016-3-25 02:20:19 | 显示全部楼层
ok123 发表于 2016-3-24 06:55
既然recursive了就不能是space O(1)吧
如果每一个都有down,recursive很难。5 的down会先打出来,然后才 ...

这样子是123456789 而不是要求的顺序了吧
回复 支持 反对

使用道具 举报

boyshone 发表于 2016-3-25 02:26:06 | 显示全部楼层
recursive 竟然算const space
我看是在黑你吧
. visit 1point3acres.com for more.
和hr complain一下,就算不能进,也要维护自己的权益
回复 支持 反对

使用道具 举报

ok123 发表于 2016-3-25 05:51:12 | 显示全部楼层
houqingniao 发表于 2016-3-25 02:20
这样子是123456789 而不是要求的顺序了吧
.鐣欏璁哄潧-涓浜-涓夊垎鍦
1 下有list, 2 下也有list,是不是要先打出1的list,再打出2的list
如果是recursive,会先打2的list
回复 支持 反对

使用道具 举报

houqingniao 发表于 2016-3-25 11:43:49 | 显示全部楼层
ok123 发表于 2016-3-25 05:51
1 下有list, 2 下也有list,是不是要先打出1的list,再打出2的list
如果是recursive,会先打2的list
. more info on 1point3acres.com
recursive 就先recurse 下面然后recurse 后面就好了
回复 支持 反对

使用道具 举报

houqingniao 发表于 2016-3-26 06:08:03 | 显示全部楼层
1peter 发表于 2016-3-25 11:58
我怎么感觉把down替换成left,next替换成right,这就是一道pre order traversal 呢。不就是换了个variable  ...

是的!精辟!
回复 支持 反对

使用道具 举报

jiaozhu200601 发表于 2016-9-1 07:23:32 | 显示全部楼层
感觉确实就是:https://leetcode.com/problems/flatten-binary-tree-to-linked-list/ 然后left变成了down,right变成了next。
public class FlattenDownTree{

        public void flatten (TreeNode root) {. Waral 鍗氬鏈夋洿澶氭枃绔,
            if (root.down!= null) {
              ListNode temp = root.next;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
              root.next = root.down;
              ListNode nextRoot = root.next;

              root.down = null;

             while (root.next != null) {
                    root = root.next;
             }
             root.next = temp;. more info on 1point3acres.com

             flatten(nextRoot);-google 1point3acres

            }else {
             flatten (root.next);
            }
        }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
}

回复 支持 反对

使用道具 举报

cicean 发表于 2016-9-21 11:09:48 | 显示全部楼层
估计 O(1) 就是每次 CustomLinkedNode node = head.down;. 1point 3acres 璁哄潧
开个辅助接点,就叫O(1)
stack 要存O(h)
回复 支持 反对

使用道具 举报

xuqicx23 发表于 2016-9-25 06:38:36 | 显示全部楼层
public void flatteNode(Node l) {
        if (l == null) {
            return;
        }. Waral 鍗氬鏈夋洿澶氭枃绔,
        flathelper(l);. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
    }
    public Node flathelper(Node root) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
        if (root == null) {
            return null;. 1point3acres.com/bbs
        }
        if (root.next == null && root.down == null) {
            return root;
        }
        if (root.down == null) {. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
            return flathelper(root.next);
        }-google 1point3acres
        if (root.next == null) {
            root.next = root.down;
            root.down = null;
            return flathelper(root.next);. visit 1point3acres.com for more.
        }
        Node leftLast = flathelper(root.down);
        Node rightlast = flathelper(root.next);
        leftLast.next = root.next;. Waral 鍗氬鏈夋洿澶氭枃绔,
        root.next = root.down;
        root.down = null;. from: 1point3acres.com/bbs
        return rightlast;
    }
回复 支持 反对

使用道具 举报

何打发123 发表于 2016-9-25 07:48:02 | 显示全部楼层
感谢分享~ 请问这题复杂度是O(n)吗 0.0
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 21:52

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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