新书推介：《语义网技术体系》
作者：瞿裕忠，胡伟，程龚
   XML论坛     W3CHINA.ORG讨论区     计算机科学论坛     SOAChina论坛     Blog     开放翻译计划     新浪微博  
 
  • 首页
  • 登录
  • 注册
  • 软件下载
  • 资料下载
  • 核心成员
  • 帮助
    		•   Add to Google

    >> 本版讨论高级C/C++编程、代码重构(Refactoring)、极限编程(XP)、泛型编程等话题
    [返回] 计算机科学论坛 → 计算机技术与应用 → 『 C/C++编程思想 』 → google面试题[讨论] ◇查看新帖 ◇ 用户列表 ◇

      发表一个新主题  发表一个新投票  回复主题  (订阅本版) 您是本帖的第 55167 个阅读者浏览上一篇主题  刷新本主题   树形显示贴子　浏览下一篇主题
     * 贴子主题： google面试题[讨论] 举报  打印  推荐  IE收藏夹 
       本主题类别:     
     firstway 帅哥哟，离线，有人找我吗？
      
      
      威望：5
      等级：大三暑假(2个月背完了红宝书)(版主)
      文章：92
      积分：947
      门派：Lilybbs.net
      注册：2005/10/31

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给firstway发送一个短消息 把firstway加入好友 查看firstway的个人资料 搜索firstway在『 C/C++编程思想 』的所有贴子 引用回复这个贴子 回复这个贴子 查看firstway的博客楼主
    发贴心情 google面试题[讨论]

    有n个人，其中超过半数是好人，剩下的是坏人
    好人只说真话，坏人可能说真话也可能说假话
    这n个人互相都知道对方是好人还是坏人

    现在要你从这n个人当中找出一个好人来，只能通过以下方式：
    每次挑出两个人，让这两个人互相说出对方的身份，
    你根具两个人的话进行判断。

    问通过何种方法才能最快的找出一个好人来,
    (要考虑最坏的情况)


       收藏   分享  
    顶(0)
      




    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2005/12/3 13:55:00
     
     firstway 帅哥哟，离线，有人找我吗？
      
      
      威望：5
      等级：大三暑假(2个月背完了红宝书)(版主)
      文章：92
      积分：947
      门派：Lilybbs.net
      注册：2005/10/31

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给firstway发送一个短消息 把firstway加入好友 查看firstway的个人资料 搜索firstway在『 C/C++编程思想 』的所有贴子 引用回复这个贴子 回复这个贴子 查看firstway的博客第2楼
    发贴心情 
    我现在提一个想法，望大家指正
    －－－－－－－－－－－－－－－－－－－－－－－－－
    先找一个人A，然后其他所有人评价A
    1如果半数说A是好人：A是好人
    2如果半数以上说A是坏人：A是坏人
    －－－－－
    如果A是坏人
    去掉说A是好人的人（一定是坏人）
    在剩下的人里找一个人重复上面的（这里好人肯定更多于一半）
    －－－
    递归进行
    最坏情况就是坏人都说实，话且每次运气不好都选出的是坏人
    这时复杂度是O(n平方)
    实际计算时选出好人的几率越来越高的，因为坏人不断的被去掉
    －－－
    大家有何高见》？
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2005/12/3 15:39:00
     
     enorm 帅哥哟，离线，有人找我吗？
      
      
      威望：4
      头衔：头衔
      等级：大三暑假(参加全国数模竞赛拿了一等奖)(版主)
      文章：144
      积分：854
      门派：Lilybbs.net
      注册：2005/12/1

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给enorm发送一个短消息 把enorm加入好友 查看enorm的个人资料 搜索enorm在『 C/C++编程思想 』的所有贴子 引用回复这个贴子 回复这个贴子 查看enorm的博客第3楼
    发贴心情 
    最坏的情况时所有坏人都被选出，前所有坏人说真话，这时才选出好人，最坏情况o(n^2)
    最好情况o(n)

    ----------------------------------------------
    天亮了

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2005/12/3 17:19:00
     
     来去如风 帅哥哟，离线，有人找我吗？
      
      
      等级：大一新生
      文章：0
      积分：54
      门派：XML.ORG.CN
      注册：2006/4/23

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给来去如风发送一个短消息 把来去如风加入好友 查看来去如风的个人资料 搜索来去如风在『 C/C++编程思想 』的所有贴子 引用回复这个贴子 回复这个贴子 查看来去如风的博客第4楼
    发贴心情 google面试题-------我的解法
    路过看了楼主的算法,觉得无法接受,应该是最慢的一个算法,下面是我的想法:
    思想是尽量多的排除坏人:
    1,如果两个人都说对方是好人,那么有两种可能,要吗都是好人,要吗都是坏人.
    2,如果有一个人说对方是坏人,那么两人种至少有一个坏人,可以同时排除,剩下的人照样满足条件好人站半树以上,再在剩下的人中找好人
       int    people[] = {0,1,1,1,1,0,0,0,1};//N个人的数组1是好人,0是坏人
        int    samePos = -1, sameNum = -1;
        while(i < N - 1)
        {
            if(samePos  != -1)
            {
                if(第samePos个人和第i个人都说对方是好人)
                {
                  i++;
                  sameNum++;
                  if(sameNum > N/2)//超过一半，肯定都是好人
                  {
                   return people[samePos];
                  }

                }
                else
                {
                    sameNum--;
                    i++;
                    if(sameNum == 0)
                    {
                       samePos = -1;
                    }
        
               }
                    continue;  
            }
            
            if(第i个人和第i + 1个人都说对方是好人)
            {
               
                   samePos = i;
                   sameNum = 2;
            }
           else
           {
               i += 2;
           }
       }

        最后要吗剩下一个好人,要吗剩下一串好人,复杂度为o(n) ,最快n/2,最慢n.写的不太严密,请大家指正.

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/4/23 17:05:00
     
     天涯客 美女呀，离线，快来找我吧！
      
      
      等级：大一新生
      文章：0
      积分：54
      门派：XML.ORG.CN
      注册：2006/7/3

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给天涯客发送一个短消息 把天涯客加入好友 查看天涯客的个人资料 搜索天涯客在『 C/C++编程思想 』的所有贴子 引用回复这个贴子 回复这个贴子 查看天涯客的博客第5楼
    发贴心情 
    我的想法,前提：被选出的人可以被一直重复选出；
    :如果N为偶数,所以至少有N/2个好人，取整  |好人-坏人|>=1(实际N为偶数的时候:
    |好人-坏人|>=2 );好人肯定说真话,保证了结论的正确性 >=50%,
    任选A,所有人评A,比较结论,评出的结果，X:好人，Y:坏人，A=X>Y?好人:坏人;
    :同样的道理，N为奇数,有一样的结果。存在边界的情况：好人比坏人只多一人，X==Y；说明A为好人人。因为就算坏人都说假话，起码也有一半的真话。
    所以整个算法的复杂度为 0(N).
    请各位赐教!
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/7/3 23:54:00
     
     DavidPotter 帅哥哟，离线，有人找我吗？
      
      
      等级：大三暑假(ITELS考了6.5分!)
      文章：150
      积分：852
      门派：Lilybbs.net
      注册：2006/3/7

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给DavidPotter发送一个短消息 把DavidPotter加入好友 查看DavidPotter的个人资料 搜索DavidPotter在『 C/C++编程思想 』的所有贴子 点击这里发送电邮给DavidPotter 引用回复这个贴子 回复这个贴子 查看DavidPotter的博客第6楼
    发贴心情 
    l来去如风的思路不错：与查找众数的方法一样，通过不断的除去坏人与好人来利用好人超过半数的条件：如果有一个人说对方是坏人,那么两人种至少有一个坏人,可以同时排除,剩下的人照样满足条件好人站半树以上,再在剩下的人中找好人。

    楼上（天涯客）的可能没有看清楚要找出好人的要求。如果A是外人的话，那么你的评选还要继续下去。

    ----------------------------------------------
    Don‘t try so hard, the best things come when you least expect them to.

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/7/4 16:18:00
     
     gln 帅哥哟，离线，有人找我吗？
      
      
      等级：大一新生
      文章：6
      积分：87
      门派：IEEE.ORG.CN
      注册：2006/7/20

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给gln发送一个短消息 把gln加入好友 查看gln的个人资料 搜索gln在『 C/C++编程思想 』的所有贴子 引用回复这个贴子 回复这个贴子 查看gln的博客第7楼
    发贴心情 
    照来去如风的思路:如果两个人都说对方是好人,那么有两种可能,要吗都是好人,要吗都是坏人.
    在此基础上,可以把这些人分为两组,A和B;
    a是A组的,a和x都说对方是好人,把x加到A组,否则加到B组,,哪一组的人数先过半数了,这组就是好人,另外一组就是坏人了.
    时间复杂度o(n),最快n/2,最慢n..

    ----------------------------------------------
    每天进步一点点!

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/7/23 20:55:00
     
     cschentao 帅哥哟，离线，有人找我吗？
      
      
      等级：大一新生
      文章：0
      积分：55
      门派：XML.ORG.CN
      注册：2006/8/8

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给cschentao发送一个短消息 把cschentao加入好友 查看cschentao的个人资料 搜索cschentao在『 C/C++编程思想 』的所有贴子 引用回复这个贴子 回复这个贴子 查看cschentao的博客第8楼
    发贴心情 
    其实firstwai几乎谈到重点了，来去如风的分析有问题。。明天得闲写下，哈哈
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/8/8 21:33:00
     
     yooga 帅哥哟，离线，有人找我吗？
      
      
      等级：大一新生
      文章：0
      积分：54
      门派：XML.ORG.CN
      注册：2007/7/23

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给yooga发送一个短消息 把yooga加入好友 查看yooga的个人资料 搜索yooga在『 C/C++编程思想 』的所有贴子 引用回复这个贴子 回复这个贴子 查看yooga的博客第9楼
    发贴心情 [原创]
    最慢是[n/2] + 1
    最快是[n/2]
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2007/7/23 16:33:00
     
     chenminyi 帅哥哟，离线，有人找我吗？狮子座1984-7-28
      
      
      等级：大三(要不要学学XML呢?)
      文章：69
      积分：555
      门派：XML.ORG.CN
      注册：2006/7/20

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给chenminyi发送一个短消息 把chenminyi加入好友 查看chenminyi的个人资料 搜索chenminyi在『 C/C++编程思想 』的所有贴子 引用回复这个贴子 回复这个贴子 查看chenminyi的博客第10楼
    发贴心情 
    这个好像就是算法导论上的课后习题，当时就没做出来。
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2007/8/27 9:59:00
     
     GoogleAdSense狮子座1984-7-28
      
      
      等级：大一新生
      文章：1
      积分：50
      门派：无门无派
      院校：未填写
      注册：2007-01-01
    给Google AdSense发送一个短消息 把Google AdSense加入好友 查看Google AdSense的个人资料 搜索Google AdSense在『 C/C++编程思想 』的所有贴子 访问Google AdSense的主页 引用回复这个贴子 回复这个贴子 查看Google AdSense的博客广告
    2025/7/20 7:19:12

    本主题贴数21，分页： [1] [2] [3]

    管理选项： 修改tag | 锁定 | 解锁 | 提升 | 删除 | 移动 | 固顶 | 总固顶 | 奖励 | 惩罚 | 发布公告
    W3C Contributing Supporter! W 3 C h i n a ( since 2003 ) 旗 下 站 点
    苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》
    		 123.047ms