微软四面凉经

整理电脑翻到了半年前的面试，发上来求点米
SDE2岗位总共面了四轮，最后的结果是排序掉了，很遗憾没能抱上巨硬大腿

round1
Jump game 2, Greedy, 我用dfs写的，也给过了
followup：如何改进-空间换时间

1. // https://leetcode.com/problems/jump-game-ii/
   
2. // written during interview, can't promise the correctness, just for draft reference
   
3. 
   
4. var minJump int = math.MaxInt
   
5. 
   
6. // Additionally: use map to store calcuated value -> o(n) time complexity
   
7. var indexToMinJump = make(map[int]int)
   
8. 
   
9. func jump(nums []int) int {
   
10.         // // special cases
    
11.         // // 1. len = 0  2. len>=1, nums[0] == 0
    
12.         // if len(nums) == 0 {
    
13.         //         return 0
    
14.         // }
    
15.         search(nums, 0, 0)
    
16.         return minJump
    
17. }
    
18. 
    
19. func search(nums []int, index, count int) {
    
20.         // index valid
    
21.         if index < 0 || index >= len(nums) {
    
22.                 return
    
23.         }
    
24. 
    
25.         // end condition
    
26.         if index == len(nums)-1 {
    
27.                 if count < minJump {
    
28.                         minJump = count
    
29.                 }
    
30. 
    
31.                 return
    
32.         }
    
33. 
    
34.         // jump
    
35.         times := nums[index]
    
36. 
    
37.         count++
    
38.         for i := times; i >= 1; i-- {
    
39.                 search(nums, index+i, count)
    
40.         }
    
41. }

复制代码

round2 主要是聊项目，然后做了个简单的小题，问一共能想出多少种解法，最优解是什么

1. // https://leetcode.com/problems/sort-colors
   
2. // written during interview, can't promise the correctness, just for draft reference
   
3. 
   
4. // sort
   
5. // [2,0,2,1,1,0] -> [0,0,1,1,2,2]
   
6. // Method 1: classify through counting for each number, then appending
   
7. 
   
8. func sortColors (nums []int){
   
9.         numToCount := make([]int, 3)
   
10. 
    
11.         for _, num := range nums {
    
12.                 numToCount[num]++
    
13.         }
    
14. 
    
15.         index := 0
    
16.         for i, v := range numToCount {
    
17.                 for j:=0; j<v; j++ {
    
18.                         nums[index] = i
    
19.                         index++
    
20.                 }
    
21.         }
    
22. }
    
23. 
    
24. // sort
    
25. // [2,0,2,1,1,0] -> [0,0,1,1,2,2]
    
26. // Method 2: two pointers, simulating quick sort, each time group one color, need to go through the process two times
    
27. 
    
28. func sortColors (nums []int){
    
29.         // input validation ?
    
30.         if len(nums) < 2 {
    
31.                 return
    
32.         }
    
33. 
    
34.         // sort
    
35.         left, right := 0, 1
    
36.         pivot := nums[0]
    
37.         
    
38.         //end condition: right - > end
    
39.         for right < len(nums) {
    
40.                 for nums[left]==pivot {
    
41.                         left++
    
42.                 }
    
43.         
    
44.                 for nums[right] != pivot {
    
45.                         right++
    
46.                 }
    
47.         
    
48.                 // switch
    
49.                 nums[left], nums[right] = nums[right], nums[left]
    
50.         }
    
51. 
    
52.         // iteration times control? 3->2
    
53.         sortColors(nums[left:])
    
54. }
    
55. 
    
56. // Method 3: iterate with two pointers, left:=0, right := len(nums), then iterate, if nums[i] == 0, switch with left, if nunms[i] == 2, switch with right

复制代码

您好！
本帖隐藏的内容需要积分高于 130 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 130 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

一周后收到thank u

微信用户_a69bb13 发表于 2025-02-11 13:50:17
lz给你加米了！请问你这几轮的题都打出来了，那你知道为什么挂了吗？谢谢啦

跟帖子说的一样排序排掉了，前面有更优秀的接了offer

软那么恶心 没什么好可惜的

lz给你加米了！请问你这几轮的题都打出来了，那你知道为什么挂了吗？谢谢啦

这么难么？ 最近面了两轮coding，两个面试官都当场反馈很好。
已经第三天了，还没有hr联系，也是国内。
请问下楼主timeline