• 技术文章 >后端开发 >php教程

    面试有关问题:给你一个文本文件,里面存储了一亿个QQ号,请用程序将其由小到大排序,汗呀!

    2016-06-13 13:47:16原创656

    面试问题:给你一个文本文件,里面存储了一亿个QQ号,请用程序将其由小到大排序,汗呀!..
    面试问题:给你一个文本文件,里面存储了一亿个QQ号,请用程序将其由小到大排序,汗呀!..
    求高手讲解思路!
    还有其它问题:
    比如Memcache的运行机制,它的工作原理它有什么优缺点!
    现有一个库存100件的产品要进行秒杀,在秒杀过程中的秒杀人数远远超过库存,请问你将如何处理,应该注意什么问题!
    请谈谈你对Mysql的优化的见解,或者说如果让你设计一个数据库,你将怎样设计并优化!
    有高手吗,今天面试都自己认为都答得不太理想,求指教,还有下面的面试!
    小弟的刚刚被裁员,本来就冬天,真的好冷啊!


    ------解决方案--------------------
    排序的问题想不出来什么好办法,有没有更具体的限制条件,比如运行时间和内存?
    如果都不限制直接sort函数就行,里面是用的快速排序法(quicksort),理论上的效率应该是最高的,况且人家是native code,怎么也比php代码里模拟一个排序算法快。

    memcache的运行机制是使用职守进程开辟一块内存空间用来保存key/value数据,所有的请求和应用都共用这些数据。优点是存取速度快,适合用来缓存频繁读写的数据。缺点是占用内存,同时只能通过key检索,无法进行关系查询(SQL等)。

    要保证原子操作,使用一定的锁机制防止多个请求同时操作一个数据造成效果与预期不符。

    mysql数据库优化主要是索引和分表,为了性能可以为所有需要排序和检索的字段建立索引,并通过水平或垂直分表方式提高效率。
    ------解决方案--------------------
    目的肯定不是让你投机,导入数据库,建索引导出,不过可以提一下


    遍历一遍,将号码按大小,写入合适的文件。。。比如约定10万一个号码段

    比如10,000,写在第0个文件,100,000,001,属于第1K个文件里面

    排序每一个文件数据,拼接文件

    排序的时候,如果文件较大,这里根据文件大小,大概能估计号码数量级的。。如果号码量少,可选择快排,否则,

    创建一个10万的数组,再次遍历,arr[qqnum-i*100000]+1;

    遍历数组,依数组值,增量写入号码即可

    复杂度是O(n),O(nlogn)之间
    ------解决方案--------------------
    这面试题有点眼熟啊,算法板块貌似讨论过,所以我回答用bitmap,空间换时间。
    而且实际要做可能需要分段处理,比如5-7位的qq直接bit hash,7-10位的bit hash值 + 1000000
    PHP code
    ";                                                                                                                
            $i++;
    }
    ?>
    
    ------解决方案--------------------
    探讨

    这面试题有点眼熟啊,算法板块貌似讨论过,所以我回答用bitmap,空间换时间。
    而且实际要做可能需要分段处理,比如5-7位的qq直接bit hash,7-10位的bit hash值 + 1000000
    PHP code
    set_time_limit(0);
    //5-7位qq
    $s = '0';
    $s{9999999} = 1;
    $s{22334} = 1;
    ……

    ------解决方案--------------------
    探讨

    跟编程珠玑里面的排序电话号码道理应该是一样的.1亿个qq号,就需要一亿个位,大概是11MB

    声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn核实处理。

    相关文章推荐

    • 分享PHP函数使用小工具(附代码示例)• PHP安全编码总结(经验分享)• 非常全面!PHP常见漏洞代码总结!• 一文详解PHP实现职责链设计模式(附代码示例)• php实现通过JSON RPC与go通讯(附代码)
    1/1

    PHP中文网