谷歌店面面经

Vyronas · 2019-10-10 03:18:25

面试官口音很标准，上来就开始做题：
给一个perfect tree（如图），写一个函数：已知某个node的value，返回该node的指针。

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

容 (2019-10-10 04:34):
每个回复我都会加米！谢谢各位帮忙

machdebagua · 2019-10-10 03:35:40

把每层的最大值存入一个数组，然后二分查找可找到层数。然后遍历这一层（还是得从root出发). 似乎期望值是O(n/2), 便宜了一点点

digdig · 2019-10-10 05:07:07

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

dengzeyu147 · 2019-10-10 04:15:05

machdebagua 发表于 2019-10-10 03:35
把每层的最大值存入一个数组，然后二分查找可找到层数。然后遍历这一层（还是得从root出发). 似乎期望值是O ...

worst case还是O n

Vyronas · 2019-10-10 03:43:33

machdebagua 发表于 2019-10-10 03:35
把每层的最大值存入一个数组，然后二分查找可找到层数。然后遍历这一层（还是得从root出发). 似乎期望值是O ...

可是如果还是要从root出发 worst case 应该还是O(n)呀？

hqOffer · 2019-10-10 03:57:09

这个tree还有什么特点吗？看你发的图，每层都是递增的，以及是不是balanced tree?

probiotic10 · 2019-10-10 03:58:18

看例子是按level从上到下，从左到右排好序的perfect tree？如果是这样的话，可以一直走右节点，直到当前节点比自己大，那就找到层数。然后在某一层用二分查找。

Vyronas · 2019-10-10 04:02:56

MiniMinyi 发表于 2019-10-10 03:58
看例子是按level从上到下，从左到右排好序的perfect tree？如果是这样的话，可以一直走右节点，直到当前节 ...

那如果找到了对应的层数，我如何才能获得这一层中的所有数呢？还应该是用bfs吧？那不就还得是O(n)嘛？

Vyronas · 2019-10-10 04:04:36

hqOffer 发表于 2019-10-10 03:57
这个tree还有什么特点吗？看你发的图，每层都是递增的，以及是不是balanced tree?

这个tree是balance的每层递增而且所有的leaf node都是同层

hqOffer · 2019-10-10 04:11:29

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

Vyronas · 2019-10-10 04:16:13

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

谷歌 店面面经