Skip to content

编码面试的间隔备忘单

原文:https://www.techinterviewhandbook.org/algorithms/interval/

简介

区间问题是数组问题的一个子集,其中给你一个二元数组的数组(一个区间),两个值代表一个开始值和一个结束值。区间问题被认为是数组家族的一部分,但它们涉及一些常见的技术,因此它们被提取到自己的特殊部分。

一个区间数组的例子:[[1, 2], [4, 7]]

对于那些以前没有尝试过的人来说,区间问题可能很棘手,因为当它们重叠时,需要考虑的情况非常多。

面试时要注意的事情

  • 向面试官澄清[1, 2][2, 3]是否被视为重叠区间,因为这会影响你如何填写你的平等检查。
  • 明确[a, b]的间隔是否严格遵循a < b ( a小于b)

拐角情况

  • 没有间隔
  • 单一区间
  • 两个间隔
  • 非重叠区间
  • 在另一个时间间隔内完全消耗的时间间隔
  • 重复的间隔(完全相同的开始和结束)
  • 恰好在另一个区间结束处开始的区间- [[1, 2], [2, 3]]

技巧

按起点 对区间数组进行排序

区间问题的一个常见例程是按照每个区间的起始值对区间数组进行排序。这一步对于解决合并区间问题至关重要。

检查两个区间是否重叠

熟悉编写代码检查两个区间是否重叠。

def  is_overlap(a, b):  return a[0]  < b[1]  and b[0]  < a[1] 

合并两个区间

def  merge_overlapping_intervals(a, b):  return  [min(a[0], b[0]),  max(a[1], b[1])] 

基本问题

如果你在学习这个话题,这些是需要练习的基本问题。

推荐练习题

这些是在你为题目学习并练习了基本问题后推荐练习的问题。

推荐课程

AlgoMonsterT3】

AlgoMonster 旨在帮助你在最短的时间内通过技术面试。由谷歌工程师开发的 AlgoMonster 使用数据驱动的方法来教你最有用的关键问题模式,并有内容帮助你快速修改基本的数据结构和算法。最重要的是,AlgoMonster 不是基于订阅的——支付一次性费用,就可以获得终身访问今天加入七折优惠→

寻找编码面试:编码问题的模式

设计大师的这门课程扩展了推荐练习题中的问题,但从问题模式的角度来进行练习,这是一种我也同意的学习方法,我个人也使用这种方法来更好地编写面试代码。本课程允许你用 Java、Python、C++、JavaScript 来练习选定的问题,并提供这些语言的示例解决方案以及一步一步的可视化。学习和理解模式,而不是背答案! 现在获得终身使用权→

掌握编码面试:数据结构+算法

这本 Udemy 畅销书是评分最高的面试准备课程之一(4.6 星,21.5k 评分,135k 学生),包含了价值 19 个小时的内容。像技术面试手册一样,它超越了编码面试,涵盖了简历,非技术面试,谈判。是一个全包!请注意,JavaScript 用于编码演示。 结账→



回到顶部