11/09 Google Onsite

多半黑了,发一个面经造福社会.

1. Flip game (allPossible moves, canWin)
2. Find Camel:
   Input: "FooBar&

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

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

0 08:17):
第五题O(N)解法: 2K windows, Quick Select, throw K away.

写了最后一题2K WINDOW的代码

1. public class QuickSelect {
   
2. 
   
3.     public static List<Integer> topK(int[] nums, int k) {
   
4.         List<Integer> result = new ArrayList<Integer>();
   
5.         if (nums == null || nums.length < k) return result;
   
6.         int n = nums.length;
   
7.         int i = 0;
   
8.         for ( ; i < k; i++) result.add(nums[i]);
   
9.         while (i < n) {
   
10.             int j = 0;
    
11.             for (; j < k && i + j < n; j++) {
    
12.                 result.add(nums[i + j]);
    
13.             }
    
14.             quickSelect(result, k);
    
15.             i += j;
    
16.         }
    
17.         return result;
    
18.     }
    
19.    
    
20.     private static void quickSelect(List<Integer> list, int k) {
    
21.         selectHelper(list, 0, list.size() - 1, k);
    
22.         List<Integer> rest = new ArrayList<Integer>();
    
23.         for (int i = k; i < list.size(); i++) rest.add(list.get(i));
    
24.         list.removeAll(rest);
    
25.     }
    
26.    
    
27.     private static void selectHelper(List<Integer> list, int start, int end, int k) {
    
28.         int randomIndex = start + (int)(Math.random() * (end - start + 1));
    
29.         swap(list, end, randomIndex);
    
30.         int i = start - 1, j = start, pivot = list.get(end);
    
31.         while (j < end) {
    
32.             if (list.get(j) >= pivot) {
    
33.                 swap(list, ++i, j);
    
34.             }
    
35.             j++;
    
36.         }
    
37.         swap(list, ++i, end);
    
38.         int leftSize = i - start + 1;
    
39.         if (leftSize == k) return;
    
40.         if (leftSize < k) selectHelper(list, i + 1, end, k - leftSize);
    
41.         else selectHelper(list, start, i - 1, k);
    
42.     }
    
43.    
    
44.     private static void swap(List<Integer> list, int i, int j) {
    
45.         int temp = list.get(i);
    
46.         list.set(i, list.get(j));
    
47.         list.set(j, temp);
    
48.     }
    
49.    
    
50.     public static void main(String[] args) {
    
51.         int[] nums = {9,0,3,2,8,1,2,3,4,5,6,7};
    
52.         List<Integer> list = topK(nums, 3);
    
53.         for (int d : list) {
    
54.             System.out.print(d + " ");
    
55.         }
    
56.         System.out.println();
    
57.             
    
58.     }
    
59. }
    

复制代码

find camel就是brute force的方法？
public class FindCamel {

        public static void main(String[] args) {
                String[] strs = {"FooBar", "FoBa", "FooBarFoo"};
                String res = findCamel(strs, "FBF");
                System.out.println(res);
        }
       
        public static String findCamel(String[] strs, String pattern) {
                if (strs == null || strs.length == 0) {
                        return "";
                }
               
                for (String str : strs) {
                        StringBuilder sb = new StringBuilder();
                        for (char c : str.toCharArray()) {
                                if (c >= 'A' && c <= 'Z') {
                                        sb.append(c);
                                }
                        }
                        if (pattern.equals(sb.toString())) {
                                return str;
                        }
                }
               
                return "";
        }
}

RagingSword 发表于 2015-11-20 08:39
有N/K 个batches， 所以是O(K * N / K) = O(K)

补充内容 (2015-11-20 08:39):

感觉不行啊，假设有N/k个batch，每个batch的长度为k，所以，每compare两个batch的时间复杂度是k，从N/k个batch中间选出第m大的时间复杂度是N/k, 所以总的复杂度就是k*N/k。
但是，你如何保证确实有那么一个batch，其k个数对应着要求的k个数呢？
谢谢了

谢谢LZ 请问下第五题 O(n) 是怎么做啊

同问第五题O(N)解法

楼主没有hr收到消息嘛

@南岸的风 发表于 2015-11-20 06:56
楼主没有hr收到消息嘛

没有...问了下说这周进HC,感觉GG了

第五题O(N)解法: 2K windows, Quick Select, throw K away.

楼主能稍微详细讲下O（N）怎么实现的么？
是在这个2k window里用quick select么？这个不是O（k）么？

stonezms 发表于 2015-11-20 08:27
楼主能稍微详细讲下O（N）怎么实现的么？
是在这个2k window里用quick select么？这个不是O（k）么？

有N/K 个batches， 所以是O(K * N / K) = O(K)

补充内容 (2015-11-20 08:39):
打错了
O(K * N / K) = O(N)

RagingSword 发表于 2015-11-20 08:39
有N/K 个batches， 所以是O(K * N / K) = O(K)

补充内容 (2015-11-20 08:39):

正解.....

第五题2k window不行吧，如果去后面k个全部小于前面k个，岂不是都会被去除，然后前面的k个会被移走？