这是一个创建于 1626 天前的主题，其中的信息可能已经有所发展或是发生改变。
大神们会怎么处理？
A 邀请->B 邀请->C
问怎么避免 C 去邀请 A
A 邀请->B 邀请->C
问怎么避免 C 去邀请 A
 |
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：０→１ FLAG_B：０ B 邀请 C FLAG_B：０→１ FLAG_C：０ 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 销等等。 |
Select Language