分享大厂的一些笔试题目
The following article is from 嵌入式与Linux那些事 Author 仲一
乐鑫
签到题
完全k叉树, 完全不会.
乐鑫的笔试题是我做过最难的, 后面批次的, 我听说直接和高数相关, 用编程来求解数学问题.
vivo
签到题
01背包原题
图的关键路径(不会)
动态规划没那么难, 经典的背包问题, 公共子串问题, 矩阵相关的问题多在力扣找几道刷一刷.
除了力扣, 在学习算法的过程中, 胡凡的<<算法笔记>>也是我经常翻阅的一本书, 网上有电子版, 里面很多问题都分析得很清晰.
图的话, 关键路径, 拓扑排序, 广度优先, 深度优先等有空就看看, 对于嵌入式来说是加分项.
大华
基本是C++题目, 坑.
如果比较看重大华, 还是多准备一下C++基础, 我也想不懂明明是C语言岗位, 搞那么多C++干嘛.
联发科技
最后的编程题是实现双向升序链表(带头节点的).
后台出了问题不管怎么提交都是0分.
联发科这道题本身不难, 但是自己很多测试样例都符合预期, 提交却是0分, 有点搞心态了.
后来笔试通过了, 所有人都是这种情况, 应该就是专门来搞你心态的吧.
蔚来汽车
两道中等题 100 + 80都挂了
leetcode75题颜色分类原题
给定一个随机数组, 求四个不同的数使得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语言.
写一下比较有印象的题目:
求container_of
这是我在rt-thread的源码里翻出来的
#define rt_container_of(ptr, type, member) \ ((type *)((char *)(ptr) - (unsigned long)(&((type *)0)->member)))
求1~n中字符1出现的次数(剑指offer原题)
这题大意了, 当作签到题来做了, 不过力扣是困难题, 应该也是不会做.
给定精度n, 求pi
第3题实在不会做, 在网上找了也没找到看得懂的方法.
大疆给得真的好高, 好好做.
诺瓦科技
一些跨时钟域的问题不会
编程题一道是串口转并口
一道是64位全加器, 但是由于器件特性, 不能使用reg [63:0]这样的寄存器.
荣耀
签到题. 输入是一行有字母有数字的字符串, 问输入的数字可组成十进制数.
动态规划走二维矩阵, 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)走时, 只能向上或向左移动.
注意, 因为怪兽杀死以后就不存在了, 所以要用一个数组来保存路径.
有一个3*3的矩阵
| 1 | 2 | 3 |
|---|---|---|
| 4 | 5 | 6 |
| 7 | 8 | 9 |
相邻的元素代表可直接到达, 比如1可到达2, 2也达到1, 元素本身也可到达自己.
即以上矩阵是一个有向有环图.
然后题目输入一些条件, 告诉你要把哪些边去掉.
然后输入一个n.
问在走n步的情况下(也可能走不完n步, 每一步都代表经过一条边), 可以组成的数字最大是多大?
比如n为3, 然后走过1 2 3 3, 那个就组成了1233这个数字.
没做出来, 感觉就是深度优先.
今年是荣耀第一年校招, 后面给开奖能去到40w, 还是挺不错的, 好好对待荣耀的考试.
美团
小美的序列检查
小美给小团一个m个数字构成的数字序列, 问小团能不能经过重新排序后形成1到n的排列.
举例:
小美给小团[2,1,3], 则可以经过重新排列后构成[1,2,3], 这是可行的.
小美给小团[4,4,1,3], 则无法重新排列后构成[1,2,3,4], 这是不可行的.
为了防止小团碰对答案, 小美会进行多组询问.
哈希表解决
小美的回文串构建
同力扣214. 最短回文串(困难)
机器人爆炸时刻
小美在数轴上放置了若干个机器人, 这些机器人每到整数时刻, 就会检查是否和其他机器人重合. 如果重合, 它就会原地爆炸. 这些机器人的移动速度均为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.
小美最快到达时间
一个图的最短路径问题.
只A了前两道, 还是暴力做出来的.
科大讯飞
将num从右往左的第二个比特0变为比特1.
做的时候用了最普通的循环方法.
后来想想可以这样做:
int ans = ~num; ans = ans & (ans – 1); // 最低比特1位清零 ans = ans & (-ans); // 取最低比特1位 nums |= ans; // num的第二个比特0变为1
输入一个字符串, 该字符串最多只会出现小写字母和'?', '?'可以代替任意一种小写字母, 求该字符串能包含26种小写字母的最小区间长度.
使用哈希表+双指针做出来了.
输入二叉树和常数k, 求有多少对叶子节点的距离为k.
这道题做了好久, 最终只通过20%.
小马智行
选择题涉及C语言基础, 单片机基础, Linux内核基础.
问答题:
简述操作系统发生中断到响应中断的过程.
这题我采用的是韦东山讲解Linux对中断的处理演进那一章的知识.
简述uart, spi, iic的异同.
编程题:
合并两个升序链表, 力扣有原题.
从一串格式字符串中解析出日期. 比较麻烦的是格式字符串可能会不符合格式, 至于会怎样不符合格式, 你要自己去猜一下.
"$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, 推理题, 程序填空题, 程序改错题.
编程题:
又到了一学期一次的大学生期末考试。但很多人期末考试的卷面成绩是不能及格的，需要靠较高的平时成绩来拖上去。平时成绩与期末考试的占比已经确定，假设平时成绩占比为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;
}
长城上有连成一排的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%.
end
往期推荐