PPLive笔试题（刚出炉的）
1、假设一个客户，他的手机中存放有全中国人民的手机号，他的手机通信录顺序很乱而且里面可能有些重复了，现在客户想让我们设计一个程序，帮他把通讯录整理一下，删除重复手机号，说机上能利用的内存只有10M，但是有无限大的硬盘，请给出设计思路，并评估算法性能。
2、有一组数字，如14,26,5,30,0，-2,108，和一个给定的整数a，是否存在其中一个或几个，它们的和等于a。
请实现方法int findNIntendo（int arr[],int count,int a)，存在返回1，否则返回0.
3、实现反转字符串。
4、以下关于红黑树的恶说法错误的是：
A、红黑树上插入操作的最差情况下的时间复杂度为O（log n)
B、红黑树上任意节点的左右子树高度差绝对不大于1
C、红黑树上删除操作最差情况的时间复杂度为O(log n)
D、红黑树上查找操作最差情况下的时间复杂度为O(log n)
5、unsigned short hash(unsigned short key){
return (key>>4)%256
}
请问hash(16)，hash(256)的值分别是______、______
6、有98个元素的排序好的数组，用二分法查找，最多需要查找几次？
7、下列哪种排序算法和数据结构是不稳定的？
A、插入排序 B、快速排序 C、基数排序 D、（选项忘了）
[最优解释]
好题mark
[其他解释]
findNIntendoHelp(arr,count,left,M,++c))==1){
M[left]=1;
return 1;
}else{
M[left]=0;
return 0;
}
}
int findNIntendo(int arr[],int count,int a){
stdext::hash_map<int,int> M;
int c=0;
int left=a;
return findNIntendoHelp(arr,count,left,M,c);
}
第三题：
void inversestr(char* str){
int r=strlen(str)-1;
int l=0;char temp;
while(r>l){
temp=str[r];
str[r--]=str[l];
str[l++]=temp;
}
}
第四题：
B
第五题：
1 16
第六题
7次。
第七题：
快排
第八题：
看不清
第九题：
A
第十题
B
[其他解释]
周末人怎么都不见了？出来冒个泡啊~~
[其他解释]
第一个：放到一个set里面，自动就删除重复的了。不过我想出题的人想考的应该是解题思路。
我的思路是按手机号分别存放到不同的文件当中，比如132的放到一个文件中，133的放到一个文件中。
遍历文件的时候，第一次遍历只读取132的，10M的空间存储132开头的手机号，重复的删除（Set集合就行了），最后剩余的存到132文件中。
然后第二次遍历只读取133的，依次下去。
第二个：我能想到的思路只有双层for循环了。算法就不写了，挺简单的，就是效率上有可能有点低。
第三个:把字符串放到一个List或者map（key和字符成映射）中，遍历list的时候用反转遍历，map就按Key值从大到小读取呗。
第四个：我不知道叫红黑树
后面的先不做了，有空继续做。
[其他解释]
谁能写出具体的实现，太笼统了作为菜鸟的我接受不了呀
[其他解释]
这个坐等思路，我是没办法啊
[其他解释]
第二题，贪心算法
[其他解释]
表示不会~~
[其他解释]
第一个，应用文件的归并排序
[其他解释]
第二道题不知道这样行不行
import java.util.ArrayList;
public class Find{
public static final int MAX = 100;
public static ArrayList<Integer> array = new ArrayList<Integer>();
public static void main(String[] args) {
int arr[] = { 2, 4, 6, 7, 100 };
int flag = findNIntendo(arr, 3, 110);
System.out.println(flag);
}
public static int findNIntendo(int arr[], int count, int a) {
int i;
int[] a1 = new int[MAX];
int[] b1 = new int[MAX];
for (i = 1; i < 100; i++)
a1[i - 1] = i;
combine(a1, arr.length, count, b1, count,arr);
for (int j = 0; j < array.size(); j++)
if (array.get(j) == a)
return 1;
return 0;
}
public static void combine(int a[], int n, int m, int b[], int M,int[] arr) {
int i, j;
for (i = n; i >= m; i--) {
b[m - 1] = i - 1;
if (m > 1)
combine(a, i - 1, m - 1, b, M,arr);
else {
int sum = 0;
for (j = M - 1; j >= 0; j--)
sum += arr[a[b[j]]-1];
array.add(sum);
}
}
}
}
[其他解释]
第六题应该是6次，第七天就应该选D吧！
[其他解释]
第三题：
code=java]
public class Test{
public static void main(String[] args) {
String str="54g34g34";
char[] s;
s=str.toCharArray();
for(int i=s.length-1;i>=0;i--){
System.out.print(s[i]);
}
}
}[[/code]
第四题还是不知道什么叫红黑树
第五题：1,16
hash(16)==>16>>4=1(把16转换为2进制数，然后退4位，就是等于16除以2的4次方)==>1%256余数等于1呗
hash(256)等于16，也即是16除以256余数还是16
第六题：取极端1，那就是分别和49,25,13,7,4,2比较。6次。至于最后一次需不需要和1比较，我不确定，还是回答6次至少证明你知道这个方法。
第七题：快速排序是不稳定的，我也是刚查的，真不起大学时候的数据结构老师。
[其他解释]
Mark，继续等回复
[其他解释]
LZ不错嘛 继续啊
[其他解释]
一般的，红黑树，满足以下性质，即只有满足以下全部性质的树，我们才称之为红黑树：
1）每个结点要么是红的，要么是黑的。
2）根结点是黑的。
3）每个叶结点，即空结点（NIL）是黑的。
4）如果一个结点是红的，那么它的俩个儿子都是黑的。
5）对每个结点，从该结点到其子孙结点的所有路径上包含相同数目的黑结点。
4.B、红黑树上任意节点的左右子树高度差绝对不大于1 感觉这个错误，还不确定。
[其他解释]
mark 关注下
[其他解释]
第一题我的思路：
// mobile = 11,person = 1300000000,momery=10M,
double storeByte = 1300000000l * 11;//13亿人需要存储多少空间，11是手机号的字节数
double memery = 10 * 1024 * 1024;//10M换算成字节数
double splitCount = storeByte / memery;//做个小运算，看要读完全部数据到内存要做多少次
1.以10M内存，需要进行计算1364次计算，才能完全处理完这些记录
2.按每次10M处理现在手机号，发现重复的则删除，并记录成一个随机文件A1直到A1364
3.读入A1文件到内存数组，读取A2-A1364文件，将A2到A1364一条记录(readLine)和A1记录比较，将不同结果写入新文件尾部
考虑不周地方，欢迎批评
[其他解释]
第一题：
先HASH把号码划分成可以放入内存中操作的N分，存入N个文件中，再对每个文件进行操作。
第二题：
这个明显的是个经典的0-1背包问题。
以下是动态规划实现
int findNIntendoHelp(int arr[],int count,int left,stdext::hash_map<int,int> M,int c){
if(M.find(left)!=M.end()){
return M[left];
}
if(left==0){
M[left]=1;
return 1;
}
if(c>=count){
M[left]=0;
return 0;
}
if((findNIntendoHelp(arr,count,left-arr[c],M,++c)
[其他解释]
补充一下 题目都说了是中国人的手机号码，那就只有13X和15X 18X了
[其他解释]
第一题：线程一：
int start = 130 0000 0000 //可以赋值到线程target
while(start++<131 0000 0000){
//文件读取 选出收个和start相同的号码的记录。
}
考虑10M内存，以及程序的线程池、线程等资源消耗，综合控制线程数。
第二题：看到某算法书上说此类问题可以递归解决。应该和背包问题一样吧。
一点浅见，欢迎指正。
[其他解释]
第二题：
package com.zf.test;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
/**
* @author Administrator
*/
public class CompomentTest {
/**
* @param array要组合的源数组
* @param n 以每n个元素作为一个组合
* @param sum 组合内所有元素的和
* @return组合后的集合
*/
public static List<int[]> combination(int[] array , int n ,int sum){
List<int[]> combinations = new ArrayList<int[]>();
if(n <= 0 && n > array.length)
return null ;
LinkedList<Integer> tmp = new LinkedList<Integer>();
for(int i = 0; i < array.length ;i++){
if(i < n)
tmp.add(1);
else
tmp.add(0);
}
boolean flag = true ;
List<LinkedList<Integer>> indexgraph = new ArrayList<LinkedList<Integer>>();
indexgraph.add(tmp);
//得到所有元素的排列
do{
//寻找到第一个 1 0
int last = tmp.get(0);
int targetIndex = 1 ;
for (; targetIndex < tmp.size() ; targetIndex++) {
int current = tmp.get(targetIndex) ;
if( current == 0 && last == 1)
break ;
last = current;
}
if(targetIndex == tmp.size()) //已经排列完所有
{
flag = false;
}
if(flag){
LinkedList<Integer> graph = new LinkedList<Integer>() ;
for (int i = 0; i < targetIndex -1 ; i++) {//保存targetIndex之前的部分
int l = tmp.get(i);
if(l == 1)
graph.addFirst(l);
else
graph.addLast(l);
}
graph.add(0);
graph.add(1);
for (int i = targetIndex + 1; i < tmp.size(); i++) {
graph.add(tmp.get(i));
}
indexgraph.add(graph);
tmp = graph ;
}
}while(flag);
//从array中取出相对应的元素
for (LinkedList<Integer> queue : indexgraph) {
int[] t = new int[n];
int index = 0 ;
for (int i = 0; i < queue.size(); i++) {
int k = queue.get(i);
if(k == 1){
t[index++] = array[i];
}
}
combinations.add(t);
}
//取除所有元素之和不等于给定值的组合
Iterator<int[]> it = combinations.iterator();
while(it.hasNext()){
int[] t = it.next();
int s = 0 ;
for (int i : t) {
s+= i ;
}
if(s != sum){
it.remove();
}
}
return combinations ;
}
public static void main(String[] args) {
List<int[]> result = combination(new int[]{0,1,2,3,4,5,8} , 3 , 10);
for (int[] is : result) {
System.out.println(Arrays.toString(is));
}
}
}
运行结果：
[2, 3, 5]
[1, 4, 5]
[0, 2, 8]
[其他解释]
菜鸟学习下
[其他解释]
作为刚入职的我来说，这题目，让我答，基本0分。
[其他解释]
第一题还是分治吧 上面不分开直接挑确实效率太低了。。。。。。。
[其他解释]
第一个哪个大牛敢不敢贴一下具体实现过程，让我等菜鸟见识见识
[其他解释]
看到无限大硬盘第一反应外部排序。。。
[其他解释]
MARK下，有空看看
[其他解释]
求第一题实现过程.
[其他解释]
手机号码共11位，第一位是1，不用考虑，剩下10个数字。
最后4位做hash分散，剩下6位,建立byte数组需要1M的内存。
根据电话号码低4位建立文件，电话号码分别保存到各自的文件里
处理每个文件
创建标志数组 byte[] sign = new byte[1000000];
根据除了低4位和最高位的1外，设置对应的byte位1，比如
13812345678， 去掉最高位的1，最低位的5678，剩下的位381234，则设置
sign[381234] = 1;
处理完毕后，根据sign[X]=1的位，输出到结果文件里。
循环处理下一个文件。
如果能使用二进制处理方式性能会更好一些。
[其他解释]
反转字符串的题目经常出现，不知道想要考察什么知识
[其他解释]
mark一下
[其他解释]
第一题应该用bitmap来实现，兄弟们去看看编程珠玑，上面有说这种题的！
[其他解释]
null
[其他解释]
第一题 ：用两阶段多路归并排序的方法解决。假设手机号有N个，一个号约为10字节，首先将这N个手机号分成大小均为5M的小文件，则大概可以分为N*10/5000000=M份小文件，运行快速排序的方法对这M份小文件分别排序，然后每次从M份小文件中取出一个号码，得到M个号码，进行外排序，对于相同的号码不进行排序，排完后，输出到硬盘，算法完成。
时间复杂度为O(nlogn)、空间复杂度为O(1)
第二题 ：该问题其实是一个子集和问题，即NP完全问题
第三题 ：定义两个指示器，一个指在最左边，向右移动，一个指在最右边，向左移动，两个指示器同时移动，直接相等。
void invert_point(char *str)
{
int i,j;
i=0;
j=strlen(str)-1;
while(i<j)
{
*(str+i)=*(str+i)^*(str+j);
*(str+j)=*(str+i)^*(str+j);
*(str+i)=*(str+i)^*(str+j);
i++;
j--;
}
}
第四题：不知道
第五题：hash(16)，hash(256)的值分别是__1____、___16___
如果short为一个字节，则hash(256)为0；如果short为两个字节，则hash(256)为16。
第六题：7(2的7次方约等于98)
第七题:B
[其他解释]
数据结构方面的知识处于空白状态，确实饶人。