IT公司面试汇总.doc

1.题目：二叉树，各边有不同权值，求一路径，使得两点之间路径的所有边的权重之和最大，路径中边不重复，问复杂度多少？分析：编程之美3.8有过解答，时间复杂度为O(v)。但是这里有点不同：树的边有权值。第一种解法：最大距离的节点一定是叶子节点，首先将二叉树看成一个连通图，首先应该求根节点到所有叶节点的最大距离叶节点A，然后求A到所有其他节点的最大距离。假设要求节点A到其他节点之间的最长路径，题目的转换为求解以A为源点的最长路径。采用单源最短路径（dijkstra）的思想求解。这里要求最长路径，因此，每次选择时，应该从未知最大距离的节点集合中选择最大距离的节点加入已知最大距离的节点集合。如果采用堆结构来维护未知节点到A的最大距离，那么时间复杂度为O（vlogv）。第二种解法：采用编程之美3.8节的递归方法，递归遍历二叉树一次，得出最大距离，时间复杂度为O（v） 2. 判断两颗二叉树是否相等，注意：相等包含两种：以下任意一种成立，root1和root2相等。 1.root1的左子树与root2的左子树相同并且root1的右子树与root2的右子树相同。 1.root1的左子树与root2的左子树相同并且root1的右子树与root2的右子树相同。 分析：按照上述两种情况写出递归即可。view plaincopy to clipboardprint?1.2. bool IsBSTEqual(BNode* root1,BNode* root2) 3. 4. if (root1=NULL & root2=NULL) 5. 6. return true; 7. 8. else if (root1=NULL | root2=NULL) 9. 10. return false; 11. 12. else 13. 14. if (root1-data != root2-data) 15. 16. return false; 17. 18.19. bool is_left = IsBSTEqual(root1-left,root2-left); 20. bool is_right = IsBSTEqual(root1-right,root2-right); 21.22. if (is_left&is_right) 23. return true; 24.25. else 26. 27. is_right = IsBSTEqual(root1-right,root2-left); 28. is_left = IsBSTEqual(root1-left,root2-right); 29.30. if (is_left&is_right) 31. return true; 32. else 33. return false; 34. 35. 36.37. 输入一颗二叉树根节点，复制该树，返回新建树的根节点。分析：这一道题跟求二叉树的高度类似，使用后续遍历即可完成。参考代码如下：view plaincopy to clipboardprint?1.2. class BNode 3. 4. public: 5. BNode() 6. 7. left = NULL; 8. right = NULL; 9. 10. BNode* left; 11. BNode* right; 12. char data; 13. ; 14.15. BNode* CopyBST(BNode* root) 16. 17. if(root = NULL) 18. return NULL; 19.20. BNode* sub_tree = new BNode; 21.22. sub_tree-data = root-data; 23. sub_tree-left = CopyBST(root-left); 24. sub_tree-right = CopyBST(root-right); 25.26. return sub_tree; 27. 题目：输入一棵二叉树的根结点，求该树的高度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的高度。分析：通过后序遍历二叉树的方式计算高度，每次从子树返回，选择子树高度大的值+1作为当前数的高度，递归实现，参考代码如下：view plaincopy to clipboardprint?1.2. class BNode 3. 4. public: 5. BNode() 6. 7. left = NULL; 8. right = NULL; 9. 10. BNode* left; 11. BNode* right; 12. char data; 13. ; 14.15. int BTreeHight(BNode* root) 16. 17. if (!root) 18. 19. return 0; 20. 21. int left_subtree_height = BTreeHight(root-left); 22. int right_subtree_height = BTreeHight(root-right); 23. int height; 24. if (left_subtree_heightright_subtree_height) 25. 26. height = left_subtree_height+1; 27. 28. else 29. height = right_subtree_height+1; 30.31. return height; 32.33. 输入一颗二元树，从上往下按层打印树的每个结点，同一层中按照从左往右的顺序打印。分析：此题是个老题，来自编程之美，需要写出漂亮的代码才对得起出题人。view plaincopy to clipboardprint?1.2. void PrintNodeByLevel(Node* root) 3. deque Q1, Q2; 4. Q1.push_back(root); 5. do 6. do 7. Node* node = Q1.front(); 8. Q1.pop_front(); 9.10. printf(%dt,node-data); 11.12. if (node-pLeft) 13. Q2.push_back(node-pLeft); 14. if (node-pRight) 15. Q2.push_back(node-pRight); 16. while (!Q1.empty(); 17.18. printf(n); 19. Q1.swap(Q2); 20. while(!Q1.empty(); 21. 分治：谷歌面试题：判断一个自然数是否是某个数的平方?方法1：遍历从1到N的数字，求取平方并和N进行比较。如果平方小于N，则继续遍历；如果等于N，则成功退出；如果大于N，则失败退出。复杂度为O(n0.5)。方法2：使用二分查找法，对1到N之间的数字进行判断。复杂度为O(log n)。方法3：由于(n+1)2=n2 + 2n + 1，= = 1 + (2*1 + 1) + (2*2 + 1) + + (2*n + 1)注意到这些项构成了等差数列（每项之间相差2）。所以我们可以比较 N-1， N 1 3， N 1 3 5 和0的关系。网络转载请注明：转载自程序员面试之家并注明本文链接地址: 谷歌面试题：判断一个自然数是否是某个数的平方题目：给出一个一维的点集，求能够包含n/2个点的第一个最小区间的左边界和右边界。例如5,-3,10，4，-2，-5第一个包含n/2个点的最小区间就是-5,-2 1. 写一个函数，参数是数组及其长度，返回第一个包含n/2个点的最小区间的左边界和右边界，不能引用任何头文件和使用任何库函数，要求完整可运行，效率尽可能高（35分） 2. 给出一些测试用例来进行测试，同时要给出每组测试用例的测试目的，要包括边界情况，错误情况（15分） 分析：方法1：将一维数组用快速排序排好序，返回最小元素和中位数。view plaincopy to clipboardprint?1.2. void QuickSort(int* A, int begin, int end) 3. 4. if (!A | begin=end) 5. 6. return; 7. 8.9. int split_pos = Partition(A,begin,end); 10.11. QuickSort(A,begin,split_pos-1); 12. QuickSort(A,split_pos+1,end); 13.14. 15. int Partition(int* A, int begin, int end) 16. 17. /分治元素 18. int X = Aend; 19.20. /Abegin.Ai-1=X 24. int j=end; 25.26. /循环开始前Aj是等待被填充的元素，该元素已被保存到X 27. while (ij) 28. 29. /从前面开始找到小于X的数 30. while (AiX & ij) 31. i+; 32.33. /Aj被填充，Ai等待被填充 34. if (i=X & ij) 38. j-; 39.40. /Ai被填充，Aj等待被填充 41. if (i=end)return;int split_pos = Partition(A,begin,end);QuickSort(A,begin,split_pos-1);QuickSort(A,split_pos+1,end);int Partition(int* A, int begin, int end)/分治元素int X = Aend;/Abegin.Ai-1=Xint j=end;/循环开始前Aj是等待被填充的元素，该元素已被保存到Xwhile (ij)/从前面开始找到小于X的数while (AiX & ij)i+;/Aj被填充，Ai等待被填充if (i=X & ij)j-;/Ai被填充，Aj等待被填充if (iend) 14. 15. return; 16. 17.18. int split_pos = Partition(A,begin,end); 19.20. if (split_pos = middle_index) 21. 22. middle_element = Asplit_pos; 23. return; 24. 25.26. FindMiddleElement(A,begin,split_pos-1,middle_index,middle_element); 27. FindMiddleElement(A,split_pos+1,end,middle_index,middle_element); 28. /*返回中位数元素para:Abegin.end为所求数组middle_index 为中位数的索引middle_element为中位数元素，返回用*/void FindMiddleElement(int* A,int begin ,int end, int middle_index,int& middle_element)if (!A | beginend)return;int split_pos = Partition(A,begin,end);if (split_pos = middle_index)middle_element = Asplit_pos;return;FindMiddleElement(A,begin,split_pos-1,middle_index,middle_element);FindMiddleElement(A,split_pos+1,end,middle_index,middle_element);第二问，边界情况： 奇数个元素的数组：A=3,2,4 偶是个元素的数组：A=4,2,3,1 含有多数相同元素的数组：A=1,2,3,3,3,3,3,4 错误情况： 空数组：A=NULL，长度不合法length 1) & 0x55555555); / 1 4. x = (x & 0x33333333) + (x 2) & 0x33333333); / 2 5. x = (x + (x 4) & 0x0F0F0F0F; /3 6. x = x + (x 8); /4 7. x = x + (x 16); /5 8. return x & 0x0000003F; / 6 9. int Count(unsigned x) x = x - (x 1) & 0x55555555); / 1 x = (x & 0x33333333) + (x 2) & 0x33333333); / 2 x = (x + (x 4) & 0x0F0F0F0F; /3 x = x + (x 8); /4 x = x + (x 16); /5 return x & 0x0000003F; / 6我们以0000 0000 0000 0000 0000 0000 1011 0101为例：第一行中，x1是右移一位，(x1) 为 0000 0000 0000 0000 0000 0000 0101 1010，该结果与0101 0101 0101 0101 0101 0101 0101 0101相与，等于 0000 0000 0000 0000 0000 0000 0101 0000，实际上，(x 1) & 055555555) 该步是想得到原数据x的偶数位的数据。（代码是先右移，再得奇数位，这个等价于：先得偶数位，再右移）然后，x-(x 1) & 055555555) 则是 用原数据减去原数据的偶数位。结果是 0000 0000 0000 0000 0000 0000 0110 0101，其实，之所有要相减就是为了得到第一位与第二位1的个数的和，第三位与第四位1的个数的和，第五位与第六位1的个数的和，以此类推。那么，为什么要用相减的方法来得到相邻两位的和呢？原理是：相邻两位1的个数的和是：A-A/2 。原数据是A，右移相当于除2。比如，如果原数据是1（01），那么一半就是0，相减后就是1，所以有1个“1”。如果原数据是3（11），那么一半就是1，相减后就是2，所有总共有2个“1”。这样，经过第一行的运算，我们得到每两个相邻位的“1”的总和。第二行，类似的，是求将原数据第一位第二位的“1“的个数的和 与 第三位第四位的“1”的个数的和 相加。这样，第二行执行后，我们可以得到每四位的“1”的个数的和第三行，可以得到每八位的“1”的个数的和第四行，可以得到每16位“1”的个数的和第五行，可以得到32位数中所有1的个数的和。第六行，由于32位的数据，1的个数最大也就32个，不可能超过2的6位方，所以只要取最后6位数据就是所有数据1的个数的和了。这里用的是二分法，两两一组相加，之后四个四个一组相加，接着八个八个，最后就得到各位之和了。解法二：view plaincopy to clipboardprint?1. int Count(unsigned x) 2. 3. unsigned n; 4.5. n = (x 1) & 033333333333; / 1 6. x = x - n; / 2 7. n = (n 1) & 033333333333; / 3 8. x = x - n; / 4 9. x = (x + (x 3) & 030707070707; /5 10. x = modu(x, 63); / 6 11. return x; /7 12. int Count(unsigned x) unsigned n; n = (x 1) & 033333333333; / 1 x = x - n; / 2 n = (n 1) & 033333333333; / 3 x = x - n; / 4 x = (x + (x 3) & 030707070707; /5 x = modu(x, 63); / 6 return x; /7这个解法更妙。需要注意的是，033333333333和033333333333都是指 八进制的数。第一行第二行连起来看，这与解法一很类似，目的是为了得到第一位与第二位的“1”的个数和。注意，第31、32位中1的个数和在这一步中被统计好了。第一行和第三行、第四行连起来看，目的是为了得到第一位与第三位的“1”的个数的和。然后，再与上步的结果加起来，就得到第一位、第二位、第三位的“1”的个数的和。所以，从第一行到第四行就是为了得到 每三位一组的“1”的个数的和。原理是：相邻三位的结果是：A-A/2-A/4. 算法中有两次向移。比如，第一位第二位第三位是011, 则第一次移位后为01，相减后为10，再移位后为0，相减还是10，所以有2个“1”。再比如，第一位第二位第三位是101，则第一次移位后为10，相减后为011，再移位后为1，相减后是010，所以有2个“1”。第五行是求相邻六位的1的个数第六行，比较难懂。在第五行执行完后，我们得到了七组数据，第32、31位为一组，第30-25为一组，第6-第1为一组。所以可以写成:x_0 + x_1 * 64 + x_2 * 64 * 64 + x_3 * 64 * 64* 64+ x_4 * 64 * 64* 64* 64+ x_5 * 64 * 64* 64* 64* 64+ x_6 * 64 * 64* 64* 64* 64* 64，这个数除以63的余数 肯定 与 x_0 +x_6 相等（因为32位的数据最多也就32个1）简短解释：首先是将二进制各位三个一组，求出每组中1的个数，然后相邻两组归并，得到六个一组的1的个数，最后很巧妙的用除63取余得到了结果。题目：输入两个整数n 和m，从数列1，2，3.n 中随意取几个数，使其和等于m，要求将其中所有的可能组合列出来。分析：这道题有点难度，应该用分治算法解决。考虑每次将m分裂成大于begin的两个数，并且使他们的和等于m，加入begin条件的目的是为了防止枚举重复的组合。view plaincopy to clipboardprint?1.2. /* 3. 每次将m分裂成大于begin的两个数，并且使他们的和等于m 4. */ 5. void Depart(int begin, /基准，防止重复的排列 6. int m, /被分裂的数 7. vector& arr /已经分裂的数存放于此 8. ) 9. 10.11. /v1,v2是被分裂的两个数 12. int v1 = begin+1; 13. int v2 = m-begin-1; 14.15. for(; v1v2 ; v1+,v2-) 16. 17. arr.push_back(v1); 18. arr.push_back(v2); 19.20. /打印当前排列 21. copy(arr.begin(), arr.end(), ostream_iterator(cout,t); 22. printf(n); 23.24. /递归分裂v2 25. arr.pop_back(); 26. Depart(v1,v2,arr); 27.28. /为其他排列做准备，清除当前的分裂情况 29. arr.pop_back(); 30. 31.32. 题目：输入一个整数数组，判断该数组是不是某二元查找树的后序遍历的结果。如果是返回true，否则返回false。分析：从例子入手，结合二叉排序树的性质寻找判断规律：10/ 6 14/ / 4 8 12 16对应的后续遍历结果是：4 8 6 12 16 14 10规律：对于二叉排序树，根节点的值大于所有左子树的节点值，小于所有右子树的节点值。现在只有一个数组，如何判断呢？对于这个数组，最后一个元素An-1一定对应二叉树的根节点，寻找左子树对应的子数组，判断右子树的所有节点是否都大于根节点的值，对于分出的左子树和右子树采用当前相同的方法去判断。代码如下：view plaincopy to clipboardprint?1.2. bool verifySquenceOfBST(int squence, int length) 3. 4. if(squence = NULL | length = 0) 5. return false; 6.7. int root = squencelength - 1; 8.9. /find left sub-tree 10. int i = 0; 11. for(; i root) 14. break; 15. 16.17. / the nodes in the right sub-tree are greater than the root 18. int j = i; 19. for(; j length - 1; + j) 20. 21. if(squencej 0) 28. left = verifySquenceOfBST(squence, i); 29.30. / verify whether the right sub-tree is a BST 31. bool right = true; 32. if(i 0); 7.8. int min_index = 0; 9. int max_index = size-1; 10.11. while(min_index max_index-1) 12. 13. /这样写的好处是可以防止整数的溢出 14. int mid_index = min_index + (max_index - min_index)/2; 15.16. if(arrmid_index v) 21. 22. max_index = mid_index - 1; 23. 24. else 25. 26. min_index = mid_index; 27. 28. 29.30. if (arrmax_index = v) 31. 32. return max_index; 33. 34. else if (arrmin_index = v) 35. 36. return min_index; 37. 38. else 39. return -1; 40.41. /*找出数组（排好序）中与v相等的元素，并且是满足这一条件中下标最大的那个*/int BiSearch1(int* arr,int size,int v)assert(arr != NULL & size 0);int min_index = 0;int max_index = size-1;while(min_index max_index-1)/这样写的好处是可以防止整数的溢出int mid_index = min_index + (max_index - min_index)/2;if(arrmid_index v)max_index = mid_index - 1;elsemin_index = mid_index;if (arrmax_index = v)return max_index;else if (arrmin_index = v)return min_index;elsereturn -1;扩展题：找出数组中与v相等的元素，并且是满足这一条件中下标最小的那个view plaincopy to clipboardprint?1.2. /* 3. 找出数组中与v相等的元素，并且是满足这一条件中下标最小的那个 4. */ 5. int BiSearch2(int* arr,int size,int v) 6. 7. assert(arr != NULL & size 0); 8.9. int min_index = 0; 10. int max_index = size-1; 11.12. while(min_index max_index) 13. 14. /这样写的好处是可以防止整数的溢出 15. int mid_index = min_index + (max_index - min_index)/2; 16.17. if(arrmid_index v) 22. 23. max_index = mid_index - 1; 24. 25. else 26. 27. max_index = mid_index; 28. 29. 30.31. if (arrmax_index = v) 32. 33. return max_index; 34. 35. /*else if (arrmin_index = v) 36. 37. return min_index; 38. */ 39. else 40. return -1; 41.42. 回溯法：题目：给定一段英文描述，包含n个单词，用空格分开每个单词，再给定m个单词的关键字，请编程实现：找出这段英文描述中包含了所有关键字的最短子串，并输出。分析：本题其实就是编程之美中的最短摘要生成。通过遍历所有可能的子串（包含了所有关键字的子串），找出这些子串中长度最短的一个，将其输出。这里可以加速的地方在于，找到一个包含了所有关键字的子串之后，如何用比较快的方式去找下一个包含了所有关键字的子串，如果使用回溯，复杂度太高。下面的实现方法比较巧妙，借用一个set集合not_find_set存放未找到的关键字，用一个map容器存放已经找到的关键字，并将找到的关键字次数进行计数。假设当前的遍历范围是begin,end，并且在这个范围所有的关键字被找到，将begin指针依次向后挪，直到某个关键字x的出现次数为0，这样当前的最短字符串即可得到。接着，将x加入not_find_set，扫描指针end向后挪，找到下一个包含了所有关键字的最短字符串。问题：给出一个无向图V，用三种颜色为V中的每个顶点去着色，假设三种颜色分别为1,2,3，使得没有两个邻接的顶点被着成相同的颜色。分析：这是一道非常经典的回溯算法题，没有非常有效的快速算法，只有用一种改进的穷举算法来解答。如果不改进穷举，那么每个顶点有3种颜色选择，那么，对于n个顶点的图，算法的复杂度为0(3n)。如何改进这种穷举的方法呢？假设我们按照顺序依次对每个顶点进行着色，如果在给某个顶点k着完色后，发现图的着色变成不合法，那么，我们没有必要去为k+1,n这些顶点继续着色，而是直接改变第k顶点现有着色，继续下去，直到遍历到第n个顶点，如果着色合法，打印输出。其实，我们在处理许多问题时，也许，一开始没有非常有效的方式，但如果能够对于穷举进行剪枝也是一种非常不错的解法。代码如下：view plaincopy to clipboardprint?1. /* 2. 使用位图表示无向图： 3. 即如果treeij != 0， 表示i,j顶点相连 4. */ 5. void ColorRec(int tree55,int n) 6. 7. int* c = new intn; 8.9. /* 10. 初始化 11. */ 12. for (int i=0;i n;i+) 13. 14. ci = 0; 15. 16.17. int k =0; 18. while( k 3) 22. 23. /回溯 24. ck = 0; 25. k-; 26. ck+; 27. 28. else 29. 30. /* 31. 判断第K个点的着色是否合法 32. */ 33. ck+; 34. if (IsValid(tree,c,k,n) 35. 36. k+; 37. 38.39. 40. 41.42. for (int i=0;in;i+) 43. 44. printf(%dt,ci); 45. 46. printf(n); 47.48. delete c; 49. 50.51. bool IsValid(int tree55,int* c,int k,int n) 52. 53. for (int i=0;i=0); 6.7. if(str = NULL) 8. return; 9.10. /当前已经处理好的结果字符串的尾指针 11. char* result_tail = str; 12.13. /顺序扫描字符串的每个字符的指针 14. char* p = str; 15.16. /存放p之前的字符是否是空格 17. bool is_pre_space=false; 18.19. /忽略字符串最前面的空格 20. while (*p= & len0) 21. 22. p+; 23. len-; 24. 25.26. while (len0) 27. 28. if (*p = )/遇到空格 29. 30. if (!is_pre_space) 31. 32. /保留空格 33. *result_tail = *p; 34. result_tail+; 35. 36. is_pre_space = true; 37. p+; 38. len-; 39. 40. else if(*p = n)/遇到换行 41. 42. /前面有空格 43. if (is_pre_space) 44. 45. result_tail-; 46. 47. is_pre_space = false; 48.49. /复制换行符 50. *result_tail = *p; 51. result_tail+; 52. p+; 53. len-; 54.55. /忽略换行后的空格 56. while (*p= & len0) 57. 58. p+; 59. len-; 60. 61. 62. else/其他字符 63. 64. /复制换行符 65. *result_tail = *p; 66. result_tail+; 67. p+; 68. len-; 69. is_pre_space = false; 70. 71. 72.73. /移除尾部空格 74. if (is_pre_space) 75. 76. result_tail-; 77. 78.79. *result_tail = 0; 80. void RemoveExtraSpace(char* str, int len)assert(len=0);if(str = NULL)return;/当前已经处理好的结果字符串的尾指针char* result_tail = str;/顺序扫描字符串的每个字符的指针char* p = str;/存放p之前的字符是否是空格bool is_pre_space=false;/忽略字符串最前面的空格while (*p= & len0)p+;len-;while (len0)if (*p = )/遇到空格if (!is_pre_space)/保留空格*result_tail = *p;result_tail+;is_pre_space = true;p+;len-;else if(*p = n)/遇到换行/前面有空格if (is_pre_space)result_tail-;is_pre_space = false;/复制换行符*result_tail = *p;result_tail+;p+;len-;/忽略换行后的空格while (*p= & len0)p+;len-;else/其他字符/复制换行符*result_tail = *p;result_tail+;p+;len-;is_pre_spa