Google 新鲜面筋

第一题:     给一个整数数组（可正可负可重复），返回其中任意两个元素乘积的最大值。

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

/font>
求过求Onsite

至今不懂怎么贴代码…打扰各位了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) {
   
10.                 res *= n;
    
11.             }
    
12.             return res;
    
13.         }
    
14. 
    
15.         // minHeap saves the k biggest numbers
    
16.         PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    
17.         // maxHeap saves the k smallest numbers
    
18.         PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> (b - a));
    
19.         int max = Integer.MIN_VALUE;
    
20.         for (int n : nums) {
    
21.             max = Math.max(max, n);
    
22.             // maintain minHeap and maxHeap both with k number
    
23.             minHeap.offer(n);
    
24.             if (minHeap.size() > k) {
    
25.                 minHeap.poll();
    
26.             }
    
27.             maxHeap.offer(n);
    
28.             if (maxHeap.size() > k) {
    
29.                 maxHeap.poll();
    
30.             }
    
31.         }
    
32. 
    
33.         int res = 1;
    
34.         // check special cases
    
35.         // if all negatives, and k is odd
    
36.         // result would be negative, choose from biggest k
    
37.         if (max < 0 && k % 2 == 1) {
    
38.             while (!minHeap.isEmpty()) {
    
39.                 res *= minHeap.poll();
    
40.             }
    
41.             return res;
    
42.         }
    
43. 
    
44.         // otherwise the result would be >= 0
    
45.         // convert heaps to sorted list
    
46.         int[] minK = new int[k];
    
47.         int[] maxK = new int[k];
    
48.         for (int i = k - 1; i >= 0; --i) {
    
49.             minK[i] = maxHeap.poll();
    
50.             maxK[i] = minHeap.poll();
    
51.         }
    
52. 
    
53.         int minPos = 0, maxPos = 0;
    
54.         // if k is odd, poll the largest non-negative first
    
55.         if (k % 2 == 1) {
    
56.             --k;
    
57.             res *= maxK[maxPos];
    
58.             ++maxPos;
    
59.         }
    
60.         // now choose k/2 pairs out of heap
    
61.         while (k != 0) {
    
62.             int minPair = minK[minPos] * minK[minPos + 1];
    
63.             int maxPair = maxK[maxPos] * maxK[maxPos + 1];
    
64.             if (maxPair > minPair) {
    
65.                 res *= maxPair;
    
66.                 maxPos += 2;
    
67.             }
    
68.             else {
    
69.                 res *= minPair;
    
70.                 minPos += 2;
    
71.             }
    
72.             k -= 2;
    
73.         }
    
74. 
    
75.         return res;
    
76.     }
    
77. 
    
78.     public static void main(String[] args) {
    
79.         int[] test1 = {-8, -7, -3, -1, 0, 5, 6, 9};
    
80.         int k = 3;
    
81.         System.out.println("test1: " + MultiK.multiK(test1, k));
    
82. 
    
83.         int[] test2 = {-8, -7, -3, -1, 0, 5, 6, 9};
    
84.         k = 2;
    
85.         System.out.println("test2: " + MultiK.multiK(test2, k));
    
86. 
    
87.         int[] test3 = {-8, -7, -3, -1};
    
88.         k = 3;
    
89.         System.out.println("test3: " + MultiK.multiK(test3, k));
    
90. 
    
91.         int[] test4 = {1, 2, 3, 5, 6, 9};
    
92.         k = 4;
    
93.         System.out.println("test4: " + MultiK.multiK(test4, k));
    
94. 
    
95.         int[] test5 = {-8, -7, -3, -1, 0, 5, 6, 9};
    
96.         k = 7;
    
97.         System.out.println("test5: " + MultiK.multiK(test5, k));
    
98.     }
    
99. }

复制代码

第一题O(n) non-sort解法：
keep four pointers: maximum_positive, second_max_positive, minimum_negative, second_min_negative.

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

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

感觉第二题略难啊！祝lz onsite！

royal_916 发表于 2016-2-18 06:17
感觉第二题略难啊！祝lz onsite！

多谢~~~~~

第二题可以用hashset存然后比较是否contains吧，或者用trie树查询？

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的话有没有更好算法

glad2mu 发表于 2016-2-25 17:14
我之前面过一样的题， 用的这个方法之后考官觉得有点hardcoded。 之后follow up 到求k个数的最大值。 当 ...

k的话就用priorityqueue好了

csgtc 发表于 2016-2-26 06:22
k的话就用priorityqueue好了

非常感谢！

csgtc 发表于 2016-2-26 06:22
k的话就用priorityqueue好了

priority_queue 的复杂度和sort是一样的吧？都是nlogn。
并且priority_queue的话 需要用一个min heap 和一个max heap来确保 负数们的乘积有可能是最大的。

hesha0987 发表于 2016-2-25 18:31
priority_queue 的复杂度和sort是一样的吧？都是nlogn。
并且priority_queue的话 需要用一个min heap 和 ...

两个priorityqueue， 复杂度并不是sort的nlogn，而是nlogk 速度肯定比sort快