飞思布克昂塞面经

其实面试中问了好些系统和项目相关的东西，为了防止暴露，这里把算法题给出来放送给大家，如果大家觉得有价值，给加点大米吧，地里好多贴子看不到。。。

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

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

第四题的话，按x轴排序后，最大值斜率只可能出现在相邻两点的连线上。

kate8528577 发表于 2018-10-23 14:37
楼主我想问问第二题是dp么？

顺便写了一下第二题，如果不对请指正呀

1. public static int makeStringPalindrome(String s) {
   
2.         if(s == null || s.length() == 0) {
   
3.             return 0;
   
4.         }
   
5.         int n = s.length();
   
6.         int[][] dp = new int[n][n];
   
7.         for(int i = 0; i < n; i++) {
   
8.             dp[i][i] = 0;
   
9.         }
   
10. 
    
11.         for(int len = 2; len <= n; len++) {
    
12.             for(int i = 0; i < n; i++) {
    
13.                 int j = i + len - 1;
    
14.                 if(j < n) {
    
15.                     if(s.charAt(i) == s.charAt(j)) {
    
16. 
    
17.                         dp[i][j] = dp[i+1][j-1];
    
18.                     } else {
    
19.                         dp[i][j] = Math.min(dp[i+1][j-1], Math.min(dp[i+1][j], dp[i][j-1])) + 1;
    
20.                     }
    
21.                 }
    
22.             }
    
23.         }
    
24.         return dp[0][n-1];
    
25.     }

复制代码

编得太假，差评

第一题面试官有特意强调 ai <= 4000 吗，只有强调这一点才能导向hackerrank的解啊
第2题n^2的dp？
第四题不会中， 再想想

sfsttz 发表于 2018-10-23 09:24
第一题面试官有特意强调 ai

面试官没有强调数据的大小范围，是我后来特意问了，才给定了一个相对小范围
第二题应该是n^2的dp
第四题我也没有什么好思路，不能大幅度降低时间复杂度

这一道tag题都没有啊

li89xin 发表于 2018-10-23 09:58
第四题的话，按x轴排序后，最大值斜率只可能出现在相邻两点的连线上。

good point

请问楼主是在哪个办公室面的？

What position? So hard!

楼主我想问问第二题是dp么？