江苏龙网

  1. 首页 > 人文 > >

常见算法笔试和面试题整理（带答案）

本文不打算介绍那些高逼格的算法 ， 就讲讲最近在面试过程中遇到的算法题以及面试的时候给出的答案 。 算法可以说是解决所有问题的基石 。 很多东西都可以转换为算法问题 ， 学习算法最大的作用就是更清楚地了解了很多东西 。 正所谓是 ， 知其然更知其所以然 。 很多人都觉得程序就是数据结构+算法+适当的注释 。 不学算法 ， 那就不要学编程了 。 虽然说可能没这么夸张 ， 因为实际上还是有很多小项目是不需要太多算法的 ， 都是代码一个劲的往上叠加就行了 。 但是就算没那么夸张 ， 但是作为一个程序员 ， 逻辑思维就是算法的思路还是很重要的 。
第1题
输入一棵二元查找树 ， 将该二元查找树转换成一个排序的双向链表 。 要求不能创建任何新的结点 ， 只调整指针的指向 。 10/614//481216转换成双向链表4=6=8=10=12=14=16 。 首先我们定义的二元查找树节点的数据结构如下：structBSTreeNode{intm_nValue;//valueofnodeBSTreeNode*m_pLeft;//leftchildofnodeBSTreeNode*m_pRight;//rightchildofnode};
第2题
设计包含min函数的栈 。 定义栈的数据结构 ， 要求添加一个min函数 ， 能够得到栈的最小元素 。 要求函数min、push以及pop的时间复杂度都是O(1) 。
第3题
求子数组的最大和题目：输入一个整形数组 ， 数组里有正数也有负数 。 数组中连续的一个或多个整数组成一个子数组 ， 每个子数组都有一个和 。 求所有的数组的和的最大值 。 要求时间复杂度为O(n) 。
例如输入的数组为1,-2,3,10,-4,7,2,-5 ， 和最大的子数组为3,10,-4,7,2 ， 因此输出为该子数组的和18 。
第4题
在二元树中找出和为某一值的所有路径
题目：输入一个整数和一棵二元树 。 从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径 。 打印出和与输入整数相等的所有路径 。 例如输入整数22和如下二元树10/512/47则打印出两条路径：10,12和10,5,7 。
二元树节点的数据结构定义为：structBinaryTreeNode//anodeinthebinarytree{intm_nValue;//valueofnodeBinaryTreeNode*m_pLeft;//leftchildofnodeBinaryTreeNode*m_pRight;//rightchildofnode};
第5题
查找最小的k个元素题目：输入n个整数 ， 输出其中最小的k个 。 例如输入1 ， 2 ， 3 ， 4 ， 5 ， 6 ， 7和8这8个数字 ， 则最小的4个数字为1 ， 2 ， 3和4 。
举一个例子 ， 数值:0,1,2,3,4,5,6,7,8,9分配:6,2,1,0,0,0,1,0,0,00在下排出现了6次 ， 1在下排出现了2次 ， 2在下排出现了1次 ， 3在下排出现了0次....以此类推..
第7题微软亚院之编程判断俩个链表是否相交给出俩个单向链表的头指针 ， 比如h1 ， h2 ， 判断这俩个链表是否相交 。 为了简化问题 ， 我们假设俩个链表均不带环 。
问题扩展：1.如果链表可能有环列?2.如果需要求出俩个链表相交的第一个节点列?
第8题此贴选一些比较怪的题 ，， 由于其中题目本身与算法关系不大 ， 仅考考思维 。 特此并作一题 。 1.有两个房间 ， 一间房里有三盏灯 ， 另一间房有控制着三盏灯的三个开关 ，
这两个房间是分割开的 ， 从一间里不能看到另一间的情况 。 现在要求受训者分别进这两房间一次 ， 然后判断出这三盏灯分别是由哪个开关控制的 。 有什么办法呢？
2.你让一些人为你工作了七天 ， 你要用一根金条作为报酬 。 金条被分成七小块 ， 每天给出一块 。 如果你只能将金条切割两次 ， 你怎样分给这些工人?
3.★用一种算法来颠倒一个链接表的顺序 。 现在在不用递归式的情况下做一遍 。 ★用一种算法在一个循环的链接表里插入一个节点 ， 但不得穿越链接表 。 ★用一种算法整理一个数组 。 你为什么选择这种方法?★用一种算法使通用字符串相匹配 。 ★颠倒一个字符串 。 优化速度 。 优化空间 。 ★颠倒一个句子中的词的顺序 ， 比如将“我叫克丽丝”转换为“克丽丝叫我” ，
实现速度最快 ， 移动最少 。 ★找到一个子字符串 。 优化速度 。 优化空间 。 ★比较两个字符串 ， 用O(n)时间和恒量空间 。 ★假设你有一个用1001个整数组成的数组 ， 这些整数是任意排列的 ， 但是你知道所有的整数都在1到1000(包括1000)之间 。 此外 ， 除一个数字出现两次外 ， 其他所有数字只出现一次 。 假设你只能对这个数组做一次处理 ， 用一种算法找出重复的那个数字 。 如果你在运算中使用了辅助的存储方式 ， 那么你能找到不用这种方式的算法吗?★不用乘法或加法增加8倍 。 现在用同样的方法增加7倍 。
例如输入5、7、6、9、11、10、8 ， 由于这一整数序列是如下树的后序遍历结果：
8/610//57911因此返回true 。 如果输入7、4、6、5 ， 没有哪棵树的后序遍历的结果是这个序列 ， 因此返回false 。
第10题翻转句子中单词的顺序 。 题目：输入一个英文句子 ， 翻转句子中单词的顺序 ， 但单词内字符的顺序不变 。
句子中单词以空格符隔开 。 为简单起见 ， 标点符号和普通字母一样处理 。 例如输入“Iamastudent.” ， 则输出“student.aamI” 。
第11题求二叉树中节点的最大距离...
如果我们把二叉树看成一个图 ， 父子节点之间的连线看成是双向的 ， 我们姑且定义"距离"为两节点之间边的个数 。 写一个程序 ， 求一棵二叉树中相距最远的两个节点之间的距离 。
第12题题目：求1+2+…+n ， 要求不能使用乘除法、for、while、if、else、switch、case等关键字以及条件判断语句（A?B:C） 。
【常见算法笔试和面试题整理（带答案）】第13题题目：输入一个单向链表 ， 输出该链表中倒数第k个结点 。 链表的倒数第0个结点为链表的尾指针 。 链表结点定义如下：structListNode{intm_nKey;ListNode*m_pNext;};
有需要的朋友可以私信回复“源码”免费领取！


    推荐阅读


    上一篇：区块链每日解读|特斯拉拒绝拼多多的背后，是对价格体系崩盘的恐惧

    下一篇：IT之家|苹果iPad Air 4概念图曝光：据爆料制作，iPad Pro设计风格