一亩三分地论坛

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

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

Bloomberg电面

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

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

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

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

x
刚刚面完,只写了一道题。貌似还没有写对肯定是跪了啊 之前看地里的电面 面经都挺简单的啊,说好的twosum呢呢呢呢
趁着fresh memory, 赶紧回忆题目回报地里



B家貌似最开始都会问个简历上的project,然后问几个基本的java,pyhton问题,thread啊什么的
然后就开始写算法了:. Waral 鍗氬鏈夋洿澶氭枃绔,

0 1 2 3 4
0 3 0 1 7. Waral 鍗氬鏈夋洿澶氭枃绔,
0 3 0 1 7
0 3 3 1 7

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

大家加油! 我去哭一会儿

评分

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;.1point3acres缃
    int m=g[0].size();
    if(!m) return 0;
    queue<pair<int,int>> q;
    int k=g[a][b];. visit 1point3acres.com for more.
    int res=0;
    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++)
        {.1point3acres缃
            int ii=i+d[cc], jj=j+d[cc+1];
            if(ii<0||ii>=n||jj<0||jj>=m) continue;. 1point 3acres 璁哄潧
            if(g[ii][jj]==k||g[ii][jj]==-k) ct++;. from: 1point3acres.com/bbs
            if(g[ii][jj]==k)
                q.emplace(ii,jj);
        }
        g[i][j]=-k;.鐣欏璁哄潧-涓浜-涓夊垎鍦
        res+=(4-ct);
    }
    return res;
}. more info on 1point3acres.com
回复 支持 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的点然后球上下左右的极值,这个不难吧
回复 支持 反对

使用道具 举报

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

使用道具 举报

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

import unittest


def count_edges(matrix, i, j):
    """
    :type matrix: List[List[int]]
    :type i: int
    :type j: int
    :rtype: int
    """
    target = matrix[j]
    is_visited = [[False for col in range(len(matrix[0]))] for row in range(len(matrix))]
. From 1point 3acres bbs
    return helper(i, j, target, matrix, is_visited)


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

    if is_visited[row][col]:
        return 0

    if target == matrix[row][col]:
        is_visited[row][col] = True
        return (0 +
                helper(row-1, col, target, matrix, is_visited) +-google 1point3acres
                helper(row, col-1, target, matrix, is_visited) +. from: 1point3acres.com/bbs
                helper(row+1, col, target, matrix, is_visited) +. from: 1point3acres.com/bbs
                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):
        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().鏈枃鍘熷垱鑷1point3acres璁哄潧
. From 1point 3acres bbs

补充内容 (2016-6-3 16:37):.鐣欏璁哄潧-涓浜-涓夊垎鍦
如果只想看解法、不想管test的話,就只看前兩個functions就行了
.鏈枃鍘熷垱鑷1point3acres璁哄潧
补充内容 (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的点然后球上下左右的极值,这个不难吧

找出「所有」為3的點,好像有點不對。我理解是:只有和題目給定的matrix[2][1]相連的3,才納入考慮。所以像matrix[0][3]的那一個3,就不必計入
回复 支持 反对

使用道具 举报

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

. 鍥磋鎴戜滑@1point 3 acres多谢安慰啊~不过我觉得肯定跪了,刚面完五分钟的时候想到中间更新result的时候貌似更新错了
回复 支持 反对

使用道具 举报

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

我用的是BFS, 找到所有可以reach的3的点,中间不断地更新现在得到的3组成图形的边数
.1point3acres缃
这是后来才想到的,当时面的时候跟新错了,没考虑完全
回复 支持 反对

使用道具 举报

 楼主| D__nancy 发表于 2016-6-3 23:00:14 | 显示全部楼层
chplushsieh 发表于 2016-6-3 16:42.1point3acres缃
找出「所有」為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?
. Waral 鍗氬鏈夋洿澶氭枃绔,
同学看下面的评论吧,我回复了。
就是所有能reach的所有3组成的图形的边长
回复 支持 反对

使用道具 举报

Jailf 发表于 2016-6-28 07:01:33 | 显示全部楼层
用C++写了一个DFS版本的,仅供参考. visit 1point3acres.com for more.
void helper(vector<vector<int>> & board, vector<vector<int>> & visited, int r, int c, int target, vector<int> & result, vector<pair<int, int>> & dir)
{.鏈枃鍘熷垱鑷1point3acres璁哄潧
        if (r >= 0 && r<board.size() && c >= 0 && c<board[0].size()){ 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                if (visited[r][c] == 0 && board[r][c] == target){. 1point3acres.com/bbs
                        //update four value;
                        if (r>result[0])
                                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;. more info on 1point3acres.com
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                        for (auto d : dir){. 1point 3acres 璁哄潧
                                helper(board, visited, r + d.first, c + d.second, target, result, dir);. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                        }
                }
        }.鏈枃鍘熷垱鑷1point3acres璁哄潧

        return;
}. Waral 鍗氬鏈夋洿澶氭枃绔,


int findMaxRec(vector<vector<int>> & board, int i, int j). from: 1point3acres.com/bbs
{
        //iterate every connected target and update the left, right, top, bottom value.

        //DFS
        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));
        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;
}

int main()
{. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
        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.. 1point3acres.com/bbs
点的个数*4-num就是答案。
回复 支持 反对

使用道具 举报

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

使用道具 举报

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

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

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 09:07

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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