Google店面

下午刚刚结束的店面，interviewer是一个口音特别重的印度小哥，他说他在google已经工作了9年。人特别nice，直接粘贴原题如下：

1. 第一题：
// image[i][j] := a value for a pixel at (colum_j, row_i).
// (0, 0) := top-left corner
// Each 'row' has the same size (:= the number of columns)
// image.size() := the number of rows
vector<vector<int>> image;

// Sum of all values i

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

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

a[index];

接着印度小哥说如果有 X billions of balls, and Y thousands of colors，你将如何更改你的程序？
我也不知道optimal的solution，就跟小哥胡乱讨论了一通:我说数组里只存颜色的种类，然后根据每个球的
个数，确定一个range，随机生成一个数后，如果在那个range之内就返回这种颜色。这样做的好处是不用把
billions大的数组放进内存。小哥说great,great又瞎聊一通结束了对话 ...

第一题的动态方程是不是等于sum[i][j] = sum[i][j-1] ＋ sum[i- 1][j] - sum[i-1][j-1] + image[i][j].这样的时间复杂度是O (n^2)