投雪花的姐妹兄弟看过来,他家OA是真·北美最有辨识度,两道题没有一道是模板题,但题库复现率高到离谱。
我运气好,撞上的俩都是地里和小红书被讨论烂的经典题,做的时候基本在默写。趁热乎分享👇
基本盘
平台HackerRank,两道题,Medium-Hard档
⚠️数据规模全是2×10⁵起步,暴力解直接见祖宗,必须先想清楚复杂度再动手
第一题:Minimum Height🌲
给一棵有根树,有max_operations次机会,每次可以剪一个节点连子树一起挂到根下面,问树的高度最小能压到多少。
破题信号词:「最小化最大值」→ 条件反射二分答案!
二分高度H,check函数自底向上贪心:哪个节点再往上就超H了,就在那儿剪,越深剪越划算。
两个坑:
🕳️ 被剪下来的子树自己也有高度,不能超过H-1,漏了直接WA
🕳️ n到2×10⁵,Python递归DFS会爆栈,老实写迭代版
复杂度O(n log n),稳过。
第二题:Pod Autoscaler📦
k8s扩缩容的皮,数组题的芯。两种操作:单独把某服务改成x;或者全体设个下限x。问跑完所有日志每个服务是多少。
老实模拟?O(n×m)=4×10¹⁰,超时超到天上去☠️
破局点:别管过程,直接想终值由什么决定——
就俩东西:最后一次被单独改的值 + 这之后出现过的最大全局下限,取max完事。
实现三步:记每个服务最后单改的时间和值→对全局操作建后缀最大值数组→逐个取max。
O(n+m),想通了十几行代码,想不通只能对着暴力解干瞪眼,典型思维题🧠
总结
雪花不考你会不会写代码,考你能不能读完题三分钟内定位到正确的算法框架。
好消息:题库更新不勤,经典题反复出,考前把地里近半年雪花帖过一遍,大概率撞原题。
我备考用的InterviewShow的北美大厂OA题库,这两道都在里面带思路提示,他家还有OA和面试辅助,需要的自己去看~
祝大家都能开题即默写,20分钟潇洒走人✌️