当前位置：文档之家 › 百度、谷歌、微软、MTK经典面试题

百度、谷歌、微软、MTK经典面试题

  • 格式：doc
  • 大小：647.00 KB
  • 文档页数：54

1. 有一个整数数组，请求出两两之差绝对值最小的值。

记住，只要得出最小值即可，不需要求出是哪两个数。

（Microsoft）方法1：两两作差求绝对值，并取最小，O( n2 )。

方法2：排序，相邻两点作差求绝对值，并取最小，O( nlgn ).方法3：有没有O( n )的解法？网上有如下解法：设数组A = { a1, a2, … , an }, 求s = min( |ai - aj| ), 其中1<= i, j <=n.设B = { b1, b2, … , bn-1 }, 且bi = ai – ai+1即：b1 = a1 – a2, b2 = a2 – a3, b3 = a3 –a4, …于是有如下规律：例如：a3 – a5 = ( a3 – a4 ) + ( a4 – a5 ) =b3 + b4a1 –a6 = b1 + b2 + … + b5即：ai –aj = bi + … + bj-1则数组A中任意两个数的差，都可以用数组B中一个字段的和表示。

则原问题可以转换为：在数组B中，求连续的某一段，使其和的绝对值最小。

（只求最小值，不需要知道具体是哪些数）例如 B = { 1, -2, 3, -1, -9, 7, -5, 6 }；则绝对值最小值为0，具体是{ -2, 3, -1 } 或{3, -1, -9, 7}网上的解法，一般到这里就没下文了。

只是简单的提了一下，类似于最大子序列的和。

具体怎么做，还要自己想想。

最大子序列和利用DP，可O( n )求解。

这题咋做？纠结。

2. 写一个函数，检查字符是否是整数，如果是，返回其整数值。

（或者：怎样只用4行代码编写出一个从字符串到长整形的函数？）据说此题是，Microsoft的大牛只有了4行代码就给出了答案。

可惜，不知道是怎么写的。

自己试着写写，当然可能会不至4行。

单纯追求行数，也没什么意义，如果你愿意可以把所有的程序都写成一行。

注意：1. 处理前导空格2. 处理正负号3. 处理进制（16进制、8进制、10进制）4. 非法字符（0---9, a---f, A---F）5. 注意整数的范围，不能溢出view plaincopy to clipboardprint?1. bool StrToInt( char *pc, long &value )2. {3. //去掉前导空格4. while( ( *pc==' ' || *pc=='\t' ) && *pc != '\0' ) pc++;5. if( *pc == '\0' ) return false;6.7. //处理正负号8. int sign = 1;9. if( *pc == '+' || *pc == '-' )10. {11. if( *(pc+1) =='\0' ) return false;12. if( *pc == '-' ) sign = -1;13. pc++;14. }15.16. //处理数值17. long tmp = 0;18. while( *pc != '\0' )19. {20. tmp *= 10;21. //++优先级比*高22. if( *pc < '0' && *pc > '9' ) return false;23. tmp += ( *pc++ - '0' );24. }25. value = tmp * sign;26. return true;}3. 给出一个函数来输出一个字符串的所有排列方法1：一个简单的DFS。

从后往前不断交互。

N个字母求全排列，O( n! )。

具体实现，看代码吧。

方法2：如果不会写递归，也可以利用STL。

STL里有一个next_permutation函数。

利用这个函数可以返回大于原字符串的下一个字典序列。

当字符串为最大字典序列时，函数返回false。

这样只要先对原字符串排序，然后不断调用next_permuation即可。

view plaincopy to clipboardprint?1. inline void Exchange( char *px, char *py )2. {3. char tmp = *px;4. *px = *py;5. *py = tmp;6. }7.8. void PrintStrPermut( char *pstr, char *pbegin )9. {10. //处理空字符串11. if( pstr == NULL || pbegin == NULL ) return;12.13. //递归终止条件14. if( *pbegin == '\0' )15. cout << pstr << endl;16. else17. {18. for( char *p=pbegin; *p!='\0'; p++ )19. {20. Exchange( p, pbegin );21. PrintStrPermut( pstr, pbegin+1 );22. Exchange( p, pbegin );23. }24. }25. }26.27. void PrintStrPermut2( char *pstr )28. {29. char *p = pstr;30. while( *p != '\0' ) p++;31.32. sort( pstr, p );33. cout << pstr << endl;34. while( next_permutation( pstr, p ) )35. {36. cout << pstr << endl;37. }}4．请编写实现malloc()内存分配函数功能一样的代码这题比较难，要是不懂点OS的内存管理，根本就无从下手。

我们知道调用malloc()后，OS就要想方设法为我们返回一块空闲空间。

这就涉及到OS的内存管理。

OS的内存管理可以这样考虑：假设整块内存有128K初始状态，128K都是空闲第一次请求，申请了16k，空闲112K第二次请求，申请了32K，空闲80K第三次请求，申请了8K，空闲72K第二次请求申请的32K被释放，空闲108K第四次请求，申请了24K，空闲84K…从上面的例子可以看出，一整块连续的空闲内存块，经过一段时间的使用，会被无情的划分为许多小块。

这些小块大小不等，并且有的空闲、有的被占用。

当调用malloc时，OS就沿内存扫描，找到一块够大的空闲块，从中划分出要使用的部分，将这部分标记为己分配，并返回这部分的首地址。

如果，空闲的块都是些小的碎片，那就悲具了（当然，OS可以把将相邻的空闲块合并，再尝试）。

现在，模拟一下malloc的过程：为了便于管理，首先定义内存控制块mcb。

这个mcb记录两个信息：块是否空闲、块的大小。

即，每个分配出去的块，其实都带有一个mcb，只不过这个mcb位于块的最前端，返回该用户的指针刚好指向mcb之后，所以对用户是不可见的。

现在，就可以处理free了。

Free只要把已分配的内存块重新标记为空闲即可，这里当然要用到该快的mcb了。

Malloc简单来说，就是维护几个指针，根据分配请求修改指针位置。

对于要分配的块，将标记置位己分配，并返回这部分的首地址。

参考/blog/static/32574109200881445518891/，这里讲的很清楚，还附有代码，我就不狗尾续貂了。

5. 字符串A的后几个字节和字符串B的前几个字节重叠。

这题似乎没什么玄机，就是个简单的字符串处理。

使用strlen和memcpy可以完成，见代码。

view plaincopy to clipboardprint?1. bool StrOverlap( char *strA, char *strB, int cnt, char *strC )2. {3. int sizeA = (int)strlen( strA );4. int sizeB = (int)strlen( strB );5.6. if( cnt > sizeA || cnt > sizeB ) return false;7.8. memcpy( strC, strA, sizeA-cnt );9. memcpy( strC+sizeA-cnt, strB+cnt, sizeB-cnt );10.11. //注意添加结束标记12. strC[sizeA+sizeB-2*cnt] = '\0';13. return true;}6. 怎样编写一个程序，把一个有序整数数组放到二叉树中？由数组建立排序二叉树。

因为数组已排序，所以可以进行类似排序二叉树上的查找。

感觉有点类似先序遍历，每次先处理根节点，然后分别是左子树、右子树。

具体做法是：1.整个数组对应一个二叉树，则中间元素对应二叉树的根节点2.中间元素左边的部分对应左子树、右边的部分对应右子树3.对左右两部分再继续递归调用。

view plaincopy to clipboardprint?1. struct BiTreeNode2. {3. int data;4. BiTreeNode* leftChild;5. BiTreeNode* rightChild;6.7. //构造函数，初始化成员变量8. BiTreeNode(): data(0), leftChild(0), rightChild(0){};9. };10.11. void ArrayToTree( int *pi, int left, int right, BiTreeNode *&root )12. {13. if( left <= right )14. {15. int mid = ( left + right ) / 2;16. root = new BiTreeNode;17. root->data = pi[mid];18.19. ArrayToTree( pi, left, mid-1, root->leftChild);20. ArrayToTree( pi, mid+1, right, root->rightChild );21. }}7. 怎样从顶部开始逐层打印二叉树结点数据？请编程。

合集下载

google 面试题

google 面试题

google 面试题Google面试题Google是全球知名的科技巨头，每年吸引了大量优秀的应聘者参与面试。

Google的面试题目以其独特性和难度而闻名，旨在考察应聘者的解决问题的能力、创造力和逻辑思维。

本文将介绍几个经典的Google面试题目，并分析解题思路。

1. 第一题：寻找字符串中的重复字符题目描述：给定一个字符串，编写一个函数来找出其中重复的字符，并返回其出现次数。

解题思路：为了找出字符串中的重复的字符，并计算它们出现的次数，我们可以使用哈希表。

遍历字符串的每个字符，如果该字符在哈希表中已经存在，则将对应的值加1；否则，在哈希表中添加该字符，并将对应的值设为1。

最后，再遍历哈希表，找出值大于1的字符，即为重复字符。

输出重复字符及其出现次数。

2. 第二题：计算两个数组的交集题目描述：给定两个整数数组，编写一个函数来计算它们的交集。

为了计算两个数组的交集，我们可以创建两个哈希表。

首先，遍历第一个数组，将数组中的元素添加到第一个哈希表中，并将对应的值设为1。

然后，遍历第二个数组，检查数组中的元素是否在第一个哈希表中存在，如果存在，则将该元素添加到第二个哈希表中，并将对应的值设为1。

最后，遍历第二个哈希表，并输出键所对应的元素，即为两个数组的交集。

3. 第三题：找出缺失的数字题目描述：给定一个包含 0, 1, 2, ..., n 中 n 个数的序列，找出序列中缺失的那个数。

解题思路：为了找出缺失的数字，我们可以将序列中的所有数字进行异或运算。

首先，初始化一个变量为0，然后，将变量与序列中的每个数字进行异或运算。

异或运算的性质是，相同数字异或结果为0，任何数字与0异或结果为其本身。

因此，最后的结果就是缺失的数字。

输出结果。

4. 第四题：二进制手表题目描述：给定一个非负整数 n 代表当前 LED 亮着的数量，返回所有可能的时间。

为了列举出亮着 n 个 LED 的所有时间，我们可以遍历二进制数。

从0到2的10次方-1，将它们表示为二进制，统计其中1的个数，如果等于给定的 n，就表示该二进制数能构成合法的时间。

谷歌面试问题

谷歌面试问题

谷歌面试问题...谷歌面试问题...谷歌面试中，15个让人疯狂的经典问题，你能回答几个?对一些身处经济衰退大潮中的初级经理和软件开发者而言，谷歌是一个避风港。

但其招聘门槛较高，首先，谷歌更青睐长春藤联盟(由美国八所知名大学所组成)的毕业生;其次，即使应聘者已年过30，谷歌也很在意其GpA(平均成绩点数)分数;第三，谷歌需要的是那些想改变世界的人。

而且，即使应聘者满足了上述要求，也有可能在面试中被谷歌提出的问题所难倒。

以下是15个让许多应聘者抓狂的谷歌面试题。

问题1：一辆校车能装下多少个高尔夫球?应聘职位：产品经理问题2：如果让你清洗西雅图市所有的窗户，你会对此索价多少?应聘职位：产品经理问题3：在一个重男轻女的国家里，每家每户都想生男孩。

若一户人家生了一个女孩，便会再生一个，直到生下的是男孩为止。

请问这个国家的男女比例是多少?应聘职位：产品经理问题4：全世界共有多少位钢琴调音师?应聘职位：产品经理问题5：下水道井盖为什么是圆的?应聘职位：软件工程师问题6：为旧金山市设计一个紧急疏散方案。

应聘职位：产品经理问题7：时钟的指针一天内总共会重合多少次?应聘职位：产品经理问题8：阐释“死牛肉”的意义所在。

应聘职位：软件工程师问题9：一个人开车来到旅馆，变得一无所有。

究竟发生了什么事情?应聘职位：软件工程师问题10：你想知道好友鲍勃是否有你正确的电话号码，但又不能直接问他。

你必须在卡片上留言，让伊芙将卡片较交给鲍勃。

除了问题以外，你还应该在卡片上写什么，才能既确保鲍勃能看懂留言，又使伊芙看不出卡片上写有你的电话号码。

应聘职位：软件工程师问题11：你是一艘海盗船的船长，你的船员要投票决定如何平分金条。

如果与你意见一致的船员数量少于一半，你将被杀死。

你应该如何提议分配金条，才能既分得较多赃物，又能活下来?应聘职位：工程经理问题12：你有8个大小一样的球，其中7个重量相同，只有一个略重一些。

给你一个天平，而且只准称两次，如何找出重量不同的那个球?应聘职位：产品经理问题13：你在一幢100层高的大楼中，给了你两个鸡蛋。

百一测评 Google谷歌面试题(八道)

百一测评 Google谷歌面试题(八道)

百一测评 Google谷歌面试题（八道）百一测评-google谷歌面试题（八道）我面试问题每题分值：15分是否题目乱序：是是否选项乱序：是是否可回溯：是难度：中1.【问答】正整数序列Q中的每个元素都可以被至少一个正整数a和B除。

现在给出a和B，需要计算出q中的前几项，例如，当a=3，b=5，n=6时，序列为3，5，6，9，10，12。

(1)设计一个函数voidgenerate（inta,intb,intn,int*q）计算q的前几项。

(2)、设计测试数据来验证函数程序在各种输入下的正确性。

参考答案：略,尚无标准答案2.【问答】有一个由大小写组成的字符串。

现在需要对其进行修改，以排列其中的所有小写字母在答谢字母的前面（大写或小写字母之间不要求保持原来次序），如有可能尽量选择时间和空间效率高的算法c语言函数原型voidproc（char*str）也可以采用你自己熟悉的语言参考答案：略,尚无标准答案3.【问答】如何随机选择1000个关键词给定一个数据流，其中包含无穷尽的搜索关键字（比如，人们在谷歌搜索时不断输入的关键字）。

4.【问答】判断一个自然数是否是一个数的平方。

注意：当然，不能使用平方运算。

参考答案：省略，没有标准答案5.[问答]给定能随机生成整数1到5的函数，写出能随机生成整数1到7的函数。

参考答案：略,尚无标准答案6.[问答]1024!末尾有多少个0？参考答案：略,尚无标准答案7.【问答】共有五名海盗，排名从5到1。

最大的海盗有权建议如何分享100枚金币币。

但其他人要对此表决，如果多数反对，那他就会被杀死。

他应该提出怎样的方案，既让自己拿到尽可能多的金币又不会被杀死？（提示：有一个海盗能拿到98%的金币）参考答案：略,尚无标准答案8、[Q＆A]谷歌2022在中国南方地区写的试题给定一个集合a=[0,1,3,8](该集合中的元素都是在0，9之间的数字，但未必全部包含)，指定任意一个正整数k，请用a中的元素组成一个大于k的最小正整数。

百度面试题目答案(3篇)

百度面试题目答案(3篇)

第1篇一、引言随着互联网行业的飞速发展，百度作为中国领先的搜索引擎公司，吸引了大量优秀人才的加入。

百度面试题目涵盖了多个领域，包括技术、产品、设计等。

本文将针对百度面试中的常见题目进行深入解析，并提供相应的答案，帮助广大求职者备战面试挑战。

二、技术类面试题目及答案1. 题目：介绍一个你参与过的项目。

答案：在回答这个问题时，要突出项目的技术亮点、你在项目中的角色和贡献，以及项目的成果。

以下是一个示例：“在上一家公司，我参与了一个电商平台的项目。

我主要负责后端开发，使用Java语言进行编程。

在项目中，我负责实现商品管理系统、订单管理系统和用户管理系统。

我运用了Spring框架和MyBatis持久层框架，提高了系统的性能和稳定性。

通过我的努力，项目成功上线，并得到了客户的好评。

”2. 题目：请实现一个二分查找算法。

答案：以下是一个简单的二分查找算法实现：```javapublic int binarySearch(int[] arr, int target) {int left = 0;int right = arr.length - 1;while (left <= right) {int mid = (left + right) / 2;if (arr[mid] == target) {return mid;} else if (arr[mid] < target) {left = mid + 1;} else {right = mid - 1;}}return -1;}```3. 题目：请解释一下Java中的volatile关键字。

答案：volatile关键字用于声明变量，确保变量的读写操作具有原子性，并禁止指令重排。

以下是一个示例：```javapublic class VolatileExample {private volatile int count = 0;public void increment() {count++;}}```在这个示例中，count变量被声明为volatile，确保了在多线程环境下，每次读取count的值都是最新的。