Google Interview Question
Software DevelopersCountry: United States
void set(int row, int col, int val) {
return matrix[row][col] = val;
}
int sum(int row, int col){
int res = 0;
for(int r = 0; r <= row; r++){
if(r==row){
for(int c = 0; c <= col; c++){
res += matrix[r][c];
}
} else {
for(int c = 0; c <= matrix[r].length; c++){
res += matrix[r][c];
}
}
}
return res;
}
sorry for the bad format above.
This can be done using 2d segment/BIT tree. The idea is that you first build a tree by first coordinate and then for each node of that tree you build a segment tree by second coordinate.
Since input parameters are int, you can build a segment tree for [0,MAX_INT] * [0, MAX_INT] and you will have O(log(INT_MAX)^2) complexity.
Do they really ask you to implement 2d segment trees? I doubt one would write that if never written before and this is so topcoder/hackerrank specific.
We can use a single hash where the key is a 64-bit int that has both the row and column in it (shift row 32 bits, OR with column).
Here's the code in C#:
private Dictionary<long, int> dict = new Dictionary<long, int>();
public void set(int row, int col, int val) {
dict[makeCoord(row, col)] = val;
}
public int sum(int row, int col) {
int result = 0;
for (int i = 0 ; i <= row; i++) {
for (int j = 0 ; j <= col; j++) {
long coord = makeCoord(i,j);
if (this.dict.ContainsKey(coord)) {
result += this.dict[makeCoord(i,j)];
}
}
}
return result;
}
private long makeCoord(int row, int col) {
long coord = (long)row << 32;
return (coord | (long)col);
}
I did not remember that it was SPARSE, but in any case you can get the idea. The time complexity is O(rows) or O(columns):.
public class NotSparseMatrix{
private int[][] matrix;
private int[][] columnSum;
private int rows, columns;
public SparseMatrix(int rows, int columns){
this.columns = columns;
this.rows = rows;
this.matrix = new int[columns][rows];
this.columnSum = new int[columns][rows];
}
public void set(int row, int col, int val){
if(row < rows && col < columns){
int difference = val - matrix[col][row];
for(int i = row; i < rows; i++){
columnSum[col][i] += difference;
}
}
}
public int sum(int row, int col){
int result = 0;
if(row < rows && col < columns){
for(int i = 0; i <= col; i++){
result += columnSum[i][row];
}
}
return result;
}
}
class SparseMatrix(object):
def __init__(self):
self.vals = dict()
def set_val(self, row, col, val):
self.vals[(row, col)] = val
def sum_matrix(self, row, col):
result = 0
if len(self.vals) < (row+1)*(col+1):
for i, j in self.vals:
if i <= row and j <= col:
result += self.vals[(i, j)]
else:
for i in xrange(row+1):
for j in xrange(col+1):
if (i, j) in self.vals:
result += self.vals[(i, j)]
return result
sm = SparseMatrix()
sm.set_val(1,1,10)
sm.set_val(2,3,10)
print sm.sum_matrix(3,3)
Since the matrix is sparse, I would like to store the data in a hashmap of hashmap rather than the traditional [][].
- jjongpark September 04, 2016