【通知】7月22,工业界资深数据科学家教你破解各大公司面试!


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 6041|回复: 17
收起左侧

Airbnb 跪经

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

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

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

x
两轮coding, 一轮project deep dive, 一轮system design, 两轮culture fit 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
.1point3acres缃
coding 1: 印度小哥,人笑呵呵的,非常nice(笑里藏刀)。 题目是给定一个2d matrix of letters和一个dictionary,找出一条path包含最多的存在于字典的word个数 讨论了半天算法,真到写code的时候时间就来不及了,test case没来得及写,也没来得及优化。
用了dfs backtracking 暴力解法。应该就是挂在这一轮。

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

system design: design airbnb, 着重internationalization。

coding 2: text justification, a家最高频的题目之一. visit 1point3acres.com for more.

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

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

评分

4

查看全部评分

wizardchen 发表于 2016-6-11 00:05:57 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地

Trie+dfs
. from: 1point3acres.com/bbs

import java.util.*;
-google 1point3acres
class TNode{
        TNode[] leaves;
        boolean isword;. Waral 鍗氬鏈夋洿澶氭枃绔,
        public TNode(){. Waral 鍗氬鏈夋洿澶氭枃绔,
                this.leaves=new TNode[26];
                this.isword=false;
        }
}

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

使用道具 举报

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

使用道具 举报

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

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

使用道具 举报

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 {
  2.     public String longest = "";. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  3. .鐣欏璁哄潧-涓浜-涓夊垎鍦
  4.     public static void main(String[] args) {
  5.         String[] dict = {"abcddd","abc"};. From 1point 3acres bbs
  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.         String[] dict2 = {"abs","abc","dd","bb"};
  11.         sol = new Solution();
  12.         sol.findmaxPath(dict2, mat);
  13.         System.out.println(sol.longest);
  14.     }. 鍥磋鎴戜滑@1point 3 acres

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

  20.         int rows = mat.length;
  21.         int cols = mat[0].length;
  22.         boolean[][] taken = new boolean[rows][cols];. visit 1point3acres.com for more.

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

  29.     private void recursiveHelper(Trie trie, char[][] mat, int row, int col, boolean[][] taken, String prev, String current) {
  30.         int rows = mat.length;
  31.         int cols = mat[0].length;. Waral 鍗氬鏈夋洿澶氭枃绔,

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

  35.         char ch = mat[row][col];
  36.         taken[row][col] = true;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  37.         current += ch;

  38.         // Case 1 : use 'current' as the end of the prefix
  39.         if (trie.search(current)) {
  40.             if ((prev + current).length() > this.longest.length()) {
  41.                 this.longest = prev + current;
  42.             }
  43. -google 1point3acres
  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, "");. From 1point 3acres bbs
  48.         }

  49. . more info on 1point3acres.com
  50.         // Case 2 : use 'current' as the start of the suffix
  51.         // e.g. we should match 'abcddd' instead of 'abc' in dict.鐣欏璁哄潧-涓浜-涓夊垎鍦
  52.         if (trie.startsWith(current)) {. Waral 鍗氬鏈夋洿澶氭枃绔,
  53.             recursiveHelper(trie, mat, row + 1, col, taken, prev, current);
  54.             recursiveHelper(trie, mat, row - 1, col, taken, prev, current);
  55.             recursiveHelper(trie, mat, row, col + 1, taken, prev, current);
  56.             recursiveHelper(trie, mat, row, col - 1, taken, prev, current);
  57.         }

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

使用道具 举报

iamafrican 发表于 2016-12-29 11:27:21 | 显示全部楼层
请问最后path是像一笔画一样吗?如果是断开的但是单词最多可以吗?
回复 支持 反对

使用道具 举报

shelly1996 发表于 2016-12-31 02:38:20 | 显示全部楼层
同问楼主,path里如果断开的单词最多可以么,一定要连在一起么
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-7-22 19:01

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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