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

问两道google的原题

全局:

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

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

x
本帖最后由 googlerr 于 2016-3-5 08:08 编辑

1. 给了一个array,该array满足heap quality,比如[20, 15, 19, 10, 11, 18, 16, 3, 5, 8, 9, 13, 14, 12, 11]就是相当于把一个heap按照level order trasveral排成数组。要求写一个函数找出里面的top K,不修改原数组,数组很大而K基本很小。
2. 给了n个骰子/色子,每个色子有f个面,点数从1,2,3...到f。所有色子视为identical/unique,问题是:投出n个色子最后点数和加起来等于s的情况分别有多少种。

第一题难道要新建一个priorityqueue然后按照求top k的方法做吗?感觉这样没意义,怎么用该array 满足 heap quality这个条件?
第二题完全没太懂,求大神解答

上一篇:amazon oa问题
下一篇:关于合并用python导入spark,RDD中的CSV数据的问题
推荐
stellari 2016-3-1 19:29:12 | 只看该作者
全局:
第一题的话,我觉得开一个PriorityQueue并无问题。只要求top k的话, 这个PriorityQueue并不会很大。
先把array中第一个元素(20)放入PriorityQueue q,然后重复下列操作k次:“从q中取出最大值M,将其加入最终结果,然后将M的两个2个子元素加入q。”。这样q中最多不会超过2k个元素,空间复杂度O(k),时间复杂度是O(klogk)。考虑到k很小,时空复杂度应该都可以接受。

第二题中的identical/unque应该分别指“组合”和“排列”:比如有骰子A和B。如果identical的话,那么“A 4点,B 3点”和“A 3点,B 4点”这两种情况不可区分,因此算一种情况;如果unique的话,那么算两种情况。
回复

使用道具 举报

推荐
fish444555 2016-3-2 06:29:34 | 只看该作者
全局:
第一题我觉得可以不需要建 优先队列,直接利用数组就可以了,需要一个k 的idx数组,以题目原来的输入为例
假设是k=5,可以得到下面的idx数组,
0  2  5  6
很难表述,大概就是 0 左右节点是 0*2+1 和 0*2+2, 对比后发现 2大,然后第三个是对比 0*2+1, 2*2+1, 2*2+2。因为 0*2+2已经在数组中,肯定比他们大,所以忽略,代码如下:

  1. std::vector<int> Solution::tt(std::vector<int> &nums, int k) {   
  2.     std::vector<int> res;
  3.     if (nums.empty())
  4.         return res;
  5.     std::vector<int> idx(1, 0);
  6.     res.push_back(nums[0]);
  7.     int num_size = (int)nums.size();
  8.     for (int i = 1; i < k; ++i)
  9.     {
  10.         int len = (int)idx.size();
  11.         int maxv = INT_MIN;
  12.         int maxidx = -1;
  13.         for (int j = 1; j <= len; ++j)
  14.         {
  15.             if (idx[j-1] * 2 + 1 < num_size && find(idx.begin()+j, idx.end(), idx[j-1] * 2 + 1) == idx.end()) {
  16.                     if (maxv < nums[idx[j-1] * 2 + 1]) {
  17.                         maxidx = idx[j-1] * 2 + 1;
  18.                         maxv = nums[idx[j-1] * 2 + 1];
  19.                     }
  20.             }
  21.             if (idx[j-1] * 2 + 1 < num_size && find(idx.begin()+j, idx.end(), idx[j-1] * 2 + 2) == idx.end()) {
  22.                     if (maxv < nums[idx[j-1] * 2 + 2]) {
  23.                         maxidx = idx[j-1] * 2 + 2;
  24.                         maxv = nums[idx[j-1] * 2 + 2];
  25.                     }
  26.             }
  27.         }
  28.         idx.push_back(maxidx);
  29.         res.push_back(maxv);
  30.     }
  31.     return res;
  32. }
复制代码


用题目的输入,k=10,结果如下,其它的输入没有试过,可能有bug.........
20  19  18  16  15  14  13  12  11  11
回复

使用道具 举报

推荐
stellari 2016-3-2 14:32:56 | 只看该作者
全局:
fish444555 发表于 2016-3-2 06:29
第一题我觉得可以不需要建 优先队列,直接利用数组就可以了,需要一个k 的idx数组,以题目原来的输入为例
...

其实优先队列一般就是一个用数组表示的堆,如果我没记错,Java中的PriorityQueue内部也是用数组来实现的。你的这段代码其实是自己实现了堆的部分功能(比如获得堆中某一点的“子节点”的getChild()),但是没有实现另外一些关键函数(如重新恢复堆性质的reheapify())。所以时间复杂度高于一般的堆:外层循环k次,内层循环len~O(k)次,每次循环最差情况下要进行2次时间复杂度为O(k)次的find(),总体来看时间复杂度O(k^3),空间复杂度O(k)。这样,比起直接使用最大堆(优先队列)的O(klogk)时间, O(k)空间的解法并无任何优势吧
回复

使用道具 举报

🔗
fish444555 2016-3-2 06:30:38 | 只看该作者
全局:
fish444555 发表于 2016-3-2 06:29
第一题我觉得可以不需要建 优先队列,直接利用数组就可以了,需要一个k 的idx数组,以题目原来的输入为例
...

0  2  5  6  是 k=4的 idx 数组
回复

使用道具 举报

🔗
fish444555 2016-3-2 06:36:19 | 只看该作者
全局:
第21 行是
if (idx[j-1] * 2 + 2 < num_size && find(idx.begin()+j, idx.end(), idx[j-1] * 2 + 2) == idx.end()) {

又是复制黏贴惹的祸
回复

使用道具 举报

🔗
fish444555 2016-3-2 21:24:45 | 只看该作者
全局:
stellari 发表于 2016-3-2 14:32
其实优先队列一般就是一个用数组表示的堆,如果我没记错,Java中的PriorityQueue内部也是用数组来实现的 ...

谢谢提醒,我再去看看Java 的PriorityQueue
回复

使用道具 举报

🔗
 楼主| 一回头的温柔 2016-3-3 17:40:15 | 只看该作者
全局:
stellari 发表于 2016-3-1 19:29
第一题的话,我觉得开一个PriorityQueue并无问题。只要求top k的话, 这个PriorityQueue并不会很大。
先把 ...

谢谢回复,很受益
回复

使用道具 举报

🔗
 楼主| 一回头的温柔 2016-3-3 17:40:29 | 只看该作者
全局:
fish444555 发表于 2016-3-2 06:36
第21 行是
if (idx[j-1] * 2 + 2 < num_size && find(idx.begin()+j, idx.end(), idx[j-1] * 2 + 2) == id ...

也谢谢你的回复
回复

使用道具 举报

🔗
bbsbbstry 2016-3-3 19:50:26 | 只看该作者
全局:
楼上说的从技术上都对。但是从面试的角度,如果我是面试官的话,我是不expect在你这道题的代码里看到priority queue的。
回复

使用道具 举报

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

本版积分规则

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