算法面试表格

1. 海康威视研究院算法岗面试经验

海康威视研究院算法岗面试经验总结如下：

1. 面试流程：

   • 自我介绍：简短介绍个人背景、教育经历及专业技能。
   • 重点项目介绍：详细阐述参与过的重点项目，突出自己的贡献和成果。
   • 项目提问：面试官会针对项目细节进行提问，考察面试者的项目经验和问题解决能力。
   • 机器学习与CV提问：涉及逻辑回归、梯度弥散与爆炸、激活函数、L2与L1正则化、数据增强、小样本学习、防止过拟合等知识点。
   • 算法题提问：考察面试者的逻辑思维能力和数据结构与算法的应用能力，如IOU计算、闭合曲线面积计算、图像旋转算法等。
   • 对面试者问题的回答：面试者可以提出自己的问题，与面试官进行交流。

2. 专业技能要求：

   • 深入理解机器学习理论：熟悉常用的损失函数、激活函数、正则化方法，并能分析并解决实际项目中的问题。
   • 算法题解决能力：具备较强的逻辑思维能力，能够灵活运用数据结构与算法解决实际问题。
   • 计算机基础：掌握堆与栈的区别、Python编程的全局解释器锁与上下文管理器等基础知识。

3. 面试表现建议：

   • 深入分析问题的能力：能够清晰地解释使用特定损失函数的原因，提出解决项目问题的策略。
   • 理论结合实际：在回答问题时，尽量结合项目经验，展现自己的实际操作能力。
   • 逻辑思维清晰：在算法题和理论问题回答中，保持清晰的逻辑思路，条理分明。
   • 积极互动：在面试过程中，积极与面试官交流，展示自己的专业素养和求知欲。

4. 综合能力评估：

   • 面试官会通过面试者的回答，评估其专业技能、逻辑思维、问题解决能力和实际项目经验。
   • 面试者需要展现出扎实的理论基础和实际项目经验，以及灵活应对各类问题的能力。

2. 【程序猿必备】数据结构与算法精选面试题

编程面试主要由数据结构问题和算法问题组成，这些问题旨在评估应聘者的编程技能、问题解决能力和对基本数据结构与算法的理解。以下是一些精选的数据结构与算法面试题，涵盖了数组、链表、字符串、二叉树以及其他常见的算法问题。

数组是最基本的数据结构之一，它将元素存储在一个连续的内存位置。数组的主要优点是，如果知道索引，它可以提供快速的O(1)搜索，但从数组中添加和删除元素通常较慢。

• 如何在一个1到100的整数数组中找到丢失的数字？

  方法：可以使用求和公式（n*(n+1)/2）计算1到100的总和，然后减去数组中所有元素的和，得到的差值就是丢失的数字。

• 如何在给定的整数数组中找到重复的数字？

  方法：使用哈希表（字典）记录每个数字出现的次数，或者对数组进行排序后检查相邻元素是否相同。

• 如何在未排序整数数组中找到最大值和最小值？

  方法：遍历数组一次，同时记录最大值和最小值。

• 如何找到数组所有和等于一个给定数的数对？

  方法：使用哈希表记录已经遍历过的元素，对于当前元素，检查是否存在一个已遍历过的元素与之相加等于给定数。

• 如果一个数组包含多重复制，那么如何找到重复的数字？

  方法：同样可以使用哈希表记录每个数字出现的次数，当发现某个数字出现次数超过1时，即为重复数字。

• 在Java中如何从给定数组中删除多重复制？

  方法：使用HashSet（集合）去重，或者利用排序后相邻元素相同的特性进行去重。

• 如何使用快速排序算法对整数数组进行排序？

  方法：快速排序是一种分治算法，通过选择一个基准元素，将数组分为两部分，递归地对这两部分进行排序。

• 如何在不使用任何库的情况下从数组中删除多重复制？

  方法：手动实现去重逻辑，如使用两个指针或哈希表等。

链表是另一种常见的数据结构，它以节点的方式存储元素，每个节点包含存储的值和指向下一个节点的指针。链表的主要优点是插入和删除操作较快，但查找元素通常较慢。

• 如何在一次遍历中找到单个链表的中值？

  方法：使用快慢指针，快指针每次移动两步，慢指针每次移动一步，当快指针到达链表末尾时，慢指针指向的节点即为中值节点。

• 如何证明给定的链表是否包含循环？如何找到循环的头节点？

  方法：使用快慢指针，如果链表存在循环，快指针和慢指针最终会相遇。相遇后，将其中一个指针重新指向链表头部，两个指针同时移动，再次相遇时即为循环的头节点。

• 如何使链表反向？

  方法：遍历链表，逐个改变节点的指针方向。

• 如何在不使用递归的情况下逆转单链表？

  方法：使用迭代方法，通过三个指针（prev、curr、next）来逆转链表。

• 如何得到单链表的长度？

  方法：遍历链表，计数节点的数量。

字符串是编程面试中的另一个热门话题，因为字符串操作是编程中常见的需求。字符串可以看作是一个字符数组，因此解决基于数组的编程问题所学习的技术也可以用于解决字符串编程问题。

• 如何从字符串打印重复字符？

  方法：遍历字符串，使用哈希表记录每个字符出现的次数，然后打印出现次数大于1的字符。

• 如何检查两个字符串是否互相颠倒？

  方法：将其中一个字符串反转后，比较两个字符串是否相等。

• 如何从字符串中打印第一个非重复字符？

  方法：使用哈希表记录每个字符出现的次数，然后遍历字符串找到第一个出现次数为1的字符。

• 如何使用递归反转给定的字符串？

  方法：递归地交换字符串的首尾字符，直到达到字符串的中间位置。

• 如何计算字符串中给定字符的出现次数？

  方法：遍历字符串，计数给定字符的出现次数。

二叉树是一种重要的树形数据结构，每个节点最多有两个子节点（左子节点和右子节点）。二叉树在编程面试中经常出现，因为它们是许多算法和数据结构的基础。

• 如何实现二叉搜索树？

  方法：定义节点类，包含值、左子节点和右子节点的引用，然后实现插入、查找和删除等操作。

• 如何在给定的二叉树中执行先序遍历？

  方法：按照“根节点-左子树-右子树”的顺序遍历二叉树。

• 如何在不使用递归的情况下按顺序遍历给定的二叉树？

  方法：使用栈或队列等辅助数据结构实现迭代遍历。

• 如何实现后序遍历算法？

  方法：按照“左子树-右子树-根节点”的顺序遍历二叉树。

除了基于数据结构的问题外，大多数编程工作面试还会涉及算法、设计、位操作和基于逻辑的问题。

• 如何实现冒泡排序算法？

  方法：重复地遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复进行的，直到没有再需要交换的元素为止。

• 如何实现迭代快速排序算法？

  方法：选择一个基准元素，通过一趟排序将待排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

• 如何实现归并排序算法？

  方法：采用分治法（Divide and Conquer），将一个大列表分成两个小列表，分别排序，然后将两个已排序的小列表合并成一个完整的排序列表。

• 如何在不使用第三个变量的情况下交换两个数字？

  方法：通过加减法或位运算实现两个数的交换。

以下是一些相关图片，展示了数据结构与算法在编程面试中的重要性：

准备这些面试题不仅有助于提高你的编程技能，还能让你对在真正的编程工作面试中可能遇到的问题有更深入的了解。一旦你掌握了这些问题，你就应该有足够的信心参加任何电话或面对面的面试。

3. 算法面试题——动态规划Kadane’s algorithm

动态规划是大公司面试必考的算法题。其中，“最大子序和”是其中的经典：

面试官：年轻人，前面表现的不错嘛！看下这道题，给你这个数组[-2, 1, -3, 4, -1, 2, 1, -5, 4]，找到其中和最大的连续子数组，返回最大值。

我：

使用Kadane’s Algorithm解决这个问题。Kadane’s Algorithm可以简单理解为动态规划的一种应用，它通过维护两个变量：localMax和globalMax，来计算连续子数组的最大和。localMax表示以当前元素结尾的子数组的最大和，而globalMax则记录遍历过程中发现的最大值。

我们以数组[-2, 1, -3, 4, -1, 2, 1, -5, 4]为例，从左到右遍历数组。

当遍历到元素4时，localMax为4（因为4是当前元素），globalMax也更新为4（因为这是遍历到的第一个元素）。

遍历到元素-1时，我们考虑两种情况：
1. 包括前面的元素4，即localMax更新为4 + (-1) = 3。
2. 不包括前面的元素4，即从元素-1开始新的子数组。由于-1 > 3，我们选择-1作为新的localMax。
因此，globalMax更新为-1。

遍历到元素2时，localMax为2（因为2 > 1），globalMax更新为2。

遍历到元素1时，localMax更新为3（因为3 > 2 + 1），globalMax也更新为3。

遍历到元素-5时，我们考虑两种情况：
1. 包括前面的元素3，即localMax更新为3 + (-5) = -2。
2. 不包括前面的元素3，即从元素-5开始新的子数组。由于-5 < 3，我们选择3作为新的localMax。
因此，globalMax更新为3。

遍历到元素4时，localMax为4（因为4 > 3 + 4），globalMax更新为4。

最终，我们得到数组的最大子序和为4。

动态规划和Kadane’s Algorithm在解决“最大子序和”问题时，通过维护局部最优解和全局最优解，避免了暴力算法中的重复计算，大大提高了效率。

理解Kadane’s Algorithm的关键在于，它通过比较当前元素和当前元素加上前面元素的最大和，来决定是否更新局部最优解。这样，我们不仅避免了重复计算，还能在遍历过程中不断更新全局最优解。

此外，Kadane’s Algorithm在解决类似问题时，如“买卖股票的最佳时机”，同样可以应用动态规划的思想，通过维护局部最优解和全局最优解，来找到最优策略。

动态规划和Kadane’s Algorithm是解决一系列动态规划问题的有效工具，通过理解和应用这些算法，可以大大提高解决问题的效率和准确性。

4. 面试会出哪些经典算法题

如下：

1、排序算法∶快速排序、归并排序、计数排序

2、搜索算法∶回溯、递归、剪枝技巧

3、图论∶最短路、最小生成树、网络流建模

4、动态规划：背包问题、最长子序列、计数问题

5、基础技巧：分治、倍增、二分、贪心

6、数组与链表：单/双向链表、跳舞链

7、栈与队列

8、树与图：最近公共祖先、并查集

9、哈希表

10、堆：大/小根堆、可并堆

11、字符串∶字典树、后缀树

算法简介：

算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。

如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。

算法中的指令描述的是一个计算，当其运行时能从一个初始状态和（可能为空的）初始输入开始，经过一系列有限而清晰定义的状态，最终产生输出并停止于一个终态。一个状态到另一个状态的转移不一定是确定的。随机化算法在内的一些算法，包含了一些随机输入。

形式化算法的概念部分源自尝试解决希尔伯特提出的判定问题，并在其后尝试定义有效计算性或者有效方法中成形。

这些尝试包括库尔特·哥德尔、Jacques Herbrand和斯蒂芬·科尔·克莱尼分别于1930年、1934年和1935年提出的递归函数，阿隆佐·邱奇于1936年提出的λ演算，1936年Emil Leon Post的Formulation 1和艾伦·图灵1937年提出的图灵机。即使在当前，依然常有直觉想法难以定义为形式化算法的情况。