亚麻OA求砸,面经神衣护体!


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
天天打游戏、照样领工资、还办H1B
这份工作你要不要?
把贵司招聘信息放这里
查看: 4712|回复: 43
收起左侧

Google 新鲜面筋

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

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

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

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

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

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

.1point3acres缃
求过求Onsite



评分

3

查看全部评分

tianlu1 发表于 2016-2-24 03:38:45 | 显示全部楼层
第一题O(n) non-sort解法:. visit 1point3acres.com for more.
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;
    . from: 1point3acres.com/bbs
  8.             for (int n : nums) {. visit 1point3acres.com for more.
  9.                 res *= n;
  10.             }. 鍥磋鎴戜滑@1point 3 acres
  11.             return res;
  12.         }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

  13.         // minHeap saves the k biggest numbers. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  14.         PriorityQueue<Integer> minHeap = new PriorityQueue<>();
  15.         // maxHeap saves the k smallest numbers. more info on 1point3acres.com
  16.         PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> (b - a));
  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);
  22.             if (minHeap.size() > k) {
  23.                 minHeap.poll();-google 1point3acres
  24.             }
  25.             maxHeap.offer(n);
  26.             if (maxHeap.size() > k) {
  27.                 maxHeap.poll();
  28.             }.1point3acres缃
  29.         }

  30.         int res = 1;
  31.         // check special cases. Waral 鍗氬鏈夋洿澶氭枃绔,
  32.         // if all negatives, and k is odd
  33.         // result would be negative, choose from biggest k. 1point 3acres 璁哄潧
  34.         if (max < 0 && k % 2 == 1) {
  35.             while (!minHeap.isEmpty()) {
  36.                 res *= minHeap.poll();
  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();. more info on 1point3acres.com
  46.             maxK[i] = minHeap.poll();
  47.         }. From 1point 3acres bbs

  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;
    . 1point3acres.com/bbs
  61.                 maxPos += 2;
  62.             }
  63.             else {
  64.                 res *= minPair;
  65.                 minPos += 2;. Waral 鍗氬鏈夋洿澶氭枃绔,
  66.             }
  67.             k -= 2;
  68.         }
  69. . 1point3acres.com/bbs
  70.         return res;. from: 1point3acres.com/bbs
  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.         int[] test3 = {-8, -7, -3, -1};
  80.         k = 3;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  81.         System.out.println("test3: " + MultiK.multiK(test3, k));. From 1point 3acres bbs

  82.         int[] test4 = {1, 2, 3, 5, 6, 9};
  83.         k = 4;
  84.         System.out.println("test4: " + MultiK.multiK(test4, k));

  85.         int[] test5 = {-8, -7, -3, -1, 0, 5, 6, 9};
  86.         k = 7;
  87.         System.out.println("test5: " + MultiK.multiK(test5, k));
    鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  88.     }
  89. }
复制代码
回复 支持 2 反对 0

使用道具 举报

googlerr 发表于 2016-2-26 11:45:37 | 显示全部楼层
hesha0987 发表于 2016-2-26 11:42. more info on 1point3acres.com
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!

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

使用道具 举报

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

使用道具 举报

glad2mu 发表于 2016-2-26 06:14:24 | 显示全部楼层
tianlu1 发表于 2016-2-24 03:38. 鍥磋鎴戜滑@1point 3 acres
第一题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个数的最大值。 当 ...

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
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) ...
. 1point3acres.com/bbs
恩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 ...

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

使用道具 举报

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

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

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-10-21 09:25

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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