一亩三分地

 找回密码 注册账号

扫描二维码登录本站

BBS
Offer多多
Salarytics
交友
Learn
Who's Hiring?
Visa Tracker
疫情动态
指尖新闻
Instant
客户端
微信公众号
扫码关注公众号
留学申请公众号
扫码关注留学申请公众号
Youtube频道
留学博客
关于我们
查看: 2127|回复: 10
收起左侧

airbnb 电面 及两种解法

[复制链接] |只看干货 |码农类general, 美国面经, 面试经验, airbnb
我的人缘0

升级   62.71%


分享帖子到朋友圈
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   97% (88)
 
 
2% (2)    👎

2019(4-6月) 码农类General 硕士 全职@Airbnb - 内推 - 技术电面  | Pass/Offer | 在职跳槽

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?注册账号

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

是它家非常高频的Palindrome pairs。
面试官上来先解释什么是Palindrome pairs,注意和面试官沟通。然后会要求写一个isPalindrome的判断method。

因为这次刷题没怎么准备太长时间,我很快写出了hashmap的解之后面试官问我有没有什么更efficient的解法,答曰既然是跟字母有关的可能可以使用Trie结构,写了一会儿TrieNode class和insert method面试官说可以了,留几分钟你问我问题。聊完之后对方还给了一些onsite的tips. 过了两天HR 跟进安排onsite,就酱。

贴上两种解法求大米呀,加米不扣自己米哦!最近看经验啥的花了不少米QAQ:

HashMap 的
[Java] 纯文本查看 复制代码
/*
 * Copyright 2019 Amazon.com, Inc. or its affiliates. All Rights Reserved.
 */

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

/**
 * Follow up: 用trie? 什么是trie?
 * [url]http://www.noteanddata.com/leetcode-336-Palindrome-Pairs-airbnb-interview-problem-java-solution-note.html[/url]
 */

public class PalindromPairs {
    public List<List<Integer>> palindromePairs(String[] words){
        List<List<Integer>> res = new ArrayList<>();
        if(words == null || words.length == 0) return res;
        HashMap<String, Integer> posMap = new HashMap<>();
        for(int i=0;i<words.length; i++) {
            posMap.put(words[i],i);
        }

        for(int i=0;i<words.length;i++) {
            for(int j=0;j<=words[i].length();j++){ //j<=0 so that it handles empty string
                String sub1 = words[i].substring(0, j);
                String sub2 = words[i].substring(j);
                if(isPalin(sub1)) {
                    String revSub2 = new StringBuilder(sub2).reverse().toString();
                    if(posMap.containsKey(revSub2) && posMap.get(revSub2) !=i) {
                        res.add(Arrays.asList(posMap.get(revSub2), i));
                    }
                }
                if(isPalin(sub2) ) { //to avoid duplicate
                    String revSub1 = new StringBuilder(sub1).reverse().toString();
                    if(posMap.containsKey(revSub1) && posMap.get(revSub1) != i) {
                        res.add(Arrays.asList(i, posMap.get(revSub1)));
                    }
                }

            }
        }

        return res;
    }

    private boolean isPalin(String str){
        int left = 0;
        int right = str.length()-1;
        while(left<right) {
            if(str.charAt(left++)!=str.charAt(right--)) return false;
        }
        return true;
    }
}




Trie的

[Java] 纯文本查看 复制代码
/*
 * Copyright 2019 Amazon.com, Inc. or its affiliates. All Rights Reserved.
 */

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class PalindromPairsTrie {
    List<List<Integer>> res = new ArrayList<>();
    TrieNode root = new TrieNode();
    private static class TrieNode {
        TrieNode[] children;
        int index;
        List<Integer> list;

        TrieNode() {
            children = new TrieNode[26];
            index = -1;
            list = new ArrayList<>();
        }
    }

    public List<List<Integer>> palindromePairs(String[] words) {

        for (int i = 0; i < words.length; i++) {
            insert(words[i], i);
        }

        for (int i = 0; i < words.length; i++) {
            search(words[i], i);
        }

        return res;
    }

    private void insert(String word, int index) {
        TrieNode trie = root;
        for (int i = word.length() - 1; i >= 0; i--) {
            int j = word.charAt(i) - 'a';

            if (trie.children[j] == null) {
                trie.children[j] = new TrieNode();
            }

            if (isPalindrome(word, 0, i)) {
                trie.list.add(index);
            }

            trie = trie.children[j];
        }

        trie.list.add(index);
        trie.index = index;
    }

    private void search(String word, int i) {
        TrieNode trie = root;
        for (int j = 0; j < word.length(); j++) { //handles when other part is shorter than words[i]
            if (trie.index >= 0 && trie.index != i && isPalindrome(word, j, word.length() - 1)) {
                res.add(Arrays.asList(i, trie.index));
            }

            trie = trie.children[word.charAt(j) - 'a'];
            if (trie == null) return; // important!!!
        }

        for (int j : trie.list) { //handles when other part is longer than words[i]
            if (i == j) continue;
            res.add(Arrays.asList(i, j));
        }
    }

    private boolean isPalindrome(String word, int i, int j) {
        while (i < j) {
            if (word.charAt(i++) != word.charAt(j--)) return false;
        }

        return true;
    }
}




评分

参与人数 5大米 +38 收起 理由
snowei0 + 1 很有用的信息!
goodluck_ccc + 3 很有用的信息!
0v0monday0v0 + 1 赞一个
清道神君 + 30
leixiang5 + 3 谢谢分享!

查看全部评分


上一篇:google 电面
下一篇:Bolt 面经
我的人缘0

升级   27.68%

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   88% (386)
 
 
11% (49)    👎
我的hr为什么说要面2轮phone才onsite
回复

使用道具 举报

我的人缘0

升级   62.71%

 楼主| xialanxuan 2019-7-1 08:57:30 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   97% (88)
 
 
2% (2)    👎
leixiang5 发表于 2019-7-1 08:56
我的hr为什么说要面2轮phone才onsite

你面的是哪里的组?不同的组可能不一样,我也有听说面了二轮的。求加米呀!谢谢同学。
回复

使用道具 举报

我的人缘0

升级   27.68%

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   88% (386)
 
 
11% (49)    👎
xialanxuan 发表于 2019/07/01 08:57:30


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

我?好像是homes吧。给米
回复

使用道具 举报

我的人缘0

升级   62.71%

 楼主| xialanxuan 2019-7-1 09:05:01 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   97% (88)
 
 
2% (2)    👎
leixiang5 发表于 2019-7-1 08:58
我?好像是homes吧。给米

地区呢?湾区那边吗~
回复

使用道具 举报

我的人缘0

升级   27.68%

leixiang5 2019-7-1 13:15:04 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   88% (386)
 
 
11% (49)    👎
xialanxuan 发表于 2019-7-1 09:05
地区呢?湾区那边吗~

好像是? 不记得了.😂
回复

使用道具 举报

头像被屏蔽
我的人缘0
crazycodyman 2019-7-1 13:55:09 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复

使用道具 举报

我的人缘0

升级   62.71%

 楼主| xialanxuan 2019-7-2 08:07:36 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   97% (88)
 
 
2% (2)    👎
crazycodyman 发表于 2019-7-1 13:55
ispalindrome可以用two pointer来做,应该是最优解了

在我第二个解里面应该已经写了这个方法哈
再贴一遍~
[Java] 纯文本查看 复制代码
private boolean isPalindrome(String word, int i, int j) {
        while (i < j) {
            if (word.charAt(i++) != word.charAt(j--)) return false;
        }
 
        return true;
    }
回复

使用道具 举报

我的人缘0

升级   27.68%

leixiang5 2019-7-25 02:44:33 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   88% (386)
 
 
11% (49)    👎
好像改革只适合local的. 比如飞到总部面的话. 是直接都安排在一天. 如果在西雅图. 然后面的西雅图职位. 就可以分成2天了.
回复

使用道具 举报

我的人缘0

升级   3.29%

dibao3878 2019-8-11 13:39:04 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (45)
 
 
0% (0)    👎
hashmap 的那个楼主有放离抠跑过么?
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

隐私提醒:
■为防止被骚扰甚至人肉,不要公开留微信等联系方式,请以论坛私信方式发送。
■特定版块可以超级匿名:https://pay.1point3acres.com/tools/thread
■其他版块匿名方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|||一亩三分地

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

Some icons made by Freepik from flaticon.com

快速回复 返回顶部 返回列表