May 2009 - May 2017 论坛八周年-你的足迹,我的骄傲


一亩三分地论坛

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

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

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

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

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

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

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

x
不久前湾区来的天竺哥的电话,口音特别重交流挺痛苦的直接上题: 给一组objects, 每个对象2个属性分别是id和父id。要求给这组objects排序保证所有父id都排在id的前面,如
给的是: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排就好了
函数是
List<Object> sortObject(List<Object> objects){}
.鐣欏璁哄潧-涓浜-涓夊垎鍦

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

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

评分

2

查看全部评分

本帖被以下淘专辑推荐:

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

使用道具 举报

 楼主| homlyee 发表于 2016-11-9 03:12:38 | 显示全部楼层
关注一亩三分地微博:
Warald
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;
  4.   vector<pair<int,int> > res;
  5.   for(auto &p : input){. 鍥磋鎴戜滑@1point 3 acres
  6.     graph[p.second].push_back(p.first);-google 1point3acres
  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] ++;
  10.   }
    . Waral 鍗氬鏈夋洿澶氭枃绔,
  11.   queue<int> q;
  12.   for(auto p : in){
  13.     if(p.second == 0) q.push(p.first);
  14.   }

  15.   while(!q.empty()){
  16.     int node = q.front();
  17.     q.pop();
  18. . from: 1point3acres.com/bbs
  19.     for(auto &neighbor : graph[node]){
  20.       res.push_back(make_pair(neighbor, node));
  21.       if(--in[neighbor] == 0)
  22.         q.push(neighbor);
  23.     }
  24.   }
  25.   //assume no circle
  26.   return res;
  27. }
复制代码

. visit 1point3acres.com for more.
不晓得这样可以么
回复 支持 反对

使用道具 举报

何打发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
排好应该得到:3->30, 10->200, 20->100, 1->10, 2->20
. Waral 鍗氬鏈夋洿澶氭枃绔,
所以上面这个例子: 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要当码农 发表于 2016-12-3 04:09:39 | 显示全部楼层
WhatsFLAG 发表于 2016-11-9 03:34
用minheap+拓扑排序来做不行吗?

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

使用道具 举报

chaosMonkey 发表于 2016-12-11 16:58:26 | 显示全部楼层
小A要当码农 发表于 2016-12-3 04:09.1point3acres缃
MinHeap+拓扑排序 也还是要用BFS+degree的方法吧? 只不过这个用一个PriorityQueue来取代Queue?

我觉得应该是这么做,利用priority_queue代替queue,而且取出一个点不能像上面程序那样马上把下一层的点放入到priority_queue中,而是先用一个set把下一层的点先保存下来,当前层所有点输出后,再把下一层的点放入到堆中,否则下一层的点参与到当前层的点的排序,有可能会发生错误。
回复 支持 反对

使用道具 举报

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

请问lz 如果按照你的说的 最终输出结果中,相同层需要按照当前id从小到大排的话,不应该比较的是入度为0的点的大小吧,比如3->30, 10->200, 20->100,中将10->200改为10->15,这样的一开始30, 15,100的入度都为零,也就是所谓的父节点对吧,如果按照他们从小到大排序输出的话应该是10->15,3->30, 20->100,这样的话当前节点id就不是按照顺序了。
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-5-25 21:45

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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