微软笔试简易题解

这次还是挺简单的,比上次实习笔试简单多了。。上次实习笔试简直就在做acm金牌题。。

1.

题意:给你一个长度为偶数的递增的序列 a ,原始的序列保证 a[1] = a[n], a[2] = a[n-1], ..., a[i] = a[n-i],现在拿掉其中一个元素,问你拿掉的那个元素是多少。
解:拿前半部分二分就好了

2.

题意:有一个空格分割的若干个单词组成的字符串,现在有一个n表示对每个单词做n次顺时针旋转,现在给你旋转之后的的字符串,问有多少个单词在原来的字符串和旋转之后的字符串中一致。比如n=2, 字符串="ba def adad",那么显然旋转之前的字符串是"ba fde adad",所以有2个单词和原来一致。
解:模拟一下就好了,用python写特别简单。

3.

题意:给你一个J和K组成的字符串,要求改变其中的若干个字符,使得:1) J和K的数量一致 2) 从左到右,K的数量始终多余J的数量。问你最少需要改变几个字符。比如KKJJ、KJKJ、KKJJKJ都是合法的,但JK、KJJK、KKJ都是不合法的。
解:显而易见的dp。设 dp[i][j] 表示从 i 到 j 的答案,那么

并且



大概解释一下,就是 dp[i][j] 要么是从两段 dp[i][k] 和 dp[k+1][j] 转移而来,要么就是去掉头尾 s[i] 和 s[j],然后转移到 dp[i+1][j-1]
#微软##笔试题目#
全部评论
第一题题目写错了吧,应该是a[0]+a[n-1] = a[1]+a[n-2]...另外能具体说下怎么做吗
1 回复
分享
发布于 2020-09-22 12:55
为何你们都有笔试
点赞 回复
分享
发布于 2020-09-22 10:54
小红书
校招火热招聘中
官网直投
第三题可以用栈
点赞 回复
分享
发布于 2020-09-22 12:57
不是,想不明白第一题那个 原始的序列保证 a[1] = a[n], a[2] = a[n-1], ..., a[i] = a[n-i] 怎么还能做到序列递增
点赞 回复
分享
发布于 2020-09-22 16:23
楼主被通知笔试了吗?
点赞 回复
分享
发布于 2020-09-24 11:49
// 第一题,用差序列做,希望有dl指正 bool isSymmetric(vector<int> &diff, int begin, int end) { for(int i = begin; i < (begin + end)/2; i++) { if(diff[i] != diff[begin + end - i]) { return false; } } return true; } int solution(vector<int>& A) { int n = A.size(); vector<int> diff(n-1, 0); for(int i = 0; i < n-1; i++) { diff[i] = A[i+1] - A[i]; } int ret = A[0]; for(int i = 0; i < (n-1)/2; i++) { if(diff[i] != diff[n-2-i]) { if(i == 0 && isSymmetric(diff, 1, n-2) || isSymmetric(diff, 0, n-3)) { if(isSymmetric(diff, 1, n-2)) { ret = A[n-1] + diff[0]; } else if(isSymmetric(diff, 0, n-3)) { ret = A[0] - diff[n-2]; } } else { if(diff[i] > diff[n-2-i]) { ret = A[i] + diff[i+1]; } else { ret = A[n-1-i] - diff[i]; } } break; } } return ret; }
点赞 回复
分享
发布于 2021-04-10 17:32

相关推荐

发个腾讯的吧,刚面完,以为是kpi,所以没录音,能写多少是多少点击查看详情自我介绍介绍项目1.java和其他语言的区别,比如c++,python,各个方面2.知道几种编程思想,比如面向对象等等3.知道的设计模式4.jvm结构、垃圾回收算法5.乐观锁CAS6.数据结构了解哪些7.排序算法呢,说一下快排,时间复杂度。空间复杂度8.计网1.OSI七层,作用2.http状态码,502如何查找排除3.http报文结构4.https的过程,三次握手,TLS四次握手等等,认证过程5.了解过哪些加密算法,什么是对称加密和非对称加密6.cookie和session了解过吗,区别,集群里,session在一个服务器,请求分配到了其他服务器,怎么解决这种情况说了一些以后,提示我想想redis、mysql7.websocket了解过吗,。。。。我不知道8.http有哪些请求方法,然后给我个场景,问我怎么解决,具体忘了,反正他最后引导我是用head(应该)9.ping用过吗,基于什么协议10.DNS解析过程、我还说了两种方法,递归,迭代,问我迭代体现在哪11.DOS攻击是什么12.TCP三次握手。四次挥手,各阶段的状态,为什么要三次握手、四次挥手,状态那还问我,SYN_RECV之前服务器是什么状态13.为什么要等待2MSL14.TCP&nbsp;&nbsp;&nbsp;UDP区别、应用场景,问我,游戏用的是什么,腾讯会议呢?我答是QUIC,不晓得对不对15.我看你这是个前后端分离项目,那么跨域问题怎么解决。我不知道。。。。16.静态资源问题,后面提醒我用CDN17.TCP拥塞控制四个过程。TCP滑动窗口了解过吗,讲一下18.TCP、UDP格式操作系统1.内核态、用户态,切换方式2.进程线程,区别、协程了解过吗(协程不知道)3.一个进程,你发现cup使用率很高,你怎么排查,我猜与协程有关,就往这方面答了4.一个线程阻塞到这里了,你怎么解决,我还是从协程方面5.进程间通信方式。调度算法6.虚拟内存了解过吗7.分段分页的调度算法8.OOM了解过吗,怎么排查,怎么解决9.什么是死锁,如何避免、解决redis、mysql1.redis持久化机制2.redis的数据结构3.其他想不起来了。。。。字数超了 #腾讯#&nbsp;#腾讯一
点赞 评论 收藏
转发
5 33 评论
分享
牛客网
牛客企业服务