Facabook Intern 2.17面经

下午刚面的FB，一道题，没写出来。 、

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

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies
i, 华文细黑, Arial, sans-serif">求其他面试不黑。

这题好像用不着这么麻烦吧，LC446变种？

1. public class Solution {
   
2.     public int maxLenArithmeticSeq(int[] nums) {
   
3.         int n = nums.length;
   
4.         HashMap<Integer, Integer>[] map = new HashMap[n];
   
5.         int max = 0;
   
6.         for (int i = 0; i < nums.length; i++) {
   
7.             map[i] = new HashMap<>();
   
8.             for (int j = 0; j < i; j++) {
   
9.                 int diff = nums[i] - nums[j];
   
10.                 int count1 = map[i].getOrDefault(diff, 1);
    
11.                 int count2 = map[j].getOrDefault(diff, 1);
    
12.                 int len = Math.max(count2 + 1, count1);
    
13.                 max = Math.max(max, len);
    
14.                 map[i].put(diff, len);
    
15.             }
    
16.         }
    
17.         return max;
    
18.     }
    
19. }

复制代码

英伦十六世纪 发表于 2017-2-19 04:55
求链接，没见到过

public class Solution {
   //given a sorted array with no dups
   //O(n^2) time, O(n^2) space
   private static int longestArithmeticProgression(int[] nums) {
       if (nums == null || nums.length < 2) {
           return 0;
       }
       HashMap<Integer, ArrayList<ArrayList<Integer>>> map = new HashMap<>();//key is diff, value is pair of indices
       for (int i = 0; i < nums.length - 1; i++) {
           for (int j = i + 1; j < nums.length; j++) {
               int diff = nums[j] - nums[i];
               if (!map.containsKey(diff)) {
                   map.put(diff, new ArrayList<>());
               }
               ArrayList<Integer> pair = new ArrayList<>(Arrays.asList(i, j));
               map.get(diff).add(pair);
           }
       }
       int max = 0;
       for (int key : map.keySet()) {
           int[] lengths = new int[nums.length];
           for (int i = 0; i < lengths.length; i++) {
               lengths[i] = 1;//initialize all nums to 1
           }
           for (ArrayList<Integer> pair : map.get(key)) {
               lengths[pair.get(1)] = lengths[pair.get(0)] + 1;//update length of this diff's Arithmetic Progression
               max = Math.max(max, lengths[pair.get(1)]);
           }
       }
       return max;
   }
}

我朋友给我的面经的原题，应该是在地里下的。你可以找一找，最近有几位大佬有几个非常牛逼的总结啊。

楼主好人，offer在路上

楼主好人一生平安！！！！祝这星期能拿OFFER!!!!!

楼主好人一生平安！

dp 吗？ 感觉是longest increasing subsequence 的升级版啊

补充内容 (2017-2-18 05:49):
Oh 跟longest palindromic substring 一模一样的思想。中心往两边扩散。

adrianliu729 发表于 2017-2-18 05:40
dp 吗？ 感觉是longest increasing subsequence 的升级版啊

对的。。。写懵逼了。。。。就写了这一题。。。写着写着卡住了。

先两两算差值, 放到 HashMap 里面
然后用 dp 过滤一遍差值?

我第一眼最直观的想法就是排个序。。之后都好办了

补充内容 (2017-2-18 07:05):
好像不太对.. Nevermind

adrianliu729 发表于 2017-2-18 05:40
dp 吗？ 感觉是longest increasing subsequence 的升级版啊

补充内容 (2017-2-18 05:49):

等差数列不一定连续，longest palindromic substring思路不适用吧？

求问楼主啥时候投的