1
xuanbg 2020-07-15 16:34:11 +08:00
先查一下目标用户是否存在,存在就不能邀请。
|
2
angryfish 2020-07-15 16:34:21 +08:00
要求过的放进 HashSet ?
|
3
keepeye 2020-07-15 16:38:47 +08:00
检查 A 是否有下级,有下级则不能再被邀请
|
5
xupefei 2020-07-15 16:41:52 +08:00 via iPhone
union-find 算法。
|
6
jtwor 2020-07-15 16:42:13 +08:00
队列 栈
|
7
DJQTDJ 2020-07-15 16:43:05 +08:00
A 邀请 B
FLAG_A:0→1 FLAG_B:0 B 邀请 C FLAG_B:0→1 FLAG_C:0 C 邀请 A FLAG_A:1 所以直接不能邀请 |
8
evill 2020-07-15 16:43:48 +08:00
并查集???猜的
|
9
yousabuk 2020-07-15 16:50:34 +08:00 via iPhone
增加邀请和被邀请的 flag
具有邀请者 flag 不能被邀请。 具有被邀请的 flag 不能被再次邀请。 一次回答 2 个问题,不信他不满意。(第二个问题:如何避免 C 被 A 再次邀请?) |
10
xkeyideal 2020-07-15 16:53:44 +08:00
并查集
|
11
coldmonkeybit 2020-07-15 16:58:21 +08:00
第一反应是栈
|
13
rioshikelong121 2020-07-15 17:05:47 +08:00
双向链表成不成。。这个邀请链条应该不是很长吧。
|
14
yonoho 2020-07-15 17:06:06 +08:00 2
有向无环图?
|
15
framlog 2020-07-15 17:07:27 +08:00
并查集
|
16
newtype0092 2020-07-15 17:08:43 +08:00 3
你这没头没尾的啊。。。
邀请是什么意思,一个人能邀请几次?能被邀请几次?避免 C 去邀请 A 是因为什么规则? |
17
John60676 2020-07-15 17:11:25 +08:00
环形链表?
|
18
hello2060 2020-07-15 17:15:38 +08:00
C 为啥不能邀请 A? 因为 A 邀请了 C? C 能邀请 A 邀请的其他人吗?如果都不能的话就是 UNION FIND, ABC 都有一个共同祖先 A, 只要共同祖先一样就不能邀请?
|
19
lv2016 2020-07-15 17:22:25 +08:00
我还真遇到过比较类似的情况,不过是在数据分析的时候碰到的。目的是为了邀请尽可能的获取高质量的用户而不是被薅羊毛。当时比较辣鸡,用了一个树来记录用户一级级邀请的情况....,判断方法和 9 楼一样
|
20
tcfenix 2020-07-15 17:22:26 +08:00
|
21
tcfenix 2020-07-15 17:25:48 +08:00
https://leetcode.com/problems/linked-list-cycle/description/
啊 是这题 实际上 set 是第一步直觉的处理办法, 然后这边面试官通常应该会加一点限定条件,比如空间复杂度不能是 O(n),再往双指针的方向引导 |
22
lff0305 2020-07-15 17:29:46 +08:00
判断有向图是否存在环路,可以用邻接矩阵,计算传递闭包
|
23
Sapp 2020-07-15 17:30:14 +08:00 5
你的这个问题都不清不楚的,
首先 c 不能邀请 a 是为什么? 因为单独不能邀请 a ?还是不能邀请已经存在的用户?还是不能邀请邀请过别人的用户?还是不能邀请和自己有关联邀请的用户?还是 a 的邀请次数满了? 不同问题显然是不同答案 |
25
xbdsky OP @newtype0092 好吧,A 可以邀请 N 个,现在不最多 3 级吗?手动狗头
|
26
iseki 2020-07-15 17:40:27 +08:00 via Android
这问题能不能再明确点
|
29
newtype0092 2020-07-15 18:02:17 +08:00
@tcfenix #21 这题好奇怪,input 里给的 pos 不就是答案么,为什么还要算?
|
30
Vegetable 2020-07-15 18:13:31 +08:00
奇怪的问题,没头没脑的,不同场景差太多了,如果是邀请加入某个范围,已经加入的人肯定无法被邀请了,A 是第一个加入的,肯定不能被邀请了,比如邀请注册的时候,不能邀请已注册用户,这时候根本不需要判断关系链(相当于所有人都属于一个集合,本质上也是并查集)。
需要判断关系链的邀请场景真滴想不出来,但是并查集的思路起码能解决你提到这个需求,被邀请者打上和邀请者一样的标记,不能邀请相同标记的人就行了,但是这样会同时堵死 A 邀请 C 的情况,除非做更复杂的判断。 |
31
zarte 2020-07-15 18:20:59 +08:00
他们不满意,你可以问面试的呀。解决一个问题即使没过面试也是有意义的。而且还能知道是不是面试的不靠谱。
|
32
tcfenix 2020-07-15 18:35:46 +08:00
@newtype0092
那个例子的输入只是为了方便读者理解题目,实际上入参就是一个 node 而已 |
33
xcstream 2020-07-15 18:40:47 +08:00
父级 id 都记录下来
|
34
westoy 2020-07-15 18:46:13 +08:00 1
这场景应该是针对社交平台病毒式传播用的, 分享得红包一类, 避免被羊毛党开马甲海闭环式刷邀请薅羊毛, 不是针对注册的
|
35
mcfog 2020-07-15 18:59:03 +08:00 via Android
这有啥奇怪的,面试者把问题及相关背景确认清楚的过程(又或者是想当然地直接开始回答)也是面试中很有价值的一环
|
36
zsdroid 2020-07-15 19:23:00 +08:00
理论上不存在 C 去邀请 A 问题,一般应用推广都是邀请新用户得奖励,A 又不是新用户。所以邀请了也白邀请。
|
37
conghuiwang 2020-07-15 19:48:04 +08:00
简单看了下评论,胡言乱语,不懂装懂的人好多
|
39
sjf122 2020-07-15 21:10:15 +08:00
下级的下级不能是自己的上级,不然就成圈了
|
40
sunjiayao 2020-07-15 22:04:13 +08:00
创建闭包表,邀请前先检测下是否已存在关系链。
|
41
liuhuan475 2020-07-16 10:44:42 +08:00
想到了哲学家就餐问题
|
43
elfsundae 2020-07-21 03:59:00 +08:00
PHP 面试?应该不是问算法,是业务设计问题。
邀请注册的话不存在此问题,因为 A 已经是老用户了。 这个问题一般存在于多级分销(代理、师徒等)关系链中,也就是:A 是 B 的师傅,B 是 C 的师傅,如何避免 C 成为 A 的师傅而导致系统混乱。其实只要打破循环就行了,也就是只允许单向链,不允许回流。通用做法是:规定每个人成为师傅前必须先拜师,或者说每个代理都必须有其上家代理。而最源头的 BOSS 是系统号—没有师傅,不参与抽成。 系统号 ... 邀请 A, A 邀请 B,B 邀请 C 。C 邀请 A 时因为 A 已经有师傅了,邀请失败。 这种做法常见于 POS 机代理、互联网应用的拉人模式,伪 chuan 销等等。 |