📣 独立日限时特惠: VIP通行证立减$68
楼主: jeanwang2012
跳转到指定楼层
上一主题 下一主题
收起左侧

狗家昂赛跪经

无效楼层,该帖已经被删除
🔗
sonofspring 2018-3-14 09:18:31 | 只看该作者
全局:
jeanwang2012 发表于 2018-3-14 05:16
输入可以自己定义,他给举的例子里看是一个类似2d vector的,以及一个会消失的砖块的位置(i,j)
**** 本 ...

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

使用道具 举报

🔗
alanlxl 2018-3-14 21:32:38 | 只看该作者
全局:
jeanwang2012 发表于 2018-3-14 05:16
输入可以自己定义,他给举的例子里看是一个类似2d vector的,以及一个会消失的砖块的位置(i,j)
**** 本 ...

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

使用道具 举报

🔗
Kwang100 2018-3-15 03:19:31 | 只看该作者
全局:
zhengyiyu 发表于 2018-3-14 07:50
rank我的理解就是sort后的顺序,所以理解的就是找到第k大的数字,或者给一个节点,想知道他在所有数据里 ...

层主,这个思路当然是对的,但是这个方法问题是不是在于如果BST不平衡的话,插入,删除都几乎是O(n)了?
回复

使用道具 举报

🔗
Kwang100 2018-3-15 03:20:26 | 只看该作者
全局:
楼主,感谢分享面经!请问第一题是不是类似于LC司令就?需要输出所有最长palindrome呗?
回复

使用道具 举报

🔗
groundzyy1 2018-3-15 03:47:22 | 只看该作者
全局:
Kwang100 发表于 2018-3-15 03:19
层主,这个思路当然是对的,但是这个方法问题是不是在于如果BST不平衡的话,插入,删除都几乎是O(n)了 ...

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

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

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

使用道具 举报

🔗
Kwang100 2018-3-15 04:17:10 | 只看该作者
全局:
zhengyiyu 发表于 2018-3-15 03:47
这个如果不写代码,纯followup的话,用个 height balance的bst就可以解决了吧

感觉不会让写出来的,最 ...

嗯..但是这一轮就这一题,看样子是要写代码的..
bucket这种方法到没有想到,skip list没听过,查一查..
回复

使用道具 举报

🔗
jy_121 2018-3-15 10:28:38 | 只看该作者
全局:
jeanwang2012 发表于 2018-3-14 05:16
输入可以自己定义,他给举的例子里看是一个类似2d vector的,以及一个会消失的砖块的位置(i,j)
**** 本 ...

问下楼主这道题是怎么回答的?每个砖块不是只由正下方的砖块支撑的吗?谢谢
回复

使用道具 举报

🔗
better1016 2018-3-18 11:46:26 | 只看该作者
全局:
请问第一题的shuffle和删除是什么意思呢?能再详细说说么?
回复

使用道具 举报

无效楼层,该帖已经被删除
您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表