一亩三分地论坛

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

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

狗家电面 一道没见过的图题

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

2016(10-12月) 码农类 硕士 全职@Google - 内推 - 技术电面 |Fail在职跳槽

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

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

x
不久前湾区来的天竺哥的电话,口音特别重交流挺痛苦的直接上题: 给一组objects, 每个对象2个属性分别是id和父id。要求给这组objects排序保证所有父id都排在id的前面,如. From 1point 3acres bbs
给的是:1->10, 2->20, 3->30, 10->200, 20->100
排好应该得到:3->30, 10->200, 20->100, 1->10, 2->20
因为10是1的父id,所以10->200一定要在1->10的前面,如果没有父id关系的话就按id排就好了
函数是. visit 1point3acres.com for more.
List<Object> sortObject(List<Object> objects){}
. Waral 鍗氬鏈夋洿澶氭枃绔,

另外父id一定比id大且给的数组元素不重复

lz当时第一反应就是感觉这是图的题,但是往托普排序上想方向错了,天竺哥也一直憋着,我说了大概托普排序的思路就让我实现,完了再拿出各种case告诉我是错的,还有XXXX没排对。
lz后面发现这题可以用并查集+mergesort解。哎,看来还是要多多修炼。希望有大神有更好的解法

评分

2

查看全部评分

本帖被以下淘专辑推荐:

elizabethxiazhi 发表于 2016-11-9 02:59:43 | 显示全部楼层
求问LZ拓扑排序为啥不行, 小哥给了什么&#127792;
回复 支持 反对

使用道具 举报

 楼主| homlyee 发表于 2016-11-9 03:12:38 | 显示全部楼层
elizabethxiazhi 发表于 2016-11-9 02:59
求问LZ拓扑排序为啥不行, 小哥给了什么&#127792;

我可能没说清楚,我直接用的托普排序不行,但思路是那个思路,各个非连通图之间加个merge sort就行了
回复 支持 反对

使用道具 举报

SiyaoZhu 发表于 2016-11-9 03:14:45 | 显示全部楼层
请问楼主 可否直接 collections.sort? 然后比较两两对之间 如果第一个的父id是第二个的id 返回-1 如果不是,就直接比较id?
回复 支持 反对

使用道具 举报

 楼主| homlyee 发表于 2016-11-9 03:31:40 | 显示全部楼层
SiyaoZhu 发表于 2016-11-9 03:14
请问楼主 可否直接 collections.sort? 然后比较两两对之间 如果第一个的父id是第二个的id 返回-1 如果不是 ...
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
不行,想想这种情况:
1->10, 100->1000, 10->100
回复 支持 反对

使用道具 举报

WhatsFLAG 发表于 2016-11-9 03:34:17 | 显示全部楼层
用minheap+拓扑排序来做不行吗?
回复 支持 反对

使用道具 举报

123呆板彻底 发表于 2016-11-9 03:39:04 | 显示全部楼层
直接拓扑排序为啥不行?
回复 支持 反对

使用道具 举报

 楼主| homlyee 发表于 2016-11-9 03:58:15 | 显示全部楼层
无论用拓扑还是unionfind,只要保证各个图是一层层按顺序输出就行。
回复 支持 反对

使用道具 举报

huai10 发表于 2016-11-9 04:22:45 | 显示全部楼层
  1. vector<pair<int,int> > toposort(vector<pair<int,int> > &input){
  2.   unordered_map<int,vector<int> > graph;
  3.   unordered_map<int,int> in;. From 1point 3acres bbs
  4.   vector<pair<int,int> > res;
    . 1point 3acres 璁哄潧
  5.   for(auto &p : input){
  6.     graph[p.second].push_back(p.first);
  7.     if(in.find(p.first) == in.end())  in[p.first] = 0;
  8.     if(in.find(p.second) == in.end())  in[p.second] = 0;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  9.     in[p.first] ++;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  10.   }
  11.   queue<int> q;
  12.   for(auto p : in){
  13.     if(p.second == 0) q.push(p.first);
  14.   }

  15.   while(!q.empty()){. from: 1point3acres.com/bbs
  16.     int node = q.front();
  17.     q.pop();

  18.     for(auto &neighbor : graph[node]){
  19.       res.push_back(make_pair(neighbor, node));
  20.       if(--in[neighbor] == 0)
    . from: 1point3acres.com/bbs
  21.         q.push(neighbor);
  22.     }
  23.   }
  24.   //assume no circle
  25.   return res;
  26. }
复制代码
. 1point 3acres 璁哄潧

不晓得这样可以么
回复 支持 反对

使用道具 举报

何打发123 发表于 2016-11-9 05:00:20 | 显示全部楼层
homlyee 发表于 2016-11-9 03:58
无论用拓扑还是unionfind,只要保证各个图是一层层按顺序输出就行。

感谢楼主的分享 ! 图是一层层按顺序输出就行 这个要求就是典型的拓扑排序了呀0.0.。。请问您当时候做的时候 是拓扑排序什么地方没考虑到? 我觉得就是最直接的拓扑排序0.0 不知道是不是理解错了。。
回复 支持 反对

使用道具 举报

 楼主| homlyee 发表于 2016-11-9 05:41:58 | 显示全部楼层
huai10 发表于 2016-11-9 04:22
不晓得这样可以么
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
你跟我犯了一样的问题,前面没问题,后面往res里放的时候,需要每次放入的是所有图里当前最父节点的最小值。 所以需要你去比较当前所有ingree为0的节点的id,找到最小的放入答案,然后最小的那个图再继续往下走,继续比较。ls说的minheap是个好方法来实现这个
回复 支持 反对

使用道具 举报

何打发123 发表于 2016-11-9 06:02:38 | 显示全部楼层
homlyee 发表于 2016-11-9 05:41
你跟我犯了一样的问题,前面没问题,后面往res里放的时候,需要每次放入的是所有图里当前最父节点的最小 ...

哦哦! 如果没有父id关系的话就按id排就好了  这句话的意思是 同一个level的点要按照大小来的意思呀! 感谢分享~~~
回复 支持 反对

使用道具 举报

huai10 发表于 2016-11-9 06:20:41 | 显示全部楼层
homlyee 发表于 2016-11-9 05:41
你跟我犯了一样的问题,前面没问题,后面往res里放的时候,需要每次放入的是所有图里当前最父节点的最小 ...

给的是:1->10, 2->20, 3->30, 10->200, 20->100.鏈枃鍘熷垱鑷1point3acres璁哄潧
排好应该得到:3->30, 10->200, 20->100, 1->10, 2->20

所以上面这个例子: 10->200, 20->100, 3->30, 1->10, 2->20, 这样就不行了么, 因为3->30 应该不和其他点connect, 如果不行的话,那的确是要加一个heap
回复 支持 反对

使用道具 举报

 楼主| homlyee 发表于 2016-11-9 07:04:30 | 显示全部楼层
huai10 发表于 2016-11-9 06:20
鏉ユ簮涓浜.涓夊垎鍦拌鍧. 给的是:1->10, 2->20, 3->30, 10->200, 20->100
排好应该得到:3->30, 10->200, 20->100, 1->10, 2->20 ...

嗯,不行,各个图之间的点是要做比较的
回复 支持 反对

使用道具 举报

Sorrow雨 发表于 2016-11-9 08:19:01 | 显示全部楼层
lz想问一下,是否保证一层id的值一定比下一层的id值大?我的意思是30 100 200是最上面一层,12 20 3 是第二层。。如果不是的话minheap里面得放pair按照层数从小到大排? 谢谢了。
回复 支持 反对

使用道具 举报

gmixy 发表于 2016-11-11 06:36:21 | 显示全部楼层
楼主 3-》30为什么在所有组合的第一位?
唯一的原因,难道是因为input给的顺序里,3->30在10和20前面? 感觉楼主你这个题目还没理解啊
回复 支持 反对

使用道具 举报

Sorrow雨 发表于 2016-11-11 23:34:51 | 显示全部楼层
WhatsFLAG 发表于 2016-11-9 03:34
用minheap+拓扑排序来做不行吗?

厉害了word哥
回复 支持 反对

使用道具 举报

小A要当码农 发表于 4 小时前 | 显示全部楼层
WhatsFLAG 发表于 2016-11-9 03:34
用minheap+拓扑排序来做不行吗?

MinHeap+拓扑排序 也还是要用BFS+degree的方法吧? 只不过这个用一个PriorityQueue来取代Queue?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-3 08:30

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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