SWE · Stage 1 Brain Teaser

Oracle 三袋硬币标签全错:只抽一枚如何重贴

从混合标签袋入手,用全部标签都错误的约束推断纯金币、纯银币与混合袋。

题目重点:从混合标签袋入手,用全部标签都错误的约束推断纯金币、纯银币与混合袋。

题意与假设

这道练习题保留了面经中值得训练的核心约束,并将需要澄清的条件单独列出。现场拿到变体时,先和面试官确认这些条件。

  • 标为混合的袋子不可能真混合,因为每个标签都贴错;纯金袋只含金币、纯银袋只含银币,混合袋至少两种币都有。
  • 只抽一次,抽取过程不改变袋子的类别;三个真实类别各恰好对应一个袋子。

解题路线

  1. 唯一有保证的信息入口是标为混合的袋子:它真实必为纯金或纯银,所以抽出的币直接确定整袋真实类别。
  2. 若抽到金币,该袋是真金;剩余标签金与银的袋子中,标金的不能真金,而真金已用,因此标金袋只能真混合,标银袋真银。
  3. 若抽到银币,对称地标混合袋真银;标银袋不能真银且真银已用,因此标银袋真混合,标金袋真金。
  4. 从标金或标银袋取币不保证成功,因为这些袋子可能是混合袋,抽到单枚不能总是区分其真实类别。

手动走一遍

标记 [金,银,混合] 的三个袋子,抽标混合袋得到银币,则真实类别依次为 [金,混合,银];检查三袋标签均与真实类别不同。

规模与取舍

只做一次抽样和常数次逻辑推导,时间 O(1)、额外空间 O(1);关键不是计算量,而是选择能让单次观察具有确定性的袋子。

易错点与追问

容易失分的边界

  • 从标金袋抽到金就认定它为纯金,违反标签全错前提。
  • 认为标混合袋仍有概率混合,忽略所有标签均错误。
  • 只推断抽样袋的类别,不检查剩余两袋唯一对应关系。

继续深挖

  • 若只保证恰有两个标签错误,单次抽样是否仍足够?
  • 若混合袋的抽样可被对抗性选择,为什么本方案仍有效?
✓已复制微信号!