最新腾讯，创新工场，淘宝等公司最新面试十三题（更新至24题）?int rand7(){return rand()%7+1}int rand10(){
最新腾讯，创新工场，淘宝等公司最新面试十三题（更新至24题）
?
int rand7(){ return rand()%7+1;}int rand10(){ int a71,a72,a10; do { a71= rand7()-1; a72 = rand7()-1; a10 = a71 *7 + a72; } while (a10>= 40); return (a71*7+a72)/4+1;}如果两个字符串的字符一样，但是顺序不一样，被认为是兄弟字符串，问如何在迅速匹配兄弟字符串（如，bad和adb就是兄弟字符串）。要求设计一个DNS的Cache结构，要求能够满足每秒5000以上的查询，满足IP数据的快速插入，查询的速度要快。一个未排序整数数组，有正负数，重新排列使负数排在正数前面，并且要求不改变原来的 相对顺序 比如： input: 1,7,-5,9,-12,15 ans: -5,-12,1,7,9,15 要求时间复杂度O(N),空间O(1) 。（此题一直没看到令我满意的答案，一般达不到题目所要求的：时间复杂度O(N),空间O(1)）淘宝面试题：有一个一亿节点的树，现在已知两个点，找这两个点的共同的祖先。海量数据分布在100台电脑中，想个办法高效统计出这批数据的TOP10。（此题请参考本博客内其它文章）。
某服务器流量统计器，每天有1000亿的访问记录数据，包括时间、url、ip。设计系统实现记录数据的
保存、管理、查询。要求能实现一下功能：
（1）计算在某一时间段（精确到分）时间内的，某url的所有访问量。
（2）计算在某一时间段（精确到分）时间内的，某ip的所有访问量。
?
假设某个网站每天有超过10亿次的页面访问量，出于安全考虑，网站会记录访问客户端访问的ip地址和对应的时间，如果现在已经记录了1000亿条数据，想统计一个指定时间段内的区域ip地址访问量，那么这些数据应该按照何种方式来组织，才能尽快满足上面的统计需求呢，
设计完方案后，并指出该方案的优缺点，比如在什么情况下，可能会非常慢？（参考答案：用B+树来组织，非叶子节点存储（某个时间点，页面访问量），叶子节点是访问的IP地址。这个方案的优点是查询某个时间段内的IP访问量很快，但是要统计某个IP的访问次数或是上次访问时间就不得不遍历整个树的叶子节点。或者可以建立二级索引，分别是时间和地点来建立索引。）
?
腾讯1.服务器内存1G，有一个2G的文件，里面每行存着一个QQ号（5-10位数），怎么最快找出出现过最多次的QQ号。
腾讯2.如何求根号2的值，并且按照我的需要列出指定小数位，比如根号2是1.141 我要列出1位小数就是1.1 2位就是1.14， 1000位就是1.141...... 等。。
?
给定一个字符串的集合，格式如：{aaa bbb ccc}， {bbb ddd}，{eee fff}，{ggg}，{ddd hhh}要求将其中交集不为空的集合合并，要求合并完成后的集合之间无交集，例如上例应输出{aaa bbb ccc ddd hhh}，{eee fff}， {ggg}。
?
创新工场面试题：abcde五人打渔，打完睡觉，a先醒来，扔掉1条鱼，把剩下的分成5分，拿一份走了；b再醒来，也扔掉1条，把剩下的分成5份，拿一份走了；然后cde都按上面的方法取鱼。问他们一共打了多少条鱼，写程序和算法实现。提示：共打了多少条鱼的结果有很多。但求最少打的鱼的结果是3121条鱼（应该找这5个人问问，用什么工具打了这么多条鱼）。（http://blog.csdn.net/nokiaguy/article/details/6800209）。我们有很多瓶无色的液体，其中有一瓶是毒药，其它都是蒸馏水，实验的小白鼠喝了以后会在5分钟后死亡，而喝到蒸馏水的小白鼠则一切正常。现在有5只小白鼠，请问一下，我们用这五只小白鼠，5分钟的时间，能够检测多少瓶液体的成分？
淘宝2012笔试（研发类）：http://topic.csdn.net/u/20110922/10/e4f3641a-1f31-4d35-80da-7268605d2d51.html（一参考答案）。
ok，这13道题加上此前本博客陆陆续续整理的微软面试187题：
int i = 0, count, tmp; while(1) { tmp = ++i; for(count = 0; count < 5; count++) { tmp = ((tmp-1) % 5 == 0)?(tmp-1)/5*4:-1; if(tmp <= 0) break; } if(count == 5) break; } printf("The result is %d\n", i);#include <stdio.h> void nswapvalue(int *arr,int i , int j) { // change positive to negative int m = arr[i]; arr[i] = arr[j]; arr[j] = -m; } void pswapvalue(int *arr,int i , int j) {//change negative to positive int m = arr[i]; arr[i] = -arr[j]; arr[j] = m; } int swaploop(int *arr,int size){//思想：执行一次循环，把所有负数置换到前面，可以保证负数的相对位置不变 int cur = 0,count=0,i; for(i = 0 ;i < size; ++i){ // 把所有负数提前，并把置换到后面的整数变为负数 if(arr[i]>0 && cur ==0){ cur = i; //cur 始终指向最前面的整数 } if(arr[i]<0 && cur < i){ nswapvalue(arr,cur,i); ++cur; ++count; //记录负数的个数 } } for(i = count ;i < size; ++i){ //处理原始负数以后的数据，并把上面变为负数的正数变回来 if(arr[i]>0 && cur ==0){ cur = i; } if(arr[i]<0 && cur < i){ pswapvalue(arr,cur,i); ++cur; } } }int GetMaxStepNormal(int n) { if(n<=0) return 0; if(n==1) return 1; if(n==2) return 2; if(n==3) return 4; int r,r1=1,r2=2,r3=4; for(int i=3;i<n;i++) { r=r1+r2+r3; r1=r2; r2=r3; r3=r; } return r; }
2.递归，注意保存以计算的结果
int GetMaxStepMain(int ,int*);int GetMaxStepRecurs(int n){int* calc;int r;if(n<=0) return 0;calc=new int[n];if(NULL==calc) return 0;for(int i=0;i<n;++i) calc=0;r= GetMaxStepMain(n,calc);delete calc;return r;}int GetMaxStepMain(int n,int* a){int t[3];if(n==1) return 1;if(n==2) return 2;if(n==3) return 4; for(int i=3;i>0;i--){if(a[n-i]==0) {t[i-1]=GetMaxStepMain(n-i,a);a[n-i]=t[i-1];}else{t[i-1]=a[n-i];}}return t[0]+t[1]+t[2];}#include <stdio.h> #include <string.h> int brothstr(const char *s1,int len1,const char *s2,int len2){ if(len1 != len2)return 0; int box[128] = {0}; int i; //pack into box for(i=0;i<len1;++i){ int v = s1[i]; ++box[v]; } //remove from box for(i=0;i<len2;++i){ int v = s2[i]; --box[v]; } // is the box empty? for(i=0;i<len1;++i){ int v = s1[i]; if(box[v]>0)return 0; } return 1; } int main(int argc, const char *argv[]) { if(argc!=3){ printf("%s s1 s2\n",argv[0]); return 1; } char *s1 = (char*)argv[1]; int l1 = strlen(s1); char *s2 = (char*)argv[2]; int l2 = strlen(s2); int isborther = brothstr(s1,l1,s2,l2); isborther? printf("is brother\n",s1,s2):printf("is not brother\n",s1,s2); return 0; }//23、人人笔试1：一个人上台阶可以一次上1个，2个，或者3个，问这个人上n层的台阶，总共有几种走法？ //思路，建模分析得出结果是 所有 (i+j+k)!/(i!*j!*k!) 的和，其中i,j,k满足条件 3*i+2*j+k=n //以下解法暂不考虑数据过大的溢出问题 int CItems::NStepFor123(int n) { int i=0; int j=0; int p; int k; int result=0; for ( i=0; i<=n/3; i++ ) { p = n-i*3; for ( j=0; j<=p/2; j++ ) { k = p -j*2; //求(i+j+k)!/(i!*j!*k!) result += GetComb(i,j,k); } } return result; }int CItems::GetComb(int i,int j,int k) { if ( i+j+k<0 || i<0 || j<0 || k<0) { return 0; } int den=1;//分母 int mun=1;//分子 int p; //临时变量 for ( p = 1;p<=i+j+k; p++ )//求分子 { mun*=p; } if (i>0) //求分母中i!部分 { for ( p = 1;p<=i; p++ ) { den*=p; } } if (j>0)//求分母中i!j!部分 { for ( p = 1;p<=j; p++ ) { den*=p; } } if (k>0)//求分母总值 { for ( p = 1;p<=k; p++ ) { den*=p; } } return (int)(mun/den);//可以用数学方法证明此除法得出的一定是整数 }document.write("没一个会的！")//搜狗笔试题：一个长度为n的数组a[0],a[1],...,a[n-1]。现在更新数组的名个元素，即a[0]变为a[1]到a[n-1]的积，a[1]变为a[0]和a[2]到a[n-1]的积，...，a[n-1]为a[0]到a[n-2]的积。 //程序要求： //要求具有线性复杂度。 //不能使用除法运算符。 #define MAX_ARRAY_SIZE 9 void CItems::GetMultiplay() { int Array[MAX_ARRAY_SIZE]={1,2,3,4,5,6,7,8,9}; int temp1[MAX_ARRAY_SIZE]={0}; int temp2[MAX_ARRAY_SIZE]={0}; temp1[0] = Array[0]; temp2[MAX_ARRAY_SIZE-1] = Array[MAX_ARRAY_SIZE-1]; for ( int j=1; j<MAX_ARRAY_SIZE; j++ ) { temp1[j] = temp1[j-1]*Array[j]; temp2[MAX_ARRAY_SIZE-1-j] = temp2[MAX_ARRAY_SIZE-j]*Array[MAX_ARRAY_SIZE-1-j]; } Array[0] = temp2[1]; Array[MAX_ARRAY_SIZE-1] = temp1[MAX_ARRAY_SIZE-2]; for ( int i = 1; i<MAX_ARRAY_SIZE-1; i++ ) { Array[i]=temp1[i-1]*temp2[i+1]; } for ( int k = 0; k<MAX_ARRAY_SIZE; k++ ) { printf("Array[%d]=%d",i,Array[i]); } return ; }int cacl(int mouse_count, int bottle_count) { int res = 0; for ( i = 1; i <= mouse_count; i++ ) { res += bottle_count/(1<<i); } return res; }int rand10() { int a, b; do { a = rand7(); } while ( a > 5 ); do { b = rand7(); } while ( b > 2 ); return a*2-(b-1); }char const* MI(string const&...[/quote] 接着 [code=cpp] char const* Add(string& x, string const& y) { char const* px = x.c_str(); char const* py = y.c_str(); char const* pxe = px + x.length(); char const* pye = py + y.length(); int carry = 0; list<char> r; for (--pxe, --pye; pxe >= px && pye >= py; --pxe, --pye) { int i = (*pxe - '0') + (*pye - '0') + carry; carry = i / 10; i %= 10; r.push_front(i + '0'); } for (; pxe >= px; --pxe) { int i = (*pxe - '0') + carry; carry = i / 10; i %= 10; r.push_front(i + '0'); } for (; pye >= py; --pye) { int i = (*pye - '0') + carry; carry = i / 10; i %= 10; r.push_front(i + '0'); } return x.assign(r.begin(), r.end() ).c_str(); }char const* MI(string const& x, int y, int z, string &s) { list<char> r; int carry = 0; for (char const* p = x.c_str(), *pe = x.c_str() + x.length() - 1; pe >= p; --pe) { int i = (*pe - '0') * y + carry; carry = i / 10; i %= 10; r.push_front(i + '0'); } if (carry > 0) { r.push_front(carry + '0'); } for (; z > 0; --z) { r.push_back('0'); } return s.assign(r.begin(), r.end() ).c_str(); }void PartitionSort(int q[], int n) { for (int i=n-1, k=0; i>=0; i--) { if (q[i] >= 0) { if (k == 0) continue; int t = q[i]; memmove(&q[i], &q[i+1], k*sizeof(int)); q[i+k] = t; } else k++; } }int total = 0; for (int i = 0; i < 10; i++) { total += Rand7(); } return total / 7;int rand7(); int Random10() { int k, i; while(1) { int i = rand7(); if(i < 6) { k = i; break; } } while(1) { int i = rand7(); if(i < 7) { if(i < 4) { k = k + 5; } break; } } return k; }int X(int iMonkey, int& iPerMonkey) { if (1 == iMonkey) { return 5 * iPerMonkey + 1; } int iLeft = X(iMonkey - 1, iPerMonkey); while (iLeft % 4) { iLeft = X(iMonkey - 1, ++iPerMonkey); } return 1 + 5 * iLeft / 4; }#include<iostream> using namespace std; int main() { char ch[100],ch1[100]; int a[27],b[27]; while(cin >> ch >> ch1) { memset(a,0,27*sizeof(int)); memset(b,0,27*sizeof(int)); int len1 = strlen(ch); int len2 = strlen(ch1); if(len1 != len2) { cout<<"不是兄弟字符串"<<endl; continue; } for(int i=0;i<len1;i++) { a[(int)ch[i] - 97]++; } for(i=0;i<len2;i++) { b[(int)ch1[i] - 97]++; } int flag=1; for(i=0;i<27;i++) { if(a[i] != b[i]) { flag=0; break; } } if(flag) { cout<<"是兄弟字符串"<<endl; } else { cout<<"不是兄弟字符串"<<endl; } } }如果两个字符串的字符一样，但是顺序不一样，被认为是兄弟字符串，问如何在迅速匹配兄弟字符串（如，bad和adb就是兄弟字符串）。 #define TABLE_SIZE 256 int main() { char string1[1000]="bad"; char string2[1000]="adb"; char *pstring1 ; char *pstring2 ; unsigned int hash_table[TABLE_SIZE] = {0}; unsigned int index = 0; pstring1 = string1; pstring2 = string2; while(*pstring1){ hash_table[*pstring1]+=1; printf("%d\r\n", *pstring1); pstring1++; } while(*pstring2){ hash_table[*pstring2]-=1; printf("%d\r\n", *pstring2); pstring2++; } for(index = 0; index < TABLE_SIZE ; index++) if(hash_table[index]!=0) break; if(index == TABLE_SIZE) printf("%s == %s\r\n", string1, string2); else printf("%s != %s\r\n", string1, string2); getchar(); return 0; }c++;
if (c == count + 1) {
return t;
} else {
return split(t, count, c);
}
}
public static void main(String args[]) throws Exception {
System.out.println("mix=" + split(1, 5, 1));
}
}
输入结果:
1->1
2->3
3->10
4->41
5->206
mix=206if (c == 6) {
return t;
} else {
return split(t, count, c);
}
}
public static void main(String args[]) throws Exception {
System.out.println("mix=" + split(1, 5, 1));
}
}
肯定基数为1是最少数，既最后一只猴子吃掉一个，最后拿走一个。如果最后一只猴子不能吃，只能拿走那自己考虑了。
输入结果：
1->2
2->5
3->16
4->65
5->326
mix=326 int Array[7]={1,2,3,4,5,6,7}; int Result[10]={0}; for ( int a1 = 0;a1<7;a1++ )//1 {for (int a2 = 0;a2<7;a2++)//2 {for (int a3 = 0;a3<7;a3++)//3 { for (int a4 = 0;a4<7;a4++)//4 {for (int a5 = 0;a5<7;a5++)//5 {for (int a6 = 0;a6<7;a6++)//6 {for (int a7 = 0;a7<7;a7++)//7 {for (int a8 = 0;a8<7;a8++)//8 {for (int a9 = 0;a9<7;a9++)//9 {for (int a10 = 0;a10<7;a10++)//10 {int k = Array[a1]+Array[a2]+Array[a3]+Array[a4]+Array[a5] +Array[a6]+Array[a7]+Array[a8]+Array[a9]+Array[a10]; k = k%10; Result[k]++; }}}}}}}}}} for ( int j=0; j<10;j++ ) printf("\nResult[%d] Count is :%d ",j,Result[j]);
而楼主发的那种方法显然不太稳定，依赖于rand7()产生两数积少于40，目前我也没找到更好的解决方法。//return:negative count int xsort(int *data, int size) { int neg_num = 0; int pos_p, neg_p; int i, j; for(i = 0; i < size; i++)//总的负数个数 if(data[i] < 0) neg_num++; int pos_num = 0; for(i = 0; i < neg_num; i++) if(data[i] >=0) pos_num++; i = 0, j = size -1; pos_p = neg_num; neg_p = neg_num - 1; while(pos_num > 0){ while(data[i] < 0) i++;//找正数 int tmp = data[i]; int k = i; while(k++ < neg_p)data[k-1] = data[k];//腾出了负数的位置 while(data[j] >=0)j--;//找负数 data[neg_p--] = data[j];//负数搁进去 k = j; while(k-- > pos_p)data[k+1] = data[k];//腾出了正数的位置 data[pos_p++] = tmp;//正数搁进去 pos_num--; } return neg_num; }int n = 0; int m = 0; int p = -1; while (n == 0) { m = rand7(); if (m == 6) { p = 0 } else if (m == 7) { p = 5; } else { if (p >= 0) { n = m + p; } } } return n;}
cout << endl;
}private void aa() { for (int n = 1; n <= 1000000; n++) { if (a1(n)) { MessageBox.Show(n.ToString()); break; } } } private bool a1(int n) { //第一次 if ((n-1)%5==0) { n = ((n - 1) / 5) * 4;//第一次结余数 if ((n - 1) % 5 == 0) { n = ((n - 1) / 5) * 4;//第二次结余数 if ((n - 1) % 5 == 0) { n = ((n - 1) / 5) * 4;//第三次结余数 if ((n - 1) % 5 == 0) { n = ((n - 1) / 5) * 4;//第四次结余数 if ((n - 1) % 5 == 0) { n = ((n - 1) / 5) * 4;//第五次结余数 return true; } } } } }public class peach { public static void main(String []args){ int i,j; int n=6; for(;;){ i=n; for(j=1;j<=6;j++){ if ((i-1)%5 == 0) i= (i-1)*4/5; else break; } if (j == 6) break; n=n+5; } System.out.println("the min number is "+n); } }bool CItems::CheckBrotherString(char *left,char *right) { //把键盘128个字符列举，使用桶排序相关原理实现 char keys[128]; for ( int i = 0; i<128; i++ ) { keys[i]=0; } //遍历第一个字符串，记录字符个数 while ( *left!='\0' ) { keys[*left++]++; } //遍历第二个字符串，记录字符个数 while ( *right!='\0' ) { keys[*right++]--; } for ( int i = 0; i<128; i++ ) { if ( keys[i]!=0) { return false; } } return true; } case 2: //m*k%4 need to equal 2 switch ( m%4 ) { case 1: k = 2; break; case 2: k = 1; break; case 3: printf("ERROR!"); break; default: printf("ERROR!"); break; } break; case 3: //m*k%4 need to equal 1 switch ( m%4 ) { case 1: k = 1; break; case 2: printf("ERROR!"); break; case 3: k = 7; break; default: printf("ERROR!"); break; } break; default: break; } return k; }int CItems::GetKValue(int y,int m) { int k=-1; //let x = y+m*k; //search k st. x is integer //y%5=1;make (m*k)%4 = 3 switch ( y%4 ) { case 0: //m*k%4 need to equal 4 switch ( m%4 ) { case 1: case 3: k = 4; break; case 2: k = 2; break; default: printf("ERROR!"); break; } break; case 1: //(m*k)%4 need to equal 3 switch ( m%4 ) { case 1: k = 3; break; case 2: printf("ERROR!"); break; case 3: k = 1; break; default: printf("ERROR!"); break; } break;void CItems::MonkeyAndPeachs() { //y0-1 = 5*y1/4; //y1-1 = 5*y2/4; //y2-1 = 5*y3/4; //y3-1 = 5*y4/4; //y4-1 = 5*y5/4; int y = 0; //int x = 0; int m = 1; int k = 0; int i; for ( i =0;i<5;i++ ) { if ( (k = GetKValue(y,m))<0 ) { printf("ERROR!"); return ; } //x = y+m*k; //y = x*5/4+1; y = (y+m*k)*5/4+1; m *=5; printf(",%d:%d \n",i,y); } printf("The result is %d",y); return ; }//需要事先知道字符集，假定为26个字母吧 bool matchbrotherstr(char* str1, char* str2) { int s1[26] = {0}, s2[26] = {0}; char *p; for(p = str1; *p != NULL;p++) s1[*p -'a']++; for(p = str2; *p != NULL;p++) s2[*p -'a']++; for(int i = 0; i < 26; i++){ if(s1[i] == s2[i]) continue; else return false; } return true; }int rand7() { return rand()%7 + 1; } int rand10() { int tmp, mid; do{ mid = rand7(); }while(mid == 4); //50%概率 if(mid < 4){//return 1-5 do{ tmp = rand7(); }while(tmp == 1 || tmp == 7); return tmp - 1; }else{//return 6-10 do{ tmp = rand7(); }while(tmp == 1 || tmp == 7); return tmp + 4; } }int _tmain(int argc, _TCHAR* argv[]) { int result = 0; while(true){ int a[6]; a[5] = result*4; int i; for(i = 4; i >=0; i--){ if(a[i+1]%4 == 0){ a[i] = a[i+1]*5/4 + 1; continue; } break; } if(i == -1){ printf("%d", a[0]); break; } else result++; } return 0; } //如果二叉树使用数组顺序存储结构，第一个节点下标是x,第二个节点下标是y; //第0个节点不使用，1为根节点，算法如下 int x =10; int y =100; while(1) { if (x==y) { break; } x>y?x/=2:y/=2; } printf("The parent is %d",x); int Array[10] = { -1,2,-3,4,-5,6,-7,8,-9,10 }; int index_front = 0; int temp; int i; int j; for ( i = 0; i<10; i++ ) { if (Array[i]<0) { temp = Array[i]; for ( j = i;j>index_front; j--) { Array[j] = Array[j-1]; } Array[index_front] = temp; index_front++; } } for ( i = 0; i<10; i++ ) { printf(", %d",Array[i]); }int rand10()
{
return rand7() * rand7() %11
} 1 楼 yuzihan607 2011-09-30 第一题是79年李政道去访问中科大，给当时少年班提出的一个问题，这个你朋友所谓的小学奥数题当时没一人答出，你朋友秒杀了当时的天才们啊
