微软 OTS 面经

热乎的面经，都是新题，自己做了，不知道结果怎么样，分享一下，为自己求个人品！
还有一道很简单的改错题，不太记得了。

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

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

第一题我没理解错的话应该是单调栈，均摊复杂度是O(N)

1. // Given a list of integers, create a new array defined as
   
2. // a list of the array index distance between current and next
   
3. // element which is bigger.
   
4. 
   
5. // E.g. Input: [2,5,3,4,7,23,15,7,16,25]
   
6. // Output: [1,3,1,1,1,4,2,1,1,0]
   
7. 
   
8. import java.util.*;
   
9. 
   
10. class Solution {
    
11.     public int[] nextBiggerDistance(int[] arr) {
    
12.         int n = arr.length;
    
13. 
    
14.         int[] res = new int[n];
    
15. 
    
16.         // val will keep track of possible candidates for each iteration:
    
17.         // Elements on the right without any larger in the middle. (not blocked)
    
18.         Stack<Integer> index = new Stack<>();
    
19.         Stack<Integer> val = new Stack<>();
    
20. 
    
21.         for (int i = n - 1; i >= 0; --i) {
    
22.             while (!val.isEmpty() && val.peek() <= arr[i]) {
    
23.                 index.pop();
    
24.                 val.pop();
    
25.             }
    
26.             if (val.isEmpty()) {
    
27.                 res[i] = 0;
    
28.             } else {
    
29.                 // arr[i] < val.peek()
    
30.                 res[i] = index.peek() - i;
    
31.             }
    
32.             val.push(arr[i]);
    
33.             index.push(i);
    
34.         }
    
35. 
    
36.         return res;
    
37.     }
    
38. }
    
39. 
    
40. class Test {
    
41. 
    
42.     public static void main(String[] args) {
    
43.         Solution s = new Solution();
    
44.         System.out.println(Arrays.toString(
    
45.             s.nextBiggerDistance(new int[] {
    
46.                 2,5,3,4,7,23,15,7,16,25
    
47.             })
    
48.         ));
    
49.     }
    
50. }
    

复制代码

huanghuan9210 发表于 2018-6-12 03:27
为啥{"car", "bat", "bar"}的summed similarity 是 4？不是3吗？

我也觉得是三。。。我就用最基本的DFS搜索的，已经过了

为啥{"car", "bat", "bar"}的summed similarity 是 4？不是3吗？

请问楼主7月9 hire event吗

seattle_huyou 发表于 2018-6-19 15:26
请问楼主7月9 hire event吗

六月18号

这不就是利口斯就留吗

第二题如何解？ 是word ladder吗？

想请教下楼主第二题思路是什么呀？
用DFS逐个搜组合然后选取最优么？