OD社招

Qing He

2025-03-10

应届生去当外包狗记录下过程。

机试部分

总分400，给定两个半小时。共三个编程题，难度应该是递增的，按通过的案例数给分。

牛客上面有华为的机试题库，难度一般，很少用到复杂的数据结构，所以说，题在网上都有，这也不算什么泄密了。

我分到的三个题分别是

小孩按身高差排序
给定全班小朋友的身高和一个新同学的身高，将原来班级的小朋友按与新同学的身高差（取绝对值）排序，相同身高差的身高较矮的排前面。
我的思路是用一个结构体表示身高和身高差，再快排。

#include <stdio.h>
#include <stdlib.h>
typedef struct {
    int height;
    int offset;
} child;
int cmp(const void *a, const void *b) {
    int h1, h2, x1, x2;
    x1 = abs(((child *)a)->offset);
    x2 = abs(((child *)b)->offset);
    if (x1 != x2)
        return x1 - x2;
    else {
        return ((child *)a)->height - ((child *)b)->height;
    }
}
int main(void) {
    int h, m;
    scanf("%d %d", &h, &m);
    child *allH = (child *)calloc(m, sizeof(child));
    for (int i = 0; i < m; i++) {
        scanf("%d", &allH[i].height);
        allH[i].offset = h - allH[i].height;
    }
    qsort(allH, m, sizeof(child), cmp);
    for (int i = 0; i < m - 1; i++) {
        printf("%d ", allH[i].height);
    }
    printf("%d\n", allH[m - 1].height);
    free(allH);
    return 0;
}

尽量花钱买三件物品
给定了一组没有重复的商品价格和口袋里有的钱，找出买三件不同物品最多花多少钱。没有就返回-1
我的思路：组合问题，只挑三件我甚至不需要回溯法，直接三层for暴力搜。（笔试题不在乎时间的，能过例子就有分。正经解法是DP，简化的背包问题）

//组合问题
int main(void) {
    int price[100] = {0};
    long long r = 0;
    int i = 0;
    while (1) {
        scanf("%d", &price[i++]);
        if (getchar() == '\n') break;
    }
    scanf("%d", &r);
    long long max = -1, tmp = 0;
    for (int i = 0; price[i] != 0; i++) {
        for (int j = i + 1; price[j] != 0; j++) {
            for (int t = j + 1; price[t] != 0; t++) {
                tmp = price[i] + price[j] + price[t];
                if (tmp > max && tmp <= r) {
                    max = tmp;
                }
            }
        }
    }
    printf("%lld\n", max);
    return 0;
}

前两道题都没什么难度，很快就能做完

加急打印，给定一串数字代表的优先级队列（0-9），每次从队头取出一个数，检查剩下的数有无比这个数大的，若有，这个数插入队尾，若无，打印这个任务，输出结果是原来队列的打印次序。
这个题麻烦就在输入是 9，3，4，3，这样，出现了两个3，但是打印次序是0，3，1，2。
考试过程中我没有想到什么快捷的好点子，就干脆直接实现一个队列

#include <stdio.h>
#include <stdlib.h>
typedef struct taskItem {
    int p;  //优先级
    int n;  //打印顺序
    struct taskItem *next;
} taskItem;
typedef struct {
    taskItem *head;
    taskItem *tail;
    int num;
} taskQueue;
void initQueue(taskQueue *Q) {
    Q->head = NULL;
    Q->tail = NULL;
    Q->num = 0;
}
void enQueue(taskQueue *Q, taskItem *p) {
    if (Q->num == 0) {
        Q->head = p;
        Q->tail = p;
    } else {
        Q->tail->next = p;
        Q->tail = p;
    }
    Q->num++;
}
taskItem *deQueue(taskQueue *Q) {
    taskItem *p;
    if (Q->num == 0) {
        p = NULL;
    } else if (Q->num == 1) {
        p = Q->head;
        Q->head = NULL;
        Q->tail = NULL;
        Q->num--;
    } else {
        p = Q->head;
        Q->head = Q->head->next;
        Q->num--;
    }
    return p;
}
int queueMax(taskQueue *Q) {
    int max = -1;
    taskItem *tmp;
    if (Q->num == 0) return 0;
    tmp = Q->head;
    for (int t = 0; t < Q->num; t++) {
        if (tmp->p > max) max = tmp->p;
        tmp = tmp->next;
    }
    return max;
}
int main(void) {
    taskItem taskTable[100];
    for (int i = 0; i < 100; i++) {
        taskTable[i].p = 0;
        taskTable[i].n = -1;
        taskTable[i].next = NULL;
    }
 
    //录入数据
    int i = 0;
    while (1) {
        scanf("%d", &taskTable[i++].p);
        if (getchar() == '\n') break;
    }
    //此时i的数值即为数量

    taskQueue Q;
    initQueue(&Q);
    for (int j = 0; j < i; ++j) {
        enQueue(&Q, &taskTable[j]);
    }

    taskItem *tmp;
    int max;
    int index = 0;
    while (Q.num > 0) {
        tmp = deQueue(&Q);
        if (tmp->p >= queueMax(&Q))
            tmp->n = index++;
        else {
            enQueue(&Q, tmp);
        }
    }

    for (int t = 0; t < i; ++t) {
        if (t != 0) putchar(',');
        printf("%d", taskTable[t].n);
    }
    putchar('\n');
    return 0;
}

运气很好，三个题通过率都是100%，最后那边告诉我400分通过。

性格测试

大概30分钟能完成，离谱的是，让我去测之前那边就提示我了应该尽量怎么选，我当耳边风了（哭唧唧）。。送分题可能最后成绩差得一批。（我要是挂在这上面岂不是今年年度大冤种）

技术面试

在线面试也不用那么拘束
面试官先给了一道leetcode的题，说给我50分钟（正常来讲应该是30分钟，可能是看我应届留情了），leecode74题，行列都递增的矩阵中的快速查找算法。这个题思路很清晰，都告诉有序了，这不就是变相告诉我用折半查找嘛。快速写完程序，然后就调试了40分钟（这就是写得少了，不熟！）。。。
我想到两种折半方法，第一种方法是先行首折半，找到对应行，再列折半查找。第二种方法是把这个矩阵直接在一维上折半查找。第一种方法如果能找到是肯定能锁定下标的，第二种方法的话可能就要转换下标，虽然题目没做要求。重点是这个题没有告诉我这个矩阵行与行之间是否是连续的地址（int *matrix[3];for(int i=0;i<3;++3)matrix[i] = (int*)calloc(3,sizeof(int));），所以优先写第一种方法。

#include <inttypes.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
bool searchMatrix(int** matrix, int matrixSize, int* matrixColSize,
                  int target) {
    //先列折半，确定行
    //行折半查找
    // matrixSize:行数
    //*matrixColSize 列数
    // printf("%d %d",matrixSize,*matrixColSize);

    if (target < matrix[0][0]) return false;  //只有一行迅速跳过
    int left = 0, right = matrixSize - 1, mid;
    while (left != right) {
        mid = (left + right) / 2;
        if (matrix[mid][0] == target)
            return true;
        else if (matrix[mid][0] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    int low = 0, high = *matrixColSize - 1;
    while (low <= high) {
        mid = (low + high) / 2;
        if (matrix[left][mid] == target)
            return true;
        else if (matrix[left][mid] > target) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return false;
}

代码写得挺快的，后期调试，处理边界值搞人心态。好在leetcode会说明是哪个用例通不过，可以迅速发现问题所在，最后是通过全部用例了。
然后面试官问了这个题的思路如何如何。
接下来：
Q1：区分int (*p)[3]和int *p[3]。
我可能是有些些紧张，有些语无伦次，这个题我是能回答上来的，但是最后没整对，很明显，第一个是定义了一个指针p，指针p指向容量3的数组,有点像int p[1][3]，访问元素的方式*p[1]或者p[0][1]；第二个是定义了一个名为容量3的int *类型数组，理解成[]的优先级比*高就行了
Q2：

char str[100],stri[10];
for(int i=0;i<10;++i){
    stri[i] = 'a'
}
strcpy(str,stri);
printf("%s",str);

这段代码的输出是？
我当时答的是会越界，后来仔细想了想，还有其他问题，首先，str和stri都没有初始化倒不是什么特大问题，从内存中栈结构上来说，str在高地址stri在相邻的低地址。在strcpy的时候，由于stri空间内没有’\0’，所以strcpy会越界去str的低内存空间中复制，但由于此处已经提前复制了’a’，所以后面会一直复制’a’，永远碰不到’\0’，最后爆栈。有些东西只有后面做总结才发现问题！这个题应该足够划分应聘者的水平了（我是大冤种，马后炮）
Q3：说出几种排序算法
这个简单，应该没什么坑，分大类，选择排序、交换排序、插入排序。具体简单选择，堆排，冒泡，快排，直插、折半、希尔，其他还有归并和基排
Q4：链表和数组的区别
最大的区别应该就是数组可以随机访问，链表需要一个一个找到目标
Q5：说出在50位置插入一个元素，链表和数组的效率哪个快
如果有序表长度在50附近，那么数组快，如果有序表长度远超50，那么链表快
Q6：散列表的特点？
我归纳不出来，回答的可以随机访问
Q7：说出图的广度优先遍历算法
广度优先遍历需要用到一个队列，入队第一个结点，出队并标记，入队该结点所有没有被标记的相连结点，最后直到队空（连通图）或者所有结点被标记（非连通图，需要手动入队）

Q8：描述下遗传算法是怎么运作的
遗传算法最重要的是解的编码和适应度函数，生成一堆初始解，再选择适应度高的父代繁殖得到子代，这样重复迭代，最后种群的基因稳定下来适应度最好的哪个解就是近似解
Q8：你怎么查文档，有哪些经验，就比如查遗传算法
这个题我还真不知道怎么答才好，从我自己的经验上来讲，需要快速解决的问题直接谷歌一搜就完事，什么博客文档里面的解决方案拿来试试先，但遇到需要研究的东西可能就需要查学术了，（毕竟博客的东西那质量是真的参差不齐）。选择年代比较久远的论文，里面的东西比较容易理解，然后再去找它的变种或扩展运用。

Q9：Linux的看进程的命令是哪个
top，ps都可以，也可以看/proc里的文件
Q10：怎么查看完整的进程包括它的子进程
这个我隐约记得是个ps，桌面环境用多了命令就用的少了点都不熟悉想不起来，事后查了下是pstree
Q11：我有一个文件，里面每一行是用逗号分割的数据，我想看每一行的第一个和第三个数据怎么用命令
（哭唧唧）隐约记得是个aw什么的还是sed。我自己用的少实在想不起来。事后去回顾了下
awk -F, '{print $1,$3}' < text.txt
或者用管道cat text.txt | awk -F, '{print $1,$3}'

数据库的操作
Q11：查询用那个命令
一听到数据库我就慌了，上次用数据库还是写机器人，一年前的事儿了
SELECT
Q12：分组查询是用哪个
想不起来（group by）

然后面试官也没再问了就结束了

技术面试二

本次面试没有什么特别新鲜的问题，常规的c语言和数据结构问题，Linux问题，然后还说了一些今后入职可能会用到的一些技术。

比较经典的是问了C语言中static的作用

static修饰局部变量：静态存储区
static修饰全局变量：限制全局变量的作用范围为本文件内。
static修饰函数：也是限制函数的可用域在本文件内。

最后同样还是要做一道leetcode101：判断给定的树是否为以根节点为对称的树
我之前在考研复习的时候碰到过这个题，当时做错了，有些心理阴影，生怕这次也做错了，好在最后逻辑表达还是很清晰，验证也通过了leetcode。（面试官前辈还很好心地提醒了哪哪哪可以简化）

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
bool isMirror(struct TreeNode* a, struct TreeNode* b) {
    if (!a && !b) return true;             //都空
    if (!(a && b)) return false;           //有一个空
    if (a->val != b->val) return false;    //都不空，但不相等
    return (isMirror(a->left, b->right) && isMirror(a->right, b->left));
}

bool isSymmetric(struct TreeNode* root){
    return (root && isMirror(root->left, root->right));
}

HR面试

面试之前我去问了问给我做面试安排的人，他说我不需要做什么准备，然后我就真的没有做什么准备（哭唧唧）。
HR的问题很有压力（相比下来，前面的技术面试官简直随和得一塌糊涂），实际上他所问的很多问题都是能在网上找到的，别人都有做总结（这下真是大冤种），面试完后一个劲后悔为什么没提前搜下HR会问的问题。。。

事后总结

华为OutDog，点击就送。（太累了，怎么会有凌晨还要接电话起来干活的工作啊！！！！），已离职去学校打廉价工了，别问我。