This is the second day of my participation in the August More Text Challenge
About Microsoft
This year, because I want to return to Jiangsu development, I went to interview Microsoft Suzhou, back-end development.
Microsoft’s back-end language is C#/C++, which will have a much smaller market compared to the current mainstream Java/Go in China, so those who want to Go to Microsoft should be prepared to improve their language.
The advantage of Microsoft is that the large platform + foreign companies do not need to be as large as the domestic first-tier Internet. At the same time, because the life in Suzhou is relatively comfortable, the housing price pressure is less than the first-tier cities.
There are also many groups in Microsoft Suzhou, such as M365, Bing, MMD, Edge, etc. Different groups have different working styles.
The interview characteristics
Microsoft interview investigation content includes basic knowledge, project experience, system design, algorithm questions this several pieces, depending on the department and the position will be slightly different, algorithm questions are basic questions for each round of interview, language is not limited, but also the focus of the interview.
Due to the impact of COVID-19, teams interviews will be conducted remotely. For code writing, screen casting can be done in IDE. Of course, some interviewers will provide links and online whiteboard programming. The difficulty of the algorithm problems is leetCode’s Easy or Medium level.
There are many rounds of interview in Microsoft, including 6 rounds, usually 1 round of technical interview +4 rounds of technical interview +1 round of executive interview. The interview cycle is also quite long.
Speaking from the difficulty of interview, my feeling is that the difficulty of Microsoft suzhou interview will be lower than the domestic first-line Internet factory.
If one department fails, Microsoft can interview other departments. I met with three departments in total, namely M365, MMD and EDGE. In the first two departments, I only did about 300 algorithm questions. No matter it was not enough for algorithm interview or technical accumulation, I failed. When I was facing edge, I had done 500 algorithm questions, and many of them were repeated for many times. I was basically familiar with common solutions, and I was also very familiar with algorithm interview. The final result was that the algorithm questions were finished in each round, but unfortunately they were rejected due to background differences.
For how to prepare for the algorithm interview, please refer to the algorithm Interview Guide written between me.
Algorithmic interview questions
Minimum number of changes between two arrays and equal
Two arrays, change one of the number, so that the sum of the two arrays is equal, find the minimum number of changes. Array nums1: for example, [6], nums2:,1,2,2,2,2 [1] to make them and equal, need to change two times, nums1:,2,3,4,5,1 [1], nums2:,1,2,2,2,2 [7]Copy the codeI did not find this question in Leetcode, which also reflects the characteristics of Microsoft interviewers. There are few common questions, which are some cold questions, but they can reflect certain code ability, especially the processing of various boundary cases.
I solved this problem by greedy method in the interview.
class Solution:
def test(self, num1, num2) :
if not num1 and not num2: return 0
s1 = sum(num1)
s2 = sum(num2)
arr = []
d = abs(s1-s2)
if d == 0:
return 0
if s1 < s2:
num1, num2 = num2, num1
for i in num1:
arr.append(i-1)
for i in num2:
arr.append(10-i)
arr.sort()
count = 0
for i in arr[::-1]:
d -= i
count += 1
if d <= 0:
return count
return -1
Copy the codeRemove the K digits
Given a non-negative integer num and an integer k represented as a string, remove the k digits from the number to minimize the remaining digits. Please return the smallest number as a string. Example 1: Input: num = "1432219", k = 3 Output: "1219" Explanation: Remove the three digits 4, 3, and 2 to form a new minimum number 1219. Example 2: Input: num = "10200", k = 1 Output: "200" Explanation: Remove the first 1 and the remaining number is 200. Note that the output cannot have any leading zeros. Example 3: Input: num = "10", k = 2 Output: "0" Description: Remove all digits from the original number.Copy the codeThis problem is the original problem in Leetcode, 402. Remove K digits.
The time complexity of this problem is O(n), which is greedy + monotone stack.
class Solution:
def removeKdigits(self, num: str, k: int) - >str:
numStack = []
# Build monotonically increasing number strings
for digit in num:
while k and numStack and numStack[-1] > digit:
numStack.pop()
k -= 1
numStack.append(digit)
# If K > 0, delete the last K characters
finalStack = numStack[:-k] if k else numStack
# Erase leading zeros
return "".join(finalStack).lstrip('0') or "0"
Copy the codeReorder strings by frequency and relative position
Input String: 123123412345 Output String: 111222333445 Resorts the String by the frequency of the letters, or by relative order if the frequency is the sameCopy the codeThis problem is a variant of leetCode 1636. Sort an array by frequency in ascending order. When doing this problem, try not to think too complicated.
I’ve developed my own Python one-line solution to this problem.
class Solution:
def interview(self, items) :
return "".join(sorted(list(items), key=lambda x: (items.count(x), -items.index(x)), reverse=True))
Copy the codeIs there a continuous subarray of sum K
Enter an array, such as [1,2,3], and a target value to determine if there are contiguous sums of subarrays for the target valueCopy the codeThis problem is actually a simplified version of leetcode’s 325 and the length of the largest array equal to k, and the interviewer only wanted me to figure out if there was a solution.
Similar to this kind of continuous subarray problem, want to think of using hash table + prefix sum idea to do, otherwise violent method of time complexity will be very exaggerated.
So what I’ve given you here is the solution to the original problem in leetcode.
class Solution:
def maxSubArrayLen(self, nums: List[int], k: int) - >int:
dic = {0: -1}
s = res = 0
for i in range(len(nums)):
s += nums[i]
if s - k in dic:
res = max(i-dic[s-k], res)
if s not in dic:
dic[s] = i
return res
Copy the codeMatches make a square
Remember the fairy tale "The Little Match Girl"? Now, you know how many matches the little girl has, please find a way to make a square using all the matches. Matches can't be broken, they can be joined together, and each match must be used. Enter the number of matches the little girl has, each match represented by its length. The output is whether you can form a square with all the matches. Example 1: Input: [1,1,2,2,2] Output: true Explanation: Can form a square of length 2 with two matches on each side.Copy the codeThis is the original problem in Leetcode: 473. Matches make squares
I wanted to use greed to do it at first, but later found it very troublesome. Fortunately, I immediately reacted and switched to backtracking.
class Solution:
def makesquare(self, nums: List[int]) - >bool:
if not nums: return False
s = sum(nums)
If the perimeter is not divisible by 4, return False
if s % 4! =0: return False
w = s // 4
Sort the array from the largest to the smallest. This is a greedy way to find solutions much faster
nums.sort(reverse=True)
def _dfs(index, w_arr) :
The array must all be 0, otherwise return False
if index == len(nums):
return all([i==0 for i in w_arr])
result = False
for j in range(len(w_arr)):
If two consecutive values of w_arr are the same, you can skip it
if j > 0 and w_arr[j] == w_arr[j-1] :continue
# try to deduct nums[index]
if w_arr[j] >= nums[index]:
w_arr[j] -= nums[index]
if _dfs(index+1, w_arr):
return True
w_arr[j] += nums[index]
return result
return _dfs(0, [w,w,w,w])
Copy the codeThe minimum difference between the sum of the two numbers and the target value
Find minimun abs(val[a] + val[b]) in an integer array.[2, -1000, 0, 33, -15, -100, -1]
Copy the codeThis problem is a variation of the classic sum of two numbers, as well as this problem in Leetcode: 1099. Sum of two numbers less than K
Because I’ve done a lot of this kind of problem, it’s easy to write it with sort + double pointer.
class Solution:
def interview(self, nums) :
if len(nums) < 2:
return -1
nums.sort()
min_value = float('inf')
i, j = 0.len(nums) - 1
while i < j:
s = nums[i] + nums[j]
if s == 0:
return 0
elif s < 0:
i += 1
else:
j -= 1
min_value = min(min_value, abs(s))
return min_value
Copy the codeQuick sort
Yes, quicksort is also a common question in the interview, I have encountered in many other interviews besides Microsoft interview, the principle of quicksort, and the average complexity O(nlogn), and the worst time complexity O(n^2).
class Solution:
def sortArray(self, nums) :
n = len(nums)
def quick(left, right) :
if left >= right:
return nums
pivot = left
i = left
j = right
while i < j:
while i < j and nums[j] > nums[pivot]:
j -= 1
while i < j and nums[i] <= nums[pivot]:
i += 1
nums[i], nums[j] = nums[j], nums[i]
nums[pivot], nums[j] = nums[j], nums[pivot]
quick(left, j - 1)
quick(j + 1, right)
return nums
return quick(0, n - 1)
Copy the codeLeetcode also has a special topic for sorting arrays: 912. Sorting arrays
The square root of x
Implement the int SQRT (int x) function. Calculates and returns the square root of x, where x is a non-negative integer. Since the return type is an integer, only the integer part of the result is retained, and the fractional part is omitted. Example 1: Input: 4 Output: 2 Example 2: Input: 8 Output: 2 Description: The square root of 8 is 2.82842... Because the return type is an integer, the decimal part will be omitted.Copy the codeThe square root of 69. X
But boundary processing is particularly error-prone, so double check.
class Solution:
def mySqrt(self, x: int) - >int:
l, r, ans = 0, x, -1
while l <= r:
mid = (l + r) // 2
if mid * mid <= x:
ans = mid
l = mid + 1
else:
r = mid - 1
return ans
Copy the codeA string with only one different character
A set of lists ['abcd', 'ACdb ',' aACd '] that exist equal to another element if only one character is replaced, and return True otherwise FalseCopy the code1554. A string with only one different character, but less popular.
class Solution:
def differByOne(self, dict: List[str]) - >bool:
Record all the different strings that might exist in the iterated string
c = set(a)for i in dict:
for j in range(len(i)):
s = i[:j] + '. ' + i[j + 1:]
if s in c:
return True
c.add(s)
return False
Copy the codeIn recent times
Given a time in the form of HH:MM, construct the next time closest to the current time using the current number. Each occurrence number can be used an unlimited number of times. You can assume that a given string must be valid. For example, "01:34" and "12:09" are legal, "1:34" and "12:9" are illegal. Example 1: Input: "19:34" Output: "19:39" Explanation: The most recent time constructed from the numbers 1, 9, 3, and 4 is 19:39, 5 minutes later. It's not 19:33 because it's 23 hours and 59 minutes later. Example 2: Input: "23:59" Output: "22:22" Explanation: The most recent time constructed from the numbers 2, 3, 5, and 9 is 22:22. The answer must be sometime the next day, so choose the smallest constructible moment.Copy the codeThis question is also the original one in LeetCode, but it is very unpopular: 681. At that time, because the language used by the interviewer was different from that of the interviewer, and the interviewer saw that I had to brush a lot of questions, so I chose a question that few people had done before, which could test the code ability and paid attention to boundary value processing.
However, when DOING this problem, I have accumulated 500 questions, a little debugging, so the test cases have passed, but also by the interviewer’s praise.
class Solution:
def nextClosestTime(self, time: str) - >str:
digit_set = set(a)for c in time:
ifc ! =':':
digit_set.add(c)
if len(digit_set) == 1:
return time
origin_minute = int(time[0:2]) * 60 + int(time[3:)#time converts to minutes
candidates = set(a)def backtrace(path: str) - >None:
if len(path) == 4:
candidates.add(path)
return
for c in digit_set:
path += c
backtrace(path)
path = path[ :-1] # back. Memory explodes without backtracking
backtrace("")
res = 0
first_calc = True
for s in candidates:
H = int(s[0:2])
M = int(s[2:4])
if 0 <= H < 24 and 0 <= M < 60:
cur = H * 60 + M Current time (in minutes)
if cur == origin_minute: # is time itself, so skip it
continue
if first_calc == True: # first calculation
res = cur
first_calc = False
else: # Not the first time
cur_diff = (cur + 24*60 - origin_minute) % (24*60) Every moment smaller than time is counted as the next day
res_diff = (res + 24*60 - origin_minute) % (24*60)
if cur_diff < res_diff:
res = cur
H, M = res//60, res%60
res_s = ""
if H < 10:
res_s += '0'
res_s += str(H)
res_s += ':'
if M < 10:
res_s += '0'
res_s += str(M)
return res_s
Copy the codeMobile zero
Given an array nums, write a function to move all zeros to the end of the array while preserving the relative order of the non-zero elements. Example: input: [0,1,0,3,12] output: [1,3,12,0,0]Copy the codeAt that time, I was very happy to get this problem, because it is too classic, I have done more than 5 times, easy to fix.
283. Move zero
class Solution:
def moveZeroes(self, nums: List[int]) - >None:
""" Do not return anything, modify nums in-place instead. """
i = 0
for j in range(len(nums)):
ifnums[j] ! =0:
nums[i], nums[j] = nums[j], nums[i]
i += 1
return nums
Copy the codeFind the percentile of the log
Web server log format: GET/API /test 200 333ms Calculate the hundredth of the time in the log fileCopy the codeThis problem is not strictly algorithmic, it’s just a scenario from everyday work that I can easily do in Python
class Solution:
def interview(self, arr, target) :
# target: decimal from 0 to 1
length = len(arr)
index = int(length*target)
print(index)
time_arr = []
for s in arr:
time = int(s.split()[-1] [: -2])
time_arr.append(time)
time_arr.sort()
print(time_arr)
return time_arr[index]
if __name__ == "__main__":
arr = ["GET /api/test 200 333ms"."GET /api/test 200 222ms"."GET /api/test 200 200ms"]
arr1 = ["GET /api/test 200 333ms"."GET /api/test 200 222ms"."GET /api/test 200 20ms"."GET /api/test 200 1ms"]
a = Solution()
print(a.test(arr, 0.5))
print(a.test(arr1, 0.5))
print(a.test(arr, 0.2))
Copy the codeAnd are all contiguous subarrays of length k greater than 1
,1,5,6,0 input: [0] k = 6 output:,1,5 [0] [1, 5] [6, 0] for a minimum length of 2Copy the codeThis question has many similar questions in Leetcode, such as: 560. And are subarrays of K
Because I’ve trained for this type of problem, so I know how to do it with hash tables and prefixes, and I can do it pretty quickly.
class Solution:
def interview(self, arr, target) :
hashmap = collections.defaultdict(list)
hashmap[0].append(-1)
s = 0
res = []
for i in range(len(arr)):
s += arr[i]
if s - target in hashmap:
left_arr = hashmap[s-target]
for j in left_arr:
if i - j > 1:
res.append(arr[j+1:i+1])
hashmap[s].append(i)
return res
Copy the codeThe value is expressed as an integer
201
two hundred and one
2001
two thousand and one
20001
twenty thousand and one
200001
two hundred thousand and one
2000001
two million and one
20 000 001
twenty million and one
200 000 001
two hundred million and one
200 300 001
two hundred million and three hundred thousand and one
two hundred million three hundred thousand and one
Copy the codeThis problem is not easy and there are many things to consider. In order to prevent time shortage, I discussed with the interviewer and only completed these use cases listed above.
Leetcode has a sister problem, 273
My following solution can be optimized, which I wrote in the interview.
class Solution:
def interview(self, s) :
num_map = {
'one': 1.'two': 2.'three': 3.'hundred': 100.'thousand': 1000.'million': 1000000.'twenty': 20
}
res = 0
cur = 1
for i in s.split():
ifi ! ='and':
cur *= num_map[i]
else:
res += cur
cur = 1
res += cur
return res
if __name__ == "__main__":
a = Solution()
print(a.test("two thousand and one"))
print(a.test("twenty thousand and one"))
print(a.test("two hundred million and one"))
print(a.test("two hundred million and three hundred thousand and one"))
Copy the codeThe interview feeling
At the beginning of the algorithm interview, I was very nervous, and often my mind went blank when I was nervous. Even I could not figure out the solution to the questions I had done before.
Later, I thought bitterly that I still didn’t practice enough, so I practiced the common questions repeatedly to deepen my understanding, and simulated the real interview scene. I wrote the whiteboard once and the IDE once.
Another thing to note is that you can take the interviewer as a partner. If you really can’t figure out a solution to a problem, you can ask him for hints instead of thinking hard and not giving the interviewer feedback, which is very bad.
Finally, after writing, it is a good habit to actively think of test cases and corner cases.
Although I did not get the offer from Microsoft, during the process of preparing for the interview with Microsoft, I mastered the algorithm more and more deeply. When meeting with other companies, the algorithm question was not difficult for me, and FINALLY I got the ideal offer.
Interview with programmer interview is more and more volume, the algorithm is higher and higher, the importance of algorithm does not like teachers just recite in advance, the algorithm is a skill that requires training day after day, from this Angle for, never lose learning algorithm, in the future, you will thank to this question is hard at the moment algorithm.