这些题目来自v_JULY_v大神博客：http://blog.csdn.net/v_july_v/article/details/7974418
-
9月11日， 京东：谈谈你对面向对象编程的认识
整理答案：
面向对象可以理解为对待每一个问题，都是首先要确定这个问题由几个本分组成，而每一个部分其实就是一个对象。然后再分别设计这些对象，最后得到整个程序。传统的程序设计多是基于功能的思想来进行考虑和设计的，而面向对象的程序设计则是基于对象的角度来考虑问题。这样做能够使得程序更加简洁，清晰。
面向对象深入理解请看这里。
2. 8月20日，金山面试，题目如下：
数据库1中存放着a类数据，数据库2中存放着以天为单位划分的表30张（比如table_20110909,table_20110910,table_20110911）,总共是一个月的数据。表1中的a类数据中有一个字段userid来唯一判别用户身份，表2中的30张表（每张表结构相同）也有一个字段userid来唯一识别用户身份。如何判定a类数据库的多少用户在数据库2中出现过？
思路1：
建立一张用户表，UserInMonth（userid）表里面只放不重复的用户Id，把（table_20110909,table_20110910,table_20110911）的用户Id放到一张User表里面userid都统一放到这个表里面去。判断的时候select count(1) from user u inner join UserInMonth um on u.userid=um.userid.
思路2：
还是怎么办都逃不过30张表的查询：
1.建立id表用来存放30张表的userid
create table id(userid varchar2(20)) 不用设主键
2.插入数据可以不去重复
insert in to id (select userid from table_20110909) 就插吧 30个挨个插
现在id表已经具备30天所有userid了
现在有两种选择
3.1把表id数据导出再导入到数据库1就可以查了
select distinct userid from a where userid in(select userid from id)
或者3.2 数据库1与数据库2建立连接 用@实现查询
select distinct userid from a where userid in(select userid from id@数据库2)
其实两种操作都差不多，都是将30张表数据提取出来，再与a中数据比较，考数据库操作(我是一点不会啊，该恶补了)。
3. 百度实习笔试题（2012.5.6）
1、一个单词单词字母交换，可得另一个单词，如army->mary，成为兄弟单词。提供一个单词，在字典中找到它的兄弟。描述数据结构和查询过程。
思路总结：
既可以用素数乘积法，也可用hash判别法，即逐个将一个字符串hash到另一个字符串的hash表中，全中则true，否则false。
关于这类试题请看程序员编程艺术：第二章、字符串是否包含及匹配/查找/转换/拷贝问题。
2、线程和进程区别和联系。什么是“线程安全”。
答案总结：
（1）定义：
一、进程是具有一定独立功能的程序关于某个数据集合上的一次运行活动，是系统进行资源分配和调度的一个独立单位。
二、线程是进程的一个实体，是CPU调度和分派的基本单位，他是比进程更小的能独立运行的基本单位，线程自己基本上不拥有系统资源，只拥有一点在运行中必不可少的资源（如程序计数器，一组寄存器和栈），一个线程可以创建和撤销另一个线程；
进程和线程的关系：
（1）一个线程只能属于一个进程，而一个进程可以有多个线程，但至少有一个线程。
（2）资源分配给进程，同一进程的所有线程共享该进程的所有资源。
（3）线程在执行过程中，需要协作同步。不同进程的线程间要利用消息通信的办法实现同步。
（4）处理机分给线程，即真正在处理机上运行的是线程。
（5）线程是指进程内的一个执行单元，也是进程内的可调度实体。
线程与进程的区别：
（1）调度：线程作为调度和分配的基本单位，进程作为拥有资源的基本单位。
（2）并发性：不仅进程之间可以并发执行，同一个进程的多个线程之间也可以并发执行。
（3）拥有资源：进程是拥有资源的一个独立单位，线程不拥有系统资源，但可以访问隶属于进程的资源。
（4）系统开销：在创建或撤销进程的时候，由于系统都要为之分配和回收资源，导致系统的明显大于创建或撤销线程时的开销。但进程有独立的地址空间，进程崩溃后，在保护模式下不会对其他的进程产生影响，而线程只是一个进程中的不同的执行路径。线程有自己的堆栈和局部变量，但线程之间没有单独的地址空间，一个线程死掉就等于整个进程死掉，所以多进程的程序要比多线程的程序健壮，但是在进程切换时，耗费的资源较大，效率要差些。
线程的划分尺度小于进程，使得多线程程序的并发性高。
另外，进程在执行过程中拥有独立的内存单元，而多个线程共享内存，从而极大的提高了程序运行效率。
线程在执行过程中，每个独立的线程有一个程序运行的入口，顺序执行序列和程序的出口。但是线程不能够独立执行，必须依存在应用程序中，有应用程序提供多个线程执行控制。
从逻辑角度看，多线程的意义子啊与一个应用程序中，有多个执行部分可以同时执行。但操作系统并没有将多个线程看做多个独立的应用，来实现进程的调度和管理以及资源分配。这就是进程和线程的重要区别。
（2）线程安全
如果代码所在的进程中有多个线程在同时运行，而这些线程可能会同时运行这段代码。如果每次运行结果和单线程运行的结果是一样的，而且其他的变量的值也和预期的是一样的，就是线程安全的。
3、C和C++怎样分配和释放内存，区别是什么?
C使用malloc和free来创建和释放内存，C++则一般使用malloc和free库函数。
区别：
（1）new，delete是操作符，可以重载，只能在C++中使用。
（2）malloc，free是函数，可以覆盖，C，C++都可以使用
（3）new 可以调用对象的构造函数，对应的delete调用相应的析构函数。
（4）malloc仅仅分配内存，free仅仅回首内存，并不执行构造和析构函数。
（5）new，delete返回的某种数据类型的指针，malloc，free返回的是void*类型的指针。
4、一个url指向的页面里面有另一个url,最终有一个url指向之前出现过的url或空，这两种情形都定义为null。这样构成一个单链表。给两条这样单链表，判断里面是否存在同样的url。url以亿级计，资源不足以hash。
情况一：两条单链表均无环
最简单的一种情况，由于两条链表如果交叉，他们的尾节点必然相等（Y字归并），所以只需要判断他们的尾节点是否相等即可。
情况二：两条单链表均有环
这种情况只需要拆开一条环路（注意需要保存被设置成null的节点），然后判断另一个单链表是否仍然存在环路，如果存在，说明无交叉，反之，则有交叉的情况。
情况三:两条单链表，一条有环路，一条无环路
这种情况显然他们是不可能有交叉的
5、数组al[0,mid-1] 和 al[mid,num-1]，都分别有序。将其merge成有序数组al[0,num-1]，要求空间复杂度O(1)。
这里有个解答，经验证可行： 数组al[0,mid-1]和al[mid,num-1]是各自有序的，对数组al[0,num-1]的两个子有序段进行merge，得到al[0,num-1]整体有序。
6、系统设计题
百度搜索框的suggestion，比如输入“北京”，搜索框下面会以北京为前缀，展示“北京爱情故事”、“北京公交”、“北京医院”等等搜索词，输入“结构之”，会提示“结构之法”，“结构之法 算法之道”等搜索词。请问，如何设计此系统，使得空间和时间复杂度尽量低。
大神直接给出了解答：
老题，直接上Trie树「Trie树的介绍见：从Trie树（字典树）谈到后缀树」+TOP
K「hashmap+堆，hashmap+堆 统计出如10个近似的热词，也就是说，只存与关键词近似的比如10个热词」？ or Double-array
trie tree？同时，StackOverflow上也有两个讨论帖子：http://stackoverflow.com/questions/2901831/algorithm-for-autocomplete，http://stackoverflow.com/questions/1783652/what-is-the-best-autocomplete-suggest-algorithm-datastructure-c-c。此外，这里有一篇关于“拼写错误检查”问题的介绍，或许对你有所启示：http://blog.afterthedeadline.com/2010/01/29/how-i-trie-to-make-spelling-suggestions/。
我自己也写了一个基于Trie树的处理字符串的自动匹配系统，代码如下：
/*
* Date:2012-11-8
* functions:Manage a system that can handle suggestion problem in serach engine.
* While user is inputing words,the system gives a list of posible words that the user may want to input displayed in a list
* that automaticlly.
* The solution is to create and manage a trie tree.
* @copyright:Chen Qin
*/
#include<iostream>
#include<vector>
#include<string>
#include<queue>
using namespace std;
//Trie tree node
typedef struct _TrieNode
{
string value;//word of the node
char added_char;//the charactor added to the parent word value
vector<struct _TrieNode*> child_list;//child pointers list
int match_count;//the count of the words match to the node value
int level;//level int the tree
}TrieNode,*pTrieNode;
//Trie tree root
typedef struct _TrieRoot
{
vector<struct _TrieNode*> child_list;//child pointers list of root of the Trie tree
}TrieTree,*pTrieTree;
class SuggestionSystem
{
public:
SuggestionSystem()
{
cout<<"construct system."<<endl;
mpTree=new TrieTree;
mpTree->child_list=vector<pTrieNode>();
}
SuggestionSystem(const vector<string> &words)
{
cout<<"construct system with data."<<endl;
mpTree=new TrieTree;
mpTree->child_list=vector<pTrieNode>();
for(vector<string>::const_iterator it=words.begin();it<words.end();it++)
{
InsertWordIntoTrieTree(*it);
}
}
~SuggestionSystem()
{
cout<<"destruct system."<<endl;
delete mpTree;
}
void CreateSystemFromWordList(const vector<string> &words);
void DisplayTree();//display the tree node
void FindSubsequencesOfGivenString(const string& str);//find the possible subsequencs of the given string
private:
void InsertWordIntoTrieTree(const string &word,bool search=false);
void InsertSubstringIntoNode(const string &word,pTrieNode pNode,bool serach=false);
void DeleteSystem();//clear the hole system
void FreeNode(pTrieNode pNode);//free trie node
void VisitNode(const pTrieNode pNode);
void DisplayTreeFromNode(const pTrieNode pNode);
private:
pTrieTree mpTree;
};
void SuggestionSystem::CreateSystemFromWordList(const vector<string> &words)
{
if(mpTree!=NULL)
{
DeleteSystem();
mpTree=new TrieTree;
mpTree->child_list=vector<pTrieNode>();
}
for(vector<string>::const_iterator it=words.begin();it<words.end();it++)
{
InsertWordIntoTrieTree(*it);
}
}
void SuggestionSystem::InsertWordIntoTrieTree(const string &word,bool search)
{
if(word.size()<=0) return;
char c=*word.begin();
for(vector<pTrieNode>::const_iterator it=mpTree->child_list.begin();it<mpTree->child_list.end();it++)
{
if((*it)->added_char==c)//alredy exits the path of the first charactor
{
if(word.size()==1)
{
(*it)->match_count++;
if(search)
{
DisplayTreeFromNode(*it);
}
}else
{
string sub=string(word.begin()+1,word.end());
InsertSubstringIntoNode(sub,*it,search);
}
return;
}
}
//create a new path of the charactor
pTrieNode pn=new TrieNode();
mpTree->child_list.push_back(pn);
pn->added_char=c;
pn->value=c;
pn->level=1;
if(word.size()==1)
{
pn->match_count=1;
}else
{
pn->match_count=0;
string sub=string(word.begin()+1,word.end());
InsertSubstringIntoNode(sub,pn,search);
}
}
void SuggestionSystem::InsertSubstringIntoNode(const string &word,pTrieNode pNode,bool search)
{
if(word.size()<=0) return;
char c=*word.begin();
for(vector<pTrieNode>::const_iterator it=pNode->child_list.begin();it<pNode->child_list.end();it++)
{
if(c==(*it)->added_char)//find the path math the first charactor of the word
{
if(word.size()==1)
{
(*it)->match_count++;
if(search)
{
DisplayTreeFromNode(*it);
}
}else
{
string sub=string(word.begin()+1,word.end());
InsertSubstringIntoNode(sub,*it,search);
}
return;
}
}
pTrieNode pn=new TrieNode();
pNode->child_list.push_back(pn);
pn->added_char=c;
string val=pNode->value;
val.push_back(c);
pn->value=val;
pn->level=pNode->level+1;
if(word.size()==1)
{
pn->match_count=1;
}else
{
pn->match_count=0;
string sub=string(word.begin()+1,word.end());
InsertSubstringIntoNode(sub,pn,search);
}
}
void SuggestionSystem::FindSubsequencesOfGivenString(const string& str)//find the possible subsequencs of the given string
{
InsertWordIntoTrieTree(str,true);
}
void SuggestionSystem::DeleteSystem()
{
if(mpTree->child_list.size()>=1)
{
for(vector<pTrieNode>::iterator it=mpTree->child_list.begin();it<mpTree->child_list.end();it++)
{
FreeNode(*it);
}
}
delete mpTree;
}
void SuggestionSystem::FreeNode(pTrieNode pNode)
{
if(pNode->child_list.size()>=1)//has children
{
for(vector<pTrieNode>::iterator it=pNode->child_list.begin();it<pNode->child_list.end();it++)
{
FreeNode(*it);
}
}
delete pNode;
pNode=NULL;
}
void SuggestionSystem::DisplayTree()
{
if(mpTree->child_list.size()<=0) return;
cout<<"------the hole tree nodes display------"<<endl;
queue<pTrieNode> que=queue<pTrieNode>();
for(vector<pTrieNode>::iterator it=mpTree->child_list.begin();it<mpTree->child_list.end();it++)
{
que.push(*it);
}
//begin visit by queue
cout<<"root-->"<<endl;
int cur_lev=1;
while(!que.empty())
{
pTrieNode pNode=que.front();
que.pop();
if(cur_lev<pNode->level)
{
cout<<"-->"<<endl;
cur_lev++;
}
VisitNode(pNode);
if(pNode->child_list.size()>0)
{
for(vector<pTrieNode>::const_iterator it=pNode->child_list.begin();it<pNode->child_list.end();it++)
{
que.push(*it);
}
}
}
cout<<endl;
}
void SuggestionSystem::DisplayTreeFromNode(const pTrieNode pNode)
{
if(pNode==NULL) return;
cout<<"------the found match subsequences are:------"<<endl;
queue<pTrieNode> que=queue<pTrieNode>();
que.push(pNode);
//begin visit by queue
int cur_lev=pNode->level;
while(!que.empty())
{
pTrieNode pNode=que.front();
que.pop();
if(cur_lev<pNode->level)
{
cout<<"-->"<<endl;
cur_lev++;
}
VisitNode(pNode);
if(pNode->child_list.size()>0)
{
for(vector<pTrieNode>::const_iterator it=pNode->child_list.begin();it<pNode->child_list.end();it++)
{
que.push(*it);
}
}
}
cout<<endl;
}
void SuggestionSystem::VisitNode(const pTrieNode pNode)
{
cout<<pNode->value<<" ";
}
int main(int argc,char *argv[])
{
cout<<"developed: chen qin"<<endl;
cout<<__DATE__<<" "<<__TIME__<<endl;
vector<string> words;
words.push_back("abc");
words.push_back("bcdf");
words.push_back("abde");
words.push_back("bce");
words.push_back("ad");
words.push_back("abcf");
words.push_back("abce");
words.push_back("bcef");
words.push_back("bcde");
SuggestionSystem ss(words);
ss.DisplayTree();
cout<<"find subquences of ab:"<<endl;
ss.FindSubsequencesOfGivenString("ab");
cout<<"find subquences of bc:"<<endl;
ss.FindSubsequencesOfGivenString("bc");
cout<<"find subquences of abc:"<<endl;
ss.FindSubsequencesOfGivenString("abc");
return 0;
}
4. 人搜笔试题
1，快排每次以第一个作为主元，问时间复杂度是多少？（O(N*logN)）
2，T(N) = N + T(N/2)+T(2N), 问T(N)的时间复杂度是多少？
点评：O(N*logN) or O(N)？
求解数列T通项？
典型求解递归式时间复杂度题目，可以看看这里：http://www.cnblogs.com/web-application-security/archive/2012/06/15/how_to_solve_recurrences.html
3，链表相邻元素翻转，如a->b->c->d->e->f-g，翻转后变为：b->a->d->c->f->e->g。
我写了一个，复杂度为O(n)。
/*
* reverse two near nodes in a link list,for expample:
* a->b->c->d->e->f to b->a->d->c->f->e
*/
#include<stdio.h>
#include<stdlib.h>
typedef struct _Node
{
char data;
struct _Node *next;
}Node,*pNode;
void reverse_node(pNode pre,pNode first,pNode second);
pNode reverse(pNode list)
{
if(NULL==list||NULL==list->next) return list;
pNode first=list,second=list->next,pre=NULL;
list=list->next;
while(first&&second)
{
reverse_node(pre,first,second);
pre=first;
first=first->next;
if(NULL==first) break;
second=first->next;
}
return list;
}
void reverse_node(pNode pre,pNode first,pNode second)
{
if(NULL==pre)
{
first->next=second->next;
second->next=first;
}else
{
pre->next=second;
first->next=second->next;
second->next=first;
}
}
pNode create_list()
{
char dat;
pNode list=NULL,last=NULL;
while(1)
{
scanf("%c",&dat);
if('#'==dat) break;
pNode pn=(pNode)malloc(sizeof(Node));
pn->data=dat;
pn->next=NULL;
if(NULL==list)
{
list=pn;
last=pn;
}else
{
last->next=pn;
last=pn;
}
}
return list;
}
void show_list(const pNode list)
{
if(NULL==list) return;
printf("list data:");
pNode p=list;
while(p)
{
printf("%c->",p->data);
p=p->next;
}
printf("NULL\n");
}
int main(int argc,char *arv[])
{
pNode list=create_list();
printf("list before reverse.\n");
show_list(list);
list=reverse(list);
printf("list after reverse.\n");
show_list(list);
}
4，编程题：
一棵树的节点定义格式如下：
struct Node{
Node* parent;
Node* firstChild; // 孩子节点
Node* sibling; // 兄弟节点
}
要求非递归遍历该树。
思路：采用队列存储，来遍历节点。与树的层序遍历相似，算法过层如下：
首先将树根节点压入队列，然后队列弹出一个节点，访问该节点，如果这个节点有兄弟节点，则将兄弟节点压入队列，有孩子节点则将孩子节点压入队列。
队列再次弹出一个节点，按照上述步骤处理，直到对空为止。
5，有N个节点，每两个节点相邻，每个节点只与2个节点相邻，因此，N个顶点有N-1条边。每一条边上都有权值wi，定义节点i到节点i+1的边为wi。
求：不相邻的权值和最大的边的集合。
解答：
动态规划求解，这里有完美解答：http://blog.csdn.net/realxie/article/details/8063885
5.人搜面试，所投职位：搜索研发工程师：面试题回忆
1，删除字符串开始及末尾的空白符，并且把数组中间的多个空格（如果有）符转化为1个。
我写了一个，时间复杂度为O(n)：
/*
* trim the space before and after a string,and change the spaces more than two inner the stirng into one.
* for example,input:"___a__bc__d_e__fgh_____"
* output should be:"a_bc_d_e_fgh".
*/
#include<stdio.h>
#include<stdlib.h>
char * const trim_space(char * const str)
{
if(NULL==str) return NULL;
char *first=str,*last=str;
//find the first charactor that is not a space
while(*first=='_'&&*first!='\0') first++;
if('\0'==*first) return "_";
//trim the space before the string
while('\0'!=*first) *last++=*first++;
*last='\0';
first=str;
last=str;
//trim the space inner and after the string
while('\0'!=*first)
{
while('_'!=*first&&'\0'!=*first) first++;
if('\0'==*first)
{
return str;
}
//first point to the first space inner the string
last=first;
while('_'==*last&&'\0'!=*last) last++;
if('\0'==*last)//end with *(--first) and spaces
{
*first='\0';
return str;
}
if(last-first>1)//more than one spaces
{
//trim spaces between first and last,leave one
first++;
while('\0'!=*last&&'_'!=*last)
{
*first++=*last;
*last='_';
last++;
}
if('\0'==*last)
{
*first='\0';
return str;
}
}else
{
first=last+1;
}
}
return str;
}
int main(int argc,char *argv[])
{
char str[]="___a__bc__d_e__fgh_____";
printf("original string: %s\n",str);
printf("after trim spaces: %s\n",trim_space(str));
char str2[]="___a_b__c_d_e__fgh";
printf("original string: %s\n",str2);
printf("after trim spaces: %s\n",trim_space(str2));
char str3[]="a__bc__d_e__fgh_____";
printf("original string: %s\n",str3);
printf("after trim spaces: %s\n",trim_space(str3));
return 0;
}
2，求数组（元素可为正数、负数、0）的最大子序列和。
思路，比较简单就是连续求和，碰到和低于零再从下一个开始重新求和，我写了一个：
/*
* get the max sum of the sub sunmbers of a array.
* for example: 5 -6 1 2 4 -9 1 3
* the sub max sum array is 1 2 4,sum is 7
*/
#include<stdio.h>
int get_max_sub_sum(int data[],int length,int *start,int *end)
{
int sum=0,max=0;
int s=0,e=0,l=0,r=0;
while(r<length)
{
sum+=data[r];
if(sum>max)
{
max=sum;
s=l;
e=r;
}
if(sum<=0)
{
l=r+1;
sum=0;
}
r++;
}
*start=s;
*end=e;
return max;
}
int main(int argc,char *argv[])
{
int d[10]={3,5,-6,1,2,4,-9,1,3};
int s=0,e=0,max=0;
max=get_max_sub_sum(d,9,&s,&e);
printf("max array:\n");
int i;
for(i=s;i<=e;i++)
{
printf("%d ",d[i]);
}
printf("the max sum:%d\n",max);
return 0;
}
3，从（0,1）中平均随机出几次才能使得和超过1？（e）
思路：数学功底
让我们先来看一个更简单的问题：任取两个 0 到 1 之间的实数，它们的和小于 1 的概率有多大？容易想到，满足 x+y<1 的点 (x, y) 占据了正方形 (0, 1)×(0, 1) 的一半面积，因此这两个实数之和小于 1 的概率就是 1/2 。类似地，三个数之和小于 1 的概率则是 1/6 ，它是平面 x+y+z=1 在单位立方体中截得的一个三棱锥。这个 1/6 可以利用截面与底面的相似比关系，通过简单的积分求得：
∫(0..1) (x^2)*1/2 dx = 1/6
可以想到，四个 0 到 1 之间的随机数之和小于 1 的概率就等于四维立方体一角的“体积”，它的“底面”是一个体积为 1/6 的三维体，在第四维上对其进行积分便可得到其“体积”
∫(0..1) (x^3)*1/6 dx = 1/24
依此类推， n 个随机数之和不超过 1 的概率就是 1/n! ，反过来 n 个数之和大于 1 的概率就是 1 - 1/n! ，因此加到第 n 个数才刚好超过 1 的概率就是
(1 - 1/n!) - (1 - 1/(n-1)!) = (n-1)/n!
因此，要想让和超过 1 ，需要累加的期望次数为
∑(n=2..∞) n * (n-1)/n! = ∑(n=1..∞) n/n! = e
解：根据公式， ∑(n=0...∞)1/n!=e，可得∑(n=1...∞)1/n!=e-1，故原试∑(n=1..∞) n/n!=1+∑(n=2..∞) 1/(n-1)!=1+∑(n=1..∞)1/n!=1+e-1=e，大功告成！
4，链表克隆。链表的结构为：
typedef struct list {
int data; //数据字段
list *middle; //指向链表中某任意位置元素(可指向自己)的指针
list *next;//指向链表下一元素
} list;
思路：复杂链表的复制，采用交错复制法达到O(n)时间复杂度，这里有完美解答：复杂链表复制
5，100万条数据的数据库查询速度优化问题，解决关键点是：根据主表元素特点，把主表拆分并新建副表，并且利用存储过程保证主副表的数据一致性。（不用写代码）
6，求正整数n所有可能的和式的组合（如；4=1+1+1+1、1+1+2、1+3、2+1+1、2+2）。点评：这里有一参考答案：http://blog.csdn.net/wumuzi520/article/details/8046350。
看过后我也写了一个：
/*
* find the possible combination of a integer.
* for example:4=1+1+1+1=1+2+1=1+3=2+2
*/
#include<stdio.h>
void find_combination_by_num(int sum,int num,int *pdata,int depth)
{
if(sum<0||pdata==NULL) return;
if(num==1)
{
pdata[depth]=sum;
int i=0;
for(;i<=depth;i++)
{
printf("%d ",pdata[i]);
}
printf("\n");
return;
}
int i=0;
if(depth==0)
{
i=1;//index form 1 when start.
}else//index from the last i
{
i=pdata[depth-1];
}
for(;i<=sum/num;i++)
{
pdata[depth]=i;
find_combination_by_num(sum-i,num-1,pdata,depth+1);
}
}
void find_all_combinations(int sum,int *pdata)
{
printf("all combinatins of %d:\n",sum);
int i=2;
for(;i<=sum;i++)
{
find_combination_by_num(sum,i,pdata,0);
}
}
int main(int argc,char *argv[])
{
int data[10]={0};
find_all_combinations(10,data);
return 0;
}
7，求旋转数组的最小元素（把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个排好序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3, 4, 5, 1, 2}为{1, 2, 3, 4, 5}的一个旋转，该数组的最小值为1）。
思路：
除了正常情况，还要注意考虑三种特殊情况：
(1). 数组是没有发生过旋转的 {1,2,3,4,5,6}
(2). 全相等的数组 {1,1,1,1,1,1}
(3). 大部分都相等的数组 {1,0,1,1,1,1}
二分查找的思路，最开始 如果数组没有旋转过，直接返回第一个元素，就是最小的元素; 如果旋转过，再按后续
首先获得 mid。 此时 ，若
(1) 如果 ar[mid] > ar[left], 代表最小值肯定在后半区 left = mid + 1
(2) 如果 ar[mid] < ar[left], 代表最小值肯定是在前半区到mid之间的（mid也有可能是最小值）， right = mid
(3) 如果 ar[mid] == ar[left], 这种情况不好说了，需要进一步分析：
（1）若 ar[mid] == ar[right] , 最麻烦的情况，前中后都相等，只好排除首尾，继续找 left++ right--
（2）若 ar[mid] < ar[right], 代表最小值肯定在前半区， right = mid
（3）若 ar[mid] > ar[right], 代表最小值肯定在后半区， left = mid + 1
基于次我写了一个：
/*
* find min number in a sorted array after change.
* for example:345612,the min is 1
* the complexity of time shold be under O(n).
*/
#include<stdio.h>
int find(const int data[],int length)
{
if(data==NULL) return -1;
int i=0;
printf("the original data:\n");
for(;i<length;i++)
{
printf("%d ",data[i]);
}
printf("\n");
if(data[0]<data[length-1]) return data[0];
int start=0,end=length-1,mid=length/2;
while(start<end)
{
if(data[mid]>data[start])
{
start=mid+1;
}else if(data[mid]<data[start])
{
end=mid;
}else
{
if(data[mid]==data[end])
{
start++;
end--;
}else if(data[mid]>data[end])
{
start=mid+1;
}else if(data[mid]<data[end])
{
end=mid;
}
}
mid=(start+end)/2;
}
return data[end];
}
int main(int argc,char *argv[])
{
int data[10]={4,5,6,7,8,9,10,1,2,3};
int res=find(data,10);
printf("find min:%d\n",res);
int data2[10]={1,1,1,1,1,1,1,1,1,1};
res=find(data2,10);
printf("find min:%d\n",res);
int data3[10]={1,1,1,0,0,1,1,1,1,1};
res=find(data3,10);
printf("find min:%d\n",res);
}
8，找出两个单链表里交叉的第一个元素
思路：求出两个链表长度L1和L2，假设L1>L2，长的链表先移动L2-L1次，然后两个链表分别比较相应元素直到相等或结束为止。
写代码时注意边界问题即可，十分简单代码略。
9，字符串移动（字符串为*号和26个字母的任意组合，把*号都移动到最左侧，把字母移到最右侧并保持相对顺序不变），要求时间和空间复杂度最小
与第一题类似，不过比它简单，只要维护两个指针，一指向字符串第一个非*字符，一个指向其后的第一个*字符，然后二者交换并且都右移一位即可。
我写了一个：
/*
* move all the '*' in a string to the left
* for example: "a*fc*3**fdj*3" the result is "*****afc3fdj3"
*/
#include<stdio.h>
void foo(char *str)
{
printf("string before foo:%s\n",str);
if(str==NULL) return ;
int left=0,right=0;
while(str[left]!='\0'&&str[right]!='\0')
{
while(str[left]!='\0'&&str[left]=='*') left++;
if(str[left]=='\0') break;
right=left+1;
while(str[right]!='\0'&&str[right]!='*') right++;
if(str[right]=='\0') break;
char temp=str[left];
str[left]=str[right];
str[right]=temp;
left++;
right++;
}
printf("string after foo:%s\n",str);
}
int main(int argc,char *argv[])
{
char str[20]="***ad*h**f****";
foo(str);
char str1[20]="a*d**h***f";
foo(str1);
char str2[20]="***a*d*h**fhg";
foo(str2);
char str3[20]="a*d*h**f**g***";
foo(str3);
return 0;
}
10，时间复杂度为O(1)，怎么找出一个栈里的最大元素
思路：比较简单，新建一个辅助栈即可，里面存放当前栈中最大元素，当数据栈中压入一个数时如果这个数比辅助栈栈顶元素大则同步压入辅助栈，否则压入辅助栈栈顶元素，弹出时辅助栈弹出一个元素即可，那么数据栈中当前最大元素就是辅助栈中的栈顶元素。
代码简单略。
11，线程、进程区别
答案见3.百度笔试题第二小题。
12，static在C和C++里各代表什么含义
对于局部变量和全局变量（函数）而言static的作用C和C++一样。
（1）局部变量
在C/C++中, 局部变量按照存储形式可分为三种auto, static, register
与auto类型(普通)局部变量相比, static局部变量有三点不同
1. 存储空间分配不同
auto类型分配在栈上, 属于动态存储类别, 占动态存储区空间, 函数调用结束后自动释放, 而static分配在静态存储区, 在程序整个运行期间都不释放. 两者之间的作用域相同, 但生存期不同.
2. static局部变量在所处模块在初次运行时进行初始化工作, 且只操作一次
3. 对于局部静态变量, 如果不赋初值, 编译期会自动赋初值0或空字符, 而auto类型的初值是不确定的. (对于C++中的class对象例外, class的对象实例如果不初始化, 则会自动调用默认构造函数,不管是否是static类型)
特点: static局部变量的”记忆性”与生存期的”全局性”
所谓”记忆性”是指在两次函数调用时, 在第二次调用进入时, 能保持第一次调用退出时的值.
（2）外部（全局）静态变量/函数
在C中 static有了第二种含义：用来表示不能被其它文件访问的全局变量和函数。但为了限制全局变量/函数的作用域, 函数或变量前加static使得函数成为静态函数。但此处“static”的含义不是指存储方式，而是指对函数的作用域仅局限于本文件(所以又称内部函 数)。注意此时, 对于外部(全局)变量, 不论是否有static限制, 它的存储区域都是在静态存储区,
生存期都是全局的. 此时的static只是起作用域限制作用, 限定作用域在本模块(文件)内部.使用内部函数的好处是：不同的人编写不同的函数时，不用担心自己定义的函数，是否会与其它文件中的函数同名.
（3）C++中静态数据成员/成员函数
C+ +重用了这个关键字，并赋予它与前面不同的第三种含义：表示属于一个类而不是属于此类的任何特定对象的变量和函数. 这是与普通成员函数的最大区别,
也是其应用所在, 比如在对某一个类的对象进行计数时, 计数生成多少个类的实例,
就可以用到静态数据成员. 在这里面, static既不是限定作用域的, 也不是扩展生存期的作用, 而是指示变量/函数在此类中的唯一性. 这也是”属于一个类而不是属于此类的任何特定对象的变量和函数”的含义. 因为它是对整个类来说是唯一的,
因此不可能属于某一个实例对象的. (针对静态数据成员而言, 成员函数不管是否是static, 在内存中只有一个副本, 普通成员函数调用时, 需要传入this指针, static成员函数调用时, 没有this指针. )
13，const 在C/C++里什么意思
在C中，const可以用来修饰常量，函数参数和函数返回值，C++const除了C中用法外还可以用来修饰常成员函数。
具体可以看着里：http://blog.csdn.net/kevinguozuoyong/article/details/5904627
14，常用linux命令
hostname:显示主机名
uname:显示系统信息
cut：用来移除文件的部分内容。
diff：用来找出两个文件的不同之处。
du： 用来显示磁盘的剩余空间的大小。
file：用来显示文件的类型。
find：用来在目录中搜索文件，并执行指定的操作。
head：只查看文件的头
source：使得刚修改的文件生效
read:从标准设备读入
cat：可以显示文件的内容（经常和more搭配使用），或将多个文件合并成一个文件。
chgrp：用来改变文件或目录所属的用户组，命令的参数以空格分开的要改变属组的文件列表，文件名支持通配符，如果用户不是该文件的所有者，则不能改变该文件的所属组。
chmod：用于改变文件或目录的访问权限，该命令有两种用法：一种是使用图形化的方法，另一种是数字设置法。
chown：用来将指定用户或组为特定的所有者。用户可以设置为用户名或用户ID，组可以是组名或组ID。特定的文件是以空格分开的可以改变权限的文件列表，文件名支持通配符。
clear：用来清除终端屏幕。
cd directory 进入指定的目录
cd .. 进入上一级目录
cd /directory 进入目录
cd 进入用户自己的目录
cp file_from file_to 拷贝文件
ln [-s] source linkname 为一个文件建立连结
ls [directory] 查看指定目录下的文件
ls -l [directory] 查看指定目录下文件的详细
ls -a [directory] 查看指定目录下的所有文件
mkdir new_directory 建一个新目录
more file 查看一个文本文件的内容
rm file 删除一个文件
rm -r directory 删除一个目录
rmdir directory 删除一个目录
find . -name "file" 从当前目录开始查找指定的文件
adduser 创建新用户
alias 设置别名或替代名
bg fg 使挂起的进程继续运行
ps ax 查询当前进程
mount 连接文件系统
more less 浏览文件内容
chown chgrp 改变文件的拥有者
chmod 改变文件属性
halt 关闭系统
man 显示手册页
passwd 改变用户口令
grep 查找字符串
find 查找文件
dd 复制磁盘或文件系统
kill 杀掉一个进程
killall 杀掉进程
15，解释Select/Poll模型
I/O复用模型（Select/Poll）
I/O复用模型会用到select或者poll函数，这两个函数也会使进程阻塞，但是和阻塞I/O所不同的的，这两个函数可以同时阻塞多个I/O操作。而且可以同时对多个读操作，多个写操作的I/O函数进行检测，直到有数据可读或可写时，才真正调用I/O操作函数。
详细信息请看：http://hi.baidu.com/nivrrex/item/54f782cfe821ef09c710b2a6
6，网易有道二面
判断一个数字序列是BST【二叉排序树(Binary Search Tree：BST)】后序遍历的结果，现场写代码。
思路：采用递归判断，一颗二叉树包含左子树，右子树以及根结点，根据二叉排序树的特新，左子树的所有结点均小于根结点，而右子树的所有结点均大于根结点，利用这个特新可以用来递归判断是否是二叉树的序列。对于后序遍历，最后一个数是根结点，其中要点是找到左子树与右子树的分界点，由二叉树的性质可知第一个大于根节点的数即是右子树中的节点，由此可以区分左子树与右子树。
我写了一个：
/*
* judge an array whether is a post order of a binary search tree.
* for example:4 8 7 11 14 12 9 is yes,4 11 7 8 14 12 9 is no!
*/
#include<stdio.h>
bool judge_post_of_BST(const int data[],int start,int end);
void judge(const int data[],int length)
{
if(data==NULL) return;
printf("the array is:\n");
int i=0;
while(i<length) printf("%d ",data[i++]);
printf("\n");
bool res=judge_post_of_BST(data,0,length-1);
if(res) printf("the array is a post order of BST.\n");
else printf("the array is not a post order of BST!\n");
}
bool judge_post_of_BST(const int data[],int start,int end)
{
if(start>=end) return true;
int index_right=-1,i=0;
for(i=start;i<=end;i++)
{
if(index_right!=-1&&data[i]<data[end]) return false;
if(index_right==-1&&data[i]>data[end]) index_right=i;
}
bool l=false,r=false;
l=judge_post_of_BST(data,start,index_right-1);
r=judge_post_of_BST(data,index_right,end-1);
return l&&r;
}
int main(int argc,char *argv[])
{
int data[7]={4,8,7,11,14,12,9};
judge(data,7);
int data2[7]={4,11,7,8,14,12,9};
judge(data2,7);
return 0;
}
7，8月30日，网易有道面试题
var tt = 'aa';
function test()
{
alert(tt);
var tt = 'dd';
alert(tt);
}
test();
什么意思？要求干嘛？是写出打印结果还是改错？
8，8月31日，百度面试题：不使用随机数的洗牌算法
这里有一堆大牛的讨论：http://bbs.csdn.net/topics/390195922
9，9月6日，阿里笔试题：平面上有很多点，点与点之间有可能有连线，求这个图里环的数目。
可以看看这里：http://blog.csdn.net/chinaczy/article/details/5730601
10，9月7日，一道华为上机题：
题目描述: 选秀节目打分，分为专家评委和大众评委，score[] 数组里面存储每个评委打的分数，judge_type[] 里存储与 score[] 数组对应的评委类别，judge_type == 1，表示专家评委，judge_type == 2，表示大众评委，n表示评委总数。打分规则如下：专家评委和大众评委的分数先分别取一个平均分（平均分取整），然后，总分 = 专家评委平均分 * 0.6 + 大众评委 * 0.4，总分取整。如果没有大众评委，则
总分 = 专家评委平均分，总分取整。函数最终返回选手得分。
函数接口 int cal_score(int score[], int judge_type[], int n)
上机题目需要将函数验证，但是题目中默认专家评委的个数不能为零，但是如何将这种专家数目为0的情形排除出去。
思路：比较简单，只要注意只有专家评委和只有大众评委的情况，代码略。
11，9月8日，腾讯面试题：
假设两个字符串中所含有的字符和个数都相同我们就叫这两个字符串匹配，
比如：abcda和adabc,由于出现的字符个数都是相同，只是顺序不同，
所以这两个字符串是匹配的。要求高效！
又是跟上述第3题中简单题一的兄弟节点类似的一道题，我想，你们能想到的，这篇blog里：http://blog.csdn.net/v_JULY_v/article/details/6347454都已经有了。
12，阿里云，搜索引擎中5亿个url怎么高效存储；
思路：B+数，分布式存储
13，一道C++笔试题，求矩形交集的面积：
在一个平面坐标系上，有两个矩形，它们的边分别平行于X和Y轴。
其中，矩形A已知， ax1(左边), ax2（右边）, ay1（top的纵坐标）, ay2（bottom纵坐标）. 矩形B，类似，就是 bx1, bx2, by1, by2。这些值都是整数就OK了。
要求是，如果矩形没有交集，返回-1， 有交集，返回交集的面积。
int area(rect const& a, rect const& b)
{
...
}
点评：
healer_kx：
补齐代码，最好是简洁的，别用库。你可以写你的辅助函数，宏定义，代码风格也很重要。
ri_aje：
struct rect
{
// axis alignment assumed
// bottom left is (x[0],y[0]), top right is (x[1],y[1])
double x [2];
double y [2];
};
template <typename T> T const& min (T const& x, T const& y) { return x<y ? x : y; }
template <typename T> T const& max (T const& x, T const& y) { return x>y ? x : y; }
// return type changed to handle non-integer rects
double area (rect const& a, rect const& b)
{
// perfectly adjacent rects are considered having an intersection of 0 area
double const dx = min(a.x[1],b.x[1]) - max(a.x[0],b.x[0]);
double const dy = min(a.y[1],b.y[1]) - max(a.y[0],b.y[0]);
return dx>=0&&dy>=0 ? dx*dy : -1;
}
下面是一个简短的证明。
对于平行于坐标轴的矩形 r，假设其左下角点坐标为 (rx0,ry0)，右上角点坐标为 (rx1,ry1)，那么由 r 定义的无限有界点集为：{(x,y)|x in [rx0,rx1] && y in [ry0,ry1]}。
根据交集的定义，则任意二维点 (x,y) 在矩形 a,b 的交集内等价于
{(x,y)|(x,y) in a 并且 (x,y) in b} <==>
{(x,y)|x in [ax0,ax1] && x in [bx0,bx1] 并且 y in [ay0,ay1] && y in [by0,by1]} <==>
{(x,y)|x in [max(ax0,bx0),min(ax1,bx1)] 并且 y in [max(ay0,by0),min(ay1,by1)]}
因此，交集矩形的边长分别为 min(ax1,bx1)-max(ax0,bx0) 和 min(ay1,by1)-max(ay0,by0)。注意当交集为空时(a,b 不相交)，则经此法计算出来的交集边长为负值，此事实可用于验证 a,b 的相交性。
鉴于笛卡尔积各个维度上的不相关性，此方法可扩展到任意有限维线性空间，比如，三维空间中平行于坐标轴的长方体的交集体积可以用类似的方法计算。
来源：http://topic.csdn.net/u/20120913/18/bc669d60-b70a-4008-be65-7c342789b925.html。
14，2012年创新工场校园招聘最后一道笔试题：工场很忙
创新工场每年会组织同学与项目的双选会，假设现在有M个项目，编号从1到M，另有N名同学，编号从1到N，每名同学能选择最多三个、最少一个感兴趣的项目。选定之后，HR会安排项目负责人和相应感兴趣的同学一对一面谈，每次面谈持续半小时。由于大家平时都很忙，所以咱们要尽量节约时间，请你按照以下的条件设计算法，帮助HR安排面试。
1）同学很忙。项目负责人一次只能与一名同学面谈，而同学会在自己第一个面试开始时达到工场，最后一个面试结束后离开工场，如果参加一个项目组的面试后不能立即参加下一个项目组的面试，就必须在工场等待。所以请尽可能让同学的面试集中在某一时间段，减少同学在工场等待的时间。
2）项目负责人很忙。众所周知，创业团队的负责人会有很多事情要做，所以他们希望能够将自己参与的面试集中在某一段时间内，请在保证1）的情况下，使得项目负责人等待的时间最少。
3）HR很忙。从第一轮面试开始以后，所有HR都必须等到最后一轮面试结束，所以需要在保证1）和2）的同时，也能尽快解放掉所有的HR，即让第一轮面试到最后一轮面试之间持续的时间最短。
输入(以文件方式输入，文件名为iw，例如iw.in)：
第1行...第n行：同学的编号 项目的编号
样例（数据间用空格隔开,两个0表示输入结束）：
1 1
1 2
1 3
2 1
3 1
3 2
0 0
表示M=3，N=3，编号为1的同学选择了项目1,2和3，编号为2的同学选择了项目1，编号为3的同学选了项目1和2
输出(以文件方式输出，文件名为iw，例如iw.out)：
第1行：编号为1的项目依次面试新同学的编号序列
第2行：编号为2的项目依次面试新同学的编号序列
...
第n行：编号为n的项目依次面试新同学的编号序列
样例（数据间用空格隔开，0表示没有面试）：
1 3
2
3 1
0
0 0
1
表示编号为1的项目在第一轮面试编号为1的同学，第二轮面试编号为3的同学，第三轮面试编号为2的同学
编号为2的项目在第一轮面试编号为3的同学，第二轮面试编号为1的同学，第三轮不用面试
编号为3的项目在第一轮和第二轮都不用面试，第三轮面试编号为1的同学
链接：http://t.qq.com/p/t/108332110988802。
我的思路：
按顺序分别安排每一个同学，安排一个同学面试的算法如下：
设项目组为个数为M，同学个数为N，同学编号为i,每一个项目设置一个二维矩阵matrix[M][3*N]，表示每个项目安排同学面试的序列，矩阵初始为空，其中数字代表学生编号，每个项目序列数组初始大小为N*3，设置一个大小为[N][M]的数组data，保存每个同学选择面试的项目序列。
1）i取值0...N-1，对于编号为i的同学，从1...3*M取值k遍历
2）matrix[x][y]，x取值0...M-1，y取值k，依次遍历matrix[x][y]，记录下其中x值为data[k]非0值的元素且matrix[x][y]为空的位置对应项目，没找到则k++
3）k>3*M则动态扩展matrix对应序列的大小。
3)在这些项目中选择面试序列数组中剩下空位最多的一个s，将其分配给i同学面试，matrix[s][k]=0，同时把i同学对应项目的值设为0表示已安排：data[i][s]=0，直到data[i]中数组值全为0即该同学所有项目面试都安排了为止，再i++回到1）。
我写了一个（时间和空间复杂度较高，假如有更好的解法欢迎指正）：
#include<stdio.h>
#include<iostream>
#include<stdlib.h>
#include<string.h>
using namespace std;
typedef struct _Project
{
int no;//the number of project
int *stuArray;//the array of the student arrangment
int size;//the size of the array
//int size_left;//the left size of the array
}Project,*pProject;
typedef struct _Student
{
int no;//the number of the student
int *proArray;//the array of the projects that he chose
int size;//
int size_left;//
}Student,*pStudent;
class Match
{
public:
Match(const char *filename,int _M,int _N);
private:
void Init();
void LoadDataFromFile(FILE* fp);
void StartMatch();
void StoreResult(FILE *fp);
int M,N;//the number of projects and students
pProject mpProjects;//the total projects
pStudent mpStudents;//the total students
};
Match::Match(const char *filename,int _M,int _N):M(_M),N(_N)
{
Init();
if(filename==NULL) return;
FILE *fp;
if((fp=fopen(filename,"r"))==NULL)
{
cout<<"open file failed!"<<endl;
return;
}
LoadDataFromFile(fp);
fclose(fp);
StartMatch();
if((fp=fopen("out.txt","wt"))==NULL)
{
cout<<"open file failed!"<<endl;
return;
}
StoreResult(fp);
fclose(fp);
}
void Match::Init()
{
mpProjects=new Project[M];
int i,j;
for(i=0;i<M;i++)
{
mpProjects[i].no=i+1;
mpProjects[i].stuArray=new int[3*N];
mpProjects[i].size=0;
//mpProjects[i].size_left=0;
for(j=0;j<3*N;j++)
{
mpProjects[i].stuArray[j]=-1;//initial
}
}
mpStudents=new Student[N];
for(i=0;i<N;i++)
{
mpStudents[i].no=i+1;
mpStudents[i].proArray=new int[M];
mpStudents[i].size=0;
mpStudents[i].size_left=0;
for(j=0;j<M;j++)
{
mpStudents[i].proArray[j]=-1;//
}
}
}
void Match::LoadDataFromFile(FILE *fp)
{
char ch;
int p=-1,s=-1;
bool change=false;
printf("input data:\n");
while((ch=fgetc(fp))!=EOF)
{
if(ch=='0') break;
if(ch=='\n')//set data
{
int k=0;
while(mpStudents[s-1].proArray[k]!=-1) k++;
mpStudents[s-1].proArray[k]=p-1;
mpStudents[s-1].size++;
mpStudents[s-1].size_left++;
printf("%d,%d\n",s,p);
s=-1,p=-1;
change=false;
}
else
{ if(ch>='0'&&ch<='9')
{
if(!change)//input the first number whitch represents student
{
if(s==-1) s=ch-'0';
else s=s*10+ch-'0';
}else//input the second number whitch represent project
{
if(p==-1) p=ch-'0';
else p=p*10+ch-'0';
}
}else if(ch==' ')
{
change=true;
}
}
}
}
void Match::StartMatch()
{
int i;
for(i=0;i<N;i++)//through N students
{
int order=0;
int match=0;
const int S=M;
int chose[S];
memset(chose,0,sizeof(int)*S);
while(mpStudents[i].size_left>0)
{
int j;
match=0;
for(j=0;j<mpStudents[i].size;j++)
{
if(mpStudents[i].proArray[j]==-2) continue;//already arranged
int pro=mpStudents[i].proArray[j];
if(mpProjects[pro].stuArray[order]==-1)
{
chose[match++]=pro;
}
}
if(match>0)//find match projects
{
if(match==1)//only one project match
{
int p=chose[0];
mpProjects[p].stuArray[order]=i;
mpProjects[p].size++;
int k=0;
while(mpStudents[i].proArray[k]!=p) k++;
mpStudents[i].proArray[k]=-2;//arrange this project,set 0
mpStudents[i].size_left--;
}else//more than one matched,chose the one whitch left_size is max
{
int i_min=0;
int k,min=0;
for(k=0;k<match;k++)
{
int c=chose[k];
if(mpProjects[c].size<min) i_min=k;
}
int p=chose[i_min];
mpProjects[p].stuArray[order]=i;
mpProjects[p].size++;
k=0;
while(mpStudents[i].proArray[k]!=p) k++;
mpStudents[i].proArray[k]=-2;//arrange this project,set 0
mpStudents[i].size_left--;
}
}
order++;
}
}
}
void Match::StoreResult(FILE *fp)
{
printf("result :\n");
for(int i=0;i<M;i++)
{
printf("project %d:,",i+1);
int j;
char *buf=new char[20];
memset(buf,'\0',20);
char *str=new char[5];
memset(str,'\0',5);
for(j=0;j<mpProjects[i].size;j++)
{
printf("%d ",mpProjects[i].stuArray[j]+1);
sprintf(str,"%d ",mpProjects[i].stuArray[j]+1);
strcat(buf,str);
}
strcat(buf,"\n");
fputs(buf,fp);
printf("\n");
}
printf("write data to file.\n");
}
int main(int argc,char *argv[])
{
Match m("data.txt",4,4);
return 0;
}
15，4**9 的笔试题，比较简单：
1，求链表的倒数第二个节点
思路：两个指针，一前一后，不多说。
2，有一个整数数组，求数组中第二大的数
思路：维护两个数，每次把数组中的数与这两个数比较，比它们中小的大则相互替换，一次类推。
16，阿里巴巴二道题
1，对于给定的整数集合S，求出最大的d，使得a+b+c=d。a,b,c,d互不相同，且都属于S。集合的元素个数小于等于2000个，元素的取值范围在[-2^28，2^28 -
1]，假定可用内存空间为100MB，硬盘使用空间无限大，试分析时间和空间复杂度，找出最快的解决方法。
点评：
@绿色夹克衫：两两相加转为多项式乘法，比如(1 2 4 6) + (2 3 4 5) => (x + x^2 + x^4 + x^6)*(x^2 + x^3 + x^4 + x^5) 。更多思路请见这：
http://www.51nod.com/answer/index.html#!answerId=569
2，原题大致描述有一大批数据，百万级别的。数据项内容是：用户ID、科目ABC各自的成绩。其中用户ID为0~1000万之间，且是连续的，可以唯一标识一条记录。科目ABC成绩均在0~100之间。有两块磁盘，空间大小均为512M，内存空间64M。
1) 为实现快速查询某用户ID对应的各科成绩，问磁盘文件及内存该如何组织；
2) 改变题目条件，ID为0~10亿之间，且不连续。问磁盘文件及内存该如何组织；
3) 在问题2的基础上，增加一个需求。在查询各科成绩的同时，获取该用户的排名，问磁盘文件及内存该如何组织。
思路：1），1000W个数据记录，每个记录采用6个字节存储，大约需要60M，因此可以全部放入内存，又因为ID连续，因此在内存中可以采用数组进行存取数据。
2），采用hash方法，将大量记录hash到两块磁盘上，查询时直接求出hash值找到对应的磁盘记录进行查询。
3），
3，代码实现计算字符串的相似度。
点评：和计算两字符串的最长公共子序列相似。
设Ai为字符串A(a1a2a3 … am)的前i个字符（即为a1,a2,a3 …ai）
设Bj为字符串B(b1b2b3 … bn)的前j个字符（即为b1,b2,b3 …bj）
设 L(i , j)为使两个字符串Ai和Bj相等的最小操作次数。
当ai等于bj时 显然L(i, j)=L(i-1, j-1)
当ai不等于bj时
若将它们修改为相等，则对两个字符串至少还要操作L(i-1, j-1)次
若删除ai或在Bj后添加ai，则对两个字符串至少还要操作L(i-1, j)次
若删除bj或在Ai后添加bj，则对两个字符串至少还要操作L(i, j-1)次
此时L(i, j)=min( L(i-1, j-1), L(i-1, j), L(i, j-1) ) + 1
显然，L(i, 0)=i，L(0, j)=j, 再利用上述的递推公式，可以直接计算出L(i, j)值。具体代码请见这：
http://blog.csdn.net/flyinghearts/article/details/5605996
17，9月14日，小米笔试
给一个浮点数序列，取最大乘积子序列的值，例如 -2.5，4，0，3，0.5，8，-1，则取出的最大乘积子序列为