盒子
盒子
Posts List
  1. 千万级的用户,提供一个服务,该服务有很多模块,现在有一个底层模块需要优化,问怎么实现,在不影响其他服务模块以及用户体验的情况下。(面IEG)
  2. 未知大小的文件,翻转整个文件
  3. 如果内存中有个cache存储qq号和最近登录时间问怎么样做hit和淘汰
  4. 检测短信敏感词
  5. 爬虫程序的核心代码和正则表达式
  6. 有没有做过协议开发相关的工作?
  7. 给你一个场景,有10个特别大的图片,要对他们进行排序,用什么数据结构存储。
  8. 给两个文件,里面均有超过50亿条域名,各自文件内假设没有重复,互相之间有若干条一样的,找出来。
  9. 群聊的数据结构/数据库怎么设计,要求每个人能够方便的看到自己想要看到的信息。比如需要存储哪些字段?怎么存?
  10. 有n台机器,原来的master宕掉了,要选举一个新的master出来,怎么选?
  11. 设计题:有500W个QQ号,设计一个合适的数据结构进行储存、查找与维护(这里考虑到查找的高效性,我想的是字典树,但和面试官探讨的过程中,感觉他不是很满意这个答案,大家如有更高效的结构欢迎分享)
  12. 如何从10亿个QQ号中快速查找给定的QQ号
  13. 40G的字符串,里面有2个字符串是重复的,怎么找出来?
  14. 不使用第三个数(临时变量)交换两个整形数
  15. 0000到9999这1万个数中有多少个数字7(请不要理解为多少个数包含7)
  16. 如何实现一个随机播放音乐,要求能够方便查看上一首播放的是什么,方便交换即将播放的歌曲顺序
  17. 6根火柴能最多摆出多少等边三角形
  18. 如何实现俄罗斯方块游戏形状的移动和旋转
  19. 怎么实现随机插入100个数字到一个长度为100的数组里,且无重复
  20. 设计题:有一个3阶魔方,设计一个数据结构来储存,并设计一个算法来求解魔方(当时设计出了数据结构,但求解算法只能想到DFS+剪枝,显然时间开销太大……事后在网上没找到特别好的求解算法,如有大神知道,还请指教)

面试内容整理—思路

千万级的用户,提供一个服务,该服务有很多模块,现在有一个底层模块需要优化,问怎么实现,在不影响其他服务模块以及用户体验的情况下。(面IEG)

http://taop.marchtea.com/09.03.html

未知大小的文件,翻转整个文件

如果内存中有个cache存储qq号和最近登录时间问怎么样做hit和淘汰

检测短信敏感词

爬虫程序的核心代码和正则表达式

有没有做过协议开发相关的工作?

给你一个场景,有10个特别大的图片,要对他们进行排序,用什么数据结构存储。

给两个文件,里面均有超过50亿条域名,各自文件内假设没有重复,互相之间有若干条一样的,找出来。

群聊的数据结构/数据库怎么设计,要求每个人能够方便的看到自己想要看到的信息。比如需要存储哪些字段?怎么存?

有n台机器,原来的master宕掉了,要选举一个新的master出来,怎么选?

https://sanwen8.cn/p/2faiv1h.html

设计题:有500W个QQ号,设计一个合适的数据结构进行储存、查找与维护(这里考虑到查找的高效性,我想的是字典树,但和面试官探讨的过程中,感觉他不是很满意这个答案,大家如有更高效的结构欢迎分享)

如何从10亿个QQ号中快速查找给定的QQ号

40G的字符串,里面有2个字符串是重复的,怎么找出来?

不使用第三个数(临时变量)交换两个整形数

提示:
方式1加法,a=a+b;b=a-b;a=a-b;(缺点,可能出现a+b超过范围);
方式2位运算,a^=b;b^=a;a^=b;(对数值类型通用)

0000到9999这1万个数中有多少个数字7(请不要理解为多少个数包含7)

提示:
方式1,可以通过找规律的方式,比如1到10,1到100,1到1000分别多少个;
方式2,对每一位单独考虑,共四位,每一位出现7的概率是1/10;
方式3,每次固定一位,变换其他位,比如固定千位为7,那么就有1000个,依次计算,得到最终结果4000

如何实现一个随机播放音乐,要求能够方便查看上一首播放的是什么,方便交换即将播放的歌曲顺序

提示:先对歌曲编号为0~999(比如有1000首歌),用洗牌算法(不懂的请自行百度)将序号顺序打乱,之后开始播放,这样播放中用户可以对歌曲再次调整顺序,调整时同步调整序号。

6根火柴能最多摆出多少等边三角形

提示:正六角星(8个等边三角形)

如何实现俄罗斯方块游戏形状的移动和旋转

提示:先用矩形将下落方块围住标记,再记录方块当前的左下角位置,移动时记录坐标变化(可以百度看更高端的答案)

怎么实现随机插入100个数字到一个长度为100的数组里,且无重复

随机洗牌问题
“随机确定a1的值,然后递归地对后n-1位进行操作”,用数学归纳法即可轻易说明算法的正确性。而事实上,这段程序一共将会产生n(n-1)(n-2)1种等可能的情况,它们正好与1至n的n!种排列一一对应。

void ShuffleArray_Fisher_Yates(char* arr, int len)
{
    int i = len, j;
    char temp;
    if ( i == 0 ) return;
    while ( --i ) {
        j = rand() % (i+1);
        temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

for i:=1 to n do swap(a[i], a[random(i,n)]);

设计题:有一个3阶魔方,设计一个数据结构来储存,并设计一个算法来求解魔方(当时设计出了数据结构,但求解算法只能想到DFS+剪枝,显然时间开销太大……事后在网上没找到特别好的求解算法,如有大神知道,还请指教)

呼呼呼山(http://code4fun.me)
18 Sep 2017 9:08 PM