amazon 电面

Job Hunting Interview
, , , ,
1

leetcode 5 https://leetcode.com/problems/longest-palindromic-substring/description/
followup: dp 方法。improve

2

是指followup改用dp吗？
improve啥

3

就是用dp improve。其实复杂度没啥大变化，都是O(n^2);

4

用expand around center也ok吧
感觉dp用的space更多啊

5

三哥面试，问了20多分钟简历。然后写题目。妈的。感觉是不是又想挂人。

6

这个，好像是这个倾向

7

一开始就用的expand around center， 然后又用了dp，要求时间复杂度提高。

8

其实没啥提高，不过他说提高就提高吧。

9

dp(i, j) represents whether s(i ... j) can form a palindromic substring, dp(i, j) is true when s(i) equals to s(j) and s(i+1 ... j-1) is a palindromic substring. When we found a palindrome, check if it’s the longest one. Time complexity O(n^2).

public String longestPalindrome(String s) {
  int n = s.length();
  String res = null;
    
  boolean[][] dp = new boolean[n][n];
    
  for (int i = n - 1; i >= 0; i--) {
    for (int j = i; j < n; j++) {
      dp[i][j] = s.charAt(i) == s.charAt(j) && (j - i < 3 || dp[i + 1][j - 1]);
            
      if (dp[i][j] && (res == null || j - i + 1 > res.length())) {
        res = s.substring(i, j + 1);
      }
    }
  }
    
  return res;
}

这个空间明显比 expand 的方法多了 。。。 O(n^2).

10

拿到onsite了，两轮电面升了bar，onsite应该是l5.

11

两轮？还有一轮的面经呢？

12

是的。不过当时我悟出了他想干嘛，就写了。他的意思是第二个循环里面从右扫到左，如果j-i+1 < res.length()就跳过。当然，我举了个corner case:"abcdefg"这样的话还是O(n^2).然后他说在大量数据的情况下，这样的复杂度会是O(nlogn)，我直接说，大哥，你说的对，我之前想到了这个思路，但是觉得没那么improve，还是你有经验。

13

还有一轮是design editor，完成 add, backspace, printcharAt, undo,的操作。主要用stack村就好了。秒了。

14

leetcode 原题吗？

15

不是吧？应该不是。

16

思路就是stringbuilder存text，然后stack存操作。还是蛮简单的。

17

电面升Bar？

18

电面决定onsite升不升bar

19

职位是l5的，但楼主只有1年多经验。

20

总之是好事