Another from the archives! A nice introductory matrix question. The 1-x trick is nice, as is the option (which I prefer) to make a new matrix.
class Solution:
def flipAndInvertImage(self, image: List[List[int]]) -> List[List[int]]:
res = []
for row in image:
newRow = []
for bit in reversed(row):
newRow.append(1-bit)
res.append(newRow)
return resOn a personal note, this question is actually one of the first interview questions I had to work through for a college internship at a giant tech company. It could have gone better; I got the internship anyways. So let’s see if I can redeem myself. I’m going to try to solve it “live”.
I know (from many years ago, and hopefully also many more years of experience) that I want to do nice-and-simple helper functions. So things like “columnWins”, “rowWins”, etc. Well, I know that Python is friendly enough where I just made a generic helper that would say which, if any, player won any length-3 sequence of values. Then I simply iterated over all relevant length-3 sequences. It’s not a small amount of code.
I had a few typos I fixed up. There are inefficiencies and redundancies, nevermind the allocations, but it’s straightforward and readable enough. The other python solutions, those that won as “best practices”, are a bit more explicit about it being a 3×3 matrix.
def seq_wins(seq):
assert(len(seq) == 3)
V = seq[0]
if V == 0: return 0
for v in seq[1:]:
if v != V:
return 0
return V
def is_solved(board):
# Check rows:
for r in board:
w = seq_wins(r)
if w != 0:
return w
# Check columns
for c in range(3):
col = []
for r in board:
col.append(r[c])
w = seq_wins(col)
if w != 0:
return w
# Check diagonals
d1 = []
d2 = []
for i in range(3):
d1.append(board[i][i])
d2.append(board[i][2-i])
w = seq_wins(d1)
if w != 0:
return w
w = seq_wins(d2)
if w != 0:
return w
for r in board:
for v in r:
if v == 0:
return -1
return 0I like this question as an interview question, actually. The reasoning-by-cases is nice and comes up in the real world. Sure, 2D arrays aren’t very common in my experience, but as a proxy for indexing into a nontrivial data structure, it’s a good one. I think a natural approach (obviously, given my own approach) is to make a helper function, either explicitly or at least implicitly, and seeing how a candidate thinks to draw the line of where/how to make a helper function can be a good insight into their views.
I decided to redo this problem, from the archives in Python. Previously I had it in C++. You’d think this post, then, of resizing a 2D array, would have been straightforward. Here are some notes:
I think this is a good exercise for junior people who say they feel comfortable with 2D arrays.
Complete with debugging statements, here is my approach:
def getRow(i, r, c):
#print('row of', i, '-th element in matrix ', r, '*', c, 'is', i // c)
return i // c
def getCol(i, r, c):
return i % c
class Solution:
def matrixReshape(self, mat: List[List[int]], r: int, c: int) -> List[List[int]]:
R = len(mat)
if R is 0: return mat
C = len(mat[0])
if R * C != r * c:
return mat
res = []
for i in range(r):
res.append([])
for j in range(c):
res[i].append(0)
for i in range(r*c):
#print(getRow(i, r, c), getCol(i, r, c), getRow(i, R, C), getCol(i, R, C))
old = mat[getRow(i, R, C)][getCol(i, R, C)]
res[getRow(i, r, c)][getCol(i, r, c)] = old
return resThis covers interesting questions like allocation (pre-allocating the results array), bounds-checking in a nontrivial setting (numrows, numcols), and then an interesting question of mapping. That mapping also really requires a comfort with indices versus the values of an array, plus array-of-arrays instead of just arrays. I think this is a good “hard” phone-screen question.
For real-world applicability, I’ve never worked too much with 2D arrays, certainly not this explicitly. However, the challenge of iterating over 2 different objects/data-structures that don’t naively both map to the same for loop (so to speak), that’s something that comes up a lot, albeit not so directly as in this code. Just recently I was iterating over 2 similar (but not the same!) trees at work, and had to make sure the iteration remains in lockstep. Of course, this complex-iteration also comes up in my favorite merge-linked-list sort of questions. Again, not literally identical, but the same “genus”.
Another from the archives. This is a “real” matrix question (versus an array-of-arrays). For the people I’ve helped enter into the tech world, the bigger challenge is the vocabulary of matrix math, rather than the actual array-of-array machinery or similar. I like this one as an operation, and I’m glad it takes the time to color and otherwise illustrate what the transpose is.
In a way the straightforward solution may seem “cute”, you “just” need to swap the i/j indices. I think, however, that that’s a real insight, and a real insight you can get in an interview setting. Maybe other people would disagree. I think you can also get there the “brute force” way of just carefully thinking about what to do. The larger challenge is allocating the transpose matrix correctly.
class Solution:
def transpose(self, matrix: List[List[int]]) -> List[List[int]]:
if len(matrix) == 0: return []
T = []
for j in range(len(matrix[0])):
T.append([])
for i in range(len(matrix)):
T[j].append(matrix[i][j])
return T