推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

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

Google 新鲜面筋

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

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

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

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

x
本帖最后由 googlerr 于 2016-3-4 12:34 编辑
-google 1point3acres
第一题:     给一个整数数组(可正可负可重复),返回其中任意两个元素乘积的最大值。follow up 到求k个数的最大值。 当时没有想出比sorting 更好的算法了。。不知道k的话有没有更好算法

第二题:   Unique Word Abbreviation


求过求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. public class MultiK {
  3.     // assume input nums is valid -> nums.length >= k
  4.     // not consider overflow.鏈枃鍘熷垱鑷1point3acres璁哄潧
  5.     public static int multiK(int[] nums, int k) {
  6.         if (nums.length == k) {
  7.             int res = 1;
  8.             for (int n : nums) {
  9.                 res *= n;
  10.             }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  11.             return res;
  12.         }

  13.         // minHeap saves the k biggest numbers
  14.         PriorityQueue<Integer> minHeap = new PriorityQueue<>();
  15.         // maxHeap saves the k smallest numbers
  16.         PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> (b - a));
  17.         int max = Integer.MIN_VALUE;
  18.         for (int n : nums) {.1point3acres缃
  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();
  24.             }
  25.             maxHeap.offer(n);
  26.             if (maxHeap.size() > k) {
  27.                 maxHeap.poll();. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  28.             }
  29.         }

  30.         int res = 1;. 1point3acres.com/bbs
  31.         // check special cases
  32.         // if all negatives, and k is odd 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  33.         // result would be negative, choose from biggest k
  34.         if (max < 0 && k % 2 == 1) {
  35.             while (!minHeap.isEmpty()) {
  36.                 res *= minHeap.poll();
  37.             }
  38.             return res;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  39.         }-google 1point3acres

  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();. visit 1point3acres.com for more.
  46.             maxK[i] = minHeap.poll();
  47.         }
  48. .1point3acres缃
  49.         int minPos = 0, maxPos = 0; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  50.         // if k is odd, poll the largest non-negative first
  51.         if (k % 2 == 1) {
  52.             --k;
  53.             res *= maxK[maxPos];
  54.             ++maxPos;
  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.             }
    . from: 1point3acres.com/bbs
  64.             else {
  65.                 res *= minPair;.1point3acres缃
  66.                 minPos += 2;
  67.             }
  68.             k -= 2;
  69.         }.鐣欏璁哄潧-涓浜-涓夊垎鍦

  70.         return res;
  71.     }-google 1point3acres

  72.     public static void main(String[] args) {.鐣欏璁哄潧-涓浜-涓夊垎鍦
  73.         int[] test1 = {-8, -7, -3, -1, 0, 5, 6, 9};. 鍥磋鎴戜滑@1point 3 acres
  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));

  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};. 鍥磋鎴戜滑@1point 3 acres
  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
nlogk如何得来?我有点没明白。。我想的是把n个元素放入priority_queue 为nlogn复杂度 然后pop k次为O(k) ...
.1point3acres缃
应该是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解法:
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. more info on 1point3acres.com
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缃
恩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
queue里面只有k 个元素,那当k+1个元素进来,如何删除最小的那个呢(假设是个max heap)?
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
Heap里面要存的是最大的K个元素,所以用Min Heap更好外带加一个max标记heap里面最大值。当加满K个元素的时候,如果当前的元素大于Heap里面最小的值,删除当前最小的,然后加当前的,同时更新max如果有必要
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-7-27 03:05

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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