Bloomberg电面

刚刚面完，只写了一道题。貌似还没有写对肯定是跪了啊 之前看地里的电面 面经都挺简单的啊，说好的twosum呢呢呢呢

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

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

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;
    queue<pair<int,int>> q;
    int k=g[a][b];
    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++)
        {
            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;
        res+=(4-ct);
    }
    return res;
}

题目没看懂。。 能求楼主详解下吗。感谢。

用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){
                        //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;

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

        return;
}


int findMaxRec(vector<vector<int>> & board, int i, int j)
{
        //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;
}

图形边数？是说围成的最大矩形边长吗？祝LZ好运。。。

没看懂题，，为什么是返回10？

感觉BB的确差异挺大的难度。。比较看面试官貌似。。也不一定是坏消息~

是的，返回围成的最大矩阵的边长

我下星期就要面Bloomberg了，
試著寫了這一題（花了好多時間，真遇到就要跪了...），
請指教（第一次在python寫unit test，以下內容可以用python3執行）：


import unittest


def count_edges(matrix, i, j):
    """
    :type matrix: List[List[int]]
    :type i: int
    :type j: int
    :rtype: int
    """
    target = matrix[i][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):
    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) +
                helper(row, col-1, target, matrix, is_visited) +
                helper(row+1, col, target, matrix, is_visited) +
                helper(row, col+1, target, matrix, is_visited))
    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()


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

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

ptbrxlphx 发表于 2016-6-3 08:10
找出所有为3的点然后球上下左右的极值，这个不难吧

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