Friday, November 27, 2015

找坏球



http://lixinzhang.github.io/jiu-zhang-suan-fa-mian-shi-ti-zong-jie.html
有12个球,1个没有砝码的天秤。其中有11个球的重量是一样的,另外1个是坏球,和其他球的重量不一样,但无法确定是轻了还是重了。请问如何用天秤称3次,就找到坏球并确定是轻了还是重了。(没有砝码的天秤只能比较出两边谁重谁轻或是重量相等,无法求得具体的重量差)

分析

12个球,编号A=(1,2,3,4 )B=(5,6,7,8)C=(9,10,11,12)
分为三组:A, B, C。
  • 先比较A,B,如果A与B平衡,则A,B中均为好球
    • 比较5,6,7与9,10,11
      • 若平衡,则坏球为8或12
        • 比较8与任何一个好球,平衡,坏球为12;不平,坏球为8。
      • 若不平,则目前可以知道是坏的球比好球是重还是轻,假设为重
        • 比较9,10,若平衡,则坏球为12;不平,坏球为重的那个
  • 若A,B不平,则C为好球
    • 比较1,2,5 与 3,4,6(交叉,这玩意面试的时候能想到?
      • 若平衡,则坏球在7,8之间,且之前已经得知轻重的一个关系,再比较一次7,8
      • 若不平衡,或者1,2为坏球,或者5,6为坏球,再比较一次

Labels

Review (572) System Design (334) System Design - Review (198) Java (189) Coding (75) Interview-System Design (65) Interview (63) Book Notes (59) Coding - Review (59) to-do (45) Linux (43) Knowledge (39) Interview-Java (35) Knowledge - Review (32) Database (31) Design Patterns (31) Big Data (29) Product Architecture (28) MultiThread (27) Soft Skills (27) Concurrency (26) Cracking Code Interview (26) Miscs (25) Distributed (24) OOD Design (24) Google (23) Career (22) Interview - Review (21) Java - Code (21) Operating System (21) Interview Q&A (20) System Design - Practice (20) Tips (19) Algorithm (17) Company - Facebook (17) Security (17) How to Ace Interview (16) Brain Teaser (14) Linux - Shell (14) Redis (14) Testing (14) Tools (14) Code Quality (13) Search (13) Spark (13) Spring (13) Company - LinkedIn (12) How to (12) Interview-Database (12) Interview-Operating System (12) Solr (12) Architecture Principles (11) Resource (10) Amazon (9) Cache (9) Git (9) Interview - MultiThread (9) Scalability (9) Trouble Shooting (9) Web Dev (9) Architecture Model (8) Better Programmer (8) Cassandra (8) Company - Uber (8) Java67 (8) Math (8) OO Design principles (8) SOLID (8) Design (7) Interview Corner (7) JVM (7) Java Basics (7) Kafka (7) Mac (7) Machine Learning (7) NoSQL (7) C++ (6) Chrome (6) File System (6) Highscalability (6) How to Better (6) Network (6) Restful (6) CareerCup (5) Code Review (5) Hash (5) How to Interview (5) JDK Source Code (5) JavaScript (5) Leetcode (5) Must Known (5) Python (5)

Popular Posts