airbnb 电面 及两种解法

目前airbnb的面试正在做一些改革，过了电面之后安排onsite, onsite是分两天，第一天面design, coding, experience, pass了再去面cross functional。安排了第二轮onsite还没去，等onsite都面完了再来汇报。先来个电面经验

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

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

啥的花了不少米QAQ：

HashMap 的

1. /*
   
2. * Copyright 2019 Amazon.com, Inc. or its affiliates. All Rights Reserved.
   
3. */
   
4. 
   
5. import java.util.ArrayList;
   
6. import java.util.Arrays;
   
7. import java.util.HashMap;
   
8. import java.util.List;
   
9. 
   
10. /**
    
11. * Follow up: 用trie? 什么是trie?
    
12. * [url]http://www.noteanddata.com/leetcode-336-Palindrome-Pairs-airbnb-interview-problem-java-solution-note.html[/url]
    
13. */
    
14. 
    
15. public class PalindromPairs {
    
16.     public List<List<Integer>> palindromePairs(String[] words){
    
17.         List<List<Integer>> res = new ArrayList<>();
    
18.         if(words == null || words.length == 0) return res;
    
19.         HashMap<String, Integer> posMap = new HashMap<>();
    
20.         for(int i=0;i<words.length; i++) {
    
21.             posMap.put(words[i],i);
    
22.         }
    
23. 
    
24.         for(int i=0;i<words.length;i++) {
    
25.             for(int j=0;j<=words[i].length();j++){ //j<=0 so that it handles empty string
    
26.                 String sub1 = words[i].substring(0, j);
    
27.                 String sub2 = words[i].substring(j);
    
28.                 if(isPalin(sub1)) {
    
29.                     String revSub2 = new StringBuilder(sub2).reverse().toString();
    
30.                     if(posMap.containsKey(revSub2) && posMap.get(revSub2) !=i) {
    
31.                         res.add(Arrays.asList(posMap.get(revSub2), i));
    
32.                     }
    
33.                 }
    
34.                 if(isPalin(sub2) ) { //to avoid duplicate
    
35.                     String revSub1 = new StringBuilder(sub1).reverse().toString();
    
36.                     if(posMap.containsKey(revSub1) && posMap.get(revSub1) != i) {
    
37.                         res.add(Arrays.asList(i, posMap.get(revSub1)));
    
38.                     }
    
39.                 }
    
40. 
    
41.             }
    
42.         }
    
43. 
    
44.         return res;
    
45.     }
    
46. 
    
47.     private boolean isPalin(String str){
    
48.         int left = 0;
    
49.         int right = str.length()-1;
    
50.         while(left<right) {
    
51.             if(str.charAt(left++)!=str.charAt(right--)) return false;
    
52.         }
    
53.         return true;
    
54.     }
    
55. }
    

复制代码

Trie的

1. /*
   
2. * Copyright 2019 Amazon.com, Inc. or its affiliates. All Rights Reserved.
   
3. */
   
4. 
   
5. import java.util.ArrayList;
   
6. import java.util.Arrays;
   
7. import java.util.List;
   
8. 
   
9. public class PalindromPairsTrie {
   
10.     List<List<Integer>> res = new ArrayList<>();
    
11.     TrieNode root = new TrieNode();
    
12.     private static class TrieNode {
    
13.         TrieNode[] children;
    
14.         int index;
    
15.         List<Integer> list;
    
16. 
    
17.         TrieNode() {
    
18.             children = new TrieNode[26];
    
19.             index = -1;
    
20.             list = new ArrayList<>();
    
21.         }
    
22.     }
    
23. 
    
24.     public List<List<Integer>> palindromePairs(String[] words) {
    
25. 
    
26.         for (int i = 0; i < words.length; i++) {
    
27.             insert(words[i], i);
    
28.         }
    
29. 
    
30.         for (int i = 0; i < words.length; i++) {
    
31.             search(words[i], i);
    
32.         }
    
33. 
    
34.         return res;
    
35.     }
    
36. 
    
37.     private void insert(String word, int index) {
    
38.         TrieNode trie = root;
    
39.         for (int i = word.length() - 1; i >= 0; i--) {
    
40.             int j = word.charAt(i) - 'a';
    
41. 
    
42.             if (trie.children[j] == null) {
    
43.                 trie.children[j] = new TrieNode();
    
44.             }
    
45. 
    
46.             if (isPalindrome(word, 0, i)) {
    
47.                 trie.list.add(index);
    
48.             }
    
49. 
    
50.             trie = trie.children[j];
    
51.         }
    
52. 
    
53.         trie.list.add(index);
    
54.         trie.index = index;
    
55.     }
    
56. 
    
57.     private void search(String word, int i) {
    
58.         TrieNode trie = root;
    
59.         for (int j = 0; j < word.length(); j++) { //handles when other part is shorter than words[i]
    
60.             if (trie.index >= 0 && trie.index != i && isPalindrome(word, j, word.length() - 1)) {
    
61.                 res.add(Arrays.asList(i, trie.index));
    
62.             }
    
63. 
    
64.             trie = trie.children[word.charAt(j) - 'a'];
    
65.             if (trie == null) return; // important!!!
    
66.         }
    
67. 
    
68.         for (int j : trie.list) { //handles when other part is longer than words[i]
    
69.             if (i == j) continue;
    
70.             res.add(Arrays.asList(i, j));
    
71.         }
    
72.     }
    
73. 
    
74.     private boolean isPalindrome(String word, int i, int j) {
    
75.         while (i < j) {
    
76.             if (word.charAt(i++) != word.charAt(j--)) return false;
    
77.         }
    
78. 
    
79.         return true;
    
80.     }
    
81. }
    

复制代码

我的hr为什么说要面2轮phone才onsite

leixiang5 发表于 2019-7-1 08:56
我的hr为什么说要面2轮phone才onsite

你面的是哪里的组？不同的组可能不一样，我也有听说面了二轮的。求加米呀！谢谢同学。

论坛匿名用户 发表于 2019/07/01 08:57:30


你面的是哪里的组？不同的组可能不一样，我也有听说面了二轮的。求加米呀！谢谢同学。

我？好像是homes吧。给米

leixiang5 发表于 2019-7-1 08:58
我？好像是homes吧。给米

地区呢？湾区那边吗~

论坛匿名用户 发表于 2019-7-1 09:05
地区呢？湾区那边吗~

好像是? 不记得了.😂

ispalindrome可以用two pointer来做，应该是最优解了

crazycodyman 发表于 2019-7-1 13:55
ispalindrome可以用two pointer来做，应该是最优解了

在我第二个解里面应该已经写了这个方法哈
再贴一遍~

1. private boolean isPalindrome(String word, int i, int j) {
   
2.         while (i < j) {
   
3.             if (word.charAt(i++) != word.charAt(j--)) return false;
   
4.         }
   
5. 
   
6.         return true;
   
7.     }

复制代码

好像改革只适合local的. 比如飞到总部面的话. 是直接都安排在一天. 如果在西雅图. 然后面的西雅图职位. 就可以分成2天了.

hashmap 的那个楼主有放离抠跑过么？