📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
12
返回列表 发新帖
跳转到指定楼层
上一主题 下一主题
收起左侧

问两道google的原题

🔗
stellari 2016-3-3 21:57:38 | 只看该作者
全局:
bbsbbstry 发表于 2016-3-3 19:50
楼上说的从技术上都对。但是从面试的角度,如果我是面试官的话,我是不expect在你这道题的代码里看到priori ...

如果不用PriorityQueue或者类似的有序结构,这道题有什么能够在“不修改原数组”的情况下实现O(klogk)时间或更低的解法吗。请赐教。
回复

使用道具 举报

🔗
 楼主| 一回头的温柔 2016-3-4 16:38:56 | 只看该作者
全局:
bbsbbstry 发表于 2016-3-3 19:50
楼上说的从技术上都对。但是从面试的角度,如果我是面试官的话,我是不expect在你这道题的代码里看到priori ...

请赐教,字数
回复

使用道具 举报

🔗
bbsbbstry 2016-3-4 22:48:39 | 只看该作者
全局:
stellari 发表于 2016-3-3 21:57
如果不用PriorityQueue或者类似的有序结构,这道题有什么能够在“不修改原数组”的情况下实现O(klogk)时 ...

Never mind.又看了一遍题,用pq确实是正解
回复

使用道具 举报

🔗
bbsbbstry 2016-3-4 22:49:16 | 只看该作者
全局:

Never mind.又看了一遍题,用pq确实是正解。k特别小的话不考虑渐进复杂度用list也可以
回复

使用道具 举报

🔗
bingo1995 2016-3-4 22:54:28 | 只看该作者
全局:
第一题onsite我碰到过  按2楼的方法 一个pq+BFS就可以了  不过很囧的是我当时忘了优先级队列处理的时候比较的是数组  pop出来的应该是索引。。。被面试官指出来了。老实说  这题有点怪异。
回复

使用道具 举报

🔗
bbsbbstry 2016-3-4 23:00:03 | 只看该作者
全局:
bingo1995 发表于 2016-3-4 22:54
第一题onsite我碰到过  按2楼的方法 一个pq+BFS就可以了  不过很囧的是我当时忘了优先级队列处理的时候比较 ...

pq里放的是包含值和索引的对象吧?再另外写一个comparator
回复

使用道具 举报

🔗
bingo1995 2016-3-4 23:07:40 | 只看该作者
全局:
bbsbbstry 发表于 2016-3-4 23:00
pq里放的是包含值和索引的对象吧?再另外写一个comparator

差不多的意思   我用C++
嗯  就是comparator没注意
回复

使用道具 举报

🔗
Simon15 2016-5-15 05:31:48 | 只看该作者
全局:
本帖最后由 Simon15 于 2016-5-15 05:33 编辑

Since K is small, a recusive solutino is acceptable.

int kthElement(int[] data, int startIndex, int k) {
     if (k == 1) return data[startIndex];
     //find the k-1 th largest element in the left and right tree
     int left = kthElement(data, 2*startIndex + 1; k-1);
     int right = kthElement(data, 2*startIndex + 2; k-1);
     return (left < right ? right : left);
}
回复

使用道具 举报

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

本版积分规则

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