微软 2022 技术岗面试题（应聘 求职 面试准备资料）

1、 微软 2022 技术岗面试题第1题： 一、 描述 We say a stringis beautiful if it has the equal amount of 3 or more continuous letters (inincreasing order.) Here are someexample of valid beautiful strings: “abc”, “cde”,”aabbcc”, “aaabbbccc”. Here are someexample of invalid beautiful strings: “abd”, “cba”,”aabbc”, “zab”.

2、Given a stringof alphabets containing only lowercase alphabets (a-z), output “YES”if the string contains a beautiful sub-string, otherwise output “NO”. 输入 The first linecontains an integer number between 1 and 10, indicating how many test cases arefollowed. For each testcase: First line is the numbe

3、r of letters in the string; Second line is thestring. String length is less than 10MB. 输出 For each testcase, output a single line “YES”/”NO” to tell if the stringcontains a beautiful sub-string. 提示 Huge input. SlowIO method such as Scanner in Java may get TLE. 样例输入 4 3 abc 4 aaab 6 abccde 3 abb 样例输出

4、 YES NO YES NO 时间限制:8000ms 单点时限:1000ms 内存限制:256MB 第2题： 二、 描述 You are given atxt file, which is performance logs of a single-threaded program. Each line hasthree columns as follow: Function NameTimeStamp Action FunctionNameis a string of length between 1255 TimeStampformat is hh:mm:ss Valid values fo

5、r”Action” column are START or END, marking the start or end of afunction call. Each functionwill only be called once. Output thedepth-first traversal result of the call graph with the total time of eachfunction call. However, sometimes the performance log isnt correct and at thattime you just need t

6、o output “Incorrect performance log”. 输入 The input onlycontains 1 case, first line is a positive number N representing the number oflogs(1 = N = 20000), then there are N lines in next, each line is thelog info containing Function Name TimeStamp Action, Function Name is astring, you can assume the Fu

7、nction Name is distinct and the length between1255. 输出 Output thedepth-first traversal result of the call graph with the total time of eachfunction call for the correct performance, or output “Incorrectperformance log”. 提示 A call graph isa directed graph that represents calling relationships between

8、 subroutines in acomputer program. Call graph forthe sample input is shown as below: Another sampletest case. Sample InputSample Output 8 FuncA 00:00:01 START FuncB 00:00:02 START FuncC 00:00:03 START FuncA 00:00:04 END FuncB 00:00:05 END FuncD 00:00:06 START FuncD 00:00:07 END FuncC 00:00:08 ENDInc

9、orrect performance log 样例输入8FuncA 00:00:01 STARTFuncB 00:00:02 STARTFuncC 00:00:03 START FuncC 00:00:04 END FuncB 00:00:05 END FuncD 00:00:06 START FuncD 00:00:07 END FuncA 00:00:08 END 样例输出FuncA 00:00:07FuncB 00:00:03FuncC 00:00:01FuncD 00:00:01 窗体顶端 EmacsNormalVim 时间限制:10000ms单点时限:1000ms内存限制:256MB

10、 第3题： 三、 描述 We define thematching contents in the strings of strA and strB as common substrings of thetwo strings. There are two additional restrictions on the common substrings. The firstrestriction here is that every common substrings length should not be less than3.For example: strA:abcdefghijklm

11、n strB: ababceghjklmnThe matchingcontents in strA and strB are substrings (“abc”, “jklmn”).Note that though “e” and “gh” are common substrings of strAand strB, they are not matching content because their lengths are less than 3.The secondrestriction is that the start indexes of all common substrings

12、 should bemonotone increasing. For example:strA:aaabbbbccc strB:aaacccbbbbThe matchingcontents in strA and strB are substrings (“aaa”, “bbbb”).Note that though “ccc” is common substring of strA and strB and haslength greater than 3, the start indexes of (“aaa”, “bbbb”,”ccc”) in strB are (0, 6, 3), w

13、hich is not monotone increasing.输入Two lines. Thefirst line is strA and the second line is strB. Both strA and strB are oflength less than 2100.输出 The length ofmatching contents (the sum of the lengths of the common substrings). 样例输入 abcdefghijklmn ababceghjklmn 样例输出8 时间限制:10000ms单点时限:1000ms内存限制:256M

14、Btable 第4题： 四、 描述 Finally, youcome to the interview room. You know that a Microsoft interviewer is in theroom though the door is locked. There is a combination lock on the door. Thereare N rotators on the lock, each consists of 26 alphabetic characters, namely,A-Z. You need to unlock the door to mee

15、t the interviewer inside. There is anote besides the lock, which shows the steps to unlock it. Note: There areM steps totally; each step is one of the four kinds of operations shown below: Type1:CMD1 i j X: (i and j are integers, 1 = i = j = N; X is a character,within A-Z) This is asequence operatio

16、n: turn the ith to the jth rotators to character X (the leftmost rotator is defined as the 1st rotator) For example: ABCDEFG = CMD 1 2 3 Z = AZZDEFG Type2:CMD2 i j K: (i, j, and K are all integers, 1 = i = j = N) This is asequence operation: turn the ith to the jth rotators up K times ( if character

17、A is turned up once, it is B; if Z is turned up once, it is A now. ) For example: ABCDEFG = CMD 2 2 3 1 = ACDDEFG Type3:CMD3 K: (K is an integer, 1 = K = N) This is aconcatenation operation: move the K leftmost rotators to the rightmost end. For example: ABCDEFG = CMD 3 3 = DEFGABC Type4:CMD4 i j(i, j are integers, 1 = i = j = N): This is arecursive operation, which means: If i j: DoNothing Else: CMD4 i+1 j CMD2 i j 1 For example: ABCDEFG = CMD 4 2 3 = ACEDEFG 输入 1st line: 2 integers, N, M ( 1 = N = 50000, 1 = M = 50000 ) 2nd line: astring of N characters, standing for the original status of