工作一年半在职跳槽，分享一波面经＋经验，求加精

Google第一题：
每个点 每个长度挨着试 不知道有没有更简单的方法了

1. public class Solution1 {
   
2.     int res;
   
3.     int rows;
   
4.     int cols;
   
5.     int[][] data;
   
6.     public int solve(int[][] data) {
   
7.         if(data==null||data.length==0||data[0].length==0) return 0;
   
8.         this.rows = data.length;
   
9.         this.cols = data[0].length;
   
10.         this.res = 0;
    
11.         this.data = data;
    
12.         for(int i = 0; i<data.length; i++){
    
13.             for(int k = 0; k<data[i].length; k++){
    
14.                 if(data[i][k]==1)
    
15.                     helper(i, k, 1);
    
16.             }
    
17.         }
    
18.         return res;
    
19.     }
    
20.     private void helper(int i, int k, int len) {
    
21.         boolean flag = true;
    
22.         if(i+len >=rows || k + len>=cols){
    
23.             return;
    
24.         }
    
25.         for (int ii = i; ii <= i + len; ii++) {
    
26.             if (data[ii][k] != 1 || data[ii][k + len] != 1) {
    
27.                 flag = false;
    
28.                 break;
    
29.             }
    
30.         }
    
31.         for (int ii = k; ii <= k + len; ii++) {
    
32.             if (data[i][ii] != 1 || data[i + len][ii] != 1) {
    
33.                 flag = false;
    
34.                 break;
    
35.             }
    
36.         }
    
37.         if(flag) res++;
    
38.         helper(i, k, len+1);
    
39.     }
    
40. }
    

复制代码

跑了两个 问题不大
        int[][] nums2D1 = {{1,1,1,1},{1,0,1,1},{1,1,1,1}};    ----> 3
        int[][] nums2D2 = {{0,0,1,1,1,1},{0,0,1,1,1,1},{1,1,1,1,0,1},{1,1,1,1,1,1}};   ----> 9

吃啥才算成熟 发表于 2017-1-6 07:17
Google第一题：
每个点 每个长度挨着试 不知道有没有更简单的方法了

粗看了一下你这是O(n^4)? 最好应该是O(n^3)，先算一下每个点最远走多远，然后便利一遍每个点，数一下长度分别为1，2，3...的正方形

Google 第二题
add是O(1)所以输入很多应该没所谓。
但要是k很大。。。list就会很大 而且size*cur也有可能overflow 没想好有什么好办法

1. public class Solution2 {
   
2.     LinkedList<Integer> list;
   
3.     int k;
   
4.     double cur;
   
5.     public Solution2(int k){
   
6.         this.list = new LinkedList<Integer>();
   
7.         this.k = k;
   
8.         this.cur = 0;
   
9.     }
   
10. 
    
11.     public double add(int input) {
    
12.         int size = list.size();
    
13.         if (size == k) {
    
14.             int first = list.pollFirst();
    
15.             cur = (size * cur + input - first)/(double)size;
    
16.         } else {
    
17.             cur = (size * cur + input)/(double)(size+1);
    
18.         }
    
19.         list.add(input);
    
20.         return cur;
    
21.     }
    
22. }
    

复制代码

shabixia 发表于 2017-1-6 07:28
粗看了一下你这是O(n^4)? 最好应该是O(n^3)，先算一下每个点最远走多远，然后便利一遍每个点，数一下长度 ...

恩是一样的　Ｏ（ｎ３）

google onsite (1):

因为input不需要sorted，要是ｔｒｅｅ或者ｇｒａｐｈ，就多个ｔｒａｖｅｌ，一个个输入就行，和ａｒｒａｙ道理一样

1. import java.util.*;
   
2. 
   
3. public class Solution3 {
   
4.     public int solve(int[] input){//input 不需要sorted
   
5.         Map<Integer, Integer> map = new HashMap<>();
   
6.         int max = 0;
   
7.         for(int i = 0; i<input.length; i++){
   
8.             int left = map.getOrDefault(input[i] - 1, 0);
   
9.             int right = map.getOrDefault(input[i] + 1, 0);
   
10.             int sum = left + right + 1;
    
11.             max = Math.max(sum, max);
    
12. 
    
13.             map.put(input[i] - left, sum);
    
14.             map.put(input[i] + right, sum);
    
15.         }
    
16.         return max;
    
17.     }
    
18. }
    

复制代码

补充内容 (2017-1-6 07:56):
{10,1,-123,7,214,6,51,15,23,4513,5,14,8,61,9,2};　---> 6   (5, 6, 7, 8, 9, 10)

google onsite 2:

1. import java.util.*;
   
2. 
   
3. public class Solution4 {
   
4.     List<Iterator<Integer>> list;
   
5.     int cur;
   
6.     int size;
   
7.     public Solution4(List<Iterator<Integer>> list){
   
8.         this.list = list;
   
9.         this.cur = 0;
   
10.         this.size = list.size();
    
11.     }
    
12. 
    
13.     public int next(){
    
14.         hasNext();
    
15.         int res = list.get(cur).next();
    
16.         cur = (cur+1)%size;
    
17.         return res;
    
18.     }
    
19.     public boolean hasNext(){
    
20.         int pre = cur;
    
21.         while(!list.get(cur).hasNext()){
    
22.             cur = (cur+1)%size;
    
23.             if(cur==pre) return false;
    
24.         }
    
25.         return true;
    
26.     }
    
27. }
    

复制代码

test:

1.         Integer[] nums1 = {3,5,10,3};
   
2.         Integer[] nums2 = {1,2};
   
3.         Integer[] nums3 = {};
   
4.         Integer[] nums4 = {3,1,54,5,12,44};
   
5. 
   
6.         List<Iterator<Integer>> list = new ArrayList<>();
   
7.         list.add(Arrays.asList(nums1).iterator());
   
8.         list.add(Arrays.asList(nums2).iterator());
   
9.         list.add(Arrays.asList(nums3).iterator());
   
10.         list.add(Arrays.asList(nums4).iterator());
    
11.         Solution4 s = new Solution4(list);
    
12.         while(s.hasNext()){
    
13.             System.out.print(s.next() + " ");
    
14.         }
    

复制代码

output: 3 1 3 5 2 1 10 54 3 5 12 44

google onsite 3:
直接方法: 但复杂度高。

1. //给一个string和一列word，求最长长度的substring，比如string是abcde，然后word是abe，bc，aaaa，那最长的就是abe，followup是string特别长怎么办
   
2. public class Solution5 {
   
3.     public String solve(String str, String[] words){
   
4.         int max = 0;
   
5.         String res = "";
   
6.         for(String ss: words){
   
7.             if(ss.length() > max && sub(str, ss)){
   
8.                 max = ss.length();
   
9.                 res = ss;
   
10.             }
    
11.         }
    
12.         return res;
    
13.     }
    
14.     private boolean sub(String s1, String s2){
    
15.         char[] c1 = s1.toCharArray();
    
16.         char[] c2 = s2.toCharArray();
    
17.         int p = 0;
    
18.         for(int i = 0; i<c1.length; i++){
    
19.             if(p==c2.length) break;
    
20.             if(c1[i] == c2[p]) p++;
    
21.         }
    
22.         return p == c2.length;
    
23.     }
    
24. }
    

复制代码

补充内容 (2017-1-6 08:31):
String[] strs1 = {"a","aae","bc","abd","abe","bca","aaaa",};
        Solution5 s = new Solution5();
        String res = s.solve("abcde", strs1);

补充内容 (2017-1-6 08:36):
改进用KMP

给你一个folder的路径，然后写个method删除该folder下所有内容相同的文件

这个怎么写? 有代码吗?

google onsite 3. 扫一遍string 用一个map存index。
能快一些。但总觉得是不是哪里还是麻烦了？有更好的方法么

1.     public String solve2(String str, String[] words){
   
2.         Map<Character, LinkedList<Integer>> map = process(str);
   
3.         int max = 0;
   
4.         String res = "";
   
5.         for(String ss: words){
   
6.             if(ss.length() > max){
   
7.                 Map<Character, LinkedList<Integer>> tmp = copyMap(map);
   
8.                 int cur = 0;
   
9.                 boolean flag = true;
   
10.                 for(char c: ss.toCharArray()){
    
11.                     if(!tmp.containsKey(c) || tmp.get(c).size()==0){
    
12.                         flag = false;
    
13.                         break;
    
14.                     }
    
15.                     int p = tmp.get(c).pollFirst();
    
16.                     if( p < cur ){
    
17.                         flag = false;
    
18.                         break;
    
19.                     }
    
20.                     cur = p;
    
21.                 }
    
22.                 if(flag){
    
23.                     max = ss.length();
    
24.                     res = ss;
    
25.                 }
    
26.             }
    
27.         }
    
28.         return res;
    
29.     }
    
30. 
    
31.     private Map<Character, LinkedList<Integer>> copyMap(Map<Character, LinkedList<Integer>> map){
    
32.         Map<Character, LinkedList<Integer>> tmp = new HashMap<>();
    
33.         for(Map.Entry<Character, LinkedList<Integer>> me: map.entrySet()){
    
34.             tmp.put(me.getKey(), new LinkedList<>(me.getValue()));
    
35.         }
    
36.         return tmp;
    
37.     }
    
38. 
    
39.     private Map<Character, LinkedList<Integer>> process(String str){
    
40.         Map<Character, LinkedList<Integer>> map = new HashMap<>();
    
41.         char[] chars = str.toCharArray();
    
42.         for(int i = 0; i<chars.length; i++){
    
43.             map.computeIfAbsent(chars[i], k->new LinkedList<Integer>()).add(i);
    
44.         }
    
45.         return map;
    
46.     }

复制代码

String[] strs1 = {"a","aae","bc","adbe","abe","bca","aaaa"};
Solution5 s = new Solution5();
String res = s.solve2("abcde", strs1);  -----> abe

补充内容 (2017-1-6 09:44):
尤其用林kedlist存相同字母的每个index 和copymap哪里。不知道有没有什么更好的方法？