近期论坛无法登录的解决方案


一亩三分地论坛

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

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

Airbnb 跪经

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

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

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

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

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

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

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

coding 2: text justification, a家最高频的题目之一.鐣欏璁哄潧-涓浜-涓夊垎鍦

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

评分

4

查看全部评分

wizardchen 发表于 2016-6-11 00:05:57 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
. 1point 3acres 璁哄潧
Trie+dfs


import java.util.*;

class TNode{
        TNode[] leaves;
        boolean isword;
        public TNode(){
                this.leaves=new TNode[26];
. from: 1point3acres.com/bbs                 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;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
        private TNode root=new TNode();
       
        public int findmaxPath(String[] words, char[][] mat){
                for(int i=0;i<words.length;i++){. From 1point 3acres bbs
                        insertT(words[i]);. 鍥磋鎴戜滑@1point 3 acres
                }
                int range=mat.length*mat[0].length;
                HashSet<Integer> set=new HashSet<Integer>();
                for(int i=0;i<range;i++){. 1point 3acres 璁哄潧
                        pathfind(set,this.root,mat,i,0);
                }
                return this.max;
        }
        . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
        public void pathfind(Set<Integer> set, TNode node, char[][] mat, int pos, int curcount){. visit 1point3acres.com for more.
                if(node.isword){
                        this.max=Math.max(max,curcount+1);. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                        node.isword=false;
                        pathfind(set,this.root,mat,pos,curcount+1);. from: 1point3acres.com/bbs
                        node.isword=true;. 1point 3acres 璁哄潧
                }
                int x=pos/mat[0].length;.1point3acres缃
                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);
                                }
                        }
                        set.remove(pos);
                }
                return;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
        }
       
        public List<Integer> connected(int pos, char[][] mat){
                int m=mat.length;.鏈枃鍘熷垱鑷1point3acres璁哄潧
                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);
                        }
                        if(y+i>=0&&y+i<n){
                                res.add(x+y+i);
                        }
                }
                return res;. 鍥磋鎴戜滑@1point 3 acres
        }. Waral 鍗氬鏈夋洿澶氭枃绔,
       
        public void insertT(String s){. Waral 鍗氬鏈夋洿澶氭枃绔,
                TNode cur=this.root;
                for(int i=0;i<s.length();i++){
                        if(cur.leaves[s.charAt(i)-'a']==null){. Waral 鍗氬鏈夋洿澶氭枃绔,
                                 cur.leaves[s.charAt(i)-'a']=new TNode();
                        }
                        cur=cur.leaves[s.charAt(i)-'a'];
                        if(i==s.length()-1){.鐣欏璁哄潧-涓浜-涓夊垎鍦
                                cur.isword=true;.鐣欏璁哄潧-涓浜-涓夊垎鍦
                        }. From 1point 3acres bbs
                }
        }
}
回复 支持 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必须是一次性走出来的吗?十字型可以么?

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

使用道具 举报

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 都试 ...

. From 1point 3acres bbs感觉是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" 吗?
. from: 1point3acres.com/bbs
不可以,每次访问一个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 {-google 1point3acres
  2.     public String longest = "";

  3.     public static void main(String[] args) {
  4.         String[] dict = {"abcddd","abc"};
  5.         char[][] mat = {{'a','b','c'},{'d','d','d'},{'b','b','d'}};
  6.         Solution sol = new Solution();
  7.         sol.findmaxPath(dict, mat);
  8.         System.out.println(sol.longest);.1point3acres缃

  9.         String[] dict2 = {"abs","abc","dd","bb"};
  10.         sol = new Solution();
  11.         sol.findmaxPath(dict2, mat);. 1point 3acres 璁哄潧
  12.         System.out.println(sol.longest);
  13.     }

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

  19.         int rows = mat.length;
  20.         int cols = mat[0].length;
  21.         boolean[][] taken = new boolean[rows][cols];. Waral 鍗氬鏈夋洿澶氭枃绔,

  22.         for (int row = 0; row < rows; row++) {
  23.             for (int col = 0; col < cols; col++) {
  24.                 recursiveHelper(trie, mat, row, col, taken, "", ""); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  25.             }
  26.         }
  27.     }

  28. . more info on 1point3acres.com
  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;

  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.             recursiveHelper(trie, mat, row + 1, col, taken, prev + current, "");
  44.             recursiveHelper(trie, mat, row - 1, col, taken, prev + current, "");
  45.             recursiveHelper(trie, mat, row, col + 1, taken, prev + current, "");
  46.             recursiveHelper(trie, mat, row, col - 1, taken, prev + current, "");
  47.         }

  48.         // Case 2 : use 'current' as the start of the suffix. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  49.         // e.g. we should match 'abcddd' instead of 'abc' in dict
  50.         if (trie.startsWith(current)) {
  51.             recursiveHelper(trie, mat, row + 1, col, taken, prev, current);
  52.             recursiveHelper(trie, mat, row - 1, col, taken, prev, current);
  53.             recursiveHelper(trie, mat, row, col + 1, taken, prev, current);.1point3acres缃
  54.             recursiveHelper(trie, mat, row, col - 1, taken, prev, current);
  55.         }

  56.         taken[row][col] = false;
  57.     }. 1point 3acres 璁哄潧
  58. }
复制代码
回复 支持 反对

使用道具 举报

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

使用道具 举报

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

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-6-26 10:23

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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