字节跳动 游戏客户端开发 一面凉经2021/4/19

面试官人很nice,面试过程中一直在引导我回答
首先是自我介绍,后面的会根据自我介绍的内容来提问
1.介绍下c++中的const
2.介绍下c++中的static。回答后,又问使用static修饰的局部变量的时候,有什么要注意的?(我没有答上来,面试官提示多线程。复盘的时候发现公共变量在多线程中使用都需要额外注意)
3.介绍下c++11中的新特性
4.当实例化对象的时候,构造函数调用的过程是什么(从父类的构造函数开始调用,一直调用到子类的构造函数)
5.运行时多态,也就是指向父类的指针指向子类的时候,调用虚函数的过程(讲清楚虚指针,虚表就好了)
6.介绍下设计模式(有一个网站把设计模式归纳的挺好的:refactoringguru.cn)

图形学部分
1.MVP变换中,介绍下V矩阵的结构
2.假设在一个游戏场景中有许多棵树,我如何快速检测到主角有没有和树发生碰撞(之前一个劲的学渲染了,这方面完全没有了解过。只答了类似的情形:光线追踪中用BVH树划分三角形然后快速搜索与光线相交的三角形。现在复盘还没有找到答案,网上搜的大部分是用AABB盒。希望有高人能点一下这属于哪方面的内容。)

算法题
打印矩阵中连通的区域,这里元素之间连通是指两个元素相邻且值相等
例如输入
0 1 2 3
1 2 2 3
1 4 4 3
输出
0
1
2 2 2
1 1
4 4
3 3 3
一开始想用非递归的方法来做的,但是写到后面写不出来了,又开始用递归的思路写,最后时间到了还没有写出来,面试官看了遍代码完全不行,这次面试应该就是栽在这里了。算法题有无时间限制做起来完全是两种感觉,一定要在刷题的时候给自己时间限制。
没有在leetcode上找到原题,就把代码写在这里了

vector<int> dx = { 0, 0, 1, -1 };
vector<int> dy = { 1, -1, 0, 0 };
void findOneConnected(vector<int> &connected, const vector<vector<int>> &mat, vector<vector<int>> &flag, int i, int j, int r, int c);
vector<int> findOneConnected2(const vector<vector<int>>& mat, vector<vector<int>>& flag, int i, int j, const int r, const int c);

int main() {
    vector<vector<int>> mat = 
    {
        {0, 1, 2, 3, 3},
        {4, 2, 2, 3, 4},
        {4, 4, 4, 3, 9},
        {1, 4, 4, 5, 9}
    };
    int r = mat.size(), c = mat[0].size();
    vector<vector<int>> flag(r, vector<int>(c, 0));
    vector<vector<int>> AllConnected;
    for (int i = 0; i < r; ++i) {
        for (int j = 0; j < c; ++j) {
            if (flag[i][j] == 0) {
                //递归
                //vector<int> OneConnected;
                //findOneConnected(OneConnected, mat, flag, i, j, r, c);
                //AllConnected.push_back(OneConnected);
                //非递归
                AllConnected.push_back(findOneConnected2(mat, flag, i, j, r, c));
            }
        }
    }
    for (auto &OneConneted : AllConnected) {
        for (auto &ele : OneConneted) {
            cout << ele << ' ';
        }
        cout << '\n';
    }
}
    
    //递归        
void findOneConnected(vector<int> &connected, const vector<vector<int>>& mat, vector<vector<int>>& flag, int i, int j, const int r, const int c) {
    for (int k = 0; k < 4; ++k) {
        int newi = i + dx[k], newj = j + dy[k];
        if (newi>= 0 && newi < r && newj>= 0 && newj < c) {
            if (flag[newi][newj] == 0) {
                if (mat[newi][newj] == mat[i][j]) {
                    connected.push_back(mat[i][j]);
                    flag[i][j] = 1;
                    findOneConnected(connected, mat, flag, newi, newj, r, c);
                }

            }
        }
    }
    if (flag[i][j] == 0) {
        connected.push_back(mat[i][j]); flag[i][j] = 1;
    }
}

//非递归
vector<int> findOneConnected2(const vector<vector<int>>& mat, vector<vector<int>>& flag, int i, int j, const int r, const int c) {
    vector<int> res;
    stack<int> connected;
    stack<pair<int, int>> pos;
    stack<int> direct;
    connected.push(mat[i][j]);
    flag[i][j] = 1;
    pos.push({ i, j });
    direct.push(0);
    while (!connected.empty()) {
        while(direct.top() < 4) {
            int k = direct.top();
            int newi = pos.top().first + dx[k], newj = pos.top().second + dy[k];
            ++direct.top();
            if (newi >= 0 && newi < r && newj >= 0 && newj < c) {
                if (mat[newi][newj] == connected.top() && flag[newi][newj] != 1) {
                    connected.push(mat[newi][newj]);
                    flag[newi][newj] = 1;
                    pos.push({ newi, newj });
                    direct.push(0);
                }
            }

        }
        res.push_back(connected.top());
        connected.pop();
        pos.pop();
        direct.pop();
    }
    return res;
}
后面在努力努力,再投一遍#面经##游戏客户端开发工程师##字节跳动#
全部评论
class Solution0423 { public:     vector<vector<int>> res;     vector<int> dx = { 0,0,1,-1 };     vector<int> dy = { 1,-1,0,0 };     vector<int> temp;     vector<vector<int>> showPath(vector<vector<int>>& matrix)     {         vector<vector<int>> backUp = matrix;         int m = matrix.size(), n = matrix[0].size();         for (int i = 0; i < m; i++)         {             for (int j = 0; j < n; j++)             {                 dfs(i, j, matrix, backUp[i][j]);                 if (!temp.empty())                 {                     res.emplace_back(temp);                     temp.clear();                 }             }         }         return res;     }
1 回复
分享
发布于 2021-04-23 16:45
楼主你好,请问你是实习、校招还是社招?
点赞 回复
分享
发布于 2021-04-20 14:02
英特尔
校招火热招聘中
官网直投
树的那题应该是用K-D树写
点赞 回复
分享
发布于 2021-04-20 14:15
多久之后能投第二次丫..
点赞 回复
分享
发布于 2021-04-20 16:12
  void dfs(int i, int j, vector<vector<int>>& matrix, int cur)     {         if (i < 0 || i >= matrix.size() || j < 0 || j >= matrix[0].size() || matrix[i][j] != cur) return;         temp.emplace_back(matrix[i][j]);         matrix[i][j] = -1;         for (int k = 0; k < 4; k++)         {             int newx = i + dx[k];             int newy = j + dy[k];             dfs(newx, newy, matrix, cur);         }     } };
点赞 回复
分享
发布于 2021-04-23 16:45

相关推荐

2 20 评论
分享
牛客网
牛客企业服务