世界500强面试题.pdf

第一篇 面试题 ................................................................................ 8 1.1. 简介 ............................................................................................................... 8 1.2. 面试题集合（一） .......................................................................................... 8 1.2.1. 把二元查找树转变成排序的双向链表.................................................... 8 1.2.2. 下排每个数都是先前上排那十个数在下排出现的次数 ..........................11 1.2.3. 设计包含 min 函数的栈 ...................................................................... 14 1.2.4. 求子数组的最大和.............................................................................. 20 1.2.5. 在二元树中找出和为某一值的所有路径 .............................................. 22 1.2.6. Top K 算法详细解析---百度面试 ......................................................... 29 1.2.7. 翻转句子中单词的顺序....................................................................... 31 1.2.8. 判断整数序列是不是二元查找树的后序遍历结果 ................................ 33 1.2.9. 查找最小的 K 个元素-使用最大堆....................................................... 35 1.2.10. 求二叉树中节点的最大距离................................................................ 37 1.3. 面试题集合（二） ........................................................................................ 40 1.3.1. 求 1+2+…+n....................................................................................... 40 1.3.2. 输入一个单向链表，输出该链表中倒数第 k 个结点............................. 44 1.3.3. 输入一个已经按升序排序过的数组和一个数字.................................... 46 1.3.4. 输入一颗二元查找树，将该树转换为它的镜像.................................... 48 1.3.5. 输入一颗二元树，从上往下按层打印树的每个结点，同一层中按照从左往 右的顺序打印................................................................................................... 49 1.3.6. 在一个字符串中找到第一个只出现一次的字符。如输入 abaccdeff，则输出 b 52 1.3.7. n 个数字（0,1,…,n-1）形成一个圆圈 .................................................. 53 1.3.8. 定义 Fibonacci 数列 ............................................................................ 58 1.3.9. 左移递减数列查找某一个数.........................................
1.58.给出一个数列,找出其中最长的单调递减(或递增)子序列.121 1.5.9.四对括号可以有多少种匹配排列方式.. 1.5.10.输入一个正数n,输出所有和为n连续正数序列 125 16.面试题集合(五) 126 1.6.1.输入一棵二元树的根结点,求该树的深度 126 1.6.2.输入一个字符串,打印出该字符串中字符的所有排列.128 1.6.3.输入一个整数数组,调整数组中数字的顺序,使得所有奇数位于数组的前半部分,所有偶数 位于数组的后半部分 30 1.6.4.给定链表的头指针和一个结点指针,在O(1)时间删除该结点 132 1.6..输入一个链表的头结点,从尾到头反到来输出每个结点的值..134 1.6.6.用C+设计一个不能被继承的类 136 1.6.7.给定链表的头指针和一个结点指针,在O(1)时间删除该结点 138 16.8.—个数组中除了两个数字之外,其余数字均出现了两次…141 1.6.9.两个单向链表,找出它们的第一个公共结点 142 1.6.10.输入两个字符串,从第一字符串中删除第二个字符串中所有的字符.147 1.7.面试题集合(六) 1.7.1.寻找丑数 +·+ 148 17.2.输入数字n,按顺序输出从1最大的n位10进制数.152 17.3.用递归颠倒一个栈 156 1.7.4.从扑克牌中随机抽5张牌,判断是不是一个顺子… .158 1.7.5.把n个骰子扔在地上,所有骰子朝上一面的点数之和为S 1.7.6排出的所有数字中最小 165 1.77.数组的旋转 ……………170 17.8.给出一个函数来输出一个字符串的所有排列…171 1.7.9.实现函数 double power( double base, nt exponent) 1.7.10.更优的解法 175 1.71.单列模式 ,;非 …….…176 1.8.面试题集合(七) ·“·;;·卓··· 8.1.找出该字符串中对称的子字符串的最大长度 178 82数组中有一个数字出现的次数超过了数组长度的一半,找出这个数字180 18.3.输入二叉树中的两个结点,输出这两个结点在数中最低的共同父结点180 1.8.4.复杂链表……… 187 8.5.链表面试题 190 8.6.链表和数字的区别在哪里 197 1.8.7 strstr((函数功能… 198 8.8.—个nt数组,里面数据无任何限制,要求求出所有这样的数a[,其左 边的数都小于等于它,右边的数都大于等于它….… 199 89.—个文件,内含一干万行字符串,每个字符串在IK以内,要求找出所有 相反的串对,如abc和cba。 200 8.10.给出一个文件,里面包含两个字段{url、sic},即u为网址,sic为对应 网址访问的次数 .205 19面试题集合(八) 209 1.91.给定一个存放整数的数组,重新排列数组使得数组左边为奇数,右边为偶数 209 1.9.2.用C语言实现函数void* memmove( void* dest. const void*sre, size tn)210 1.9.3.随机发生器 212 1.9.4.搜索引擎 1.9.5.已知一个字符串,比如 as derwsde,寻找其中的一个子字符串比如sde的个数,如果没有返回 0,有的话返回子字符串的个数 216 1.9.6.编写一个程序,把一个有序整数数组放到二叉树中18 97.大整数数相乘的问题… 220 1.9.8求最大连续递增数字串 .221 1.99.函数将字符串中的字符*移到串的前部分… ? 2 1.9.10.单链表,编程实现其逆转 面试题集合(九) 225 1.10.1.删除字符串中的数字并压缩字符串... .25 1.10.2求两个串中的第一个最长子串(神州数码以前试题) 226 1.10.3.不开辟用于交换数据的临时空间,如何完成字符串的逆序∴...28 1.10.4.求随机数构成的数组中找到长度大于3的最长的等差数列.28 1.10.5外排序 230 1.106.用递归的方法判断整数组aN是不是升序排列 232 1.10.7.N个鸡蛋放到M个篮子中,篮子不能为空 1.10.8. Hash 234 1.10.9如何迅速匹配兄弟字符串 1242 1.10.10.腾讯数组乘积赋值的问题…. 243 1.11.面试题集合(十) 1.11.1.有一个整数数组,请求出两两之差绝对值最小的值. 244 1.11.2.给出一个函数来合并两个字符串A和B。字符串A的后几个字节和字符 串B的前几个字节重叠 245 1.113.编程实现两个正整数的除法(不能用除法操作符 250 1.11.4.平面上N个点,没两个点都确定一条直线,求出斜率最大的那条直线所 通过的两个点 ,251 1.115.字符串原地压缩 .252 116.一排N(最大1M)个正整数+1递增,乱序排列… l7.找出被重复的数字 Hashtable和 Hashmap的区别… 264 119.用1、2、2、3、4、5这六个数字,写一个main函数,打印出所有不同的排列 268 I.10.局部变量、全局变量和静态变量的含义 269 面试题集合(十-) 272 12..有两个双向循环链表A,B,知道其头指针为: pHeadA, p head B,请写一 函数将两链表中data值相同的结点删除… 1.122.找出两个字符串中最大公共子字符串,如" abcc ade";" dgc adde"的最大子串为"cad"274 1.12.3.把十进制数(ong型)分别以二进制和十六进制形式输出,不能使用 printf系列 275 1.12.4.40亿个整数 1.12.5.bmap减少hash算法所用空间 281 12.6.定义一个类似函数的宏,宏运算的结果来表示大于和小于 285 1.127.给定一个集合A 8 1.12.8.已知一个函数f可以等概率的得到1-5间的随机数,问怎么等概率的得到 7的随机数 .289 1.129.判断一个自然数是否是某个数的平方 290 1.12.10.一棵排序二叉树,令∩(最大值+最小值)2,设计一个算法,找出距离∫值最近、大于∩ 值的结点。复杂度如果是O(n2)不得分。 291 1.12.11.stst和 strncmp源码实现 面试题集合(十二) 295 1.131.对于从1到N的连续整集合合,能划分成两个子集合,且保证每个集 合的数字和是相等 295 1.13.1.对于从1到N的连续整集合合,能划分成两个子集合,且保证每个集 合的数字和是相 5 1.13.2 Topk 1.13.3 Collection∴ 301 1.13.4输入一个矩阵,按照从外向里以顺时针的顺序依次打印出毎一个数字311 1.13.5求集合的所有子集的算法 1.13.6.将一个数中的偶数位bit和奇数位b交换 318 1.13.7.二分查找实现 318 1.13.8.集合合并………… 1.139把求子集运算转换为组合问题 323 1.13.10.算法设计 324 1.14.面试题集合(十三) 327 1.14.1.各种排序算法 327 15 面试题集合(十四)… 1.15.1.判断图里有环…… 1.152.整数的素数和分解问题 422 1.15.3.求两个或N个数的最大公约数(gcd)和最小公倍数(cm)的较优算法….4.5 面试题集合(十五)… ………426 1.16.1 Application Context… 426 1.16.2. Application Context事件传播 431 1.16.3. mysql有多种存储引擎. 433 1.164论 My SQL何时使用索引,何时不使用索引 ,, 436 1.165.SQL多表连接查询实现语句 0 1.17. 面试题集合(十六) 442 1.17.1.12个高矮不同的人排成两排,每排必须是从矮到高排列而且第二排比对 应的第一排的人高问排列方式有多少种 17.2.毒酒……… ………………148 1.17.3.用代码验证阿里巴巴的一道关于男女比例的面试题 448 17.4.金币…… 451 1.17.5.海盗 “++· 452 1.17.6. 1024. 17.7.最少零钱问题最少硬币问题 455 1.17.8.石子合并………………… 1.18. 面试题集合(十七) 460 18.1.生产者消费者模式 460 1.18.2.动态规划……… 14166 1.18.3.0背包 18.4.贪心算法 477 .18.5.装箱问题…………… 1.19.教你如何迅速秒杀掉:99%的海量数据处理面试题 4184 第一篇刀疤鸭之数据结构面试题 11.简介 数据的逻辑结构:指反应数据元素之间的逻辑关系的数据结构,其中的逻辑关系 是指数据元素之间的前后件关系,而与他们在计算机中的存储位置无关。数据结构是每个程序炅面试必须掌 握的基础。 12.面试题集合(-) 12.1.把二元查找树转变成排序的双向链表 题目 输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。 要求不能创建任何新的结点,只调堊指针的指向。 614 八/ 481216 转换成双向链表 4=6-8=10=12-14=16 首先我们定义的二元查找树节点的数据结构如下: struct BSTreeNode int m n val uc;∥ valuc of nodc BSTreeNode m pLeft; / left child of node BSTreeNode*m pRight; //right child of node 1.∥1:构造二叉查找树; 2.∥2:中序遍历二叉查找树,因此结点按从小到大顺序访问,假设之前访问过的结点已经调整为一个双向链表,那 么 3.∥只需要将当前结点迕接至双向链表的最后一个结点即可,访问完后,双向链表也就调鍪完了