互联网开发面试题.docxVIP

互联网开发面试题　　1一共有100万，抽中的2万，每月增加4万，问20个月能抽中的概率为：?　　2 for(int i=0;i　　3 手机wifi(A)….wifi ap….局域网(B)…..路由器…ADSL(C)…..互联网…..服务器　　断掉上述ABC哪些点TCP链接会立刻断掉?　　4 12345入栈，出栈结果 21543 31245 43215 12534 可能的为?(第一个和第三个)　　5 x^n+a1x^n-1+…+an-1x+an,最少要做—乘法?题目中a1，a2，an为常数。　　9月26日，百度一二面：　　1、给定一数组，输出满足2a=b(a，b代表数组中的数)的数对，要求时间复杂度尽量低。　　2、有哪些信誉好的足球投注网站引擎多线程中每个线程占用多少内存?如果有哪些信誉好的足球投注网站引擎存储网页内存占用太大怎么解决?　　3、有很多url，例如*.，*. ......　　现在给你一个 快速匹配出是*.。点评：老题，此前blog内曾整理过。　　4、找出字符串的编辑距离，即把一个字符串s1最少经过多少步操作变成编程字符串s2，操作有三种，添加一个字符，删除一个字符，修改一个字符(只要听过编辑距离，知道往动态规划上想，很快就可以找到解法)。　　点评：请看链接：http:///Lost_Painting/article/details/6457334。　　5、编程实现memcopy，注意考虑目标内存空间和源空间重叠的时候。　　6、实现简单的一个查找二叉树的深度的函数。　　9月26日晚，优酷土豆笔试题一道：　　优酷是一家视频网站，每天有上亿的视频被观看，现在公司要请研发人员找出最热门的视频。　　该问题的输入可以简化为一个字符串文件，每一行都表示一个视频id，然后要找出出现次数最多的前100个视频id，将其输出，同时输出该视频的出现次数。　　1.假设每天的视频播放次数为3亿次，被观看的视频数量为一百万个，每个视频ID的长度为20字节，限定使用的内存为1G。请简述做法，再写代码。　　2.假设每个月的视频播放次数为100亿次，被观看的视频数量为1亿，每个视频ID的长度为20字节，一台机器被限定使用的内存为1G。　　点评：有关海量数据处理的题目，请到此文中找方法(无论题目形式怎么变，基本方法不变，当然，最最常用的方法是：分而治之/Hash映射 + Hash统计 + 堆/快速/归并排序)：http:///v_july_v/article/details/7382693。注：上题第二问文件太大，则可如模1000，把整个大文件映射为1000个小文件再处理 ....　　9月26日，baidu面试题：　　1.进程和线程的区别　　2.一个有序数组(从小到大排列)，数组中的数据有正有负，求这个数组中的最小绝对值　　3.链表倒数第n个元素　　4.有一个函数fun能返回0和1两个值，返回0和1的概率都是1/2，问怎么利用这个函数得到另一个函数fun2，使fun2也只能返回0和1，且返回0的概率为1/4,返回1的概率为3/4。(如果返回0的概率为而返回1的概率为呢)　　5.有8个球，其中有7个球的质量相同，另一个与其他球的质量不同(且不知道是比其他球重还是轻)，请问在最坏的情况下，最少需要多少次就能找出这个不同质量的球　　6.数据库索引　　7.有一个数组a，设有一个值n。在数组中找到两个元素a和a，使得a+a等于n，求出所有满足以上条件的i和j。　　万个元素的数组，90%的元素都是1到100的数，10%的元素是101--10000的数，如何高效排序。　　小米的web开发笔试题：　　一场星际争霸比赛，共8个人，每个人的实力用分数表示，要分成两队，如何保证实力最平均?给定一个浮点数的序列，F1,F2,……，Fn(1　　9月27日，趋势科技面试题：　　马路口，30分钟内看到汽车的概率是95%，那么在10分钟内看不到汽车的概率是?　　9月27日晚，IGT笔试题：　　给定一个字符串里面只有R G B 三个字符，请排序，最终结果的顺序是R在前 G中 B在后。　　要求：空间复杂度是O(1)，且只能遍历一次字符串。　　点评：本质是荷兰国旗问题，类似快排中partition过程，具体思路路分析及代码可以参考此文第8节：http:///v_july_v/article/details/6211155。　　9月27日，人人两面：　　一面　　1 实现atoi　　2 单链表变形 如 1 2 3 4 5 变为 1 3 5 4 2 如1 2 3 4 变为 1 3 4 2　　(就是拆分链表 把偶数为反过来接在奇数位后面)　　二面　　1 二叉树查找不严格小于一个值的最大值(返回节点)。　　2 有序数组里二分查找一个数(如果有相同的找最后一次出现的)。　　3 等价于n*n的矩阵，填写0，1，要求每行每列的都有偶数个1 (没有1