头条AI-LAB算法实习生面试 2019-04-24

头条AI-LAB算法实习生面试 2019-04-24

一面

1. 浮点数开平方（正数）
   用二分查找法，需要注意的是浮点数不能用==判断相等，需要用阈值判断。

double my_sqrt(double num){ if (abs(num - 1.0) < 1e-6) return 1.0;
    double left = num, right = 1.0; if (num > 1.0)
        left = 1.0, right = num; while (right > left){
        double mid = (left + right) / 2; if (abs(num - mid * mid) < 1e-6) return mid; else if (num > mid * mid)
            left = mid; else right = mid;
    }
}

1. 项目，R2Plus1D模型中的卷积核与3D卷积核的区别；整个pipeline的时间开销；效果如何(讲了在公开数据集上的结果和自建数据集上的结果)
2. faiss，索引类型，针对某种数据分布应该如何修改索引类型；
3. 学习路径，CS231n后的课后习题；

二面

1. 有一个HxW的方块，用11，12，1*3的砖块填满，只能横着填，有多少种方法？
   解法1：定义状态f(a,b)是高为a，宽为b的方块一共有多少种填法，状态转移方程
   f(i,j) = f(i-1,j) * f(0, j)
   结果是f(H-1,W-1)，时间复杂度O(W*H)

int blocks_question(int w, int h){
    vector<vector<int>> memo(h, vector<int>(w, 0));
    memo[0][0] = 1;
    memo[0][1] = 2;
    memo[0][2] = 4; for (int i = 3; i < w; ++i)
        memo[0][i] = memo[0][i - 1] + memo[0][i - 2] + memo[0][i - 3]; for (int i = 1; i < h; ++i) for (int j = 0; j < w; ++j)
            memo[i][j] = memo[i - 1][j] * memo[0][j]; return memo[h - 1][w - 1];
}

解法2：首先看每一行有多少种填法，再用排列组合计算
每一行为1，2，4…
memo[i] = memo[i-1]+memo[i-2]+memo[i-3]
结果是 power(memo[w-1], h)
时间复杂度 O(W)

int blocks_question2(int w, int h){
    vector<int> memo(w, 0);
    memo[0] = 1, memo[1] = 2; memo[2] = 4; for (int i = 3; i < w; ++i)
        memo[i] = memo[i - 1] + memo[i - 2] + memo[i - 3];
    int result = 1; for (int num = 0; num < h; ++num)
        result *= memo[w - 1]; return result;
}

解法3：斐波那契数列的快速矩阵幂解法
参考讲解 https://www.jianshu.com/p/1c3f88f63dec
依然是计算每一行的拼法，然后乘方，对每一行用快速矩阵幂计算
时间复杂度 O(logW)

vector<vector<int>> matrix_mul(vector<vector<int>> num1, vector<vector<int>> num2){
    vector<vector<int>> result(num1.size(), vector<int>(num1[0].size(), 0)); for (int i = 0; i < num1.size(); ++i){ for (int j = 0; j < num1[0].size(); ++j){
            int val = 0; for (int k = 0; k < num1.size(); ++k)
                val += num1[i][k] * num2[k][j];
            result[i][j] = val;
        }
    } return result;
}

vector<vector<int>> matrix_power(vector<vector<int>> m, int t){ if (t == 1) return m;
    vector<vector<int>> half_t = matrix_power(m, t / 2); if (t % 2 == 1) return matrix_mul(matrix_mul(half_t, half_t), m); else return matrix_mul(half_t, half_t);
}

int quick_matrix(int w, int h){
    vector<vector<int>> coef{ { 1, 1, 1 }, { 1, 0, 0 }, { 0, 1, 0 } };
    vector<vector<int>> coef_power = matrix_power(coef, w - 3);
    int init_line = coef_power[0][0] * 4 + coef_power[0][1] * 2 + coef_power[0][2] * 1;
    cout << init_line << endl;
    int result = 1; for (int i = 0; i < h; ++i)
        result *= init_line; return result;
}

面试官不断提醒让优化，我只写出了前两种，第三种解法没有想出来。

1. k-means 中的k如何确定
2. 其他项目问题。