分享大厂的一些笔试题目

乐鑫

1. 签到题
2. 完全k叉树, 完全不会.

乐鑫的笔试题是我做过最难的, 后面批次的, 我听说直接和高数相关, 用编程来求解数学问题.

vivo

1. 签到题
2. 01背包原题
3. 图的关键路径(不会)

动态规划没那么难, 经典的背包问题, 公共子串问题, 矩阵相关的问题多在力扣找几道刷一刷.

除了力扣, 在学习算法的过程中, 胡凡的<<算法笔记>>也是我经常翻阅的一本书, 网上有电子版, 里面很多问题都分析得很清晰.

图的话, 关键路径, 拓扑排序, 广度优先, 深度优先等有空就看看, 对于嵌入式来说是加分项.

大华

基本是C++题目, 坑.

如果比较看重大华, 还是多准备一下C++基础, 我也想不懂明明是C语言岗位, 搞那么多C++干嘛.

联发科技

最后的编程题是实现双向升序链表(带头节点的).

后台出了问题不管怎么提交都是0分.

联发科这道题本身不难, 但是自己很多测试样例都符合预期, 提交却是0分, 有点搞心态了.

后来笔试通过了, 所有人都是这种情况, 应该就是专门来搞你心态的吧.

蔚来汽车

两道中等题 100 + 80都挂了

1. leetcode75题颜色分类原题
2. 给定一个随机数组, 求四个不同的数使得a+b=c+d

我A了第一道题, 第2题拿了80%的分数, 最后笔试没通过.

后面蔚来给别人开的确实很高还有期权, 一般感觉上海的厂都要难一点.

第2题我用的是先排序, 然后找两数之和相等的方法.

力扣里有两数之和, 三数之和, 四数之和可以多练练.

我的同学看我练习求和这么欢乐, 自己搞了个n数之和.

紫光展锐

太简单了.

简单到不记得考过什么...

星宸科技

选择填空是基本的C语言知识.

关于函数指针和函数指针数组这一块不记得怎么做了.

可以参考"C和指针"第13章有关函数指针的话题.

(考完这场以后, 我补习了这块知识, 后面经常被问到).

智力题

0 1 2 3 4 5 6 7 8 9

- - - - - - - - - -

在每个_上填一个数字, 代表它正上方的数字在_中将出现的次数.

比如3下面填1, 那么3就在下面出现一次, 比如说是0下面, 那么0就要出现3次.

还有一道小学数学题

两个线程对初始值为0的变量a进行操作(一次), a的可能值, 要写推理过程.

线程1: a++;a++;

线程2: a += 2;

手写strcat()

手写合并升序链表, 不可破坏原链表.

禾赛科技

做对了2道题都把我挂了(又是上海的公司).

第3题是一道复杂的排序问题.

好吧, 别人不是小公司, 群里有个搞硬件的拿到了40w多的总包.

诺瓦科技

比较简单的C语言.

CVTE

有单选题, 不定项, 涉及C++, C, Linux驱动, 简单的数据结构与算法.

两道编程题:

(1)同leetcode70爬楼梯(要求时间空间低).

(2)质因数分解.(这里可以参考胡凡的算法笔记).

编程题不能编译, 不能运行, 写就完事.

大疆

一些选择填空, 涉及ARM, Linux, C语言.

写一下比较有印象的题目:

1. 求container_of

这是我在rt-thread的源码里翻出来的

#define rt_container_of(ptr, type, member) \ ((type *)((char *)(ptr) - (unsigned long)(&((type *)0)->member)))

1. 求1~n中字符1出现的次数(剑指offer原题)

这题大意了, 当作签到题来做了, 不过力扣是困难题, 应该也是不会做.

1. 给定精度n, 求pi

第3题实在不会做, 在网上找了也没找到看得懂的方法.

大疆给得真的好高, 好好做.

诺瓦科技

一些跨时钟域的问题不会

编程题一道是串口转并口

一道是64位全加器, 但是由于器件特性, 不能使用reg [63:0]这样的寄存器.

荣耀

1. 签到题. 输入是一行有字母有数字的字符串, 问输入的数字可组成十进制数.
2. 动态规划走二维矩阵, n*n矩阵里面只有-1 0 1三种元素, -1代表障碍, 0代表什么也没有, 1代表怪兽.

奥特曼一开始在(0,0)他要走到(n-1,n-1)然后返回(0,0), 问奥特曼最多可以打败多少怪兽(怪兽杀死以后就没了, 对应的格子从1变成0. 奥特曼可能无法到达(n-1,n-1), 这时要返回0. 往(n-1,n-1)走时, 只能向下或向右移动, 往(0,0)走时, 只能向上或向左移动.

注意, 因为怪兽杀死以后就不存在了, 所以要用一个数组来保存路径.

1. 有一个3*3的矩阵

相邻的元素代表可直接到达, 比如1可到达2, 2也达到1, 元素本身也可到达自己.

即以上矩阵是一个有向有环图.

然后题目输入一些条件, 告诉你要把哪些边去掉.

然后输入一个n.

问在走n步的情况下(也可能走不完n步, 每一步都代表经过一条边), 可以组成的数字最大是多大?

比如n为3, 然后走过1 2 3 3, 那个就组成了1233这个数字.

没做出来, 感觉就是深度优先.

今年是荣耀第一年校招, 后面给开奖能去到40w, 还是挺不错的, 好好对待荣耀的考试.

美团

1. 小美的序列检查

小美给小团一个m个数字构成的数字序列, 问小团能不能经过重新排序后形成1到n的排列.

举例:

小美给小团[2,1,3], 则可以经过重新排列后构成[1,2,3], 这是可行的.

小美给小团[4,4,1,3], 则无法重新排列后构成[1,2,3,4], 这是不可行的.

为了防止小团碰对答案, 小美会进行多组询问.

哈希表解决

1. 小美的回文串构建

同力扣214. 最短回文串(困难)

1. 机器人爆炸时刻

小美在数轴上放置了若干个机器人, 这些机器人每到整数时刻, 就会检查是否和其他机器人重合. 如果重合, 它就会原地爆炸. 这些机器人的移动速度均为1. 举例来说, 如果一个机器人初始位于点3, 然后它的方向是向右的, 则时刻1会位于点4, 时刻2会位于点5.

小美给小团这样一个任务: 小美将给出所有机器人的初始位置和初始朝向. 小团的任务是判断每个机器人的爆炸时刻. 当然, 如果有一些机器人永远不会爆炸, 则输出-1.

小团向你求助, 你能帮帮小团吗?

注意事项1: 一个机器人爆炸了之后, 就不会再继续存在在这个数轴上.

举例来说, 如果有三个机器人, 一个位于位置0, 向右, 一个位于位置2, 向右, 一个位于位置4, 向左. 则时刻1的时候, 后两个机器人会在位置3相遇并发生爆炸. 此后第一个机器人和第三个机器人不会在时刻2继续爆炸(因为此时已经不存在第三个机器人了).

注意事项2: 请注意, 只有整数时刻机器人才会检查重合.

举例来说, 如果有两个机器人, 一个位于位置1, 向右, 一个位于位置2, 向左, 则它们并不会在整数时刻重合. 因此它们两个不存在相遇爆炸.

注意事项3: 保证机器人初始时刻不会重叠. 换句话说, 不存在时刻0就立刻爆炸的机器人.

输入描述:

第一行一个正整数n, 表示有n个机器人.

接下来n行, 每行一个正整数和一个字符, 以空格分隔, 正整数代表机器人的坐标, 字符为大写字母L和R其中的一个, 分别表示机器人向左运动和向右运动. (坐标不是从小到大录入的, 是随机的)

输出描述:

输出n行, 每行一个数字, 对应每个机器人的答案: 若该机器人会爆炸, 输出爆炸时间; 若该机器人不会爆炸, 输出-1.

1. 小美最快到达时间

一个图的最短路径问题.

只A了前两道, 还是暴力做出来的.

科大讯飞

1. 将num从右往左的第二个比特0变为比特1.

做的时候用了最普通的循环方法.

后来想想可以这样做:

int ans = ~num; ans = ans & (ans – 1); // 最低比特1位清零 ans = ans & (-ans); // 取最低比特1位 nums |= ans; // num的第二个比特0变为1

1. 输入一个字符串, 该字符串最多只会出现小写字母和'?', '?'可以代替任意一种小写字母, 求该字符串能包含26种小写字母的最小区间长度.

使用哈希表+双指针做出来了.

1. 输入二叉树和常数k, 求有多少对叶子节点的距离为k.

这道题做了好久, 最终只通过20%.

小马智行

选择题涉及C语言基础, 单片机基础, Linux内核基础.

问答题:

1. 简述操作系统发生中断到响应中断的过程.

这题我采用的是韦东山讲解Linux对中断的处理演进那一章的知识.

1. 简述uart, spi, iic的异同.

编程题:

1. 合并两个升序链表, 力扣有原题.
2. 从一串格式字符串中解析出日期. 比较麻烦的是格式字符串可能会不符合格式, 至于会怎样不符合格式, 你要自己去猜一下.

"$GPRMC,144326.00,A,5107.0017737,N,11402.3291611,W,0.080,323.3,210307,0.0,E,A*20\r\n"

20070321

从第10段数据中解析出正确年月日.

"$GPRMC,144326.00,A,5107.0017737,N,11402.3291611,W,0.080,323.3,21030*,0.0,E,A*20\r\n"

0

格式有错误

"$GPRMC,144326.00,A,5107.0017737,N,11402.3291611,W,0.080,323.3,2103,0.0,E,A*20\r\n"

0

日期是从1980.1.1开始到当前.

考试系统已经给出部分代码, 我只需要实现ParseGprmcAndGetDate()函数.

下面是我的答案

#include <stdio.h>
#include <stdint.h>
#include <string.h>

// dd-mm-yy
int ParseGprmcAndGetDate(const char* gprmc_string) {
  // 请在这里实现解析并返回结果
    int cnt = 0;
    int i = 0;
    int ans = 0;
    int dd = 0, mm = 0, yy = 0;
    int n = strlen(gprmc_string);
    while(i < n && cnt != 9) {
        if(gprmc_string[i++] == ',') {
            ++cnt;
        }
    }
    if(cnt != 9) return 0; 
    while(i < n && cnt != 10) {
        char ch = gprmc_string[i];
        if(ch == ',') {
            ++cnt; 
        }
        else if('0' <= ch && ch <= '9') {
            ans = ans * 10 + ch - '0';
        }
        else {
            return 0;
        }
        ++i;
    }
    yy = ans % 100; ans /= 100;
    mm = ans % 100; ans /= 100;
    dd = ans;
    if(mm == 0 || dd == 0) return 0;
    int rslt = 0;
    if(80 <= yy && yy <= 99) {
        rslt = (1900 + yy) * 10000 + mm * 100 + dd;
    }
    else if(yy <= 21) {
        rslt = (2000 + yy) * 10000 + mm * 100 + dd;
    }
    return rslt;
}

int main() {
    char input_str[1000] = {0};
    scanf("%s", input_str);
    printf("%d\r\n", ParseGprmcAndGetDate(input_str));
}

小马这次笔试还是挺简单的, 听说以前的笔试题都很难.

360

选择题什么都有: java, c++, c, 数据库, Linux, 推理题, 程序填空题, 程序改错题.

编程题:

1. 又到了一学期一次的大学生期末考试。但很多人期末考试的卷面成绩是不能及格的，需要靠较高的平时成绩来拖上去。平时成绩与期末考试的占比已经确定，假设平时成绩占比为p，期末考试占比为q，平时分为a，期末考试分数为b，则总成绩为(pa+qb)/100。（平时分与期末成绩都是整数，但总成绩可以是小数。） 饶老师心肠特别好，他希望自己的学生及格率尽可能的高。但他也坚持期末考试分数更高的学生平时成绩也一定要更高。饶老师想知道在这种情况下，他们班的最大及格人数是多少（及格是指总成绩不低于60分）。

输入

第一行: 三个正整数n p q

第二行：n个学生的期末考试成绩

这道题不难, 用贪心做就好了, 倒是自己被数组下标卡了好久, 状态不太好.

#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

int main(int argc, char **argv) {
    int n, p, q;
    vector<int> nums;
    scanf("%d%d%d", &n, &p, &q);
    for(int i = 0; i < n; ++i) {
        int ans;
        scanf("%d", &ans);
        nums.push_back(ans);
    }
    sort(nums.begin(), nums.end());
    
    n = nums.size();
    int minDayScore = 100;
    
    // 最高分平时分满分也没办法及格
    if((p * minDayScore + q * nums[n - 1]) < 6000) {
        printf("0\n");
        return 0;
    }
    int rslt = 1;
    for(int i = n - 2; i >=0; --i) {
        if(nums[i] == nums[i + 1]) {
            ++rslt;
        }
        else {  // nums[i] < nums[i + 1]
            minDayScore -= 1;
            if(minDayScore < 0) {
                break;
            }
            if((p * minDayScore + q * nums[i]) >= 6000) {
                ++rslt;
            }
            else break;
        }
    }
    printf("%d\n", rslt);
    return 0;
}

1. 长城上有连成一排的n个烽火台，每个烽火台都有士兵驻守。第i个烽火台驻守着ai个士兵，相邻峰火台的距离为1。另外，有m位将军，每位将军可以驻守一个峰火台，每个烽火台可以有多个将军驻守，将军可以影响所有距离他驻守的峰火台小于等于x的烽火台。每个烽火台的基础战斗力为士兵数，另外，每个能影响此烽火台的将军都能使这个烽火台的战斗力提升k。长城的战斗力为所有烽火台的战斗力的最小值。请问长城的最大战斗力可以是多少？

样例输入

5 2 1 2 4 4 2 4 4

样例输出

6

提示:

有5个烽火台，2名将军，将军的影响范围为1，提升战斗力的值为2。令将军驻守在第2和第4个烽火台，这样所有烽火台的战斗力都是6。

完全没思路.

ARM

选择题有数据结构, C语言, Linux, 推理题.

编程题:

(1) 程序改错: 反转字符串

(2) 程序填空: 判断有环链表

(3) 程序填空: 将视频的YUV格式转换为RGB8888格式.

(4) 编程题: 反转字符串中出现的每个单词, 字符串可能会出现所有可打印字符, 完全由字母组成的一串字符字串可以看作一个单词.

ARM用的是acmcoder系统, 设置成了不可跳出界面, 编辑器没有补全, 不可以用tab键, 不可以复制粘贴, 不可以编译运行, 总之体验很差.

英伟达

选择题没什么难度, 就是全英文.

1签到题.

2.c++重载运算符输出二维矩阵的求和(直接放弃).

3 长度相差1的字符串A B, 如果A删减一个字符可得到B，则存在A到B的路径 求一个字符串数组的最长路径长度.

第三题应该是转换为图 然后搜索一下 只做对了一半 被字符串对比函数卡了好久

英伟达挂了, 群里有个老哥, 英伟达给开了30w+40w股票, 爽翻了. 外企作息, 老婆生娃有产假.

燧原

做的什么题目忘了, 感觉题目很一般.

后面也把面试拒了.

OPPO

第1题.

小欧同学写了一个随机字符串生成机，它会生成长度为[1,10000]之间的字符串mSg，且仅包含小写字母或者大写字母。小欧想知道生成的每个字符串msg所包含的字母能拼成多少个 oppoyes（都为小写），要求msg中的字母不能重复使用，但是每个大写字母能当作对应两个小写字母来使用。请帮小欧同学完成这个需求。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回字符串msg包含的字母能拼成oppoyes的数量
     * @param msg string字符串 输入字符串
     * @return int整型
     */
    int getCount(string msg) {
        // write code here
        char ht[300] = {0};
        
        for(auto ch : msg) {
            switch (ch) {
                case 'o': case 'p': case 'y': case 'e':
                case 's': ht[ch] += 1; break;
                case 'O': case 'P': case 'Y': case 'E':
                case 'S': ht[tolower(ch)] += 2; break;
                default: break;
            }
        }
        int rslt = 10000000;
        string str("opyes");
        for(auto ch : str) {
            if(ch == 'o' || ch == 'p') {
                ht[tolower(ch)] /= 2;
            }
            rslt = rslt < ht[ch] ? rslt : ht[ch];
        }
        return rslt;
    }
};

第2题:

给你一个整数数组nums，该数组中至少有一个元素为0，其余的都为正数。假设你的起始位置为数组索引 begin处。当你位于数组任意索引index处时，你可以选择移动到下一个索引值为index+nums[index]或者index-nums[index]的位置。当你想要移动的位置超过数组边界时，就采取循环移动的方式，比如假设nums长度为10，你想要移动到位置12，那么你实际移动到位置2，如果你想要移动到-1，那么你实际移动到9。

请你判断你是否能移动到数组中元素值为0的位置。其中，0<nums.size()<10000，0<=nums[index]<10000， 0<=begin<nums.size()

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 检测是否可以从数组nums的初始位置begin处开始，移动到元素值为0的位置
     * @param nums int整型vector 输入数组
     * @param begin int整型 起始位置
     * @return bool布尔型
     */
    bool helper(vector<int>& nums, int begin, vector<int> &isUsed) {
        int n = nums.size();
        if(nums[begin] == 0) return true;
        if(isUsed[begin]) return false;
        isUsed[begin] = 1;
        int left = begin - nums[begin];
        int right = begin + nums[begin];
        if(left < 0) {
            left = n - ((-left) % n);
        }
        right %= n;
        return helper(nums, left, isUsed) || helper(nums, right, isUsed);
    }
    bool checkReach(vector<int>& nums, int begin) {
        // write code here
        int n = nums.size();
        vector<int> isUsed(n, 0); // isUsed[i]表示索引为i的元素是否已经遍历过
        return helper(nums, begin, isUsed);
    }
};

第3题:

小欧认为这样的二叉树属于漂亮树：

偶数层上所有节点的值都为偶数，且从左往右严格单调递增奇数层上所有节点的值都为奇数，也满足从左往右严格单啁递增下图所示即为一棵漂亮树：

其中，二又树结点数量范围为[1,10 ^ 5]，且每个节点的值的范围为[0,10 ^ 5]给你一颖二叉树，请帮小欧判断其是否属于漂亮树。

说明：#表示二叉树对应位置节点为空

/**
 * struct TreeNode {
 * int val;
 * struct TreeNode *left;
 * struct TreeNode *right;
 * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 判断root是否是一颗漂亮树
     * @param root TreeNode类 二叉树根节点
     * @return bool布尔型
     */
    bool isBeautyTree(TreeNode* root) {
        // write code here
        queue<TreeNode *> qe;
        int curLevel = 0;
        int eveodd = 1;
        qe.push(root);
        while(!qe.empty()) {
            int size = qe.size();
            eveodd = eveodd ^ 1;   // 当前是奇数层还是偶数层
            int preVal;
            for(int i = 0; i < size; ++i) {
                TreeNode *node = qe.front();
                int ans = node->val;
                if((ans & 1) != eveodd) return 0;
                if(i == 0) {
                    preVal = ans;
                }
                else if(ans <= preVal) {
                    return false;
                }
                else {
                    preVal = ans;
                }
                qe.pop();
                if(node->left) qe.push(node->left);
                if(node->right) qe.push(node->right);
            }
        }
        return true;
    }
};

oppo的题目还是挺简单的, 很快就全A了.

不过今年oppo大量裁员, 对它的印象不太好. 后面开了34w, 拒了.

vivo

第1题:

某业务平台策划了一次运营推广活动：通过向新用户推送广告消息，吸引用户到平台中来。现在已知给用户 person_i发推送信息，需要支付cost_i的费用，但是该用户只有p_i（0<=p_i<=1）的概率会被吸引到平台中，即该用户的转化期望为p_i，那么定义：期望推广成本avg_cost=总用/总期望转化用户数。

请问：如何选择用户并推送广告，确保 avg_cost<=K的同时能给平台吸引到最多的新用户？

这道题读完题目没搞懂, 就放弃了. 只有一个小时, 先看后面.

第2题:

已知完成一个简单的工作需要1天工时，完成一个中等难度的工作需要2天工时，完成一个困难的工作需要4天工时。假设未来4周有n个工作日有空闲时间可以用来接受这些工作，请编程返回能够填满n个工作日所有可能的任务排列数可用1,2,4分别表示简单，中等，困难的任务。

一开始以为是完全背包的变种, 后来才知道是爬楼梯的变种, 然后在初始值哪里被坑了好久.

这道题全A, 但是做出来时间所剩无几了.

第3题:

zeoy同学正在对wvo游戏中心的某款游戏做分析评估。已知该游戏中有N个武将，每个武将均有K个属性（例如：武力、智力、敏捷、防御等等），若对于每个属性来说，武将A该属性的值都大于武将B该属性的值，那我们就称之为武将A碾压武将B

现给出一个二维数组 heroes[N][K]，其中N表示有多少个武将、K表示有多少个属性值（每个属性值均为整数），请你帮助zeoy在所有武将中挑选出尽可能多的武将，使挑选出来的武将两两之间都存在碾压关系。请问最多能挑选出多少个符合条件的武将？注：若无法挑出任意两个武将形成碾压关系时，返回0

没什么思路.

直接return 0;通过率30%.