I had an interview question that asked me a rather simple question:
Design a function that takes in a matrix and indices i and j. The function should return the sum of all numbers in the matrix along $i$ and $j$, but not after $i,j$.
So, if you had a matrix $$A = [[1, 2, 3] \\ \space\space\space\space\space\space\space\space\space [4, 5, 6]\\ \space\space\space\space\space\space\space\space\space\space [7, 8, 9]]$$
And indices $i = 1, j = 1$, you would need to return $2+5+4=11$. If you had $i=2,j=1$, then you would need to return $2+5+8+7 = 22$. If you had $i=2,j=2$, you would be returning $3+6+9+8+7=33$. And so on.
Cool, easy enough:
def get_add(matrix, i, j):
sum1 = 0
for a in range(i + 1):
print "i ", a, matrix[a][j]
sum1 += matrix[a][j]
sum2 = 0
for a in range(j):
print "j ", a, matrix[i][a]
sum2 += matrix[i][a]
return sum1 + sum2
But I had an interesting follow-up question. The interviewer said, "Okay, now I want you to design a function that will construct another matrix $B$ with $B_{i,j}$ equal to the output of your function get_add(A, i, j).
Now, the question was proposed in a way that was saying, "Is there a more efficient way of creating this matrix B?" Using get_add to make this matrix would be, what, $O(n^3)$ or something? Is there a better solution? I couldn't really come up with something, though I am sure there must be something better.
Thank you
