📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 1711| 回复: 2
跳转到指定楼层
上一主题 下一主题
收起左侧

[树/链表/图] 一道面试的tree的题目。

全局:

注册一亩三分地论坛,查看更多干货!

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

x
给一个树的root 要求返回一个random node
要求each node should have equal probability to be returned
follow up:
每个节点有一个info:  total = number of left children ++ number of right children + 1
问这个info是否有助于解决上面的问题

上一篇:求问大家说的刷一遍leetcode是指easy,med,hard全部么?
下一篇:求教各位一道gg面试题
推荐
stellari 2016-2-13 12:24:23 | 只看该作者
全局:
如果是数组的话,返回一个随机值最好的方法是:
   取得数组a中所有候选值的个数N,生成一个1~N之间的随机“下标”k,返回a[k]。


但是,这里我们
1. 不知道N,
2. 就算知道N能生成k,也不能在O(1)时间内在树中找到a[k]。这样就必须从树的第一个node开始一个个遍历。因此最差时间是O(N)的。

如果有了total信息,上述的1,2两个问题都会得到一定程度的解决。比如:
root.total = 100
root.left.total = 33;
root.right.total = 67;
那么根据root.total,知道N=100,因此可以马上得到k,比如是52.
此时又知道左边只有33个,所以知道往左边走肯定没戏,那么一定是向右走。以此类推,在每个节点就马上知道该向左还是向右找。如果树是平衡的,那么这个算法能够实现O(logN)的最差时间。
回复

使用道具 举报

🔗
 楼主| 111180611 2016-2-13 16:21:33 | 只看该作者
全局:
stellari 发表于 2016-2-13 12:24
如果是数组的话,返回一个随机值最好的方法是:

感谢! 但是纠正一点root.left.total = 33的话root.right.total应该是 66 相加应该是99
回复

使用道具 举报

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

本版积分规则

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