腾讯实习生面试题
偶投的是游戏开发方面的岗位，今天面试的时候，面试官问了三个问题。
1、寻找一个字符串中最长的重复子串。 如 abcdabc 最长重复串 是abc
2、1G的内存，对10亿个数字进行排序，有什么比较好的方法。
3、游戏打斗中出现很卡应该如何解决？
4、三维数据的网格优化是怎么处理的？

各位大侠，大家都发挥一下能力，讨论一下这几个问题吧，偶当时回答的不太好，悲剧啊。。

[解决办法]
第2个:

vector<bool> vec(1024*1024*1024*4,false);
for(int i=0;i<1e8;i++)
{
int val;
scanf("%d",&val);
vec[(unsigned int)val]=true;
}
for(size_t i=0;i!=vec.size();i++)
{
if(vec[i])
printf("%d\t",(int)i);
}
[解决办法]
10亿个数字，如果每个数字是4个字节，有3G多，肯定超过1g
如果用位图的话就是3G除以32肯定是小于1g
至于代码怎么写，goolge到处都是
[解决办法]
第一个题 用后缀数组。
第二个题 不知道数字有无重复，如果没重复才用位图，否则不好办。
第三个，是看网络的问题还是内存不够用。看样子是服务器端吧，那么就考虑网络连接模型，内存需要把一些常用东西缓存起来。
第四个不太清楚。
[解决办法]
第2题我觉的可以这样搞：
把0-2^32所有数人为的分成128份，每份是33554432个数，每份有个连续的，每份对应一个文件，排一个数的时候先看在哪个区别，然后再在这个区间上排，并且排序结果可以保存在这个区间对应的文件里。

算法不懂，偶只会瞎想。