一道有意思的题目

刚群里有人发了一道面试题 觉得蛮有意思 试着做了下 原题如上 给出伪代码如下：
AllCards == 黑桃A4Q 红桃23478J 梅花456QK 方片A5
甲说：不知道哪张牌 ==>
if cardCount == 1 then delete thisCard
leftCards = 黑桃A4Q 红桃4 梅花45Q 方片A5
// 因为甲知道点数却不知哪张牌则点数必不唯一
乙说：我知道你不知道哪张牌 ==>
if exist card (cardCount == 1) in cardColour then delete this cardColour
leftCards = 黑桃A4Q 方片A5
// 乙敢断言甲不知道则花色里的牌的点数全不唯一 否则甲有可能知道 红桃梅花剔除
甲说：现在我知道了 ==>
if cardCount > 2 then delete thisCard
leftCards = 黑桃4Q 方片5
//则必不为A 甲知道点数 若为A则判断不出是黑桃A还是方片A
乙说：我也知道了 ==>
则只能是方片5，乙才能知道
if leftCardCounts > 1 then delete thisCardColour
leftCards = 方片5
//乙知道花色 此时能推断出是哪张牌 则该花色必只剩一张 所以为方片5

这篇博文不定期更新 收集算法专用 ====================》
题目二：有一个无序的实数序列x1,x2.....xn，请设计个算法在线性时间内找到相邻（不是序列相邻，而是在实数轴上相邻）两点间最大距离。
double max_gap(double* num, int n)
{
int i;
//找出最大最小值
double max=0.0,min = INT_MAX;
for(i=0;i<n;i++)
{
if(num[i]>max) max=num[i];
if(num[i]<min) min=num[i];
}

int *count=new int[n];        //动态分配，实际分到每个桶的数据个数
double *low=new double[n];    //实际分到每个桶的最小数据(下界)
double *high=new double[n];    //实际分到每个桶的最大数据（上界）

for(i = 0; i < n; i++)  //初始化每个桶
{
count[i] = 0;
low[i] = max;
high[i] = min;
}

double ave=(max-min)/(n-1);

//按如下规则将num[i]分配到某个桶(编号doublemp)中
for(i=0;i < n; i++)
{
int temp=(int)((num[i]-min)/ave);
count[temp]++;
//调整分到该桶的最大最小数据
if(num[i] > high[temp])
high[temp] = num[i];
if(num[i] < low[temp])
low[temp] = num[i];
}

//寻找最大间隙
double left = high[0], res = 0.0;
for(i = 1;i < n; i++)
{
if(count[i]>0)
{
double temp = low[i]- left;
if(temp > res)   res = temp;
left = high[i];
}
}
return res;
}

int main()
{
int num;
cin >> num;
double* pdArr = new double[num];
for (int i = 0; i < num; i++)
{
cin >> pdArr[i];
}
cout << max_gap(pdArr, num)<<endl;
return 0;
}

题目三：下列随机排列算法有问题没
RANDOMIZE-IN-PLACE(A)
n <- length[A]
for i <- 1 to n-1
      do swap A[i] <-> A[RANDOM(i+1,n)]
这样数i 永远不会在自己的位置上！可改为：
RANDOMIZE-IN-PLACE(A)
n <- length[A]
for i <- 1 to n-1
      do swap A[i] <-> A[RANDOM(i,n)]

题目四：淘宝部分笔试题 
选择题：
1、vim里怎么换行（命令模式和insert模式）
2、两个有序列表连接成一个，最少比较次数
3、给一个前缀表达式，求中缀表达式
4、-73的补码
5、函数f【1001】=0，f【1011】=1，问可以成为f的表达式的是？我选了异或
6、一数组和指向该数组的指针，指针自增后，求输出。。。
7、struct 和类的区别
 
问答题：
1、100用户，每人好友约10个，如何准实时显示好友状态；当用户增至100万时候，会出现什么问题，你之前的方案是否仍然可行
2、JavaScript写一个排序函数
3、JavaScript写一个函数，每隔五秒调用某个函数
4、JavaScript写一个函数，判断输入的字符串是否有效的email地址，用正则表达式
5、html和css方面：给出代码，画出网页大体布局
6、评价令狐冲对岳不群的态度
7、随便涂鸦，表达你的梦想和未来打算
8、用json格式写一个person变量

通用题目 
1、选择题 
语法的含义 
对初始排列顺序不敏感的排序算法 
可能指的是在最好与最坏情况下，排序算法的效率浮动过大
 
动态联编 
//只能对基类指针或引用，才能使用动态联编 
int main() 
{ 
Base *d = new Derived; 
d->af 
delete d; 
return 0; 
}
 
2、简答题 
简述set list map及在何种情况下使用
http://zhidao.baidu.com/question/16113509.html 
2、程序设计 
有不限数目的1、5、10、20、50面额的纸币，有多少种方法凑出100元 
3、数据库设计 
购买商品会赠予积分，积分可以兑换商品，过期无效。 
请设计数据库，不限一张表 
  
测试类题目 
逻辑推理题，记不住题目了，不难 
  
剩下的就记不住分类了 
  
Web服务器工作的runlevel 
  
http正确的响应代码 
一、HTTP响应码
响应码由三位十进制数字组成，它们出现在由HTTP服务器发送的响应的第一行。
响应码分五种类型，由它们的第一位数字表示：
1.1xx：信息，请求收到，继续处理
2.2xx：成功，行为被成功地接受、理解和采纳
3.3xx：重定向，为了完成请求，必须进一步执行的动作
4.4xx：客户端错误，请求包含语法错误或者请求无法实现
5.5xx：服务器错误，服务器不能实现一种明显无效的请求
下表显示每个响应码及其含义：
100 继续
101 分组交换协
200 OK
201 被创建
202 被采纳
203 非授权信息
204 无内容
205 重置内容
206 部分内容
300 多选项
301 永久地传送
302 找到
303 参见其他
304 未改动
305 使用代理
307 暂时重定向
400 错误请求
401 未授权
402 要求付费
403 禁止
404 未找到
405 不允许的方法
406 不被采纳
407 要求代理授权
408 请求超时
409 冲突
410 过期的
411 要求的长度
412 前提不成立
413 请求实例太大
414 请求URI太大
415 不支持的媒体类型
416 无法满足的请求范围
417 失败的预期
500 内部服务器错误
501 未被使用
502 网关错误
503 不可用的服务
504 网关超时
505 HTTP版本未被支持
  
重定向的用法 
<meta http-equiv="refresh" content="5;url=http://www.cppblog.com/cool-liangbing/">，
也就是告诉你的浏览器5秒之后自动跳转到我的c++博客首页http://www.cppblog.com/cool-liangbing/。
  
函数名前加const表示什么含义 
 
const表示得到的一个结果常量，所修饰的蛮量和函数结果都不能被修改，所以一切想修改const年修饰的值的都会报错
http://topic.csdn.net/t/20020221/19/536312.html
Const int * //const指针
Int * const //指向const的指针
Const int* const //指针const的指针

题目五：排序复杂度


题目六：搜狐某编程题
{1,2,2,3,4,5,}排列组合要求，4不放第三位，3,5不相连。
刚写了个java的实现版本如下：

import java.util.Set;
import java.util.TreeSet;
public class perm {

Set<String> set = new TreeSet<String>();
StringBuilder sb = new StringBuilder();
public  <T> void goperm(T list[], int k, int m){
int i;
if(k == m){
if(testCondition(list)){
sb.replace(0, sb.length(), "");
// if(true){
for(int j=0; j<=m; j++)
{
sb.append(list[j]);
// System.out.print(list[j]);
}
// System.out.println("");
set.add(sb.toString());
}
}else{
for(i = k; i<=m; i++){
// if(testCondition(list,k,i)){
swap(list,k,i);
goperm(list, k+1, m);
swap(list,i,k);
// }
}
}
}
public <T> boolean testCondition(T list[]){
if(list[2].toString() == "4" ){return false;}
for(int i=0; i<5; i++){
if(list[i].toString() == "3"){
if(list[i+1].toString() == "5") return false;
else return true;
}
if(list[i].toString() == "5"){
if(list[i+1].toString() == "3") return false;
else return true;
}
}
return true;
}
public <T> boolean testCondition(T list[],int k,int i){
if(k!=i  && list[k].toString() == "2"){return false;}
return true;
}
public void printSet(){
System.out.println("total number:"+set.size());
System.out.println(set);
}
public <T> void swap(T list[], int a, int b){
T temp = list[a];
list[a] = list[b];
list[b] = temp;
}
public static void main(String[] args) {
String[] str = new String[]{"1","2","2","3","4","5"};
perm p = new perm();
p.goperm(str,0,5);
p.printSet();

}
}


题目七：百度三面某编程题
N个台阶，每次可走一个或两个
问共有多少种走法？ Java版实现如下（递归思想）：
public class stepCount {
static int count = 0;
static void func(int left){
if(left <= 1) count ++;
else{
func(left-1);
func(left-2);
}
}
public static void main(String[] args) {
func(4);
System.out.println(count);
}
}
题目八：轩辕互动上级题
有一个存储每日股票价格的数组A[0,1,2,...n]，求买入卖出的最大差价，即最大赢利是多少，如果输入的数据有几百兆字节该怎么办，求最大赢利还好求，这个输入过大该怎么办 （先买后卖）
minValue=min(a[0],a[1]);
maxDelta=a[1]-a[0];
for i=2→n
   if (a[i]<minValue) minValue=a[i];
   else if ((a[i]-minValue)>maxDelta)    maxDelta=a[i]-minValue

题目九：完美题
死锁是怎么出现的？如何避免？
数据库设计的第三范式；
什么是存储过程？其原理和好处？
IP头和TCP头分别包含什么信息；
JAVA中异常的分类；
Linux中syslog的分类？默认文件？日志轮转的配置；
C++中虚函数的实现机制；
windows的hernel32.dll和user.dll分别完成了哪些方面的函数封装；

原帖：http://blog.sina.com.cn/s/blog_67afbf0b0100mn0c.html