一亩三分地论坛

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

一亩三分地官方iOS手机应用下载
查看: 3404|回复: 43
收起左侧

Google 新鲜面筋

[复制链接] |试试Instant~ |关注本帖
mwsak47 发表于 2016-2-18 06:05:15 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 硕士 全职@Google - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
本帖最后由 googlerr 于 2016-3-4 12:34 编辑

第一题:     给一个整数数组(可正可负可重复),返回其中任意两个元素乘积的最大值。follow up 到求k个数的最大值。 当时没有想出比sorting 更好的算法了。。不知道k的话有没有更好算法

第二题:   Unique Word Abbreviation.1point3acres缃

. 1point 3acres 璁哄潧
求过求Onsite



评分

3

查看全部评分

tianlu1 发表于 2016-2-24 03:38:45 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
第一题O(n) non-sort解法:
keep four pointers: maximum_positive, second_max_positive, minimum_negative, second_min_negative.
回复 支持 2 反对 0

使用道具 举报

mrhohn 发表于 2016-3-16 05:20:15 | 显示全部楼层
关注一亩三分地微博:
Warald
至今不懂怎么贴代码…打扰各位了orz
  1. import java.util.*;
  2. 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  3. public class MultiK {
  4.     // assume input nums is valid -> nums.length >= k
  5.     // not consider overflow
  6.     public static int multiK(int[] nums, int k) {
  7.         if (nums.length == k) {
  8.             int res = 1;
  9.             for (int n : nums) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
  10.                 res *= n;
  11.             }
  12.             return res;
  13.         }

  14.         // minHeap saves the k biggest numbers
  15.         PriorityQueue<Integer> minHeap = new PriorityQueue<>();
  16.         // maxHeap saves the k smallest numbers
  17.         PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> (b - a));.1point3acres缃
  18.         int max = Integer.MIN_VALUE;
  19.         for (int n : nums) {
  20.             max = Math.max(max, n);
  21.             // maintain minHeap and maxHeap both with k number
  22.             minHeap.offer(n);
  23.             if (minHeap.size() > k) {. 1point 3acres 璁哄潧
  24.                 minHeap.poll();
  25.             }
  26.             maxHeap.offer(n);
  27.             if (maxHeap.size() > k) {
  28.                 maxHeap.poll();
  29.             }
  30.         }

  31.         int res = 1;.1point3acres缃
  32.         // check special cases
  33.         // if all negatives, and k is odd
  34.         // result would be negative, choose from biggest k-google 1point3acres
  35.         if (max < 0 && k % 2 == 1) {
  36.             while (!minHeap.isEmpty()) {
  37.                 res *= minHeap.poll();
    .鐣欏璁哄潧-涓浜-涓夊垎鍦
  38.             }
  39.             return res;
  40.         }

  41.         // otherwise the result would be >= 0
  42.         // convert heaps to sorted list
  43.         int[] minK = new int[k];
  44.         int[] maxK = new int[k];. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  45.         for (int i = k - 1; i >= 0; --i) {
  46.             minK[i] = maxHeap.poll();
    .鏈枃鍘熷垱鑷1point3acres璁哄潧
  47.             maxK[i] = minHeap.poll();
  48.         }

  49.         int minPos = 0, maxPos = 0;. from: 1point3acres.com/bbs
  50.         // if k is odd, poll the largest non-negative first
  51.         if (k % 2 == 1) {
  52.             --k;
  53.             res *= maxK[maxPos];
  54.             ++maxPos;. from: 1point3acres.com/bbs
  55.         }
  56.         // now choose k/2 pairs out of heap
  57.         while (k != 0) {
  58.             int minPair = minK[minPos] * minK[minPos + 1];
  59.             int maxPair = maxK[maxPos] * maxK[maxPos + 1];
  60.             if (maxPair > minPair) {
  61.                 res *= maxPair;
  62.                 maxPos += 2;
  63.             }
  64.             else {-google 1point3acres
  65.                 res *= minPair;
  66.                 minPos += 2;
  67.             }
  68.             k -= 2;
  69.         }

  70.         return res;
  71.     }

  72.     public static void main(String[] args) {
  73.         int[] test1 = {-8, -7, -3, -1, 0, 5, 6, 9};
  74.         int k = 3;
  75.         System.out.println("test1: " + MultiK.multiK(test1, k));

  76.         int[] test2 = {-8, -7, -3, -1, 0, 5, 6, 9};
  77.         k = 2;
  78.         System.out.println("test2: " + MultiK.multiK(test2, k));
  79. . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  80.         int[] test3 = {-8, -7, -3, -1};
  81.         k = 3;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  82.         System.out.println("test3: " + MultiK.multiK(test3, k));

  83.         int[] test4 = {1, 2, 3, 5, 6, 9};
  84.         k = 4;
  85.         System.out.println("test4: " + MultiK.multiK(test4, k));
  86. . 1point 3acres 璁哄潧
  87.         int[] test5 = {-8, -7, -3, -1, 0, 5, 6, 9};. 1point 3acres 璁哄潧
  88.         k = 7;
  89.         System.out.println("test5: " + MultiK.multiK(test5, k));. Waral 鍗氬鏈夋洿澶氭枃绔,
  90.     }
  91. }
复制代码
回复 支持 2 反对 0

使用道具 举报

googlerr 发表于 2016-2-26 11:45:37 | 显示全部楼层
hesha0987 发表于 2016-2-26 11:42
nlogk如何得来?我有点没明白。。我想的是把n个元素放入priority_queue 为nlogn复杂度 然后pop k次为O(k) ...

应该是Queue里面只放K个元素,一个里面放最大的K个,另一个里面放最小的K个

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

royal_916 发表于 2016-2-18 06:17:13 | 显示全部楼层
感觉第二题略难啊!祝lz onsite!
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 反对

使用道具 举报

 楼主| mwsak47 发表于 2016-2-18 06:27:05 | 显示全部楼层
royal_916 发表于 2016-2-18 06:17
感觉第二题略难啊!祝lz onsite!

多谢~~~~~
回复 支持 反对

使用道具 举报

lxy16555 发表于 2016-2-26 04:21:29 | 显示全部楼层
第二题可以用hashset存然后比较是否contains吧,或者用trie树查询?
回复 支持 反对

使用道具 举报

glad2mu 发表于 2016-2-26 06:14:24 | 显示全部楼层
tianlu1 发表于 2016-2-24 03:38
第一题O(n) non-sort解法:
keep four pointers: maximum_positive, second_max_positive, minimum_negati ...

我之前面过一样的题, 用的这个方法之后考官觉得有点hardcoded。 之后follow up 到求k个数的最大值。 当时没有想出比sorting 更好的算法了。。不知道k的话有没有更好算法
回复 支持 反对

使用道具 举报

csgtc 发表于 2016-2-26 06:22:15 | 显示全部楼层
glad2mu 发表于 2016-2-25 17:14
我之前面过一样的题, 用的这个方法之后考官觉得有点hardcoded。 之后follow up 到求k个数的最大值。 当 ...
. 1point 3acres 璁哄潧
k的话就用priorityqueue好了
回复 支持 反对

使用道具 举报

glad2mu 发表于 2016-2-26 06:27:21 | 显示全部楼层
csgtc 发表于 2016-2-26 06:22
k的话就用priorityqueue好了

非常感谢!
回复 支持 反对

使用道具 举报

hesha0987 发表于 2016-2-26 07:31:54 | 显示全部楼层
csgtc 发表于 2016-2-26 06:22
k的话就用priorityqueue好了
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
priority_queue 的复杂度和sort是一样的吧?都是nlogn。
并且priority_queue的话 需要用一个min heap 和一个max heap来确保 负数们的乘积有可能是最大的。
回复 支持 反对

使用道具 举报

csgtc 发表于 2016-2-26 08:13:25 | 显示全部楼层
hesha0987 发表于 2016-2-25 18:31. 1point 3acres 璁哄潧
priority_queue 的复杂度和sort是一样的吧?都是nlogn。
并且priority_queue的话 需要用一个min heap 和 ...

两个priorityqueue, 复杂度并不是sort的nlogn,而是nlogk 速度肯定比sort快
回复 支持 反对

使用道具 举报

hesha0987 发表于 2016-2-26 11:42:02 | 显示全部楼层
csgtc 发表于 2016-2-26 08:13
两个priorityqueue, 复杂度并不是sort的nlogn,而是nlogk 速度肯定比sort快

nlogk如何得来?我有点没明白。。我想的是把n个元素放入priority_queue 为nlogn复杂度 然后pop k次为O(k)复杂度 总共是nlogn 能说说你的思路吗?
回复 支持 反对

使用道具 举报

tianlu1 发表于 2016-2-27 00:07:36 | 显示全部楼层
第一题可以sort吗?最大乘积就是Max(最小两个负数乘积,最大两个正数乘积)
回复 支持 反对

使用道具 举报

tianlu1 发表于 2016-2-27 00:09:34 | 显示全部楼层
tianlu1 发表于 2016-2-27 00:07
第一题可以sort吗?最大乘积就是Max(最小两个负数乘积,最大两个正数乘积)

忘了以前回复过,参看地板楼,忽略此楼
回复 支持 反对

使用道具 举报

csgtc 发表于 2016-2-27 03:09:30 | 显示全部楼层
hesha0987 发表于 2016-2-25 22:42
nlogk如何得来?我有点没明白。。我想的是把n个元素放入priority_queue 为nlogn复杂度 然后pop k次为O(k) ...

恩queue里只有k个元素,没必要把所有元素放queue里啊,所有元素放queue里就是heapsort了
回复 支持 反对

使用道具 举报

hesha0987 发表于 2016-2-27 03:12:10 | 显示全部楼层
csgtc 发表于 2016-2-27 03:09
恩queue里只有k个元素,没必要把所有元素放queue里啊,所有元素放queue里就是heapsort了

明白了 然后每次pop出一个来 多谢!
回复 支持 反对

使用道具 举报

houqingniao 发表于 2016-2-27 06:56:20 | 显示全部楼层
unique word abbreviation 是啥?
回复 支持 反对

使用道具 举报

未命名0Zero 发表于 2016-3-4 03:37:47 | 显示全部楼层
csgtc 发表于 2016-2-27 03:09
恩queue里只有k个元素,没必要把所有元素放queue里啊,所有元素放queue里就是heapsort了

queue里面只有k 个元素,那当k+1个元素进来,如何删除最小的那个呢(假设是个max heap)?
回复 支持 反对

使用道具 举报

zxl9171 发表于 2016-3-4 06:39:01 | 显示全部楼层
tianlu1 发表于 2016-2-24 03:38
第一题O(n) non-sort解法:
keep four pointers: maximum_positive, second_max_positive, minimum_negati ...
. visit 1point3acres.com for more.
为什么需要存second?直接存最大值会有什么问题么?one pass, 如果小于0,与最小负数乘法,然后更新最大值,如果大于0和最大正数乘法,然后更新最大值。
回复 支持 反对

使用道具 举报

googlerr 发表于 2016-3-4 10:28:36 | 显示全部楼层
未命名0Zero 发表于 2016-3-4 03:37
queue里面只有k 个元素,那当k+1个元素进来,如何删除最小的那个呢(假设是个max heap)?

Heap里面要存的是最大的K个元素,所以用Min Heap更好外带加一个max标记heap里面最大值。当加满K个元素的时候,如果当前的元素大于Heap里面最小的值,删除当前最小的,然后加当前的,同时更新max如果有必要
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-2-22 05:34

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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