目录[隐藏][展示]
- 1.你如何定义一个数组?
- 2. 动态数组:它们是什么? 是什么让它们与基本数组不同?
- 3. 数组和字典有何不同?
- 4. 列出数组的一些优点和缺点。
- 5. “稀疏数组”指的是什么?
- 6. 你什么时候会选择链表而不是数组?
- 7. 索引数组与关联数组的区别是什么?
- 8. 堆比有序数组有什么优势?
- 9. 我们可以将数组的大小定义为负数吗?
- 10. 如何在 1 到 100 个元素的数组中找到缺失的整数?
- 11.如何找到数组中元素的索引?
- 12. 如何从数组中删除特定元素?
- 13. 如何验证两个数组的相等性?
- 14. 当我们讨论数组时,你所说的“维度”和“下标”是什么意思?
- 编码面试问题
- 15. 在具有指定总和的数组中寻找一对
- 16. 线性时间的二进制数组排序
- 17. 找出数组中最大的二整数积。
- 18.如何将数组的所有零移到末尾
- 19. 如何对一次操作中切换的两个条目的数组进行排序。
- 20. 如何就地组合两个排序数组。
- 21. 如何重新排列高低交替排列的项目数组?
- 22. 如何在不使用除法运算符的情况下用数组中每个元素的乘积替换数组的每个元素?
- 23. 在对数时间内找到数组中最奇数的元素
- 24.如何获取循环数组中每个元素的后续较大元素?
- 25. 求一个数组的倒数?
- 26. 什么是雨水滞留问题?
- 结论
编码面试包含一系列 DSA 问题。 如果您准备好迎接即将到来的 FAANG 或其他一级技术企业的技术面试,那么您应该精通阵列。
在大多数编码面试中,它仅次于 Strings。 数组是一组相关的数据元素,它们在内存中彼此靠近。
由于它们连接到所有编程语言,例如 C、C++、Java、Python、Perl 和 Ruby,它们无处不在。 继续阅读一些练习编码挑战和基于数组的面试问题和答案。
在这篇文章中将使用 Python 来解决编码问题,因为它易于使用、理解并且我们大多数人都必须熟悉它。
让我们开始。
1.你如何定义一个数组?
- 一组相关的数据类型是一个数组。
- 数组总是固定的。
- 数组对象将相同类型的变量存储在多个位置。
- 原始类型和对象引用都与它兼容。
2. 动态数组:它们是什么? 是什么让它们与基本数组不同?
动态数组(也称为可增长数组、可调整大小数组、可变数组或 Java 中的 ArrayList)提供的自动缩放是一个显着优势。
由于数组具有固定大小,因此您必须始终知道数组将存储多少元素。 另一方面,动态数组会随着您向其中添加其他成员而增长,因此您无需事先知道其确切大小。
3. 数组和字典有何不同?
这是一组经常被问到的基于基本面的面试问题。 以下是数组和字典之间的主要区别:
- 数组是相似项目的有序列表。 另一方面,字典具有键值对。
- 数组大小可以动态变化。 这种动态的想法在字典中是不存在的。
- 在使用数组之前,必须指定其大小。 字典大小不需要定制。
- 如果您希望扩展数组的大小,请使用 Redim 语句。 在字典中,可以在没有声明的情况下添加元素。
4. 列出数组的一些优点和缺点。
优点:
- 数组可以同时对多个元素进行排序。
- 其他名称 数据结构,就像堆栈、队列、链表、树、图等一样,可以在数组中实现。
- 索引可用于到达数组的元素。
缺点:
- 数组的大小必须提前声明。 然而,在数组声明的那一刻,我们可能不知道我们需要的大小。
- 数组的结构是静态的。 这意味着数组大小始终是固定的,并且内存分配不能增加或减少。
5. “稀疏数组”指的是什么?
稀疏数组是具有大量零值条目的数据数组。 相反,密集数组包含其大部分具有非零值的项目。 将数字转换为对象的稀疏数组的索引可能包含间隙。 与 HashMap 相比,它们更节省内存。
6. 你什么时候会选择链表而不是数组?
当使用链表而不是数组时,请考虑:
- 您不需要任何元素即可进行随机访问。
- 在时间可预测性至关重要的情况下,您需要从列表中进行恒定时间的插入和删除。
- 为了创建优先级队列,您可能需要将项目放置在列表的中心。
- 你不知道这个列表会有多长。 如果数组大小增加,您必须重新声明和复制内存,就像使用简单数组一样。
7. 索引数组与关联数组的区别是什么?
下表列出了关联数组和索引数组之间的主要区别。
- 文本或数字格式的键值对用于对关联数组进行排序。 索引数组的键都是数字的,每个键都连接到一个不同的值。
- 在关联数组中,键可能是字符串。 具有从 0 开始的整数键的索引数组。
- 一个包含两列的表格模拟了关联数组的行为。 与单列表类似的是索引数组。
- 映射是一种关联数组类型。 索引数组不是地图。
8. 堆比有序数组有什么优势?
利用堆而不是排序数组的时间效率是关键优势。 虽然堆操作更快,但对数组进行排序需要大量时间。 堆可以比数组排序更快地发现最小元素。
可以使用排序数组以两种方式之一排列给定的数字集合。 另一方面,对于给定的数字集合,可能存在多个潜在堆。
9. 我们可以将数组的大小定义为负数吗?
不,我们不能将负整数定义为数组的大小。 如果我们声明,就不会出现编译时错误。 然而,在运行时,我们会遇到 NegativeArraySizeException。
10. 如何在 1 到 100 个元素的数组中找到缺失的整数?
该系列的总数可以通过应用以下函数来计算:n (n + 1) / 2
只有当数组没有任何重复项或缺少一个以上整数时,此函数才会运行。 数组是否有重复元素,可以对数组进行排序,看是否有等价的元素。
11.如何找到数组中元素的索引?
元素的索引可以通过线性或二分搜索来发现。 在找到所需元素的匹配项之前,线性搜索函数会遍历数组中的每个元素。 一旦找到匹配的元素,它就会返回索引。 因此,线性搜索的时间复杂度为 O. (n)。 排序数组和未排序数组都可以使用线性搜索。
使用二分查找,它不断地将数组分成两半,直到区间的中位数与所需元素匹配并提供索引,如果数组已排序,您可以获得元素的索引。 因此,二分查找的时间复杂度为 O. (log n)。
12. 如何从数组中删除特定元素?
由于您不能简单地从原始数组中删除元素,因为它们是具有定义大小的固定集合,因此面试官正在寻求您提出不同的方法并处理问题提出的问题。 最好的做法是创建一个新数组以删除一个元素。 您可以复制此数组中第一个数组中的元素,并且只包含您希望删除的元素。
另一种策略涉及在数组中找到目标元素,然后反转目标元素右侧的所有项目的顺序。
13. 如何验证两个数组的相等性?
您必须首先验证提供的两个数组的长度。 当两个数组的长度相等时,比较两个数组的匹配项。 这两个数组将被视为相等。 如果每个对应关系中的每一对分量都是相等的。 如果数组的大小很大,则不建议使用这种方法检查两个数组的相等性,因为这会花费很多时间。 您也可以使用 Arrays 类中包含的 equals() 方法,但是,如果面试官要求您在不使用内置方法的情况下比较两个数组,这种方法会很有用。
14. 当我们讨论数组时,你所说的“维度”和“下标”是什么意思?
数组的“维度”是标识每个单独成员所需的索引或下标的数量。 下标和尺寸可能不清楚。 维度是对允许键范围的描述,而下标是一个数字。 每个数组维度只需要一个下标。
例如,数组 arr[10][5] 有两个维度。 一个尺寸为 10,另一个尺寸为 5。 要处理其组件,您需要两个下标。 两者都在 0 到 4 之间; 介于 0 和 9 之间的一个,包括 XNUMX 和 XNUMX。
编码面试问题
15. 在具有指定总和的数组中寻找一对
例如,
输入:
- 数字 = [8, 7, 2, 5, 3, 1]
- 目标= 10
输出:
- 找到一对 (8, 2)
- Or
- 找到一对 (7, 3)
输入:
- 数字 = [5, 2, 6, 8, 1, 9]
- 目标= 12
输出:
- 未找到配对
16. 线性时间的二进制数组排序
在线性时间和固定区域内对二进制数组进行排序。 输出应该首先显示全零,然后全是一。
例如,
- 输入:{ 1, 0, 1, 0, 1, 0, 0, 1 }
- 输出:{ 0, 0, 0, 0, 1, 1, 1, 1 }
一种直接的方法是计算数组的 0 总数,比如 k,然后用 0 填充数组中的前 k 个索引,用 1 填充剩余的索引。作为替代方案,我们可以计算数组中总共有多少个 1数组 k,用 1 填充数组中的最后 k 个索引,其余的索引用 0 填充。
给定的方法具有 O(n) 时间复杂度并且不使用额外的存储,其中 n 是输入的大小。
17. 找出数组中最大的二整数积。
在一个整数数组中找到两个数的最大乘积。
以数组 10 3 5 6 2 为例。 (-10, -3) 或 (5, 6) 对是最高乘积。
考虑每个元素组合并找出他们的产品是一种愚蠢的方法。 如果当前对的乘积大于迄今为止获得的最大乘积,则更新最大乘积。 最后打印最终产品的组件。
上面的解决方案,其中 n 是输入的数量,时间复杂度为 O(n2) 并且不占用更多空间。
18.如何将数组的所有零移到末尾
将整数数组中的所有零移动到末尾。 答案应该避免使用常量空间并保持数组组件的相对顺序。
输入:{1,2,3,0,8,0,4,7,XNUMX}
输出将是 {1,2,3,8,4,7,0,0}
如果当前元素不为零,则将元素放在数组中的以下可用位置。 处理完数组的项目后,用 0 填充所有剩余的索引。
前面的解决方案具有 O(n) 时间复杂度,其中 n 是输入的大小。
19. 如何对一次操作中切换的两个条目的数组进行排序。
给定两个交换的项目和一个所有元素按升序排列的数组,在线性时间内对数组进行排序。 假设数组不包含重复项。
输入:= [1,9,3,4,7,2] 或 [9,3,7,2,1,4] 或 [2,4,1,7,3,9]
输出:= [1,2,3,4,7,9]
从数组中的第二个元素开始,目标是将每个元素与其前一个元素进行比较。 通过取两个指针 x 和 y 来存储争议的位置。
如果前者大于后者,则将 x 更新为前一个元素的索引,将 y 更新为当前元素的索引。 如果结果是前一个元素大于当前元素,则将 y 更新为当前元素的索引。
最后,在我们处理完每对相邻的元素后,切换索引 x 和 y 处的元素。
由于上述方法仅对大小为 n 的输入数组执行单次扫描,因此其时间复杂度为 O(n)。 该解决方案不需要额外的空间。
20. 如何就地组合两个排序数组。
合并数组 X[] 和 Y[] 的项目——两个大小分别为 m 和 n 的排序数组——通过保持排序顺序,即用前 m 个最小元素填充 X[],用前 m 个最小元素填充 Y[]剩余元素。
如果数组 X[] 中的一个元素已经在正确的位置(即其余元素中最小的那个),则忽略它; 否则,用最小的元素替换它,它也恰好是 Y[] 的第一个成员。 要在交换后保留排序顺序,请将元素(现在位于 Y[0])转移到 Y[] 中的正确位置。
第一个数组的大小为 m,第二个数组的大小为 n,时间复杂度为 O(mn)。
21. 如何重新排列高低交替排列的项目数组?
重新排列一个整数数组,使每个后续成员都大于前面和后面的元素。 假设数组不包含任何重复元素。
对数组进行排序或利用额外的空间对于有效的方法来说不是必需的。 该计划首先是数组的第二个成员,每次循环迭代增加两个。
如果最后一个元素超过第一个元素,则交换组件。 同样,如果后面的元素大于当前元素,则切换这两项。 我们将在循环结束时获得符合指定限制的所需数组。
22. 如何在不使用除法运算符的情况下用数组中每个元素的乘积替换数组的每个元素?
在不使用除法运算符的情况下,将整数数组中的每个元素替换为所有其他元素的乘积。
在线性时间和恒定空间中,我们可以利用递归来解决这个问题。 递归计算右子数组中每个元素的乘积并将左子数组乘积作为函数参数传递是这个概念。
时间复杂度为 O(n)。
23. 在对数时间内找到数组中最奇数的元素
给定一个整数数组,其中除了一个成员之外的所有成员都出现偶数次,问题是确定这个元素出现了多少次。 如果相同的元素在数组中成对出现并且同一行中的给定元素的实例永远不会超过两个,则在对数时间和恒定空间中找到奇数出现的元素。
XOR 操作使我们能够在线性时间内解决这个问题。 目标是对数组中的每个元素进行异或。 在偶数出现的元素相互抵消后,只剩下奇数出现的元素。
这个问题甚至可以在 O(log(n)) 时间内解决。
24.如何获取循环数组中每个元素的后续较大元素?
应该定位循环整数数组中每个元素的下一个更大的元素。 数组中元素 x 之后的第一个较大整数是该元素的后续较大元素。
从右到左,我们可以对数组项进行操作。 目标是对每个元素 x 进行循环,直到堆栈为空或我们在其顶部有更高的元素。 将 x 的下一个较大元素设置为出现在堆栈顶部。
25. 求一个数组的倒数?
求一个数组的反转总数。 如果 I j) 和 (A[i] > A[j]),则一对 I j) 称为数组 A 的反转。 我们必须计算数组中的每一对。
计算所有小于其右侧的数组成员并将结果添加到输出是一种简单的方法。
该解决方案的复杂度为 O(n2),其中 n 是输入的大小。
26. 什么是雨水滞留问题?
在一组宽度为一个单位的给定条中找到最多可以捕获的水被称为“捕获降雨”问题。
目标是确定可以放置在每个条的左侧和右侧的最高条。 左边和右边的前导条的最小值减去当前条的高度,就是每个条顶部存储的水量。
结论
与其他数据结构主题相比,数组更简单。 为了解决数组面试问题,您需要对数组有基本的了解。
您应该广泛地复习数组的基础,包括数组操作(从声明/创建数组到访问/修改数组项),以及循环、递归和基本运算符等编程概念,以便成功回答数组面试问题。 完全认清问题。
如果您有任何疑问,您应该寻求澄清。 考虑将问题划分为更易于管理的部分。 确保在开始编程之前记住算法; 写下来或在流程图中可视化。 然后开始写代码。
发表评论