一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 4834|回复: 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 编辑 . Waral 鍗氬鏈夋洿澶氭枃绔,
. more info on 1point3acres.com
第一题:     给一个整数数组(可正可负可重复),返回其中任意两个元素乘积的最大值。follow up 到求k个数的最大值。 当时没有想出比sorting 更好的算法了。。不知道k的话有没有更好算法

第二题:   Unique Word Abbreviation
. Waral 鍗氬鏈夋洿澶氭枃绔,

求过求Onsite



评分

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.*;
  2. . 1point 3acres 璁哄潧
  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) {. 鍥磋鎴戜滑@1point 3 acres
  10.                 res *= n;. more info on 1point3acres.com
  11.             }
  12.             return res;. Waral 鍗氬鏈夋洿澶氭枃绔,
  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));
  18.         int max = Integer.MIN_VALUE;
  19.         for (int n : nums) {. from: 1point3acres.com/bbs
  20.             max = Math.max(max, n);
  21.             // maintain minHeap and maxHeap both with k number
  22.             minHeap.offer(n);
  23.             if (minHeap.size() > k) {
  24.                 minHeap.poll();. visit 1point3acres.com for more.
  25.             }
  26.             maxHeap.offer(n);
  27.             if (maxHeap.size() > k) {
  28.                 maxHeap.poll();. Waral 鍗氬鏈夋洿澶氭枃绔,
  29.             }
  30.         }

  31.         int res = 1;
  32.         // check special cases
  33.         // if all negatives, and k is odd
  34.         // result would be negative, choose from biggest k
  35.         if (max < 0 && k % 2 == 1) {
  36.             while (!minHeap.isEmpty()) {
  37.                 res *= minHeap.poll();
  38.             }-google 1point3acres
  39.             return res;
  40.         }
  41. .鐣欏璁哄潧-涓浜-涓夊垎鍦
  42.         // otherwise the result would be >= 0
  43.         // convert heaps to sorted list
  44.         int[] minK = new int[k];
  45.         int[] maxK = new int[k];
  46.         for (int i = k - 1; i >= 0; --i) {
  47.             minK[i] = maxHeap.poll();
  48.             maxK[i] = minHeap.poll();
  49.         }-google 1point3acres

  50.         int minPos = 0, maxPos = 0;
  51.         // if k is odd, poll the largest non-negative first .鐣欏璁哄潧-涓浜-涓夊垎鍦
  52.         if (k % 2 == 1) {
  53.             --k;
  54.             res *= maxK[maxPos];
  55.             ++maxPos;
  56.         }
  57.         // now choose k/2 pairs out of heap
  58.         while (k != 0) {
  59.             int minPair = minK[minPos] * minK[minPos + 1];
  60.             int maxPair = maxK[maxPos] * maxK[maxPos + 1];
  61.             if (maxPair > minPair) {
  62.                 res *= maxPair;
  63.                 maxPos += 2;
  64.             }
  65.             else {
  66.                 res *= minPair;
  67.                 minPos += 2;
  68.             }
  69.             k -= 2;. visit 1point3acres.com for more.
  70.         }

  71.         return res;
  72.     }

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

  77.         int[] test2 = {-8, -7, -3, -1, 0, 5, 6, 9};
  78.         k = 2;
  79.         System.out.println("test2: " + MultiK.multiK(test2, k));. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

  80.         int[] test3 = {-8, -7, -3, -1};
  81.         k = 3;
  82.         System.out.println("test3: " + MultiK.multiK(test3, k));

  83.         int[] test4 = {1, 2, 3, 5, 6, 9};-google 1point3acres
  84.         k = 4;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  85.         System.out.println("test4: " + MultiK.multiK(test4, k));

  86.         int[] test5 = {-8, -7, -3, -1, 0, 5, 6, 9};
  87.         k = 7;
  88.         System.out.println("test5: " + MultiK.multiK(test5, k));
  89.     }.1point3acres缃
  90. }
复制代码
回复 支持 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!

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

使用道具 举报

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个数的最大值。 当 ...
-google 1point3acres
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好了
.1point3acres缃
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。. 1point3acres.com/bbs
并且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了
. 1point3acres.com/bbs
明白了 然后每次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-12-13 05:45

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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