databricks电面挂经

oumizx

您需要登录才可以下载或查看附件。没有帐号？注册账号

x

一个亚裔小哥面的，之前就把LC上tag题做了下，他家流程非常长。一轮电面一轮3小时task一轮HR面最后再是4轮onsite。题目是

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

这题之前没做过面试时没做出来。move on了。

lurukami · 2020-10-29 12:13:24

请问他会给你你root node吗？

nina9128

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

Rootuny

楼主能解释下，直接dfs遍历是O1空间吗，parent node有什么用呢

adwith

Rootuny 发表于 2020-8-30 12:14
楼主能解释下，直接dfs遍历是O1空间吗，parent node有什么用呢

dfs遍历需要stack是O(n)

Rootuny

这题好难啊

_Perry · 2020-11-29 06:48:21

这是一个用O(1) space做level order traversal的问题。假设binary tree的深度为d，可以做d次Morris traversal，第i次遍历只打印深度为i的节点。虽然space是O(1)的，但是最坏情况下时间复杂度是O(n^2)。这是我能想出满足要求的最优解法了。