V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
xbdsky
V2EX  ›  PHP

面试问了一个问题,怎么避免 C 去邀请 A,觉得有点意思?

  •  
  •   xbdsky · 2020-07-15 16:31:06 +08:00 · 5468 次点击
    这是一个创建于 1583 天前的主题,其中的信息可能已经有所发展或是发生改变。
    大神们会怎么处理?
    A 邀请->B 邀请->C
    问怎么避免 C 去邀请 A
    44 条回复    2020-07-23 10:54:30 +08:00
    xuanbg
        1
    xuanbg  
       2020-07-15 16:34:11 +08:00
    先查一下目标用户是否存在,存在就不能邀请。
    angryfish
        2
    angryfish  
       2020-07-15 16:34:21 +08:00
    要求过的放进 HashSet ?
    keepeye
        3
    keepeye  
       2020-07-15 16:38:47 +08:00
    检查 A 是否有下级,有下级则不能再被邀请
    xbdsky
        4
    xbdsky  
    OP
       2020-07-15 16:39:50 +08:00
    @keepeye 我也是这样回答的,貌似面试的人不是很满意 哈哈
    xupefei
        5
    xupefei  
       2020-07-15 16:41:52 +08:00 via iPhone
    union-find 算法。
    jtwor
        6
    jtwor  
       2020-07-15 16:42:13 +08:00
    队列 栈
    DJQTDJ
        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 所以直接不能邀请
    evill
        8
    evill  
       2020-07-15 16:43:48 +08:00
    并查集???猜的
    yousabuk
        9
    yousabuk  
       2020-07-15 16:50:34 +08:00 via iPhone
    增加邀请和被邀请的 flag

    具有邀请者 flag 不能被邀请。
    具有被邀请的 flag 不能被再次邀请。

    一次回答 2 个问题,不信他不满意。(第二个问题:如何避免 C 被 A 再次邀请?)
    xkeyideal
        10
    xkeyideal  
       2020-07-15 16:53:44 +08:00
    并查集
    coldmonkeybit
        11
    coldmonkeybit  
       2020-07-15 16:58:21 +08:00
    第一反应是栈
    xbdsky
        12
    xbdsky  
    OP
       2020-07-15 17:00:50 +08:00
    @yousabuk flag 我也说了,感觉没有什么特别好的办法的
    rioshikelong121
        13
    rioshikelong121  
       2020-07-15 17:05:47 +08:00
    双向链表成不成。。这个邀请链条应该不是很长吧。
    yonoho
        14
    yonoho  
       2020-07-15 17:06:06 +08:00   ❤️ 2
    有向无环图?
    framlog
        15
    framlog  
       2020-07-15 17:07:27 +08:00
    并查集
    newtype0092
        16
    newtype0092  
       2020-07-15 17:08:43 +08:00   ❤️ 3
    你这没头没尾的啊。。。
    邀请是什么意思,一个人能邀请几次?能被邀请几次?避免 C 去邀请 A 是因为什么规则?
    John60676
        17
    John60676  
       2020-07-15 17:11:25 +08:00
    环形链表?
    hello2060
        18
    hello2060  
       2020-07-15 17:15:38 +08:00
    C 为啥不能邀请 A? 因为 A 邀请了 C? C 能邀请 A 邀请的其他人吗?如果都不能的话就是 UNION FIND, ABC 都有一个共同祖先 A, 只要共同祖先一样就不能邀请?
    lv2016
        19
    lv2016  
       2020-07-15 17:22:25 +08:00
    我还真遇到过比较类似的情况,不过是在数据分析的时候碰到的。目的是为了邀请尽可能的获取高质量的用户而不是被薅羊毛。当时比较辣鸡,用了一个树来记录用户一级级邀请的情况....,判断方法和 9 楼一样
    tcfenix
        20
    tcfenix  
       2020-07-15 17:22:26 +08:00
    tcfenix
        21
    tcfenix  
       2020-07-15 17:25:48 +08:00
    https://leetcode.com/problems/linked-list-cycle/description/

    啊 是这题
    实际上 set 是第一步直觉的处理办法,
    然后这边面试官通常应该会加一点限定条件,比如空间复杂度不能是 O(n),再往双指针的方向引导
    lff0305
        22
    lff0305  
       2020-07-15 17:29:46 +08:00
    判断有向图是否存在环路,可以用邻接矩阵,计算传递闭包
    Sapp
        23
    Sapp  
       2020-07-15 17:30:14 +08:00   ❤️ 5
    你的这个问题都不清不楚的,
    首先 c 不能邀请 a 是为什么? 因为单独不能邀请 a ?还是不能邀请已经存在的用户?还是不能邀请邀请过别人的用户?还是不能邀请和自己有关联邀请的用户?还是 a 的邀请次数满了? 不同问题显然是不同答案
    qwertyzzz
        24
    qwertyzzz  
       2020-07-15 17:36:47 +08:00
    @Sapp 一看就是不能成一个环吧
    xbdsky
        25
    xbdsky  
    OP
       2020-07-15 17:37:39 +08:00
    @newtype0092 好吧,A 可以邀请 N 个,现在不最多 3 级吗?手动狗头
    iseki
        26
    iseki  
       2020-07-15 17:40:27 +08:00 via Android
    这问题能不能再明确点
    xbdsky
        27
    xbdsky  
    OP
       2020-07-15 17:41:37 +08:00
    @hello2060
    @Sapp
    就简单的问下这个需求呢,没说太多的东西,估计是想考怎么优化。
    xbdsky
        28
    xbdsky  
    OP
       2020-07-15 17:43:05 +08:00
    @iseki 面试的没说太多条件呢,发现你们这些大神考虑的东西还是很全面的 dog
    newtype0092
        29
    newtype0092  
       2020-07-15 18:02:17 +08:00
    @tcfenix #21 这题好奇怪,input 里给的 pos 不就是答案么,为什么还要算?
    Vegetable
        30
    Vegetable  
       2020-07-15 18:13:31 +08:00
    奇怪的问题,没头没脑的,不同场景差太多了,如果是邀请加入某个范围,已经加入的人肯定无法被邀请了,A 是第一个加入的,肯定不能被邀请了,比如邀请注册的时候,不能邀请已注册用户,这时候根本不需要判断关系链(相当于所有人都属于一个集合,本质上也是并查集)。

    需要判断关系链的邀请场景真滴想不出来,但是并查集的思路起码能解决你提到这个需求,被邀请者打上和邀请者一样的标记,不能邀请相同标记的人就行了,但是这样会同时堵死 A 邀请 C 的情况,除非做更复杂的判断。
    zarte
        31
    zarte  
       2020-07-15 18:20:59 +08:00
    他们不满意,你可以问面试的呀。解决一个问题即使没过面试也是有意义的。而且还能知道是不是面试的不靠谱。
    tcfenix
        32
    tcfenix  
       2020-07-15 18:35:46 +08:00
    @newtype0092
    那个例子的输入只是为了方便读者理解题目,实际上入参就是一个 node 而已
    xcstream
        33
    xcstream  
       2020-07-15 18:40:47 +08:00
    父级 id 都记录下来
    westoy
        34
    westoy  
       2020-07-15 18:46:13 +08:00   ❤️ 1
    这场景应该是针对社交平台病毒式传播用的, 分享得红包一类, 避免被羊毛党开马甲海闭环式刷邀请薅羊毛, 不是针对注册的
    mcfog
        35
    mcfog  
       2020-07-15 18:59:03 +08:00 via Android
    这有啥奇怪的,面试者把问题及相关背景确认清楚的过程(又或者是想当然地直接开始回答)也是面试中很有价值的一环
    zsdroid
        36
    zsdroid  
       2020-07-15 19:23:00 +08:00
    理论上不存在 C 去邀请 A 问题,一般应用推广都是邀请新用户得奖励,A 又不是新用户。所以邀请了也白邀请。
    conghuiwang
        37
    conghuiwang  
       2020-07-15 19:48:04 +08:00
    简单看了下评论,胡言乱语,不懂装懂的人好多
    xl9211
        38
    xl9211  
       2020-07-15 19:53:12 +08:00 via iPhone
    @zsdroid 正解
    sjf122
        39
    sjf122  
       2020-07-15 21:10:15 +08:00
    下级的下级不能是自己的上级,不然就成圈了
    sunjiayao
        40
    sunjiayao  
       2020-07-15 22:04:13 +08:00
    创建闭包表,邀请前先检测下是否已存在关系链。
    liuhuan475
        41
    liuhuan475  
       2020-07-16 10:44:42 +08:00
    想到了哲学家就餐问题
    xbdsky
        42
    xbdsky  
    OP
       2020-07-16 18:44:24 +08:00
    @westoy
    @mcfog
    @zsdroid
    是的,这家做的微信商城系统,里面就有分销奖励的,估计问这个就是考察这个
    elfsundae
        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 销等等。
    xbdsky
        44
    xbdsky  
    OP
       2020-07-23 10:54:30 +08:00
    @elfsundae 是的,你的回答很细致,确实的,可能是我本身表达能力比较欠缺的原因,里面要注意的点我已经说了,估计面试觉得有点乱吧
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1003 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 21:55 · PVG 05:55 · LAX 13:55 · JFK 16:55
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.