一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1312|回复: 11
收起左侧

google phone interviw

[复制链接] |试试Instant~ |关注本帖
jeager 发表于 2015-3-24 05:57:41 | 显示全部楼层 |阅读模式

2015(1-3月) 码农类 本科 全职@Google - 网上海投 - 技术电面 |Other

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

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

x
感觉像是一个三哥T T不过人感觉还是不错. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷


给的例子:
Graph g = new Graph();
g.addEdge(“abb”, “cde”);
g.addEdge(“abb”, “ff”);
g.addEdge(“ff”, “abb”);

implement  graph, addEdge,

之后 要求implement 一个cycle detection
. from: 1point3acres.com/bbs
三哥的没有明说的要求是这个graph里的node可以self point,也可以mult point to one node;. 鍥磋鎴戜滑@1point 3 acres
所以cycle detection最好是用recursive 的 DFS. (MD, 这点儿把老子整惨了)

houqingniao 发表于 2015-3-24 08:35:42 | 显示全部楼层
最近这么多图的题。。。.鏈枃鍘熷垱鑷1point3acres璁哄潧

很少练习这些
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
bless 卤煮
回复 支持 反对

使用道具 举报

tyr034 发表于 2015-3-24 09:37:52 | 显示全部楼层
请问 楼主:
g.addEdge(“abb”, “cde”);
这是说在 node abb和  node cde之间加edge?
回复 支持 反对

使用道具 举报

 楼主| jeager 发表于 2015-3-24 10:10:08 | 显示全部楼层
houqingniao 发表于 2015-3-24 08:35
最近这么多图的题。。。

很少练习这些

多练练吧....看还有个实现hashtable的
回复 支持 反对

使用道具 举报

 楼主| jeager 发表于 2015-3-24 10:10:32 | 显示全部楼层
tyr034 发表于 2015-3-24 09:37
请问 楼主:
g.addEdge(“abb”, “cde”);
这是说在 node abb和  node cde之间加edge?
. Waral 鍗氬鏈夋洿澶氭枃绔,
是的 一个是source node 第二个是child node
回复 支持 反对

使用道具 举报

timtam85 发表于 2015-3-27 11:57:30 | 显示全部楼层
楼主能把你的解法分享一下么,谢谢
回复 支持 反对

使用道具 举报

zj45499 发表于 2015-3-27 12:04:36 | 显示全部楼层
g.addEdge(“abb”, “ff”);
g.addEdge(“ff”, “abb”);
这两种有什么区别么? 不是无向图?
回复 支持 反对

使用道具 举报

 楼主| jeager 发表于 2015-3-27 14:09:37 | 显示全部楼层
timtam85 发表于 2015-3-27 11:57.1point3acres缃
楼主能把你的解法分享一下么,谢谢

解法真的没啥好分享的啊 就是最基本的graph啊....
回复 支持 反对

使用道具 举报

 楼主| jeager 发表于 2015-3-27 14:12:19 | 显示全部楼层
zj45499 发表于 2015-3-27 12:04
g.addEdge(“abb”, “ff”);
g.addEdge(“ff”, “abb”);
这两种有什么区别么? 不是无向图?
.鏈枃鍘熷垱鑷1point3acres璁哄潧
就是abb跟ff组成了一个cycle嘛
这个图是有向的

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

say543 发表于 2015-6-9 05:34:15 | 显示全部楼层
self point 的cycle 用BFS 也可以detect阿? 为什么一定要recurisve DFS?
回复 支持 反对

使用道具 举报

ivanzjj 发表于 2015-6-9 19:27:38 | 显示全部楼层
say543 发表于 2015-6-9 05:34
self point 的cycle 用BFS 也可以detect阿? 为什么一定要recurisve DFS?

这要分两种情况讨论:
如果图是无向图,则可以用disjoint-set来detect cycle
如果是有向图,直接topological sort就ok了
回复 支持 反对

使用道具 举报

say543 发表于 2015-6-10 03:20:37 | 显示全部楼层
感谢回应   如果是无向图要特别处理   那如果是有向图因该topological order , BFS,DFS 因该都可以做到?
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

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

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-9 19:59

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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