一亩三分地论坛

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

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

bloomberg 8.3 onsite 两轮跪经

[复制链接] |试试Instant~ |关注本帖
xwjjjw 发表于 2016-8-15 11:00:56 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 全职@Bloomberg - 内推 - Onsite |Failfresh grad应届毕业生

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

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

x
过了两周,想想还是发一下跪经回馈一下地里。。。楼主第一次onsite有点紧张,导致第一题没做出来,直接跪了。。。
第一轮:
国人大哥+疑似韩国cmu校友小哥
首先cmu小哥先问了一下简历上一个他也上过的神课的project,然后出题,题目是普通二叉树以in-order的顺序转化为双向链表,要求in place,即直接将左右指针用作链表的前后指针且不用new一个新的节点出来,非常类似下面这个链接的题目(tree to circular doubly linked list):
https://www.youtube.com/watch?v=Dte6EF1nHNo
只是楼主的题是头节点的前指针和尾节点的后指针都指向null。。。不难,但太紧张没做出来. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
然后,国人大哥看时间不多了,就出了一题地里都有的病毒文件复制题:
// virus program
generate-100MB();
while (true) {
        sleep-1-min();
        clone();       // clone program it self.
}

If I click this virus program 1 time, it will take 10 minutes to fill the disk. My question is if I click the virus program twice, how long it will take to fill the disk?
答案:9分钟。One click: 0 min —> 1file, 1 min —> 2 files, 2 min —> 4 files, …, 10 min —> 1024 files. Two click: 0min —> 2 files, 1 min —> 4files, …, 9 min 1024 files.
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

第二轮:. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
看到只来了一个白人小哥就知道不妙了,果然只问了一下fibonacci数列的递归和迭代版本,分析了一下优劣就完了。。。直接领我出去了。。。
. from: 1point3acres.com/bbs
过了一个周末就收到拒信。。。哎,第一次onsite,当交点学费吧。。。

希望大家和我都会offer满满吧!求点大米,之前花得有点狠。。。谢谢大家!

评分

1

查看全部评分

csushin1992 发表于 2016-8-15 12:25:08 | 显示全部楼层
对于第一题,楼主给的那个视频比较难懂, 在geeksforgeeks上找到一个比较容易理解的方法:
http://www.geeksforgeeks.org/convert-given-binary-tree-doubly-linked-list-set-3/

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

 楼主| xwjjjw 发表于 2016-8-16 00:01:54 | 显示全部楼层
csushin1992 发表于 2016-8-15 12:25
对于第一题,楼主给的那个视频比较难懂, 在geeksforgeeks上找到一个比较容易理解的方法:
http://www.gee ...

谢谢你的补充!
回复 支持 反对

使用道具 举报

wantanintern 发表于 2016-8-29 06:43:47 | 显示全部楼层
请问一下lz, bb家面试是只能用c++嘛?谢谢!
回复 支持 反对

使用道具 举报

llatjob 发表于 2016-8-29 12:32:54 | 显示全部楼层
第一题用 recursion吧

. 鍥磋鎴戜滑@1point 3 acres
void BstToDLL(TreeNode* root) {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
    helper(root);
    return;
}
std::pair<TreeNode*, TreeNode*> helper(TreeNode* root) {
    if (nullptr == root) {
        return {nullptr, nullptr};
    } else if (nullptr == root->left && nullptr == root->right) {
        return {root, root};
    } else if (root->left) {.鐣欏璁哄潧-涓浜-涓夊垎鍦
        auto l = helper(root->left);
        root->left = l.second;. more info on 1point3acres.com
        l.second->right = root;
        return {l.first, root};
    } else if (root->right) {
        auto r = helper(root->right);. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
        root->right = r.first;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
        r.first->left = root;
        return {root, r.second};
    }
    auto l = helper(root->left);
    auto r = helper(root->right);. From 1point 3acres bbs
    l.second->right = root;
    r.first->left = root;
    root->left = l.second;
    root->right = r.first;
    return {l.first, r.second};
}
回复 支持 反对

使用道具 举报

qiu_cqupt 发表于 2016-9-9 09:48:58 | 显示全部楼层
第一题Recursion 和 Iteration两种解法。

class Solution(object):
    def __init__(self): 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
        self.pre = None
        self.head = None

    def bt2dll(self, root):. from: 1point3acres.com/bbs
        self.helper(root)
        return self.head

    def helper(self, root)
        if root:
            self.helper(root.left)
            if not pre:
                head = root
            else:
                root.left = pre
                pre.right = root
            pre = root
            self.helper(root.right)




class Solution(object):

    def bt2dll(self, root):

        stack = []. Waral 鍗氬鏈夋洿澶氭枃绔,
        pre = None
        head = None
        while stack or root:.鏈枃鍘熷垱鑷1point3acres璁哄潧
            while root:
                stack.append(root)
                root = root.left
            tmp = stack.pop()
            if not pre:
                head = root
            else:
                tmp.left = pre
                pre.right = tmp
            if tmp.right:
                root = tmp.right. visit 1point3acres.com for more.

        return head
回复 支持 反对

使用道具 举报

cicean 发表于 2016-10-7 07:51:02 | 显示全部楼层
第一轮 in place 是 用morris traversal 的O(1) space 的算法? no stack 的?
回复 支持 反对

使用道具 举报

cicean 发表于 2016-10-7 07:51:49 | 显示全部楼层
llatjob 发表于 2016-8-29 12:32
第一题用 recursion吧
. 1point 3acres 璁哄潧
recursive 不也得要栈么。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-7 05:58

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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