Bloomberg跪经 Mar 23

怀着极其沉重的心情发这条面经。。。interviewer： 印度小哥，冷漠，口语还行
1. why BBG？interesting project
2. 只有一道题  其实和flatten tre

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

总共面了30 分钟。。。
挂不挂到是无所谓，但是作为第一次面试经历太糟糕了。。。觉得自己好挫啊，稍微遇到一点变动的题目就吓得要死。。。

我怎么感觉把down替换成left，next替换成right，这就是一道pre order traversal 呢。不就是换了个variable 那么吗？

public void flatteNode(Node l) {
        if (l == null) {
            return;
        }
        flathelper(l);
    }
    public Node flathelper(Node root) {
        if (root == null) {
            return null;
        }
        if (root.next == null && root.down == null) {
            return root;
        }
        if (root.down == null) {
            return flathelper(root.next);
        }
        if (root.next == null) {
            root.next = root.down;
            root.down = null;
            return flathelper(root.next);
        }
        Node leftLast = flathelper(root.down);
        Node rightlast = flathelper(root.next);
        leftLast.next = root.next;
        root.next = root.down;
        root.down = null;
        return rightlast;
    }

感觉确实就是：https://leetcode.com/problems/flatten-binary-tree-to-linked-list/ 然后left变成了down，right变成了next。
public class FlattenDownTree{

        public void flatten (TreeNode root) {
            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;

             flatten(nextRoot);

            }else {
             flatten (root.next);
            }
        }
}

recursive能是O(1)的space麽。。。

碇真嗣 发表于 2016-3-24 04:52
recursive能是O(1)的space麽。。。

所以O（1）应该是什么呀？他自己提醒我用recursive的。。。

既然recursive了就不能是space O（1）吧
如果每一个都有down，recursive很难。5 的down会先打出来，然后才是4 的down
DFS 用stack 不也有这个问题吗？求解释

跟树的level order traverse一样，用一个queue，把第一level的node放就去。
loop q里的node有没有down，有就把down指的那一level 的node全放到q里去
然后从头打印这个Q的node

这印度小哥简直在逗我……我觉得worst case是一定要O(n)的，你可以看能不能找到那个三哥的邮箱然后给他发邮件说他在扯淡……

recursion的stack不要钱么lol。。。

ok123 发表于 2016-3-24 06:55
既然recursive了就不能是space O（1）吧
如果每一个都有down，recursive很难。5 的down会先打出来，然后才 ...

这样子是123456789 而不是要求的顺序了吧

recursive 竟然算const space
我看是在黑你吧

和hr complain一下，就算不能进，也要维护自己的权益

houqingniao 发表于 2016-3-25 02:20
这样子是123456789 而不是要求的顺序了吧

1 下有list， 2 下也有list，是不是要先打出1的list，再打出2的list
如果是recursive，会先打2的list

ok123 发表于 2016-3-25 05:51
1 下有list， 2 下也有list，是不是要先打出1的list，再打出2的list
如果是recursive，会先打2的list

recursive 就先recurse 下面然后recurse 后面就好了