4.3 微软笔试题回忆

昨晚笔试被微软爸爸虐哭😰其实是我太菜了hh 虽然做题做得要自闭了…还是先记录一下以便之后再想解法。以下是我自己理解的题意,如有纰漏请大家指正~


1. 击鼓传花

嗯…突发奇想给这题起了个名😂

N个人每个人编号1-N,编号能整除的两个人互相连通,从编号为i的人开始传,最后要传回i手上,要在T次之内传完,问最多有几种传法?


测试

参数:N=3, i=2, T=2

路径:2-1-2

返回:1


参数:N=3, i=2, T=4

2-1-2

2-1-3-1-2

2-1-2-1-2

返回:3


思路

1. DFS

2. DP


2. 最少射击几次

N个瓶子都有编号,每次能射击1个或多个瓶子,如果是回文的就能一次性击倒。最少几次能全击倒?


测试

输入:[1, 2]

输出:2


输入:[1,3,4,1,5]

输出:3

说明:第一次先射3,变成[1,3,1,5],因为有[1,3,1]回文可以一次击倒,剩下[5]再一次


思路

本来看到回文就一直在想怎么找回文,后来感觉不对啊,好像方向走偏了…

看大佬评论说可以用DP,不过状态转移方程还没想明白…



3. 排队

N个人排队编号1-N,可能3种情况:

E1: 排在队首的人离开

E2: 队伍中编号为K的人离开

E3: 返回编号为X的人在队伍中的位置

输入一组query,返回所有E3累加的结果


测试

N=5 query=3

[1,0] [2,3] [3,2]

输出:1

说明:第一次队首编号1的人走了,第二次编号为3的人走了,第三次编号2的人排在队伍中的第一个


思路

感觉这题是4题里相对最容易的了,可是我还是有2个测试用例没过TAT

我想得比较简单,用一个数组pos保存每个人在队中的位置,E1则每人pos-1;E2则K之后的人pos-1,K之前的不变;E3则将pos[x]累加。



4. 蜜蜂采蜜

蜜蜂从家里出发,有几朵花和几处仓库(有坐标),每朵花有一份蜂蜜,蜜蜂一次只能带一份蜂蜜,可以先把采好的蜂蜜送到仓库,最后要回到家里。蜜蜂飞一单位的距离就会消耗一单位的时间(欧式距离),在限定时间T内,蜜蜂最多能采多少蜂蜜?


测试

这题数据太多记不清了…只记得参数了:

• home坐标:[x, y]

• m朵花

• n个仓库

• 花的坐标 二维数组

• 仓库坐标 二维数组

• 限定时间 T


思路

这题其实不太会…本来想用贪心,每次找最近的花/仓库,但是还要保证最后能在规定时间里到家,所以应该还要保存之前的路径?后来选择放弃这题了…



最后总结一下,微软的编程题首先是理解题目,其实每题都是用应用场景包装了一层,要从中抽象出核心的问题。

时间其实不是太大问题…因为真不会的题就算耗很多时间也搞不出来…所以平时不太刷算法题就很吃亏。另外感觉DP的挺常用的,不过自己DP还用得不熟,所以有些题只是有思路但跑不出来…以后要多多练习!


#笔试题目##微软#
全部评论
今年又考击瓶子的题了。
3 回复
分享
发布于 2020-03-25 20:39
#include <vector> #include <climits> #include <iostream> using namespace std; int main() {     int N = 8;     vector<int> bottles = { 1,2,3,2,9,8,9,1 };     vector<vector<int>> scores(N, vector<int>(N));     for (int i = 0; i < N; i++) {         scores[i][i] = 1;     }     for (int i = 1; i < N; i++) {         for (int j = 0; j < N - i; j++) {             int min_score = INT_MAX;             if (bottles[j] == bottles[j + i]) {                 min_score = i > 1 ? scores[j + 1][j + i - 1] : 1;             }             for (int k = 0; k < i; k++) {                 int temp = scores[j][j + k] + scores[j + k + 1][j + i];                 if (temp < min_score) {                     min_score = temp;                 }             }             scores[j][j + i] = min_score;         }     }     cout << scores[0][N - 1];     return 0; } 第二题
点赞 回复
分享
发布于 2019-04-04 14:06
淘天集团
校招火热招聘中
官网直投
问一下,微软笔试用的是什么平台啊
1 回复
分享
发布于 2019-09-03 16:09
楼主做了几道
点赞 回复
分享
发布于 2019-04-04 12:44
真难啊
点赞 回复
分享
发布于 2019-04-04 12:54
#include <vector> #include <climits> #include <iostream> using namespace std; class tree_array { public:     vector<int> vec;     int N;     tree_array(int n) {         int len = 0;         while (n >>= 1) len++;         N = 1<<(len+1);         vec = vector<int>(N, 0);     }     inline int lowbit(int t){ return t&(-t);}     int find(int i) {         int res = 0;         while (i > 0) {             res += vec[i-1];             i -= lowbit(i);         }         return res;     }     void insert(int n) {         for (int i = n; i <= N; i += lowbit(i))             vec[i-1] ++;     }     void pop(int n) {         for (int i = n; i <= N; i += lowbit(i))             vec[i-1] --;     }     void pop_front() {         int i = N;         while (vec[i-1] > 0) {             int temp = lowbit(i) >> 1;             vec[i-1]--; i -= temp;             if (!vec[i-1]) i -= temp;         }     } }; 第三题
点赞 回复
分享
发布于 2019-04-04 13:23
???我啥我是后面做了,而第一题通过最低。。ps:我报的是pm
点赞 回复
分享
发布于 2019-04-04 14:10
请问是通过什么途径做的笔试呢,我在官网投了简历没有任何消息
点赞 回复
分享
发布于 2019-04-05 06:48
第一题过了所有case 第二题过了四个basic case 第三题有个necessary case没过,也搞不懂啥是necessary case 第四题暴力过了两个corner case 不知道做成这样有没有过的可能23333
点赞 回复
分享
发布于 2019-04-07 15:08
话说有大佬收到面试通知的吗?
点赞 回复
分享
发布于 2019-04-11 12:29

相关推荐

15 108 评论
分享
牛客网
牛客企业服务