来源:Mitbbs, Google First Phone Interview
原帖:http://www.mitbbs.com/article_t1/JobHunting/32574909_0_1.html
题目:
Given a 2D space of maximum size NxN which supports two operations :
[1] void UPDATE(x,y,v) - sets the value of cell [x,y] to v
[2] int QUERY(x1,y1,x2,y2) - returns sub-rectangle sum (x1,y1) to (x2,y2)
inclusive, and there is an infinite stream of such 2 types of operations which have to supported. How would you store the values for efficient updates and retrievals ? (二维线段树 说算法+分析复杂度)
思路:
我gg的电面题目。后来发现这道题在mitbbs和meetqun上曾经出现过多次。
有O(logn)的解法,用quad-tree或者树状数组(binary index tree)
不过面试官对于O(n)的复杂度是可以接受的。面试官期待的也是O(n)的解法
代码:
原帖:http://www.mitbbs.com/article_t1/JobHunting/32574909_0_1.html
题目:
Given a 2D space of maximum size NxN which supports two operations :
[1] void UPDATE(x,y,v) - sets the value of cell [x,y] to v
[2] int QUERY(x1,y1,x2,y2) - returns sub-rectangle sum (x1,y1) to (x2,y2)
inclusive, and there is an infinite stream of such 2 types of operations which have to supported. How would you store the values for efficient updates and retrievals ? (二维线段树 说算法+分析复杂度)
思路:
我gg的电面题目。后来发现这道题在mitbbs和meetqun上曾经出现过多次。
有O(logn)的解法,用quad-tree或者树状数组(binary index tree)
不过面试官对于O(n)的复杂度是可以接受的。面试官期待的也是O(n)的解法
代码:
vector<vector<int>> matrix;
int M = matrix.size(), N = matrix[0].size();
// update > > sum
// update O(1); sum O(n^2)
void update(int r, int c, int val) {
matrix[r][c] = val;
}
// (r1,c1) upper left, (r2,c2) bottom right
int sum(int r1, int c1, int r2, int c2) {
int res = 0;
for (int i = r1; i <= r2; ++i) {
for (int j = c1; j <= j2; ++j) {
res += matrix[i][j];
}
}
return res;
}
// sum > > update
// dp[i][j] computer sum of rectangle [0,0] --- [0,j] --- [i,0] --- [i,j]
// update O(n^2), sum O(1).
vector<vector<int>> dp(M,vector(N,0));
void compute() {
dp[0][0] = matrix[0][0];
for (int j = 1; j < N; ++j) {
dp[0][j] = dp[0][j-1] + matrix[0][j];
}
for (int i = 1; i < M; ++i) {
dp[i][0] = dp[i-1][0] + matrix[i][0];
}
for (int i = 1; i < M; ++i) {
for (int j = 1; j < N; ++j) {
dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + matrix[i][j];
}
}
}
void update(int r, int c, int val) {
int dif = val - matrix[i][j];
for (int i = r; i < M; ++i) {
for (int j = c; j < N; ++j) {
dp[i][j] += dif;
}
}
}
int sum(int r1, int c1, int r2, int c2) {
if (r1 == 0 && c1 == 0) return dp[r2][c2];
else if (r1 == 0) return dp[r2][c2] - dp[r2][c1-1];
else if (c1 == 0) return dp[r2][c2] - dp[r1-1][c2];
else return dp[r2][c2] - dp[r1-1][c2] - dp[r2][c1-1] + dp[r1-1][c1-1];
}
// sum ~= update
// update
vector<vector<int>> dp(M,vector(N,0));
// row dp; dp[i][j] = sum_i_{k = 0}^{k = j};
void compute() {
for (int i = 0; i < M; ++i) {
for (int j = 0; j < N; ++j) {
if (j == 0) dp[i][j] = matrix[i][j];
else dp[i][j] = dp[i][j-1] + matrix[i][j];
}
}
}
void update(int r, int c, int val) {
int dif = val - matrix[i][j];
for (int j = c; j < N; ++j) {
dp[r][j] += dif;
}
}
int sum(int r1, int c1, int r2, int c2) {
int res = 0;
for (int i = r1; i <= r2; ++i) {
res += c1 == 0 ? dp[i][c2] : dp[i][c2] - dp[i][c2-1];
}
return res;
}
No comments:
Post a Comment