面试上一个神仙公司,运维50岁了,其他研发也45多了。公司不裁员,只要好好干活就行。我打算进去了,今年35岁了,是不是进入有点早
刚看到个贴子,说网友面试到一家“神仙公司”,运维50岁还在干,研发45岁也稳稳当当,公司不裁员,只要好好干活就行。楼主35岁就想进去,还担心是不是去早了,哈哈这心态挺真实。
网友回帖里有人说这种公司稳定但天花板低,也有人说能干到老是福气。嗯…我觉得关键还是看你图啥。如果你追求稳定、节奏正常,那这种环境就像早上排队买早餐,虽然慢点,但排到了心安;但要是你还想折腾、想冲晋升,那可能会觉得节奏太稳像坐慢车。
换个角度想,35岁进稳定公司绝对不算早,反而是刚刚合适。比起盲卷,能找到一个踏实干活的地方,本身就是稀缺资源。说到底还是性价比的问题——岗位稳、团队成熟、风险低,这些对职场中后期的人太重要了。【备注:文末可领最新资料】
面试题:天际线问题
说“天际线问题”这个名字挺浪漫的哈,但本质就是个很典型的扫线+堆的算法题,用 Python 写起来也不算难,就是第一次接触会有点绕,我慢慢聊一遍。
想象你站在城市对面河边,看过去一排高楼,能看到的轮廓线就是“天际线”。 题目一般给你一堆楼,每栋楼用三个数表示:
[L, R, H]
L:左边界 x 坐标
R:右边界 x 坐标
H:高度
所有楼都紧贴地面,相互之间可以重叠。我们要输出的是一串“关键点”:
[x, h]
x:从这个 x 开始,最高楼的高度变成 h
串起来就是天际线的折线图。比如有一段高度从 0 → 3 → 5 → 0,那我们就要在高度变化的地方记录点。
暴力想法为什么不行
很多人第一反应是:要不我把所有 x 都离散化一遍,比如从最小 L 到最大 R,每个单位点都算一下当前最高楼,然后再把这些高度压成折线?
问题是:
坐标可能很大,比如到 10^9,你根本不可能从 0 枚举到 10^9 即便离散化,只要楼很多,这样扫一整条 x 轴也是 O(坐标范围) 的复杂度,直接超时
所以正确的方向是:我只关心“高度会变的那些 x”,中间那些高度不变的地方完全可以跳过。
扫描线的基本思路
比较经典的套路就是“扫描线”:
想象一根竖直的线,从左往右扫过整个平面 每到一个“关键 x”,我们更新一下当前有哪些楼是“活跃的”(覆盖到当前 x) 随时维护一个“当前最高楼高度” 一旦最高高度发生变化,就把 [x, 当前最高高度]记下来
关键问题有两个:
怎么表示这些“关键 x” 怎么快速知道“当前最高楼高度”
把楼拆成一堆“事件”
每栋楼 [L, R, H],我们可以拆成两个事件:
在 x = L处,这栋楼开始生效在 x = R处,这栋楼结束
于是我们构造一个数组:
(L, -H, R) # 楼开始:高度取负数是个小技巧
(R, 0, 0) # 楼结束:高度为 0,表示只是一个结束标记
为啥高度要取负数?
因为 Python 的 heapq 是小根堆,而我们想要“最高的楼”,所以把高度取负数,这样“原来越高的楼,负数越小”,放在堆顶刚刚好。
然后我们把所有事件按照 x 排序:
x小的在前同一个
x上:先处理“楼开始”(负高度更小) 再处理“楼结束”(高度为 0)
这样可以保证同一个位置上,先把新楼加进去,再计算高度变化,避免边界处理出锅。
用堆维护“当前最高楼”
我们用一个堆 heap 来维护“当前覆盖这个 x 的所有楼”:
堆的元素是
(neg_h, r):neg_h:负高度r:这栋楼的右边界,用来判断它啥时候过期
遍历事件时,逻辑大概是:
先把已经“过期”的楼清掉: 只要堆顶的 r <= 当前 x,说明这栋楼已经不覆盖当前 x 了,弹出如果当前事件是“楼开始”(neg_h != 0),把 (neg_h, R)加进堆看一眼堆顶,此刻最高高度是 curr_h = -heap[0][0]如果 curr_h和上一个高度prev_h不一样,说明天际线发生变化,记录一个点[x, curr_h]
整体时间复杂度大概是:O(n log n)
排序 O(n log n)每栋楼进堆出堆一次,也是 O(n log n)
Python 代码实现一遍
直接给你一个函数版本,输入是楼的列表,输出是天际线关键点:
import heapq
from typing import List
defgetSkyline(buildings: List[List[int]]) -> List[List[int]]:
events = []
for L, R, H in buildings:
# 楼开始事件:高度取负保证大楼优先
events.append((L, -H, R))
# 楼结束事件:高度为 0,只用 x 触发清理
events.append((R, 0, 0))
# 按 x 排序,同 x 时,楼开始(-H) 会排在楼结束(0)前面
events.sort()
# 堆里放 (neg_h, R),初始放一个地面高度 0
heap = [(0, float('inf'))]
prev_h = 0
res = []
for x, neg_h, R in events:
# 先把已经结束的楼从堆里清掉
while heap and heap[0][1] <= x:
heapq.heappop(heap)
# 遇到楼开始事件,加入堆
if neg_h != 0:
heapq.heappush(heap, (neg_h, R))
# 当前最高高度
curr_h = -heap[0][0]
# 如果高度变了,就记录一个关键点
if curr_h != prev_h:
res.append([x, curr_h])
prev_h = curr_h
return res
你可以简单测一下,比如:
print(getSkyline([
[2, 9, 10],
[3, 7, 15],
[5, 12, 12],
[15, 20, 10],
[19, 24, 8]
]))
会得到一串 [x, h] 的点,把这个点列表画成折线,就是那条“城市天际线”。
这个题看上去是几何题,实际上是“扫描线 + 最大堆 + 精细排序规则”的综合练习,重点就是:
只在“事件点”处理高度变化 用堆维护当前最高楼 注意结束楼的“过期清理”和同 x 排序细节
搞懂这一套,后面遇到矩形覆盖、区间合并、最大区间之类的题,思路会顺很多。
-END-
我为大家打造了一份RPA教程,完全免费:songshuhezi.com/rpa.html
虎哥作为一名老码农,整理了全网最全《python高级架构师资料合集》,总量高达650GB。