一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1560|回复: 17
收起左侧

[算法题] 问两道google的原题

[复制链接] |试试Instant~ |关注本帖
一回头的温柔 发表于 2016-2-29 16:43:55 | 显示全部楼层 |阅读模式

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

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这个条件?
第二题完全没太懂,求大神解答
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的话,那么算两种情况。
回复 支持 2 反对 0

使用道具 举报

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
回复 支持 反对

使用道具 举报

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()) {

又是复制黏贴惹的祸
回复 支持 反对

使用道具 举报

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 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的。
回复 支持 反对

使用道具 举报

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);
}
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-5 01:10

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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