传说中的谷歌招聘委员会成员之一,从幕后走出来,教你学系统设计!


一亩三分地论坛

 找回密码
 获取更多干活,快来注册
Babeltime游戏工作室招工程师、美术和策划
Tubi TV招安卓、前端和机器学习工程师
把贵司招聘信息放这里
查看: 6378|回复: 17
收起左侧

Airbnb 跪经

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

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

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

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

x
两轮coding, 一轮project deep dive, 一轮system design, 两轮culture fit. from: 1point3acres.com/bbs

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

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. Waral 鍗氬鏈夋洿澶氭枃绔,


import java.util.*;. from: 1point3acres.com/bbs

class TNode{
        TNode[] leaves;
        boolean isword;
        public TNode(){
                this.leaves=new TNode[26];
                this.isword=false;
        }
}

public class Solution {
        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();
                System.out.println(sol.findmaxPath(dict,mat));
        }
       
        private int max=0;. Waral 鍗氬鏈夋洿澶氭枃绔,
        private TNode root=new TNode();. Waral 鍗氬鏈夋洿澶氭枃绔,
       
        public int findmaxPath(String[] words, char[][] mat){-google 1point3acres
                for(int i=0;i<words.length;i++){
                        insertT(words[i]);
                }. Waral 鍗氬鏈夋洿澶氭枃绔,
                int range=mat.length*mat[0].length;
                HashSet<Integer> set=new HashSet<Integer>();. Waral 鍗氬鏈夋洿澶氭枃绔,
                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){.1point3acres缃
                if(node.isword){. 鍥磋鎴戜滑@1point 3 acres
                        this.max=Math.max(max,curcount+1);
                        node.isword=false;. 1point 3acres 璁哄潧
                        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){. 1point 3acres 璁哄潧
                        set.add(pos);
                        for(Integer connect:connected(pos,mat)){
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴                                if(!set.contains(connect)){
                                        pathfind(set,node.leaves[mat[x][y]-'a'],mat,connect,curcount);
                                }
                        }. visit 1point3acres.com for more.
                        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>();. 1point 3acres 璁哄潧
                for(int i=-1;i<=1;i+=2){-google 1point3acres
                        if(x+i>=0&&x+i<m){
                                res.add((x+i)*n+y);. more info on 1point3acres.com
                        }
                        if(y+i>=0&&y+i<n){
                                res.add(x+y+i);
                        }
                }
. visit 1point3acres.com for more.                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();
                        }. 鍥磋鎴戜滑@1point 3 acres
                        cur=cur.leaves[s.charAt(i)-'a'];
                        if(i==s.length()-1){
                                cur.isword=true;
                        }
                }
        }
}
回复 支持 1 反对 0

使用道具 举报

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

使用道具 举报

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

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

使用道具 举报

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. . visit 1point3acres.com for more.
  2. public class Solution {
  3.     public String longest = "";

  4.     public static void main(String[] args) {
  5.         String[] dict = {"abcddd","abc"};. 1point 3acres 璁哄潧
  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.     }
  15. . from: 1point3acres.com/bbs
  16.     public void findmaxPath(String[] dict, char[][] mat) {. more info on 1point3acres.com
  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. 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  25.         for (int row = 0; row < rows; row++) {
  26.             for (int col = 0; col < cols; col++) {
    . from: 1point3acres.com/bbs
  27.                 recursiveHelper(trie, mat, row, col, taken, "", "");
  28.             }
  29.         }. from: 1point3acres.com/bbs
  30.     }

  31.     private void recursiveHelper(Trie trie, char[][] mat, int row, int col, boolean[][] taken, String prev, String current) {
  32.         int rows = mat.length;
  33.         int cols = mat[0].length;
  34. . From 1point 3acres bbs
  35.         if (row < 0 || col < 0 || row >= rows || col >= cols || taken[row][col]) {
  36.             return;
  37.         }

  38.         char ch = mat[row][col];. visit 1point3acres.com for more.
  39.         taken[row][col] = true;. visit 1point3acres.com for more.
  40.         current += ch;
  41. . 1point 3acres 璁哄潧
  42.         // Case 1 : use 'current' as the end of the prefix
  43.         if (trie.search(current)) {
  44.             if ((prev + current).length() > this.longest.length()) {
  45.                 this.longest = prev + current;
  46.             }

  47.             recursiveHelper(trie, mat, row + 1, col, taken, prev + current, "");
  48.             recursiveHelper(trie, mat, row - 1, col, taken, prev + current, "");
  49.             recursiveHelper(trie, mat, row, col + 1, taken, prev + current, "");. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  50.             recursiveHelper(trie, mat, row, col - 1, taken, prev + current, "");
  51.         } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

  52.         // Case 2 : use 'current' as the start of the suffix
  53.         // e.g. we should match 'abcddd' instead of 'abc' in dict
  54.         if (trie.startsWith(current)) {
  55.             recursiveHelper(trie, mat, row + 1, col, taken, prev, current);
  56.             recursiveHelper(trie, mat, row - 1, col, taken, prev, current);
  57.             recursiveHelper(trie, mat, row, col + 1, taken, prev, current); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  58.             recursiveHelper(trie, mat, row, col - 1, taken, prev, current);
  59.         }

  60.         taken[row][col] = false;. 鍥磋鎴戜滑@1point 3 acres
  61.     }
  62. }
复制代码
回复 支持 反对

使用道具 举报

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

使用道具 举报

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

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-9-22 07:16

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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