123
返回列表 发新帖
楼主: maktf
跳转到指定楼层
上一主题 下一主题
收起左侧

Google intern 面经

🔗
 楼主| maktf 2015-10-23 00:23:39 | 只看该作者
全局:
cszeus 发表于 2015-10-14 03:04
我也想问问,第二题怎么做的啊?

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

使用道具 举报

🔗
tangvictor 2015-10-23 02:00:31 | 只看该作者
全局:
第四题一般用快排,数据量再大用heap sort更快些。这篇帖子其实提到了归并排序更快,但空间复杂度要O(N), 这题显然只能用堆排序了。

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

使用道具 举报

🔗
tangvictor 2015-10-23 02:12:06 | 只看该作者
全局:
贴一下第二题
  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.         def set(self, i, j, value):
  7.                 self.A[i][j] = value
  8.                 for x in range(i + 1, len(self.sum)):
  9.                         for y in range(j + 1, len(self.sum)):
  10.                                 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]

  11.         def get(self, i, j):
  12.                 return self.sum[i + 1][j + 1]

  13.         def getBetween(self, a, b, x, y):
  14.                 return self.sum[x + 1][y + 1] - self.sum[a][y + 1] - self.sum[x + 1][b] + self.sum[a][b]
复制代码
回复

使用道具 举报

🔗
 楼主| maktf 2015-10-23 03:05:38 | 只看该作者
全局:
tangvictor 发表于 2015-10-23 02:00
第四题一般用快排,数据量再大用heap sort更快些。这篇帖子其实提到了归并排序更快,但空间复杂度要O(N),  ...

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

使用道具 举报

🔗
mooc 2015-10-23 10:30:29 | 只看该作者
全局:
maktf 发表于 2015-10-23 00:22
哦对, 忘了说query是要计算从1个点到另一个点组成的方阵的和

query多write 少和 query少write有什么区别啊,是用到cache吗?
回复

使用道具 举报

🔗
 楼主| maktf 2015-10-24 03:45:28 | 只看该作者
全局:
mooc 发表于 2015-10-23 10:30
query多write 少和 query少write有什么区别啊,是用到cache吗?

如果不做处理的话,query是O(n^2),如果query多就不合理了
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表