[3/8] Google Onsite

bobzhang2004 发表于 2016-3-29 05:21
请问” count of smaller number before itself“ 这个题楼主是选择建树还是divide and conquer，面试官对 ...

我建了树，满意

bobzhang2004 发表于 2016-3-29 05:22
楼主可以给下“求最大能获取的假期和Path. ”的具体代码吗？看到很多次这个题，但还是不清楚具体怎么做

不想写了，但是dp公式都给了，应该不需要具体代码了吧。。。。path的话就track一下就行

论坛匿名用户 发表于 2016-3-29 07:23
提示一下，不想说太细了，看看java中round函数是什么样的，怎么实现的

The java.lang.Math.round(float a) returns the closest int to the argument. The result is rounded to an integer by adding 1/2, taking the floor of the result, and casting the result to type int.

论坛匿名用户 发表于 2016-3-11 06:24
比如2f 最接近 33对吧，所以就转换成33， 3d 最接近33也转换成33，比如5a->66
findNthsmallest element  ...

那就建一个sorted array, 然后将输入的指通过二分查找找到那个最近的值就行了吧，将3d都这些都转化为十进制，然后查找

machen982003 发表于 2016-3-13 04:12
那这个题是扫四遍的做法么? 做一遍右一遍, 上一遍下一边, 然后求和最大?

分享下代码吧

1. public class FlowersInGarden {
   
2. 
   
3.         public static void main(String[] args) {
   
4.                 char[][] matrix = {{'f', 'x', 'x', 'w', 'f'},
   
5.                                      {'f', 'f', 'x' ,'x' ,'x'},
   
6.                                      {'x', 'x', 'f', 'w', 'f'},
   
7.                                      {'f', 'f', 'x', 'w', 'x'}};
   
8.                 maxFlowersInGarden(matrix);
   
9.         }
   
10.        
    
11.         public static int maxFlowersInGarden(char[][] matrix) {
    
12.                 if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
    
13.                         return 0;
    
14.                 }
    
15.                 int m = matrix.length;
    
16.                 int n = matrix[0].length;
    
17.                
    
18.                 int[][] res = new int[m][n];
    
19.                 for (int i = 0; i < m; i++) {
    
20.                         int count = 0;
    
21.                         int j = 0;
    
22.                         int start = 0;
    
23.                         while (j < n) {
    
24.                                 if (matrix[i][j] == 'f') {
    
25.                                         count++;
    
26.                                 } else if (matrix[i][j] == 'w') {
    
27.                                         for (int k = start; k < j; k++) {
    
28.                                                 res[i][k] = count;
    
29.                                         }
    
30.                                         start = j + 1;
    
31.                                         count = 0;
    
32.                                 }
    
33.                                 j++;
    
34.                         }
    
35.                         for (int k = start; k < j; k++) {
    
36.                                 res[i][k] = count;
    
37.                         }
    
38.                 }
    
39.                 for (int j = 0; j < n; j++) {
    
40.                         int count = 0;
    
41.                         int i = 0;
    
42.                         int start = 0;
    
43.                         while (i < m) {
    
44.                                 if (matrix[i][j] == 'f') {
    
45.                                         count++;
    
46.                                 } else if (matrix[i][j] == 'w') {
    
47.                                         for (int k = start; k < i; k++) {
    
48.                                                 res[k][j] += count;
    
49.                                         }
    
50.                                         start = i + 1;
    
51.                                         count = 0;
    
52.                                 }
    
53.                                 i++;
    
54.                         }
    
55.                         for (int k = start; k < i; k++) {
    
56.                                 res[k][j] += count;
    
57.                         }
    
58.                 }
    
59.                 for (int i = 0; i < m; i++) {
    
60.                         for (int j = 0; j < n; j++) {
    
61.                                 if (matrix[i][j] == 'f') {
    
62.                                         res[i][j] -= 1;
    
63.                                 }
    
64.                         }
    
65.                 }
    
66.                 int max = 0;
    
67.                 for (int i = 0; i < m; i++) {
    
68.                         for (int j = 0; j < n; j++) {
    
69.                                 System.out.print(res[i][j] + " ");
    
70.                                 max = Math.max(max, res[i][j]);
    
71.                         }
    
72.                         System.out.println();
    
73.                 }
    
74.                
    
75.                
    
76.                 return max;
    
77.         }
    
78. }
    

复制代码

simplessssss 发表于 2016-3-28 09:53
请问楼主第五轮的第一题是怎么做的，怎么计算 slidingwindow avg, global avg, update(insert) value都可以 ...

update的意思就只能是加一个数吗？如果这样的话应该就是sliding window average的变形啊，就是多一个sum几轮全局的和就行了

bobzhang2004 发表于 2016-3-29 12:49
那就建一个sorted array, 然后将输入的指通过二分查找找到那个最近的值就行了吧，将3d都这些都转化为十进 ...

你想想怎么用java的round logic on 这道题，很简单，O(1)时间就能做出来

bobzhang2004 发表于 2016-3-29 12:52
update的意思就只能是加一个数吗？如果这样的话应该就是sliding window average的变形啊，就是多一个sum ...

嗯，对，就是变形应该

slidingwindow avg, global avg, update(insert) value 怎样能达到o(1)？

这个数据结构不能用array吧？用array的话，insert不能达到o（1）吧？如果用segment tree, 也都不是o(1)，如果用linked list的话，插入可以o(1)，别的怎么达到o(1)呢？

假期那题楼主可以再说一下吗，没看懂题目。谢谢