搜狗笔试感想
选择:
1、顺序、查半、分块、hash查找时间效率比较(顺序<分块<折半<hash)
2、排序空间占用(快排O(lgn),归并O(n),其它O(1))
3、三星指针(理解&a+1和取*操作)
#include <stdio.h> int main() { const char *c[]={"enter", "new", "point", "first"}; const char **cp[]={c+3,c+2,c+1,c}; const char ***cpp = cp; const char ***cpp1 = cp; printf("%s", **++cpp); printf("%s",*--*++cpp+3); printf("%s",*cpp[-2]+3); printf("%s\n",cpp[-1][-1]+1); return 0; }
结果:pointerstew
4、sum和
#include <stdio.h> int main() { short input[10]={'A','B','C','D','E'}; int s = 0; char* p = (char*)input; for(int i=0;i<sizeof(input);++i){ char v = p[i]; if(v>0) s+=v-'A'+i; } printf("%d\n",s ); return 0; }
结果:30
填空:
1、高度为8的AVL树至少节点数(类似于Fibonacci数列求解,54)
2、A、B、C、D四个节点组成二元树种类(求好的解释)
编程:
1、二维数组A[n][n],对数组每一个元素满足A[i][j]>A[i-1][j] && A[i][j]>A[i][j-1](在下标满足条件时),现在实现一个函数find快速查找给定value的元素,如果存在返回true并给出i,j,否则返回false。(折半查找)
#include <stdio.h> const int n = 1024; bool find(int A[n][n], int x1, int x2, int y1, int y2, int value, int& a, int& b) { if(x1==x2 && y1==y2){ if(A[x1][y1]== value){ a = x1, b = y1; return true; }else{ a = b = -1; return false; } }else if(x1>x2 || y1>y2){ a = b = -1; return false; }else{ int i = x1, j = y1; while(i <= x2 || j <= y2){ if(A[i][j] > value){ if(find(A,x1,i-1,j,y2,value,a,b)) return true; else if(find(A,i,x2,y1,j-1,value,a,b)) return true; else return false; }else if(A[i][j] == value){ a = i, b = j; return true;; } if(i>x2 && j>y2) return false; else if(i > x2){ return find(A,x1,x2,j,y2,value,a,b); } else if(j > y2){ return find(A,i,x2,y1,y2,value,a,b); }else{ ++i, ++j; } } } } int main() { int a[n][n]={ {1,2,3,4,6}, {5,7,8,9,10}, {11,12,13,14,16}, {15,17,18,19,20}, {21,22,23,24,25}, }; const int num = 5; for(int i=0;i<num;++i){ for(int j=0;j<num;++j) printf("%d\t", a[i][j]); printf("\n"); } int x, y; int findArray[]={0,1,5,9,10,26,31}; int size = sizeof(findArray)/sizeof(int); for(int i=0;i<size;++i){ int value = findArray[i]; bool ans = find(a,0,num-1,0,num-1,value,x,y); if(ans){ printf("find %d in x=%d\ty=%d\n", value, x, y); }else{ printf("can't find %d\n", value); } } return 0; }
2、一维数组A[n],可以从中找到长度相等的非降等差数列子串若干,求使等差数列长度L最大的这些子等差数列。
例子:A={1,8,3,5,10,12} => L = 2 子序列为{1,3,5}和{8,10,12}(求思路)
有道笔试感想
1、什么是Singleton模式及实现(多线程时需要加锁)
2、前序、中序求后序,要求返回后序串(关键是如何实现不用全局返回后序串,采取static指针首次申请内存实现)
3、字符串的最长回文子串(DP实现)
Google一面感想
1、返回一个字符串十进制数加一后的结果。(写出最精简的代码)
2、12345(?)67(?)89返回可以整除7的数,其中?表示[0-9]。(算是DP思想?)
3、一维坐标上n个点,如果去掉m个点,使得余下的点最小间距最大。(二分查找)
百度前两面感想
1、小端模式判断(union判断)
2、实模式保护模式(考的有点偏,偶又不是搞X86的)
3、LRU算法实现(链表模拟)
4、字符串十进制整数除以d除余(类似DP)
5、36匹马6个跑道,如果最少场数求出前K快的马(求解答)
美国国家仪器电面感想
1、各种排序
2、多态
3、拷贝构造(有点意思)、赋值
4、单链表反序(电话中说出代码,还是有点难度)
5、英语介绍一下北京和苏州(说了一半说不下去了)
小米笔试感想
1、字符串中word反序,比如“i love you”=>"you love i"
2、打印n对括号所有合理排列,“)()(”这种即不合理。(用进栈出栈模拟)
3、O(1)实现栈的max或min操作(双栈实现)
4、一致性hash(很重要,解决n个object映射到m个server上的问题)
Cadence一面感想
1、extern和static
2、拷贝构造函数
3、C编译与C++编译后符号区别,为什么C++可重载
盘古搜索笔试感想
各种C/C++问题
微策略笔试感想
1、去掉C/C++注释(很考验编程能力)
2、判断串s1插入s2后能否回文(先拼接s1和s2判断回文,然后再剥离s2首尾字符,子问题求解)
3、8*8的格,每个格有value,只允许向下向右走,问从(0,0)到(7,7)路过的value和最大多少?如果不超过max的value和最大多少?(第一问简单DP,最二问背包)
Yahoo笔试感想
1、判断单链表是否回文
2、rand6()如何实现rand7()