Google intern 面经

cszeus 发表于 2015-10-14 03:04
我也想问问，第二题怎么做的啊？

第二题忘说了，query是要返回一个点到另一个点组成的方阵的每一个元素的和

第四题一般用快排，数据量再大用heap sort更快些。这篇帖子其实提到了归并排序更快，但空间复杂度要O(N), 这题显然只能用堆排序了。

补充内容 (2015-10-22 14:00):
http://bbs.csdn.net/topics/190116334

贴一下第二题

1. class Array:
   
2.         def __init__(self, A):
   
3.                 self.sum = [[0] * (len(A[0]) + 1) for i in range(len(A) + 1)]
   
4.                 self.A = A
   
5.                 self.set(0, 0, self.A[0][0])
   
6. 
   
7.         def set(self, i, j, value):
   
8.                 self.A[i][j] = value
   
9.                 for x in range(i + 1, len(self.sum)):
   
10.                         for y in range(j + 1, len(self.sum)):
    
11.                                 self.sum[x][y] = self.sum[x - 1][y] + self.sum[x][y - 1] + self.A[x - 1][y - 1] - self.sum[x - 1][y - 1]
    
12. 
    
13.         def get(self, i, j):
    
14.                 return self.sum[i + 1][j + 1]
    
15. 
    
16.         def getBetween(self, a, b, x, y):
    
17.                 return self.sum[x + 1][y + 1] - self.sum[a][y + 1] - self.sum[x + 1][b] + self.sum[a][b]

复制代码

tangvictor 发表于 2015-10-23 02:00
第四题一般用快排，数据量再大用heap sort更快些。这篇帖子其实提到了归并排序更快，但空间复杂度要O(N),  ...

用什么排序不是关键，关键是mapreduce的设计结构和外排序的基本方法

maktf 发表于 2015-10-23 00:22
哦对， 忘了说query是要计算从1个点到另一个点组成的方阵的和

query多write 少和 query少write有什么区别啊，是用到cache吗？

mooc 发表于 2015-10-23 10:30
query多write 少和 query少write有什么区别啊，是用到cache吗？

如果不做处理的话，query是O（n^2），如果query多就不合理了