一亩三分地论坛

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

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

Google 新鲜面筋

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

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

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

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

x
本帖最后由 googlerr 于 2016-3-4 12:34 编辑 . more info on 1point3acres.com

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

第二题:   Unique Word Abbreviation


求过求Onsite


. from: 1point3acres.com/bbs

评分

3

查看全部评分

tianlu1 发表于 2016-2-24 03:38:45 | 显示全部楼层
第一题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 | 显示全部楼层
至今不懂怎么贴代码…打扰各位了orz
  1. import java.util.*;.1point3acres缃

  2. public class MultiK {
  3.     // assume input nums is valid -> nums.length >= k
  4.     // not consider overflow
  5.     public static int multiK(int[] nums, int k) {
  6.         if (nums.length == k) {
  7.             int res = 1;
  8.             for (int n : nums) {. 1point 3acres 璁哄潧
  9.                 res *= n;
  10.             }
  11.             return res;
  12.         }

  13.         // minHeap saves the k biggest numbers. from: 1point3acres.com/bbs
  14.         PriorityQueue<Integer> minHeap = new PriorityQueue<>();
  15.         // maxHeap saves the k smallest numbers
  16.         PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> (b - a));. visit 1point3acres.com for more.
  17.         int max = Integer.MIN_VALUE;
  18.         for (int n : nums) { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  19.             max = Math.max(max, n); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  20.             // maintain minHeap and maxHeap both with k number
  21.             minHeap.offer(n);. more info on 1point3acres.com
  22.             if (minHeap.size() > k) {
  23.                 minHeap.poll();
  24.             }
  25.             maxHeap.offer(n);
  26.             if (maxHeap.size() > k) {
  27.                 maxHeap.poll();
  28.             }
  29.         }

  30.         int res = 1;. 1point 3acres 璁哄潧
  31.         // check special cases. 1point3acres.com/bbs
  32.         // if all negatives, and k is odd
  33.         // result would be negative, choose from biggest k. more info on 1point3acres.com
  34.         if (max < 0 && k % 2 == 1) {
  35.             while (!minHeap.isEmpty()) {
  36.                 res *= minHeap.poll();. 1point3acres.com/bbs
  37.             }
  38.             return res;
  39.         }

  40.         // otherwise the result would be >= 0
  41.         // convert heaps to sorted list
  42.         int[] minK = new int[k];
  43.         int[] maxK = new int[k];
  44.         for (int i = k - 1; i >= 0; --i) {
  45.             minK[i] = maxHeap.poll();. from: 1point3acres.com/bbs
  46.             maxK[i] = minHeap.poll();. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  47.         }

  48.         int minPos = 0, maxPos = 0;
  49.         // if k is odd, poll the largest non-negative first
  50.         if (k % 2 == 1) {
  51.             --k;
  52.             res *= maxK[maxPos];
  53.             ++maxPos;
  54.         }
  55.         // now choose k/2 pairs out of heap. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  56.         while (k != 0) {
  57.             int minPair = minK[minPos] * minK[minPos + 1];
  58.             int maxPair = maxK[maxPos] * maxK[maxPos + 1];
  59.             if (maxPair > minPair) {
  60.                 res *= maxPair;
  61.                 maxPos += 2;
  62.             }
  63.             else {
  64.                 res *= minPair;-google 1point3acres
  65.                 minPos += 2;
  66.             }
  67.             k -= 2;
  68.         }

  69.         return res;. more info on 1point3acres.com
  70.     }

  71.     public static void main(String[] args) {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  72.         int[] test1 = {-8, -7, -3, -1, 0, 5, 6, 9};
  73.         int k = 3;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  74.         System.out.println("test1: " + MultiK.multiK(test1, k));

  75.         int[] test2 = {-8, -7, -3, -1, 0, 5, 6, 9};
    . From 1point 3acres bbs
  76.         k = 2;
  77.         System.out.println("test2: " + MultiK.multiK(test2, k));

  78.         int[] test3 = {-8, -7, -3, -1};
  79.         k = 3;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  80.         System.out.println("test3: " + MultiK.multiK(test3, k));

  81.         int[] test4 = {1, 2, 3, 5, 6, 9};. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  82.         k = 4;
  83.         System.out.println("test4: " + MultiK.multiK(test4, k));

  84.         int[] test5 = {-8, -7, -3, -1, 0, 5, 6, 9};
  85.         k = 7;
  86.         System.out.println("test5: " + MultiK.multiK(test5, k));
  87.     }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  88. }
复制代码
回复 支持 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!
回复 支持 反对

使用道具 举报

 楼主| mwsak47 发表于 2016-2-18 06:27:05 | 显示全部楼层
royal_916 发表于 2016-2-18 06:17
感觉第二题略难啊!祝lz onsite!
.鏈枃鍘熷垱鑷1point3acres璁哄潧
多谢~~~~~
回复 支持 反对

使用道具 举报

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解法:. 鍥磋鎴戜滑@1point 3 acres
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个数的最大值。 当 ...

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.鏈枃鍘熷垱鑷1point3acres璁哄潧
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了
. more info on 1point3acres.com
明白了 然后每次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解法:. from: 1point3acres.com/bbs
keep four pointers: maximum_positive, second_max_positive, minimum_negati ...

为什么需要存second?直接存最大值会有什么问题么?one pass, 如果小于0,与最小负数乘法,然后更新最大值,如果大于0和最大正数乘法,然后更新最大值。
回复 支持 反对

使用道具 举报

googlerr 发表于 2016-3-4 10:28:36 | 显示全部楼层
未命名0Zero 发表于 2016-3-4 03:37. more info on 1point3acres.com
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, 2016-12-5 03:36

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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