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


一亩三分地论坛

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

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

只想安静的狗带的airbnb面试

[复制链接] |试试Instant~ |关注本帖
664077398 发表于 2016-11-8 08:31:02 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 硕士 实习@Airbnb - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
转专业找实习太艰辛了。。直接上题吧
电话面试,是一道新题,拓扑排序,aliendictionary做熟了就很简单了

skype面两轮,.1point3acres缃
第一轮 新题,给一个有向图,如果把一个点放到res那么该点下游的点都当成是被选择了。example: a->b->c,选了a的话bc都被选了。求选最少的点集合让包含整个graph。在国人大哥循循善诱上最后写出来了,然后最后一秒才把bug改出来。面完就感觉想💩,心想第二轮给我来个boggle game让我绝地反击好不好,蓝后
第二轮 ip2cidr 我做了地里30多道题就是没做这道和那个连socket的。看到这题真的是生无可恋,然后想破罐破摔写吧,结果也是在国人大哥提醒下最后一秒把bug改好了。。。

为什么别人都是round num,schedule meeting,csv parser,order meal我就要经历这些磨难。好了,也不求他家能过了,lz狗带去了,大家面airbnb的同学加油



补充内容 (2016-11-9 04:52):
lz已挂,的确现在水平太差,继续加油吧

评分

11

查看全部评分

Travianfood 发表于 2016-11-12 09:06:05 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
some3411 发表于 2016-11-12 08:34. From 1point 3acres bbs
什么意思呀?比如1->2, 2->1, 3->2这个graph的SCC是{1,2},{3} 但最优解是[3]啊..

写的详细点好了. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
. more info on 1point3acres.com
考虑我们现在有一个有向图,然后我们现在要选某些点使得整个图的所有点都被碰到。
那我们做过了SCC代表了什么?做了SCC代表的其实是一个缩点的动作,今天假如有a, b, c三个点要选,但是我做了SCC之后他们被合并成一个S,那就是说其实a,b,c三个点里面 我只要选一个就好了
那我们做完了SCC之后,我们就得到了一个有向的拓朴图
我们找这些拓朴图里面in-degree=0的就行了。因为in-degree=0代表的就是说,这个点没有人碰的到,你必选。而in-degree > 0的就是说,我前面有人被选过了,至少会有人碰到我,我就能直接满足我缩点后整个集合里面的点,再往下碰这样。


补充内容 (2016-11-12 09:11):
补充一下,可以在杭电找到类似的题目:
http://acm.hdu.edu.cn/showproblem.php?pid=1827

有比过NOI或是NOIP的这应该算是基本题lol 但拿来面试我觉得有点太超过了,毕竟SCC不是一个很直接就能想到的算法
回复 支持 5 反对 0

使用道具 举报

Travianfood 发表于 2016-11-12 07:39:21 | 显示全部楼层
关注一亩三分地微博:
Warald
第一题我没误解的话不是经典题吗?先对整个graph做SCC,然后会得到一个topological graph,然后就直接把根选下去就行啦~
回复 支持 1 反对 0

使用道具 举报

gy21 发表于 2016-11-10 03:03:00 | 显示全部楼层
Jasonyuan 发表于 2016-11-8 18:17. from: 1point3acres.com/bbs
想问下第二题能用类似于拓扑排序做吗,每次找入度最小的点进行dfs。

拓扑排序的前提是有向无环图。。。。。
回复 支持 1 反对 0

使用道具 举报

 楼主| 664077398 发表于 2016-11-8 10:25:48 | 显示全部楼层
illumakou 发表于 2016-11-8 10:10
楼主 能share一下 boggle game的代码吗 跪谢

刚把爹!

import java.util.*;

public class boggleGame {

        public static void main(String[] args) {
                char[][] board = {{'a','b'},{'c','d'},{'a','b'},{'c','d'}};
                String[] dict = {"ab","ac","acd","c","d"};
                System.out.println(boggle(board,dict));
        }
       
        public static ArrayList<String> boggle(char[][] board, String[] dict) {
                ArrayList<String> res = new ArrayList<>();
                Trie trie = new Trie();
                for(String s : dict) trie.insert(s);
                boolean[][] visited = new boolean[board.length][board[0].length];
                ArrayList<String> curRes = new ArrayList<>();
               
                dfs(board,visited,trie,res,curRes,0,0);
               
                return res;
        }
       
        public static void dfs(char[][] board, boolean[][] visited, Trie trie, ArrayList<String> res,
                        ArrayList<String> curRes, int x, int y) {
                int row = board.length, column = board[0].length;
                if(x == row) {
                        if(curRes.size() > res.size()) {
                                res.clear();
                                for(String s : curRes) res.add(s);
                        }
                        return;
                }
               
                ArrayList<String> strs = new ArrayList<>();
                List<ArrayList<Integer>> paths = new ArrayList<>();
               
                dfs2(board,visited,trie,strs,paths,new StringBuilder(),new ArrayList<Integer>(),x,y);
                dfs(board,visited,trie,res,curRes,x+(y+1)/column,(y+1)%column);
                for(int i = 0; i < strs.size(); i++) {
                        curRes.add(strs.get(i));
                        for(int j : paths.get(i)) {
                                visited[j/column][j%column] = true;
                        }
                        trie.delete(strs.get(i));
                       
                        dfs(board,visited,trie,res,curRes,x+(y+1)/column,(y+1)%column);
                       
                        curRes.remove(strs.get(i));
                        for(int j : paths.get(i)) {
                                visited[j/column][j%column] = false;
                        }
                        trie.insert(strs.get(i));
                }
        }
       
        public static void dfs2(char[][] board, boolean[][] visited, Trie trie, ArrayList<String> strs,
                        List<ArrayList<Integer>> paths, StringBuilder curString, ArrayList<Integer> curPath, int x, int y) {
                int row = board.length, column = board[0].length;
                if(x<0 || x>=row || y<0 || y>=column || visited[x][y]) return;
                curString.append(board[x][y]);
                if(!trie.hasPrefix(curString.toString())) {
                        curString.deleteCharAt(curString.length()-1);
                        return;
                }
               
                visited[x][y] = true;
                curPath.add(x*column+y);
                if(trie.hasWord(curString.toString())) {
                        paths.add((ArrayList<Integer>)curPath.clone());
                        strs.add(curString.toString());
                }
               
                dfs2(board,visited,trie,strs,paths,curString,curPath,x+1,y);
                dfs2(board,visited,trie,strs,paths,curString,curPath,x-1,y);
                dfs2(board,visited,trie,strs,paths,curString,curPath,x,y+1);
                dfs2(board,visited,trie,strs,paths,curString,curPath,x,y-1);
               
                curString.deleteCharAt(curString.length()-1);
                visited[x][y] = false;
                curPath.remove(curPath.size()-1);
        }

}

public class Trie {
        public Trie[] next;
        public boolean isWord;
        public Trie() {
                next = new Trie[26];
        }
       
        public void insert(String s) {
                Trie cur = this;
                for(char c : s.toCharArray()) {
                        if(cur.next[c-'a'] == null) cur.next[c-'a'] = new Trie();
                        cur = cur.next[c-'a'];
                }
                cur.isWord = true;
        }
       
        public boolean hasWord(String s) {
                Trie cur = this;
                for(char c : s.toCharArray()) {
                        if(cur.next[c-'a'] == null) return false;
                        cur = cur.next[c-'a'];
                }
                return cur.isWord;
        }
       
        public boolean hasPrefix(String s) {
                Trie cur = this;
                for(char c : s.toCharArray()) {
                        if(cur.next[c-'a'] == null) return false;
                        cur = cur.next[c-'a'];
                }
                return true;
        }
       
        public void delete(String s) {
                Trie cur = this;
                for(char c : s.toCharArray()) {
                        if(cur.next[c-'a'] == null) return;
                        cur = cur.next[c-'a'];
                }
                cur.isWord = false;
        }

}
.鏈枃鍘熷垱鑷1point3acres璁哄潧

评分

2

查看全部评分

回复 支持 1 反对 0

使用道具 举报

梦醒的我 发表于 2016-11-12 00:52:42 | 显示全部楼层
楼主这个代码感觉有点问题,考虑这个情况:1->2->3->1,4->2。最优解应该是[4],如果一开始选了1最后的结果应该会是[1,4]
回复 支持 1 反对 0

使用道具 举报

wtcupup 发表于 2016-11-8 08:34:07 | 显示全部楼层
我的天,楼主是妹子吗?我直接被简历据了
回复 支持 反对

使用道具 举报

 楼主| 664077398 发表于 2016-11-8 08:36:14 | 显示全部楼层
wtcupup 发表于 2016-11-8 08:34
我的天,楼主是妹子吗?我直接被简历据了

我是个boy
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2016-11-8 08:53:49 | 显示全部楼层
楼主第一题啥思路啊。。。好难
回复 支持 反对

使用道具 举报

 楼主| 664077398 发表于 2016-11-8 09:02:26 | 显示全部楼层
小A要当码农 发表于 2016-11-8 08:53
楼主第一题啥思路啊。。。好难
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
把每个还没有visit的点n放到先res里面,然后用dfs,如果dfs过程中碰到了某个点是在res中的,那么从res中删除,表达能力好差。。。大概是这样吧
回复 支持 反对

使用道具 举报

illumakou 发表于 2016-11-8 10:10:29 | 显示全部楼层
楼主 能share一下 boggle game的代码吗 跪谢
回复 支持 反对

使用道具 举报

mdzzxswl 发表于 2016-11-8 10:28:26 | 显示全部楼层
这是实习??实习这么难啊。。。
回复 支持 反对

使用道具 举报

 楼主| 664077398 发表于 2016-11-8 10:29:16 | 显示全部楼层
mdzzxswl 发表于 2016-11-8 10:28. 鍥磋鎴戜滑@1point 3 acres
这是实习??实习这么难啊。。。

他家实习和全职题一样的
回复 支持 反对

使用道具 举报

namelessness 发表于 2016-11-8 10:35:22 | 显示全部楼层
想问一下楼主找的谁内推,能告诉一下吗,各种拿不到面试,伤心。
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2016-11-8 10:59:41 | 显示全部楼层
664077398 发表于 2016-11-8 09:02
把每个还没有visit的点n放到先res里面,然后用dfs,如果dfs过程中碰到了某个点是在res中的,那么从res中 ...

那就是纯暴力解么? 一个个试过去? 把每个点作为candidate这样dfs过去?
回复 支持 反对

使用道具 举报

 楼主| 664077398 发表于 2016-11-8 11:07:24 | 显示全部楼层
小A要当码农 发表于 2016-11-8 10:59 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
那就是纯暴力解么? 一个个试过去? 把每个点作为candidate这样dfs过去?
. visit 1point3acres.com for more.
比如a->b->c,我第一次选了b,然后dfs,bc都visit了,b在res里面,下一次选c,已经visit了不用dfs,再选到a,dfs发现b在res中,然后删去b换a,差不多是这样,当然还有环的情况,你再想想环是怎样运作的
回复 支持 反对

使用道具 举报

 楼主| 664077398 发表于 2016-11-8 11:08:37 | 显示全部楼层
namelessness 发表于 2016-11-8 10:35. 鍥磋鎴戜滑@1point 3 acres
想问一下楼主找的谁内推,能告诉一下吗,各种拿不到面试,伤心。
.1point3acres缃
找的学长,你在地里多问问吧
回复 支持 反对

使用道具 举报

Believers 发表于 2016-11-8 11:12:14 | 显示全部楼层
小A要当码农 发表于 2016-11-8 10:59
那就是纯暴力解么? 一个个试过去? 把每个点作为candidate这样dfs过去?

我觉得不能算暴力解吧,我的理解是,先把所有点放入hashset里,然后随机从set里挑选一个未访问过的点开始做dfs,做完dfs标记visited。对于dfs过程中的每个点,如果还在set中就remove,一直重复,直到set中的点都访问过,剩下的就应该是要保留的。

不知道lz说的是不是这个意思。
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2016-11-8 11:38:24 | 显示全部楼层
Believers 发表于 2016-11-8 11:12
我觉得不能算暴力解吧,我的理解是,先把所有点放入hashset里,然后随机从set里挑选一个未访问过的点开始 ...

但是你这样做没有办法保证是最优解啊。比如楼主给的例子, 你从b开始dfs, 你这样操作的话最后答案就是{b , a}?
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2016-11-8 11:43:29 | 显示全部楼层
664077398 发表于 2016-11-8 11:07
比如a->b->c,我第一次选了b,然后dfs,bc都visit了,b在res里面,下一次选c,已经visit了不用dfs,再选到a ...

懂你的意思了。。我觉得有环应该也没事吧。。这样做也可以啊
回复 支持 反对

使用道具 举报

 楼主| 664077398 发表于 2016-11-8 11:46:51 | 显示全部楼层
小A要当码农 发表于 2016-11-8 11:43
懂你的意思了。。我觉得有环应该也没事吧。。这样做也可以啊

对啊,环是可以的,我就是让你想想环的话是怎么process的。
回复 支持 反对

使用道具 举报

Believers 发表于 2016-11-8 11:56:14 | 显示全部楼层
小A要当码农 发表于 2016-11-8 11:38
但是你这样做没有办法保证是最优解啊。比如楼主给的例子, 你从b开始dfs, 你这样操作的话最后答案就是{b  ...

不是啊,a->b->c,hashset里一开始有a,b,c;从b开始,c被remove;a还没有被visit,所以还需要从a开始做dfs,然后遇到b,b就被remove了。
回复 支持 反对

使用道具 举报

clxy2008 发表于 2016-11-8 12:07:16 | 显示全部楼层
他家最近新题好多啊
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2016-11-8 12:11:13 | 显示全部楼层
Believers 发表于 2016-11-8 11:56
不是啊,a->b->c,hashset里一开始有a,b,c;从b开始,c被remove;a还没有被visit,所以还需要从a开始做df ...

Sorry, my misunderstanding..应该是对的
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-6-26 06:43

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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