狗家昂赛跪经

alanlxl 发表于 2018-3-13 10:50
round2那个题能说的详细一些么？

输入可以自己定义，他给举的例子里看是一个类似2d vector的，以及一个会消失的砖块的位置(i,j)

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

游客，您好！
本帖隐藏的内容需要积分高于 120 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

zhengyiyu 发表于 2018-3-13 11:42
第4轮是否可以考虑为一个bst，然后每个节点额外存上左树所有node的数量，这样就知道自己是第多少个了

所 ...

不太明白，节点的rank是怎么计算的？

idatascience 发表于 2018-3-14 07:31
不太明白，节点的rank是怎么计算的？

rank我的理解就是sort后的顺序，所以理解的就是找到第k大的数字，或者给一个节点，想知道他在所有数据里面的sort后的位置吧

变成了一个bst，如何用log(n)的时间找到t-th数字， （而不是top-K，只是第k个）
插入，删除和查询都是log(n), 我也是狗家昂赛时候碰到的类似的这个题

还在拖延症中，一直没写面筋 哈哈

idatascience 发表于 2018-3-14 07:31
不太明白，节点的rank是怎么计算的？

看这个高票答案https://stackoverflow.com/questi ... tree-in-optimum-way

heroic 发表于 2018-3-14 08:08
看这个高票答案https://stackoverflow.com/questions/2329171/find-kth-smallest-element-in-a-binary-se ...

多谢女神！

jeanwang2012 发表于 2018-3-14 05:16
输入可以自己定义，他给举的例子里看是一个类似2d vector的，以及一个会消失的砖块的位置(i,j)
**** 本 ...

楼主，你好，请问我们怎么确定一个 "b" 会不会下落呢？ 如图中如果去掉 比如说第二行中左数第四个 b 的话，是哪些 brick 掉下来呢？ 谢谢！

jeanwang2012 发表于 2018-3-14 05:16
输入可以自己定义，他给举的例子里看是一个类似2d vector的，以及一个会消失的砖块的位置(i,j)
**** 本 ...

这题感觉应该首先以紧挨着天花板的几个砖块作为种子进行BFS，构造每个砖块的依赖和被依赖列表（记录a被b和c稳定住， b稳定了d和e等），然后对于输入的砖块(i,j)，遍历它的被依赖列表，把里面元素的依赖列表里删除该砖块，如果依赖列表为空了，说明这个砖也会掉，又是一次类似BFS的过程
我理解的对么？

zhengyiyu 发表于 2018-3-14 07:50
rank我的理解就是sort后的顺序，所以理解的就是找到第k大的数字，或者给一个节点，想知道他在所有数据里 ...

层主，这个思路当然是对的，但是这个方法问题是不是在于如果BST不平衡的话，插入，删除都几乎是O（n）了？

楼主，感谢分享面经！请问第一题是不是类似于LC司令就？需要输出所有最长palindrome呗？

Kwang100 发表于 2018-3-15 03:19
层主，这个思路当然是对的，但是这个方法问题是不是在于如果BST不平衡的话，插入，删除都几乎是O（n）了 ...

这个如果不写代码，纯followup的话，用个 height balance的bst就可以解决了吧

感觉不会让写出来的，最多就提一下红黑树/avl树之类的呗。

其实这个题，我还想过另外一种方式就是用bucket的思想，在对数据有假设的情况下，或许能做到overhead很高的O（1），或者O（logn）的话，在bucket级别上加上skip list的结构。但是基本只能用来口头讨论，不能写代码了