So, should we do a hard Google coding interview next? 👀 Be sure to check out the other video that we filmed on Ben’s channel, where he gave me an intermediate React interview! kzfaq.info/get/bejne/bNlggrmV1NWYgWg.html

I should stick to inverting binary trees

There’s something about seeing people being nervous for a mock interview like this that’s so satisfying

Me after 5 minutes: I don't think I am made for this

Always love how Ben Awad deduces his problems. 50% Troll 50% Serious

Watched this the day after you released Clement. During an interview with a fintech startup a week later, they gave me this exact problem. I was able to remember and successfully work through roughly 80% of it. Got offered the job and ultimately rejected their offer because one interviewer who would have been my daily collaborator, was rude and demeaning. All in all, this is great information and a great video you've produced here!

I think this shows that you need to practice specifically for these coding interviews. It doesn't matter if you are a programmer or you can code or if you are smart and you have experience. Ben is all these things. You need to practice problems like these to get a job at a company that does these interviews. It's like preparing for an exam. Even if you do ok like Ben did someone will do better because he spent hours and hours practicing. So many people want to get in these companies that it is very competitive. It's just how it is

Please keep doing these! This is great and love hearing the thought process

Almost two months ago, I started this video but didn't finish it because I wanted to solve this problem for myself. I didn't find a way to do it on my own, and both the problem and the video sat in the back of my mind for weeks. Today, after quite a lot of reading and practice (on other problems!), I returned to the problem with a fresh point of view and solved it in an hour (plus a few minutes), in one sitting, without any outside reference. It's been tough measuring my progress over the last few months, but thanks for giving me a point of reference!

really love this format! so entertaining! very interesting to see "live" how ppl approach a problem

Damn, this is a great coding interview question! ;)

thank you for making these videos! I solved this problem by modifying the grid to have perimeter of 1s (so both len(grid) and len(grid[0]) increase by 2) and running BFS on the grid. After finding an island, all other islands are changed to 0s. Pausing the video after you explain the question and talking out loud "back" to you has been so so helpful.

for the "is_border" and "is_border_matrix" functions, since returning True and False over an If statement is redundant, I would have simply done a one-liner: "return ". That would tell me he's been through a number of code reviews or is part of a larger team. I've done my share of interviewing candidates as a Senior Eng at a huge retail company and even for me, a Google interview is anxiety-inducing.

I absolutely love these videos! Do more of these interviews !

Here's my approach 1. Loop all edges - Only edges 2. If it's 0, then move to next 3. If it's 1, then update to 0 and find adjacent 1 and update to 0 until it can't find adjacent 1 At the end of this loop, you end up with a new matrix where 1s connected to edge is all 0s then finally, you subtract the new matrix from the original. Since all edges and connected cells are turn to 0, you're not changing anything, but the island cells will be 0

I'm addicted to these mock interview. Thank you for these quality content.

I like how both of them interview each other and post the video on same time

You guys are just incredible and an inspiration, that helps me keep on learning. Thanks for sharing!!

Mark all the ones you shouldn’t touch with a different value. You can use DFS to do this. Go over the entire grid at the end, changing the marked cells back to one, the 1s to zero, and the 0s skip.

This is extremely inspiring some how… Well done.

I somehow stumble upon this video and I really enjoyed it. Watching you two talk through the process was very insightful and it made it very easy to comprehend more so than if this was just a tutorial video.

Seeing this level of skill, almost feel as if I am not worth my salt to be in this industry. As someone who does app development for a living, this was overwhelming and quite literally humbling to watch.

I could watch this 2 forever lol, amazing, entertaining and learned a lot :)

Clément seems like a really good interviewer which is hugely helpful.

Well done Ben! Coding when the entire world is watching - it's a nightmare. You're a really brave guy!

Make a hard coding interview one! These two were so good!

Looking forward to solving hard coding challenge with Ben... that would be fun for sure lol

Great coding interview ! Brilliant stuff, Clément !

Store the index of rows and index of columns with ONES in seperated arrays and find the abs distance between indexes. Just drop the 2d-indexes that don't have min abs distance equal to 1. Redraw according to the remaining indexes that represent the Aces after the drop.

Ben laughing when Clement stops him for a second is great cause he knows it's a jank approach.

This wasn't easy. Good job Ben. Good job coach Clément

There is another optimization, you can skip checking every 2nd square. Like a checker board. Because if each square checks the 4 neighbors, then the next neighbor doesn't need to check any neighbors, because the neighbors are already going to check that for it. So if there were all 0's on the board, you could cut the time in half, less so if more 1's, however that's already optimized by skipping islands.

Wow Clements product has come a long way. So awesome!! Keep up the amazing work buddy.

Just wanted to say a nice very fast solution I thought up to this problem: 1) Make a second matrix (we'll call it m2) of the same size filled with zeroes 2) Iterate over the edges of the original matrix. 3) Each time you encounter a 1, do a depth first search. At each visited position, add a 1 to the corresponding position in m2 and then set the value to 0 in the original matrix. 4) Once you've iterated all edges, m2 will contain all islands that connected to the edges, though none that didn't. Return m2.

This is my favorite crossover

This just shows that having too much knowledge can slow you down sometimes. I have a few years of coding experience and the first thing I thought of what the recommended solution, while I didn't know all of the things Ben was talking about.

I'm basically new to code. I am currently learning the very basics of C++. This video is way harder to understand for me but i watched either way. I will rewatch it again in a few years and hopefully my skills are better and i can be able to understand it. Great content!!

The "if return True else return False" lines are killing me :)

0:55 That Ben's laugh as Clement promoted AlgoExpert 🤣🤣

I was waiting for this😎🤙

I honestly can tell Clement enjoy these coding problems. These problems are like math problems to me. There’s multiple ways of doing these, but it’s always fun to find the most optimize solution. 😉

We waited a lengthy period for this, but it was worth it🙌

Love your interview series

This was AWESOME. Thank you!

“I really hope I don’t refactor and just ruin my code even more” - that always happens 😂 34:16

I think there's a problem with the way he's naming the keys such that i = 1, j = 12 for example gives the same key as i = 11, j = 2 when they are two completely different coordinates. I think adding a space in between the i and j would solve this immediately though.

I liked the question. Well done, Ben! and Clement, you were very helpful :)

start from a blank matrix then start a recursive "walking" starting from the boders on the original matrix in all directions (recurssivly) on 1's and if it is valid put 1's on the new matrix (y and y coordinates must be maintained on the recursive process )

Actually u can do it easier with same the same time limit Run a dfs from each cell on the boarder that is 1 and you will mark all connected edges to that cell So basically u will mark all connected components that are connected to the boarder After that u know that each cell that is 1 and unmarked is part of an island (because it doesn't have a path to any boarder)

This has a bug if the dimensions of the matrix have 2 digits. In your border_island dictionaries when you store Row 1, Col 12 and Row 11, Col 2 both of these are going to be represented as {'112', True } which are both same ... you probably should have used tuples to store them ... But I love this.

I value the thought process. The question about how to make sense of the 1 in the second row literally is a eureka moment that his code isnt gonna work. Because he still hasnt done the inner most square. The follow up question was litterally a saving grace lol

get the position of all 1s . for each 1 check the elements at the index(+1 ,-1 , +length, -length(length of row)) till we reach the max length possible and store if it is connected to island. Do this for each 1's and we can exit if we hit 1 which has connected to island flag and remove the 1's which are not in boarder which are position of multiples of row length.

I think there is 1 small bug in the code I see which went unnoticed. The key for border_islands should not just be 'ij' this would not work with double digits. The key should probably have a separator in between i and j. Also, this should be caught by the test cases. Please add more tests Clement.

When you do functions with a single boolean expression, just do return boolean expression rather than if/else.

Astonishing interview question! Really enjoyed it!

Recursively check each index with value 1 the top, left, right, bottom for value of 1 until at border. Return true if 0 at border, false if 1 at border.

Nice and easy if you map it to a bitboard and can use bitwise operators to find your borders and store your islands as ints. Also makes it very fast on large matrices :)

My approach :- do bfs/ dfs from 1s present in first row, last row, first column and Last column and then change all the ones encountered to -1 After BFS/DFS Convert all 1s to 0 and -1 to 1

Below is my solution in js. I don't see anyone suggesting a DP solution so wanted to see if I'm thinking about the problem correct/am missing something. I solved this using DP. 1. One pass from top left to bottom right to mark nodes as "connected" based on whether top/left neighbors are borders/connected 2. One pass from bottom right to top left to mark nodes as "connected" based on whether bottom/right neighbors are borders/connected 3. Nodes marked as "not connected" after both passes are changed to 0 This is O(N*M) time and O(N*M) space but can be reduced to something like O(M) by only storing relevant rows for DP. Code is below: function removeIslands(map){ const isConnected = [] for(let i=0; i= map.length-1) return map[row][col] === 1 if(col === 0 || col >= map[0].length-1) return map[row][col] === 1 // now determine if neighbors are connected if(isConnected[row-1][col]) return true if(isConnected[row+1][col]) return true if(isConnected[row][col-1]) return true if(isConnected[row][col+1]) return true return false }

You guys are Awesome! 👏🏻👏🏻👏🏻👏🏻

Clement I haven't seen the full video but the first problem was literally easy medium-ish. For boundary elements you can just do DFS/BFS and mark the connected elements as connected to the boundary of matrix and then finally iterate the matrix and remove the 1s not connected with the boundary 1 elements. This would be O(rows * columns) time and space complexity. We might optimise the space further.

Did the test cases include matrices with more than 10 rows/columns? I expected the way Ben named the key to cause bugs. For example key "123" is ambiguous as (12, 3) and (1, 23) both map to this key - and that would mess up the visited map logic.

Love this Clem!

I tried this one on your website, it was actually suprisingly easy. Basically just a stack based flood fill.

as an ex-Googler, you must interview him in Angular >: )

Great interview! Really enjoyed this question. I have one question about the code -- shouldn't there be a comma in the key? Like "0,0" instead of "00"? The way the code stands, the key could refer to multiple different coordinates. For example, "2020" could refer to both positions (20,20) and (202,0).

These interviews are great for revising topics

I think the simple solution if not concerned by the storage would be to have a matrix of zeros then loop over the borders. Wheb finding a 1, add its coords to a list and set the 1 in the new matrix. Then find the neighbors recursively (just traverse for the coords not in the list or dict). Then return the new matrix

Hey Clement! What are your thoughts on quantum computing (Open source or through a provider like AWS)?

Saying I'm not gonna be asked to find max element in an array at my interview

the way i would solve this is (i still didn't watch the vid) ... 1:mark all "1"s on the edges 2:go through the matrix from edge to center in a spiral or only horizontally (in c++ it would be for (int i =0; i< n^2) and mark every "1" that is connected to an already marked 1 and also mark every "1" that was connected to it but not marked 3:for loop to delete unmarked "1"s

Islands = copy of input loop on each values in the border of variable islands if value == 1 set it to 0, then recurse on each 4 directions in the recurse, if the value is 1 set it to 0 and recurse 4 directions at the end return intput - islands no need to store and query a separate visited structure

This is the reason i hate interviews like this. I could solve this for sure just might take a week

Clement be like "I don't mean to interrupt you between your thought process, but, ANYWAYS Imma just interrupt you" Lmao, Clement is the best

A Card has 4 attributes (color, count, shading, shape), each attribute can have value 0, 1 or 2. 3 cards are considered as a set if for each attribute, 3 cards either have the same value or have different value from each other. For example: card1 (2, 0, 1, 2), card2 (1, 0, 0, 1) and card3(0, 0, 2, 0) are 1 set. card1(2, 0, 1, 2), card2 (1, 1, 0, 1) and card3(0, 1, 2, 0) are not 1 set. write a boolean function with 3 cards as input. This function returns true if they are 1 set, otherwise returns false. Now given a collection of cards, return true if there is a set of cards exsits, otherwise return false.

Clement is such a good interviewer 👌

Question for Ben and Clément! Can y’all each make a video for best practices in React in front end and best practices in Python for algorithms?

I love how Ben starts randomly laughing without any apparent reason

This is so cool Clement~! EZ MEDIUM ADVANCE?! XD Thx for a gr8 content!

I just solved this on AlgoExpert by myself and came back to this video to get a feel of how this question would've felt in the coding interview

There was a potential issue with the key. The key for the border_islands dictionary was just concatenation of the row & col indices. So, the index (1,21) and index (12,1) for instance will have the same key "121", which may mess up the visited checking for some different test cases.

I have a coding competition tomorrow please wish me luck

This was so cool to watch!

I can see an Algo Expert graph-related ad coming :D

Ben laughing at his ratings has me dying lol

Do a hard one with Ben Awad

I would like to know if there will be a 3rd SWE contest organized by your company? The first one took place almost a year ago around the same time, hence why I'm asking if we to expect a 3rd one to be hold soon

Ezz :) Going to use this question in my next video! Edit: I think it could have been quite fast and short. I used recursions, and the code is pretty small and simple! Clement I like your videos a lot! Would love to see you giving my comment a heart :)

Interesting! However there is a bug in border_island_key function if one of the dimensions of the matrix exceeds 10. The key is ambiguous for (1, 11) & (11, 1) for instance (which both give '111'). Just inserting a space between both indexes will solve the issue.

Immediately after seeing him make the key by concatenating string representations of integers, I knew there would be an issue but sadly the test cases didn't cover it somehow. But basically, if *i* = 1, *j* = 11, the key generated for that is identical to the key generated when *i* = 11, *j* = 1. So basically he has no way to differentiate them, right? steps to generate test case his code will fail: 1. create a 13x13 matrix of zeroes 2. set matrix[1][11]=1 3. set matrix[11][1]=1 4. set matrix[12][1]=1 to connect the previous to the border since the step 3 tile is connected to the border, the key "111" is in the *border_islands* map, and this will prevent the tile at *matrix[1][11]* from properly being set to 0 as it should. if my logic or reasoning is wrong, let me know.

I'd use a bfs by putting all coordinates on the edge that have value 1 into a queue. Then work off the queue, mark each discovered cell (eg. by setting the value to 2), and add neighboring cells with value 1 to the queue. Then just iterate over the matrix and set every 1 to 0, and every 2 to 1. Time complexity O(n * m), extra space complexity O(1).

Maybe a recursive function for outside-in matrix which generates the next inside border using an AND between the current border and the next one would do the trick, at least for "clearing" the islands. To get a "removed islands" matrix would need some more planning though.

I love these data structure problems! Because there's no single unique way to solve them (I do not refer to PvsNP)

Hahaha Clement was being nice to Ben when he said he would be a lean hire and it went to Ben's head so Clement had to stop being nice and just be honest with him 😂

Just my approach to it would be. For (1 to less than length-1){ For(1 to less than length of inside array -1){ Check side ways neighbour and up and down neighbour by -1 +1 on index if it's 1, If all checks prove its island, replace it with 0 } }

for the string formatting thing (using '{}{}'.format(i, j) as a dict key): you can use tuple (i, j) as the dict key as tuples are hashable. No need for a key generator function or that fancy stuff also for your rec() function. you can create a global BORDER_ISLANDS dict and pass this in as a default argument: BORDER_ISLANDS = dict(). # global object def rec(i, j, border_islands=BORDER_ISLANDS): # default arg is this global object and so all recursive calls use the same object you wont need to pass this object around and all functions will use the same single instance of BORDER_ISLANDS.

I dont know why am i here, but i like it. I'm 30 and randomly started liking coding/software development and got reminded of C++ programs i made in school days😂 Can i make money in this field in a year or two if i start today? I m very much tempted

Just throwing an idea out there: For each row, I think I'd identify each one that matches "010" because that means it has no horizontal neighbors. I'd keep it's x,y coords in a horizontal_ones dict. Then, for each column, I'd do the same thing, looking for the same "010" pattern, those of course go into the vertical_ones dict. The overlap, that is, the elements present in both the horizontal_ones and vertical_ones dicts would be islands and be removed. The center part is done now. Now, for the edges, I think I just realized that if you took this grid, maybe it's height and width are 10, if you just put the whole thing in the center of a 12x12 grid of 0s, then you can use the same logic to do the edges. That's not very memory efficient, but it's definitely lazy efficient, because I wouldn't have to write any more logic to deal with the edges.

Thank you guys for honest mock interview!

Improvements that I'm thinking of, but not certain if they'd work. Let me know what you think. 1. Would it be possible to simplify the first nested for-loop to just checking first and last row, and first and last column? Wouldn't that bring the algorithm down to O(n+m)? 2. Would it be possible to assign the 0 in the recursive part to avoid re-traversing the entire matrix, to avoid going to O(n*m)?