一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 6388|回复: 38
收起左侧

Airbnb 新鲜skype

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

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

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

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

x
第一轮,merge intervals,一个白人小哥面的,第二轮是找最少的点遍历整个graph,之前地里有人发过,面试官是个国人妹子。. 1point3acres.com/bbs

求过求过。

评分

3

查看全部评分

本帖被以下淘专辑推荐:

 楼主| Jasonyuan 发表于 2016-12-15 11:20:44 | 显示全部楼层
minibear12 发表于 2016-12-15 11:09
visited2是干嘛的呢?不是很看得懂。
面试官举了什么了反例吗?

visited2确保每次可以遍历这个新加的点可以的到的点。

假设图是  0->1->0, 2->3->2->1,如果你遍历的顺序是1,0,2,3,遍历1的时候只有1,遍历0的时候会把1删了,里面只有0,遍历2的时候,访问不到0,因为到1就结束了。
回复 支持 1 反对 0

使用道具 举报

 楼主| Jasonyuan 发表于 2016-12-13 13:06:26 | 显示全部楼层
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <climits>
#include <cmath>

using namespace std;

void dfs(unordered_set<int>& visited,vector<vector<int>> &edges,unordered_set<int> &result,int num,int start,unordered_set<int> visited2)
{
    if(visited2.find(num) != visited2.end())
        return;
    visited2.insert(num);
    visited.insert(num);
    for(int i = 0;i < edges.size();i++)
    {
        if(edges[0] == num)
        {
            int next = edges[1];
            if(result.find(next) != result.end())
            {
                if(next != start)
                    result.erase(next);
            }
            dfs(visited,edges,result,next,start,visited2);
        }
    }
}
. From 1point 3acres bbs
void traverse(vector<vector<int>>& edges)
{
    unordered_set<int> result,visited,list,visited2;
    for(int i = 0;i < edges.size();i++)
    {
        list.insert(edges[0]);
        list.insert(edges[1]);
    }
   
    for(int num : list)
    {
        if(visited.find(num) == visited.end())
        {
            result.insert(num);
            dfs(visited,edges,result,num,num,visited2);
        }
    }
    for(int num:result)
        cout<<num<<endl;
   
}


. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
/*
0  1  2  3  4  5  6  7  8  9
0[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
1[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
2[0, 0, 0 ,0, 0, 0, 0, 0, 0, 1],
3[0, 0, 0, 1, 0, 1, 0, 1, 0, 0],
4[0, 0, 0, 0, 0, 0 ,0, 0, 1, 0],
5[0, 0, 0, 0, 0, 0, 0, 0, 1, 0],
6[0, 0, 0, 0, 0, 0, 1, 0, 0 ,0],
7[0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
8[0, 0, 0, 0, 0, 0, 0, 1, 0, 0],
9[0, 0, 0, 1, 0, 0, 1, 0, 0, 0]] */


// To execute C++, please define "int main()"
int main() {
    //vector<vector<int>> edges = {{0,1},{1,0},{3,2},{3,1},{2,1}};
    vector<vector<int>> edges = {{2,9},{3,3},{3,5},{3,7},{4,8},{5,8},{6,6},{7,4},{8,7},{9,3},{9,6}};
    traverse(edges);
    return 0;
}

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

 楼主| Jasonyuan 发表于 2016-12-13 13:07:05 | 显示全部楼层
之前好像有人问到。。后来忘了,把代码贴这里了,供参考
回复 支持 1 反对 0

使用道具 举报

八月 发表于 2016-11-22 08:05:55 | 显示全部楼层
都是面经题,楼主应该没问题了
回复 支持 反对

使用道具 举报

 楼主| Jasonyuan 发表于 2016-11-22 08:09:06 | 显示全部楼层
八月 发表于 2016-11-22 08:05
都是面经题,楼主应该没问题了

给dalao递茶 哈哈哈哈
回复 支持 反对

使用道具 举报

wtcupup 发表于 2016-11-22 08:44:10 | 显示全部楼层
找最少的点遍历整个graph 是哪个经典算法啊?
回复 支持 反对

使用道具 举报

 楼主| Jasonyuan 发表于 2016-11-22 09:32:30 | 显示全部楼层
wtcupup 发表于 2016-11-22 08:44
找最少的点遍历整个graph 是哪个经典算法啊?

我是对每个node进行dfs做的,之前地里面那个贴子里有讨论这个。
回复 支持 反对

使用道具 举报

some3411 发表于 2016-11-22 11:37:09 | 显示全部楼层
Jasonyuan 发表于 2016-11-22 09:32
我是对每个node进行dfs做的,之前地里面那个贴子里有讨论这个。

. visit 1point3acres.com for more.楼主能具体说下吗?不需要先把strongly connected component找出来吗
回复 支持 反对

使用道具 举报

jy_121 发表于 2016-11-22 11:54:03 | 显示全部楼层
Jasonyuan 发表于 2016-11-22 09:32
我是对每个node进行dfs做的,之前地里面那个贴子里有讨论这个。

能再说下或给个链接吗?谢谢!
回复 支持 反对

使用道具 举报

han4011 发表于 2016-11-22 13:48:09 | 显示全部楼层
求个链接吧 第二个题 求求求!!
回复 支持 反对

使用道具 举报

peterharrison 发表于 2016-11-22 14:33:27 | 显示全部楼层
求问楼主是海投还是内推?大概投多久有回复?。。。
回复 支持 反对

使用道具 举报

 楼主| Jasonyuan 发表于 2016-11-23 23:47:55 | 显示全部楼层
peterharrison 发表于 2016-11-22 14:33
求问楼主是海投还是内推?大概投多久有回复?。。。

内推,2周
回复 支持 反对

使用道具 举报

 楼主| Jasonyuan 发表于 2016-11-23 23:48:27 | 显示全部楼层
0  1  2  3  4  5  6  7  8  9.1point3acres缃
0[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
1[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
2[0, 0, 0 ,0, 0, 0, 0, 0, 0, 1],
3[0, 0, 0, 1, 0, 1, 0, 1, 0, 0],
4[0, 0, 0, 0, 0, 0 ,0, 0, 1, 0],
5[0, 0, 0, 0, 0, 0, 0, 0, 1, 0],
6[0, 0, 0, 0, 0, 0, 1, 0, 0 ,0],
7[0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
8[0, 0, 0, 0, 0, 0, 0, 1, 0, 0],
9[0, 0, 0, 1, 0, 0, 1, 0, 0, 0]]

这是当时的一个test case,找最少的点遍历所有点,结果是0,1,2.
回复 支持 反对

使用道具 举报

goodluck888 发表于 2016-11-24 01:48:31 | 显示全部楼层
请问第二题的做法是要先找strongly connected component吗?
如果有环,dfs怎么做呢?谢谢楼主!!
回复 支持 反对

使用道具 举报

 楼主| Jasonyuan 发表于 2016-11-24 05:14:38 | 显示全部楼层
goodluck888 发表于 2016-11-24 01:48. From 1point 3acres bbs
请问第二题的做法是要先找strongly connected component吗?
如果有环,dfs怎么做呢?谢谢楼主!!
. 鍥磋鎴戜滑@1point 3 acres
我没找scc,用dfs遇到visited就return就好啦
回复 支持 反对

使用道具 举报

runningMajia 发表于 2016-11-24 07:11:40 | 显示全部楼层
Jasonyuan 发表于 2016-11-23 23:48
0  1  2  3  4  5  6  7  8  9
0[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
1[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
这个testcase的为什么是0,1,谢谢!2呢?楼主有原来题目的链接吗?xie'x
回复 支持 反对

使用道具 举报

 楼主| Jasonyuan 发表于 2016-11-24 12:48:07 | 显示全部楼层
runningMajia 发表于 2016-11-24 07:11
这个testcase的为什么是0,1,谢谢!2呢?楼主有原来题目的链接吗?xie'x

0,1,2呀。我找不到原来的链接啦,没有存
回复 支持 反对

使用道具 举报

期末求过 发表于 2016-11-25 04:22:54 | 显示全部楼层
楼主能不能把代码发一个,我看之前有个暴力的n次dfs的代码,求问你也是那样做的吗
回复 支持 反对

使用道具 举报

goodluck888 发表于 2016-11-27 01:14:16 | 显示全部楼层
Jasonyuan 发表于 2016-11-24 05:14
我没找scc,用dfs遇到visited就return就好啦

请问一下,如果是 1->2->3->1, 2->4这样的例子。答案是2。用dfs怎么找到2呢?谢谢楼主
回复 支持 反对

使用道具 举报

jy_121 发表于 2016-12-13 21:52:38 | 显示全部楼层
goodluck888 发表于 2016-11-27 01:14
请问一下,如果是 1->2->3->1, 2->4这样的例子。答案是2。用dfs怎么找到2呢?谢谢楼主

问下这个例子选1的话不也是可以的吗?谢谢
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-12-14 02:45

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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