首页 > 笔经面经 > 4.3 微软笔试题回忆

4.3 微软笔试题回忆

头像
M!hu
编辑于 2019-04-04 12:20:28 APP内打开
赞 7 | 收藏 65 | 回复9 | 浏览3794

昨晚笔试被微软爸爸虐哭😰其实是我太菜了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还用得不熟,所以有些题只是有思路但跑不出来…以后要多多练习!


9条回帖

回帖
加载中...

本文相关内容

近期热帖

热门推荐