一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 3401|回复: 15
收起左侧

Airbnb 跪经

[复制链接] |试试Instant~ |关注本帖
皮蛋豆腐 发表于 2016-5-24 13:06:27 | 显示全部楼层 |阅读模式

2016(4-6月) 码农类 硕士 全职@Airbnb - 猎头 - Onsite |Fail在职跳槽

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
两轮coding, 一轮project deep dive, 一轮system design, 两轮culture fit

coding 1: 印度小哥,人笑呵呵的,非常nice(笑里藏刀)。 题目是给定一个2d matrix of letters和一个dictionary,找出一条path包含最多的存在于字典的word个数 讨论了半天算法,真到写code的时候时间就来不及了,test case没来得及写,也没来得及优化。
-google 1point3acres用了dfs backtracking 暴力解法。应该就是挂在这一轮。

project deep dive:中国小哥,一进来就笑嘻嘻的,介绍你做过的project,会问的非常细。包括design level和implementation level的。准备过都没什么问题。

system design: design airbnb, 着重internationalization。

coding 2: text justification, a家最高频的题目之一. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

最后两轮各半小时的culture fit: 各种有的没的behavior questions。能聊的应该都问题

总结: a家需要code clean and runnable, 写test case 并且bug free。 题目至少是hard level的,而且大都写起来非常繁琐(python 50行代码以上)。除非两轮code都写的干净利落 或者某一轮非常impressive,有人advocate你,说非你不可。不然跪的脾气都没有。
还是怪自己技艺不精,需要多加磨练。

评分

4

查看全部评分

wizardchen 发表于 2016-6-11 00:05:57 | 显示全部楼层
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
Trie+dfs. 1point 3acres 璁哄潧


import java.util.*;

class TNode{
        TNode[] leaves;
        boolean isword;
        public TNode(){
                this.leaves=new TNode[26];
                this.isword=false;. 1point 3acres 璁哄潧
        }
}
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
public class Solution {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
        public static void main(String[] args){.鏈枃鍘熷垱鑷1point3acres璁哄潧
                String[] dict={"abs","abc","dd","bb"};
                char[][] mat={{'a','b','c'},{'d','d','d'},{'b','b','d'}};
                Solution sol=new Solution();
                System.out.println(sol.findmaxPath(dict,mat));
        }
       
        private int max=0;
        private TNode root=new TNode();
       
        public int findmaxPath(String[] words, char[][] mat){
                for(int i=0;i<words.length;i++){. from: 1point3acres.com/bbs
                        insertT(words[i]);. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                }
                int range=mat.length*mat[0].length;
                HashSet<Integer> set=new HashSet<Integer>();
                for(int i=0;i<range;i++){
                        pathfind(set,this.root,mat,i,0);. from: 1point3acres.com/bbs
                }
                return this.max;
        }
       
        public void pathfind(Set<Integer> set, TNode node, char[][] mat, int pos, int curcount){
                if(node.isword){-google 1point3acres
                        this.max=Math.max(max,curcount+1);
                        node.isword=false;
                        pathfind(set,this.root,mat,pos,curcount+1);. 鍥磋鎴戜滑@1point 3 acres
                        node.isword=true;
                }. from: 1point3acres.com/bbs
                int x=pos/mat[0].length;
                int y=pos%mat[0].length;
                if(node.leaves[mat[x][y]-'a']!=null){
                        set.add(pos);. more info on 1point3acres.com
                        for(Integer connect:connected(pos,mat)){
                                if(!set.contains(connect)){
                                        pathfind(set,node.leaves[mat[x][y]-'a'],mat,connect,curcount);
                                }
                        }
                        set.remove(pos);
                }
                return; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
        }
       
        public List<Integer> connected(int pos, char[][] mat){
                int m=mat.length;
                int n=mat[0].length;
                int x=pos/n;
                int y=pos%n;
                List<Integer> res=new ArrayList<Integer>();
                for(int i=-1;i<=1;i+=2){
                        if(x+i>=0&&x+i<m){
                                res.add((x+i)*n+y);. from: 1point3acres.com/bbs
                        }. 鍥磋鎴戜滑@1point 3 acres
                        if(y+i>=0&&y+i<n){
                                res.add(x+y+i);
                        }. more info on 1point3acres.com
                }
                return res;. visit 1point3acres.com for more.
        }. visit 1point3acres.com for more.
       
        public void insertT(String s){
                TNode cur=this.root;
                for(int i=0;i<s.length();i++){
                        if(cur.leaves[s.charAt(i)-'a']==null){
                                 cur.leaves[s.charAt(i)-'a']=new TNode();. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                        }. Waral 鍗氬鏈夋洿澶氭枃绔,
                        cur=cur.leaves[s.charAt(i)-'a'];. more info on 1point3acres.com
                        if(i==s.length()-1){
                                cur.isword=true;. 鍥磋鎴戜滑@1point 3 acres
                        }
                }
        }
}
回复 支持 1 反对 0

使用道具 举报

wtcupup 发表于 2016-5-24 14:14:22 | 显示全部楼层
coding 1: 这个path必须是一次性走出来的吗?十字型可以么?
回复 支持 反对

使用道具 举报

 楼主| 皮蛋豆腐 发表于 2016-5-24 14:19:59 | 显示全部楼层
wtcupup 发表于 2016-5-24 14:14. 鍥磋鎴戜滑@1point 3 acres
coding 1: 这个path必须是一次性走出来的吗?十字型可以么?

是的。十字形不可以。
. from: 1point3acres.com/bbs 每次移动只能上下左右走一步
回复 支持 反对

使用道具 举报

huai10 发表于 2016-5-24 16:41:41 | 显示全部楼层
说实话这个烙印有点坏, 我只能想到每个点都试一下,一个tmp string 记录, 碰到字典里有 + 1 和不+1 都试一下。。。最后找一个最长的?
回复 支持 反对

使用道具 举报

 楼主| 皮蛋豆腐 发表于 2016-5-24 21:32:05 | 显示全部楼层
huai10 发表于 2016-5-24 16:41
说实话这个烙印有点坏, 我只能想到每个点都试一下,一个tmp string 记录, 碰到字典里有 + 1 和不+1 都试 ...

感觉是2d word break的变形,不知道2维dp能不能做,等有心思了再好好写写发上来。
a家和p家面的我挺受打击的,自信心严重受损。
回复 支持 反对

使用道具 举报

erin99425 发表于 2016-5-25 04:11:36 | 显示全部楼层
请问A家面完多久能通知结果呀?
回复 支持 反对

使用道具 举报

 楼主| 皮蛋豆腐 发表于 2016-5-25 04:19:20 | 显示全部楼层
erin99425 发表于 2016-5-25 04:11
请问A家面完多久能通知结果呀?
.鐣欏璁哄潧-涓浜-涓夊垎鍦
a家move非常快,三天之内能拿到结果
回复 支持 反对

使用道具 举报

hkc593 发表于 2016-5-25 13:01:37 | 显示全部楼层
第一题中一个letter可以重复用吗? 比如说 'b' 'e' 'd' 'a' 'd', 这条path可以是 "bed" + "dad" 吗?
回复 支持 反对

使用道具 举报

 楼主| 皮蛋豆腐 发表于 2016-5-25 16:11:08 | 显示全部楼层
hkc593 发表于 2016-5-25 13:01
第一题中一个letter可以重复用吗? 比如说 'b' 'e' 'd' 'a' 'd', 这条path可以是 "bed" + "dad" 吗?

不可以,每次访问一个position,访问过了就不能再访问了
回复 支持 反对

使用道具 举报

ipure 发表于 2016-5-26 04:18:06 | 显示全部楼层
这题好难啊, 没见过类似的, 回去做作.
回复 支持 反对

使用道具 举报

ipure 发表于 2016-5-26 05:55:26 | 显示全部楼层
楼主 能不能讲讲design细节怎么问的, 是backend还是frontend, 是要整套系统符合国际化么
回复 支持 反对

使用道具 举报

 楼主| 皮蛋豆腐 发表于 2016-5-26 07:43:41 | 显示全部楼层
ipure 发表于 2016-5-26 05:55
楼主 能不能讲讲design细节怎么问的, 是backend还是frontend, 是要整套系统符合国际化么
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
问的非常笼统,需要你自己去clarify
回复 支持 反对

使用道具 举报

kayv 发表于 2016-5-26 09:45:35 | 显示全部楼层
dfs+字典树应该可以,字典树快速判断是否可行
回复 支持 反对

使用道具 举报

18658109706 发表于 2016-8-23 04:46:19 | 显示全部楼层
问一下,onsite也是直接写直接跑吗?还是白板写呀
回复 支持 反对

使用道具 举报

hardy616 发表于 2016-8-24 07:39:51 | 显示全部楼层
我也写一个trie+dfs的穷举

  1. public class Solution {. from: 1point3acres.com/bbs
  2.     public String longest = "";
  3. . from: 1point3acres.com/bbs
  4.     public static void main(String[] args) {. Waral 鍗氬鏈夋洿澶氭枃绔,
  5.         String[] dict = {"abcddd","abc"};
  6.         char[][] mat = {{'a','b','c'},{'d','d','d'},{'b','b','d'}};
  7.         Solution sol = new Solution();
  8.         sol.findmaxPath(dict, mat);
  9.         System.out.println(sol.longest);
  10. .1point3acres缃
  11.         String[] dict2 = {"abs","abc","dd","bb"};. 鍥磋鎴戜滑@1point 3 acres
  12.         sol = new Solution();
  13.         sol.findmaxPath(dict2, mat);
  14.         System.out.println(sol.longest);
  15.     }

  16.     public void findmaxPath(String[] dict, char[][] mat) {
  17.         Trie trie = new Trie();
  18.         for (String s : dict) {
  19.             trie.insert(s);
  20.         }

  21.         int rows = mat.length;
  22.         int cols = mat[0].length;
  23.         boolean[][] taken = new boolean[rows][cols];

  24.         for (int row = 0; row < rows; row++) {
    . From 1point 3acres bbs
  25.             for (int col = 0; col < cols; col++) {
  26.                 recursiveHelper(trie, mat, row, col, taken, "", "");. 1point 3acres 璁哄潧
  27.             }
  28.         }
  29.     }

  30.     private void recursiveHelper(Trie trie, char[][] mat, int row, int col, boolean[][] taken, String prev, String current) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
  31.         int rows = mat.length;
  32.         int cols = mat[0].length;

  33.         if (row < 0 || col < 0 || row >= rows || col >= cols || taken[row][col]) {
  34.             return;
  35.         }

  36.         char ch = mat[row][col];
  37.         taken[row][col] = true;
  38.         current += ch;

  39.         // Case 1 : use 'current' as the end of the prefix
  40.         if (trie.search(current)) {
  41.             if ((prev + current).length() > this.longest.length()) {
  42.                 this.longest = prev + current;
  43.             }

  44.             recursiveHelper(trie, mat, row + 1, col, taken, prev + current, "");
  45.             recursiveHelper(trie, mat, row - 1, col, taken, prev + current, "");
  46.             recursiveHelper(trie, mat, row, col + 1, taken, prev + current, "");
  47.             recursiveHelper(trie, mat, row, col - 1, taken, prev + current, "");
  48.         }

  49.         // Case 2 : use 'current' as the start of the suffix
  50.         // e.g. we should match 'abcddd' instead of 'abc' in dict
  51.         if (trie.startsWith(current)) {. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  52.             recursiveHelper(trie, mat, row + 1, col, taken, prev, current);
  53.             recursiveHelper(trie, mat, row - 1, col, taken, prev, current);
  54.             recursiveHelper(trie, mat, row, col + 1, taken, prev, current);
  55.             recursiveHelper(trie, mat, row, col - 1, taken, prev, current);
  56.         }

  57.         taken[row][col] = false;
  58.     }
  59. }
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-3 10:37

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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