Python Coding Interview Practice - Difficulty: Medium

In this video I will walk through a coding interview question and provide a solution in python! This specific problem is medium difficulty and involves using a graph traversal algorithm.

Use the discount code "techwithtim" for 10% off!

◾◾◾◾◾
💻 Enroll in The Fundamentals of Programming w/ Python

◾◾◾◾◾◾

⚡ Please leave a LIKE and SUBSCRIBE for more content! ⚡

Tags:
- Tech With Tim
- Python Tutorials
- Python Coding Interview Practice
- Coding Interview Practice

#Python #CodingInterview

[lathasri]

Hey Tim,
I really loved ur graph traversal algorithm
I just tried this one using recursion and got the code much easier 😄
It's working perfectly😁

Here's the code:

def check(m, n, c):
arr[m][n] = 0
if m!=0:
if arr[m-1][n] == 1:
c = check(m-1, n, c+1)

if n!=0:
if arr[m][n-1] == 1:
c = check(m, n-1, c+1)

if m!=len(arr)-1:
if arr[m+1][n] == 1:
c = check(m+1, n, c+1)

if n!=len(arr[m])-1:
if arr[m][n+1] == 1:
c = check(m, n+1, c+1)

return c

def riversizes(arr):
l = []
for m in range(len(arr)):
for n in range(len(arr[m])):

if arr[m][n] != 0:
count = check(m, n, 1)
l+=[count]

return l

Did i miss something?🤔

[LLsul]

I went a similar approach with depth first search but preferred to eliminate the visited "1"s with "0"s after they were done, so I didn't have to worry about the worst case complexity of the "in"-operator for sets.

[leyahsutton]

Really liked the diagram on the whiteboard, and followed the code along! Noticed a slight mistake in your original version that was fixed in the copy and pasted one, when you call the get_neighbours function the first argument should be ‘current’ and not (y, x). Once I fixed that the code worked for me on vs code !

[JoeWong]

Thanks a lot Tim solid walk through please keep up this series!! this exact question is in cracking the coding interview except I believe in that she also counts diagonals as part of the river as well.

[anynamecanbeuse]

remove the neighbor zeros as doing in-depth search would be a little more efficient since you don't have to query them in the next round.

[usmanomar]

Thanks for the vid! Very helpful - could you make a video similar to this but you haven’t seen the question before? Would love to see your whole thinking process when approaching a brand new problem :)

[randomuser]

i once got this problem, and i got a similar solution, i think is faster but becouse am still a newi i cant really tell, the only really diference is that
instead of saving each coord of the already checked bits, you change the checked "1" for "0" that way you dont repeat a bit and you dont move through an other list, intuitively i think is better

[antoneliseev]

I think there are little mistake in "get_neighbors" because you should compare index x not with len(matrix[0]) but with len(matrix[y])

[domelperez]

Great tutorials Tim! Very informative and excellent explanations in all videos. Keep up the awesome feed!

[geoffmahugu]

The explanation in this video is way better 👍

[elahehshahmir]

very helpful, wish we could have more of these

[ElliyahuRosha]

I initially thought of doing it with recursion, but your stack idea blew my mind!
Thx

[soumyodeepmukherjee]

Just a thought, I think - on the get_neighbours function - the len(matrix[0[) would fail in cases where the length of columns are not-equal across all the rows because the question specifies that the matrix may be of unequal width. So. I think we should do len(matrix[x[) instead. Please correct me if I am wrong. Btw, Great explanation!! loved it.

[dineshshekhawat]

What if we don't even need the visited variable, once the element is visited mark the element as zero in matrix. Then no need to check if it is contained in visited set.

checking for 1 would be enough...

[tassoskat]

Shouldn't :
MAX_X = len(matrix[y]) # for the case that all raws are not the same length as the 0 row?

Also I think that at:
if x < MAX_X - 1: # It should be <=
ns.append((y, x+1))

Please let me know.
Thanks

[mrblock]

I've got a long way to go😂 at least I understand the logic, just need to burn it into my brain.

[meethamin]

hey, i wrote my code on pycharm and then pasted it on algoexpert but it is'nt running got an error!!!

[gaurishagrawal]

Is it still okay if for my solution I did something similar to flood-fill?

[programmingwithjackchew]

it is only me thought that medium is difficult than hard from algoexpert free questions

[puentemanuel]

Isn't checking previous row and previous column a waste of time? I did it with recursion and saving a "tested" matrix so that I don't test the same starting point twice.
Here is the code just in case. Maybe I'm missing something.

def riverSizes(input):
global n
global m
n=len(input)
m=len(input[0])
result=[]
tested=numpy.zeros(shape=(n, m))
for i in range(0, n):
for j in range(0, m):
if tested[i][j]==0:
if input[i][j]==1:
riversize=1
[tested, riversize]=helper(input, tested, i, j, riversize)
result.append(riversize)
return result



def helper(input, tested, i, j, riversize):
tested[i][j]=1
if i<(n-1):
if input[i+1][j]==1:
riversize+=1
[tested, riversize]=helper(input, tested, i+1, j, riversize)
if j<(m-1):
if input[i][j+1]==1:
riversize+=1
[tested, riversize]=helper(input, tested, i, j+1, riversize)
return [tested, riversize]