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


一亩三分地论坛

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

Bloomberg电面

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

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

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

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

x
刚刚面完,只写了一道题。貌似还没有写对肯定是跪了啊 之前看地里的电面 面经都挺简单的啊,说好的twosum呢呢呢呢. 1point3acres.com/bbs
趁着fresh memory, 赶紧回忆题目回报地里
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷


B家貌似最开始都会问个简历上的project,然后问几个基本的java,pyhton问题,thread啊什么的 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
然后就开始写算法了:. visit 1point3acres.com for more.

0 1 2 3 4 .鐣欏璁哄潧-涓浜-涓夊垎鍦
0 3 0 1 7.鐣欏璁哄潧-涓浜-涓夊垎鍦
0 3 0 1 7
0 3 3 1 7

如果start在【2, 1】点,那么我们target就是3, 那么就找所有能reach的3做成的图形的边数。 比如这个就是返回10.-google 1point3acres

大家加油! 我去哭一会儿

评分

1

查看全部评分

本帖被以下淘专辑推荐:

dong882205 发表于 2016-6-19 06:47:47 | 显示全部楼层
int cal(vector<vector<int>> &g, int a, int b)
{
    int n=g.size();
    if(!n)return 0;
    int m=g[0].size();
    if(!m) return 0;-google 1point3acres
    queue<pair<int,int>> q;
    int k=g[a][b];
    int res=0;. more info on 1point3acres.com
    q.emplace(a,b);
    const vector<int> d={0,1,0,-1,0};
    while(q.size())
    {
        int i=q.front().first, j=q.front().second;
        int ct=0;
        q.pop();
        if(g[i][j]==-k) continue;
        for(int cc=0;cc<4;cc++)
        {
            int ii=i+d[cc], jj=j+d[cc+1];
            if(ii<0||ii>=n||jj<0||jj>=m) continue;
            if(g[ii][jj]==k||g[ii][jj]==-k) ct++;
            if(g[ii][jj]==k)
                q.emplace(ii,jj);
        }
        g[i][j]=-k;.1point3acres缃
        res+=(4-ct);
    }.鐣欏璁哄潧-涓浜-涓夊垎鍦
    return res;
}. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
回复 支持 1 反对 0

使用道具 举报

dajiang 发表于 2016-6-3 05:49:30 | 显示全部楼层
题目没看懂。。 能求楼主详解下吗。感谢。
回复 支持 1 反对 0

使用道具 举报

Fustang 发表于 2016-6-3 05:18:31 | 显示全部楼层
图形边数?是说围成的最大矩形边长吗?祝LZ好运。。。
回复 支持 反对

使用道具 举报

aojing 发表于 2016-6-3 06:31:20 | 显示全部楼层
没看懂题,,为什么是返回10?
回复 支持 反对

使用道具 举报

碇真嗣 发表于 2016-6-3 07:36:34 | 显示全部楼层
感觉BB的确差异挺大的难度。。比较看面试官貌似。。也不一定是坏消息~
回复 支持 反对

使用道具 举报

 楼主| D__nancy 发表于 2016-6-3 07:36:57 | 显示全部楼层
是的,返回围成的最大矩阵的边长
回复 支持 反对

使用道具 举报

ptbrxlphx 发表于 2016-6-3 08:10:02 | 显示全部楼层
找出所有为3的点然后球上下左右的极值,这个不难吧.鏈枃鍘熷垱鑷1point3acres璁哄潧
回复 支持 反对

使用道具 举报

ptbrxlphx 发表于 2016-6-3 08:10:31 | 显示全部楼层
时间复杂度为所有点的个数
回复 支持 反对

使用道具 举报

chplushsieh 发表于 2016-6-3 16:35:25 | 显示全部楼层
我下星期就要面Bloomberg了,
試著寫了這一題(花了好多時間,真遇到就要跪了...),
請指教(第一次在python寫unit test,以下內容可以用python3執行):
. visit 1point3acres.com for more.

import unittest
. from: 1point3acres.com/bbs

def count_edges(matrix, i, j):
    """. From 1point 3acres bbs
    :type matrix: List[List[int]]-google 1point3acres
    :type i: int.鐣欏璁哄潧-涓浜-涓夊垎鍦
    :type j: int
. Waral 鍗氬鏈夋洿澶氭枃绔,    :rtype: int
    """
    target = matrix[j]
    is_visited = [[False for col in range(len(matrix[0]))] for row in range(len(matrix))]
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
    return helper(i, j, target, matrix, is_visited)


def helper(row, col, target, matrix, is_visited):. 1point3acres.com/bbs
    if row < 0 or col < 0 or row > len(matrix)-1 or col > len(matrix[0])-1:.1point3acres缃
        print('border[', row, '][', col, '] counted')
        return 1
.1point3acres缃
    if is_visited[row][col]:
        return 0

    if target == matrix[row][col]:. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
        is_visited[row][col] = True
        return (0 +
. Waral 鍗氬鏈夋洿澶氭枃绔,                helper(row-1, col, target, matrix, is_visited) +
                helper(row, col-1, target, matrix, is_visited) +
                helper(row+1, col, target, matrix, is_visited) +
                helper(row, col+1, target, matrix, is_visited)).1point3acres缃
    else:
        print('matrix[', row, '][', col, ']:', matrix[row][col], ' counted')
        return 1


class TestCountEdgesMethods(unittest.TestCase):

    def testcase1(self):.鏈枃鍘熷垱鑷1point3acres璁哄潧
        testcase1 = [
            [0, 1, 2, 3, 4],
            [0, 3, 0, 1, 7],
            [0, 3, 0, 1, 7],
            [0, 3, 3, 1, 7]
        ]
        result1 = count_edges(testcase1, 2, 1)
        self.assertEqual(result1, 10).鐣欏璁哄潧-涓浜-涓夊垎鍦

    def testcase2(self):
        testcase2 = [
            [0]
        ]
        result2 = count_edges(testcase2, 0, 0)
        self.assertEqual(result2, 4)

if __name__ == '__main__': 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
    unittest.main()


补充内容 (2016-6-3 16:37):
如果只想看解法、不想管test的話,就只看前兩個functions就行了

补充内容 (2016-6-3 16:49):
不知道為什麼貼過來第一行就漏了[ i ]... 正確的count_edges第一行應該是:target = matrix [ i ] [j]
回复 支持 反对

使用道具 举报

chplushsieh 发表于 2016-6-3 16:42:45 | 显示全部楼层
ptbrxlphx 发表于 2016-6-3 08:10
找出所有为3的点然后球上下左右的极值,这个不难吧
. visit 1point3acres.com for more.
找出「所有」為3的點,好像有點不對。我理解是:只有和題目給定的matrix[2][1]相連的3,才納入考慮。所以像matrix[0][3]的那一個3,就不必計入
回复 支持 反对

使用道具 举报

 楼主| D__nancy 发表于 2016-6-3 22:56:08 | 显示全部楼层
aojing 发表于 2016-6-3 06:31
没看懂题,,为什么是返回10?
. From 1point 3acres bbs
多谢安慰啊~不过我觉得肯定跪了,刚面完五分钟的时候想到中间更新result的时候貌似更新错了
回复 支持 反对

使用道具 举报

 楼主| D__nancy 发表于 2016-6-3 22:58:32 | 显示全部楼层
ptbrxlphx 发表于 2016-6-3 08:10
时间复杂度为所有点的个数

我用的是BFS, 找到所有可以reach的3的点,中间不断地更新现在得到的3组成图形的边数

这是后来才想到的,当时面的时候跟新错了,没考虑完全
回复 支持 反对

使用道具 举报

 楼主| D__nancy 发表于 2016-6-3 23:00:14 | 显示全部楼层
chplushsieh 发表于 2016-6-3 16:42
找出「所有」為3的點,好像有點不對。我理解是:只有和題目給定的matrix[2][1]相連的3,才納入考慮。所以 ...

是的,找到所有从<x,y> 能reach的3的点组成的图形
我用的是BFS,中间不断地更新当前的图形的边数
回复 支持 反对

使用道具 举报

 楼主| D__nancy 发表于 2016-6-3 23:14:42 | 显示全部楼层
aojing 发表于 2016-6-3 06:31
没看懂题,,为什么是返回10?

同学看下面的评论吧,我回复了。
就是所有能reach的所有3组成的图形的边长
回复 支持 反对

使用道具 举报

Jailf 发表于 2016-6-28 07:01:33 | 显示全部楼层
用C++写了一个DFS版本的,仅供参考
void helper(vector<vector<int>> & board, vector<vector<int>> & visited, int r, int c, int target, vector<int> & result, vector<pair<int, int>> & dir). 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
{
        if (r >= 0 && r<board.size() && c >= 0 && c<board[0].size()){
                if (visited[r][c] == 0 && board[r][c] == target){. 鍥磋鎴戜滑@1point 3 acres
                        //update four value;
                        if (r>result[0]). Waral 鍗氬鏈夋洿澶氭枃绔,
                                result[0] = r;
                        if (r<result[1])
                                result[1] = r;
                        if (c<result[2])
                                result[2] = c;
                        if (c>result[3])
                                result[3] = c;

                        visited[r][c] = 1;

                        for (auto d : dir){
                                helper(board, visited, r + d.first, c + d.second, target, result, dir);
                        }
                }
        }

        return;
}
. From 1point 3acres bbs

int findMaxRec(vector<vector<int>> & board, int i, int j). from: 1point3acres.com/bbs
{. 鍥磋鎴戜滑@1point 3 acres
        //iterate every connected target and update the left, right, top, bottom value.. more info on 1point3acres.com

        //DFS. 1point 3acres 璁哄潧
        vector<int> result = { i, i, j, j }; //bottom, top, left, right
        int target = board[i][j];
        vector<vector<int>> visited(board.size(), vector<int>(board[0].size(), 0));. 鍥磋鎴戜滑@1point 3 acres
        vector<pair<int, int>> dir = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };

        helper(board, visited, i, j, target, result, dir);

        return (result[0] - result[1] + 1 + result[3] - result[2] + 1) * 2;
}.1point3acres缃

int main(). 鍥磋鎴戜滑@1point 3 acres
{
        vector<vector<int>> board = { { 0, 1, 2, 3, 4 }, { 0, 3, 0, 1, 7 }, { 0, 3, 0, 1, 7 }, { 0, 3, 3, 1, 7 } };
        cout<<findMaxRec(board, 2, 1);

        system("pause");
        return 0;
}
回复 支持 反对

使用道具 举报

chenqidi 发表于 2016-7-30 13:44:15 | 显示全部楼层
不是说B家主要考C/C++吗?
回复 支持 反对

使用道具 举报

leyhzm 发表于 2016-8-4 01:03:23 | 显示全部楼层
DFS找到所有不重复的符合条件的点,设置一个数为num=0,每找到一个点,这个数num-2.. 鍥磋鎴戜滑@1point 3 acres
点的个数*4-num就是答案。
回复 支持 反对

使用道具 举报

何打发123 发表于 2016-8-15 00:48:35 | 显示全部楼层
感谢楼主分享~~~
回复 支持 反对

使用道具 举报

何打发123 发表于 2016-8-15 00:50:26 | 显示全部楼层
请问. 鍥磋鎴戜滑@1point 3 acres
3 1 2 3 4
3 3 0 1 7
3 3 0 1 7
0 3 3 1 7  如果长这样的话 应该返回的边长是不是12?

补充内容 (2016-8-15 00:51):
还是应该是14?。。 题目理解我还是有点问题 bb现在怎么这么难了>.<,,...
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-11-24 15:38

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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