腾讯2014软件开发笔试题目

腾讯2014软件开发笔试题目

-----9月21日，腾讯2014软件开发校招-简答题-广州

简答题：

1、请设计一个排队系统，能够让每个进入队伍的用户都能看到自己在 中所处的位置和变化。队伍可能随时有人加入和退出，当有人退出影响到用户的位置排名时需要即时反馈到用户。

2、A、B两个整数集合，设计一个算法求他们的交集，尽可能的高效。

（博主能力有限，不是所有题目都会求解，第1题不是我的擅长，这里贴出来让大家知道腾讯的考题。我的重点放在第2题上面！）

第2题 题解（个人见解，仅供参考！）

思路1：排序法

　　对集合A和集合B进行排序（升序，用快排，平均复杂度O(N*logN)），设置两个指针p和q，同时指向集合A和集合B的最小值，不相等的话移动*p和*q中较小值的指针，相等的话同时移动指针p和q，并且记下相等的数字，为交集的元素之一，依次操作，直到其中一个集合没有元素可比较为止。

　　优点：操作简单，容易实现。

　　缺点：使用的排序算法不当，会耗费大量的时间，比如对排好序的集合使用快排， 时间复杂度是O(N2)

　　这种算法是大家都能比较快速想到的办法，绝大多数时间放在了对集合的排序上，快排的平均复杂度是O(N*logN)，对排好序的集合做查找操作，时间复杂度为O（N），当然这种算法肯定比遍历要快多了。

code：

　　对于第三个方法，我只是把算法的思想做了一下总结，并没有编写代码运行调试并与其他算法做比较！比较过的朋友，欢迎告知三种算法的优劣性！
题目部分摘取自july CSDN网站：http://blog.csdn.net/v_july_v/article/details/11921021 
注：1.本文版权归作者和CSDN所有，未经允许不得转载，侵权必究！
2.本博客与博客园上的博客为同一博客主：http://www.cnblogs.com/bestDavid/
后记：　　
　　只要是算法，就无法同时解决时间复杂度和空间复杂度这一矛盾，我们只能具体问题具体分析，根据实际情况选取最合适的算法，尽量保持程序高效的执行效率！我的写代码能力和算法能力只能算初学者级别，所以在贴出的代码中可能有许多漏洞，朋友们若是有什么建议，请多多给与我更多的指教！在这里发表一下自己的看法，多谢支持！