Medium Google Coding Interview With Ben Awad

  Рет қаралды 1,324,732

Clément Mihailescu

Clément Mihailescu

Күн бұрын

Пікірлер: 1 000
@clem
@clem 3 жыл бұрын
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! kzbin.info/www/bejne/bKSTgImapNRnh5Y
@addledanorak8297
@addledanorak8297 3 жыл бұрын
PLEASE DO!!!!
@boundless-sher
@boundless-sher 3 жыл бұрын
sure 👀
@karthik_sama
@karthik_sama 3 жыл бұрын
Yes
@mexicanmax227
@mexicanmax227 3 жыл бұрын
Absolutely! Por favor!
@dinasina3558
@dinasina3558 3 жыл бұрын
Yes.
@bawad
@bawad 3 жыл бұрын
I should stick to inverting binary trees
@crvlwanek
@crvlwanek 3 жыл бұрын
Time to go back to your root(s)
@mkhnuser
@mkhnuser 3 жыл бұрын
Thank you for you positive, it was very pleased to watch this video.
@carlossegura403
@carlossegura403 3 жыл бұрын
Lmao
@dinasina3558
@dinasina3558 3 жыл бұрын
You did ok
@dinasina3558
@dinasina3558 3 жыл бұрын
Yesterday I was taking Facebook screening interview and they want you to solve this FAST
@harispapadopoulos4295
@harispapadopoulos4295 3 жыл бұрын
There’s something about seeing people being nervous for a mock interview like this that’s so satisfying
@clem
@clem 3 жыл бұрын
😂Loving to witness other people's misery, huh?
@harispapadopoulos4295
@harispapadopoulos4295 3 жыл бұрын
@@clem Yeah, I just hope my future interviewers are not seeing this comment 🤫
@karthickshankar1527
@karthickshankar1527 3 жыл бұрын
coding while the whole world is watching your competency and you are in position to prove it. Nah I would rather prefer real interviews.
@aakarshitrekhi8071
@aakarshitrekhi8071 3 жыл бұрын
Sadist😂😂
@mal5256
@mal5256 3 жыл бұрын
A villain in the making😂
@christsciple
@christsciple 3 жыл бұрын
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!
@clem
@clem 3 жыл бұрын
Amazing story! Thanks for sharing!
@joelaucca9081
@joelaucca9081 3 жыл бұрын
how much was the offer you declined? out of curiosity
@humann5682
@humann5682 2 жыл бұрын
Nice! Fintech companies IME can be horrible places to work because many are fundamentally banks/insurance companies at heart with tech departments. You'll be forced to appease some pretty unpleasant people in Fintech and try as they might Fintech just can't get the whole "tech" vibe good companies have.
@Rob-vg6lw
@Rob-vg6lw 2 жыл бұрын
Sometimes you just got to man up and work with A-holes.
@christsciple
@christsciple 2 жыл бұрын
@@Rob-vg6lw I come from a construction and ranching background; worked with plenty of A-holes. Working with A-holes doesn't make you a man. Ethics, love, and principles do. Thankfully I have those, and am now in a much richer and better environment and am in control of my future. Word of advice - whoever told you it's manly to take a miserable job over better options, was incredibly wrong. Sometimes you may have no other option, but when you can afford to take a different job with a more supportive group, do it.
@FrostTechSoftware
@FrostTechSoftware 3 жыл бұрын
Always love how Ben Awad deduces his problems. 50% Troll 50% Serious
@geoffnolan1053
@geoffnolan1053 3 жыл бұрын
"You know what? I'm being a pleb I think."
@VictorZamanian
@VictorZamanian 3 жыл бұрын
He was over-engineering this problem completely.
@VladIDrago
@VladIDrago 2 жыл бұрын
Donald Duck Coding, is amazing.
@cgerman
@cgerman 3 жыл бұрын
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
@ducthinh2412
@ducthinh2412 3 жыл бұрын
^^^THIS. I am nowhere as knowledgable as Ben in technologies that are actually useful on the job, but because I have done many similar problems, it only took me 10 min to code up the solution. I didn't even have to think, my hands just spit out code from muscle memory lol
@lolnoob5015
@lolnoob5015 3 жыл бұрын
Same, came up with a solution within the first 3-5mins because I've been doing these non stop, everyday for the last 4-5 weeks
@amynguy
@amynguy 3 жыл бұрын
@@ducthinh2412 yup as soon as he showed the question, I knew this was dfs lol
@cartoons__for__kids_Hindi
@cartoons__for__kids_Hindi 3 жыл бұрын
@@ducthinh2412 where you do problems like these ? Gfg, leetcode etc ?
@johnpainter367
@johnpainter367 3 жыл бұрын
I'm 17 and I almost always have a solution to leetclde medium or easy level problems in less than a minute. Hard usually needs some testing so that the solution is fast enough.
@changkim8883
@changkim8883 3 жыл бұрын
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
@SomethingSomething1337
@SomethingSomething1337 2 жыл бұрын
Nice!
@JassimBjj
@JassimBjj 2 жыл бұрын
That's a smart and out of the box approach.
@SlimeSlayzMinecraftnMore
@SlimeSlayzMinecraftnMore 2 жыл бұрын
thats rlly cool approach
@IzanBF
@IzanBF 2 жыл бұрын
So, dfs
@sona943
@sona943 2 жыл бұрын
I came up with this too, but went a step further and stored all of the 1's found on the edge in a stack to dfs over all in one go
@alsoSeeb
@alsoSeeb 3 жыл бұрын
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!
@kimgysen10
@kimgysen10 3 жыл бұрын
You'd think that all software developers are building search engines. Lmfao. These coding questions can be solved, but the majority of problems in the software industry revolve around devops and system maintenance. Sometimes building new extensions / microservices / libraries, but these kind of problems only present themselves in my own pet (hobby) projects. Basically you can solve all of these abstract problems and still be a noob by lack of experience. Imo, time is much better spent by studying apis.
@frankzander6234
@frankzander6234 3 жыл бұрын
@@kimgysen10 dont forget actualy coding something thats where you notice a lot of problems and learn how important it is to write clean code
@kimgysen10
@kimgysen10 3 жыл бұрын
@@frankzander6234 For hobby projects yes. Majority of jobs as developer in the corporate world to earn a living requires quite a different skillset. That is in my experience.
@txic.4818
@txic.4818 3 жыл бұрын
@@frankzander6234 right but i'm not sure youre getting his point
@anjanathreya8306
@anjanathreya8306 2 жыл бұрын
@@kimgysen10 I don't think he's trying to progress professionally when he wrote this comment, the progress he's talking about is the progress he's made in how he thinks and his ability to problem solve. The relevancy of the project is none.
@whatsnextforkev
@whatsnextforkev 2 жыл бұрын
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.
@WaqasRants
@WaqasRants 3 жыл бұрын
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.
@razrgu3838
@razrgu3838 2 жыл бұрын
seriously? his thinking was really messy。i had watched some college kid wrote a much more complicated board game in one sit including all the gui code in c without internet access,and almost no bugs. This guy was like without thinking and just try
@agfd5659
@agfd5659 2 жыл бұрын
That was not impressive at all I don't think. It felt to me like early monday morning level of coding, or really nervous level of coding. Maybe if it was me in his place I would do stupid stuff too, but either way, he didn't impress me :)
@kelvinxg6754
@kelvinxg6754 2 жыл бұрын
​@@razrgu3838 mildly ADHD maybe (i assume)
@rolfspuler1056
@rolfspuler1056 2 жыл бұрын
I'm an experienced software developer but I would have definitively not passed that test. These Google interviews are all about algorithms which is something I learned twenty years ago in my studies but in my professional life I hardly ever came across algorithms again. I think this kind of interviews are pretty artificial and to pass them you have to train for it. I'm pretty sure it won't have much to do with your real work you will do.
@varunshrivastava2706
@varunshrivastava2706 2 жыл бұрын
@@rolfspuler1056 in which company do you work?
@MorganBlem
@MorganBlem 2 жыл бұрын
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.
@Lorkwondo1234
@Lorkwondo1234 2 жыл бұрын
why do you have to set the value to zero in the original matrix
@MorganBlem
@MorganBlem 2 жыл бұрын
@@Lorkwondo1234 just helpful to avoid having to keep track of which positions you've visited. Setting to 0 means future function calls that check a cell which has already been visited just return.
@megadeth_9611
@megadeth_9611 2 жыл бұрын
Oof i don't know what is dfs yet, will learn about it and come back 🤠 I was thinking the same approach but didn't knew how to determine if it's on the edge or not. Maybe after knowing dfs i'll know
@noobygames7363
@noobygames7363 Жыл бұрын
Hey this must be very late and I have implemented this in my own java code , what would the time complexity be for this ? I was thinking O(n log(n)) ? But im not sure
@madomation7984
@madomation7984 3 жыл бұрын
I like how both of them interview each other and post the video on same time
@madomation7984
@madomation7984 3 жыл бұрын
Me after 5 minutes: I don't think I am made for this
@salimahmedali9249
@salimahmedali9249 3 жыл бұрын
Trust me. I used to feel the same. Just keep at it, doing harder and harder probs and then you're solving such problems in no time :P
@janehoe531
@janehoe531 3 жыл бұрын
*le Clement after seeing this "...and how to make sure that never happens to you,,, ALGOEXPERT"
@diegovulcan1
@diegovulcan1 3 жыл бұрын
@@anonymousasdoasidjasd9911 Best comment. lol
@gujeffrey5433
@gujeffrey5433 3 жыл бұрын
Don't worry the guy getting interviewed isn't either.
@microapple97
@microapple97 3 жыл бұрын
@@gujeffrey5433 For real. It's hard to stay motivated when interview coding questions are so contrived.
@RushOrbit
@RushOrbit Жыл бұрын
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.
@DavidEspinosa21
@DavidEspinosa21 2 ай бұрын
As someone else pointed out, BFS would have time complexity O(min(N, M)) whereas DFS would have time complexity O(N*M)
@TechWithTim
@TechWithTim 3 жыл бұрын
Damn, this is a great coding interview question! ;)
@clem
@clem 3 жыл бұрын
I wonder who filmed the video explanation for it on AlgoExpert 👀
@mustafaaljanabi4818
@mustafaaljanabi4818 3 жыл бұрын
@@clem 👀
@morenokv
@morenokv 3 жыл бұрын
Please keep doing these! This is great and love hearing the thought process
@goodnightvids
@goodnightvids 2 жыл бұрын
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!!
@pvtryan
@pvtryan 2 жыл бұрын
Don't give up
@pvtryan
@pvtryan 2 жыл бұрын
This is your 2 week reminder to keep practicing
@icyrex7893
@icyrex7893 2 жыл бұрын
Adding on to Ryan’s comment. How is your understanding of the video now? I’m about 75% of the way through Codecademy’s Full Stack development course and I can understand the majority of what’s going on, but still am lost in some places.
@youisstupid2586
@youisstupid2586 Жыл бұрын
@@icyrex7893 do you understand it all now?
@jerodewert8334
@jerodewert8334 7 ай бұрын
As a computer scientist with ten years in industry, it was neat but nothing crazy: how is your understanding now?
@nathannatchevincent
@nathannatchevincent 3 жыл бұрын
Ben laughing when Clement stops him for a second is great cause he knows it's a jank approach.
@mojo_jojo913
@mojo_jojo913 3 жыл бұрын
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)
@TheBenjaminsky
@TheBenjaminsky 3 жыл бұрын
The "if return True else return False" lines are killing me :)
@NirEndal
@NirEndal 3 жыл бұрын
After getting harassed by teachers all year when someone did this, it also triggers me ^^
@ButerWarrior44
@ButerWarrior44 3 жыл бұрын
@@NirEndal how are you supposed to do it?
@NirEndal
@NirEndal 3 жыл бұрын
@@ButerWarrior44 "return something" with an eventual cast to boolean if it is not a boolean already
@ButerWarrior44
@ButerWarrior44 3 жыл бұрын
@@NirEndal pseudocode please
@NirEndal
@NirEndal 3 жыл бұрын
@@ButerWarrior44 Instead of: IF condition THEN RETURN TRUE ELSE RETURN FALSE Use: RETURN condition I can't do anything more explicit ^^'
@szeryk324
@szeryk324 3 жыл бұрын
Well done Ben! Coding when the entire world is watching - it's a nightmare. You're a really brave guy!
@sarthakjain3476
@sarthakjain3476 3 жыл бұрын
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
@nag0074
@nag0074 3 жыл бұрын
Same
@averroes331
@averroes331 2 жыл бұрын
show your source code to check if it works
@_ityadi
@_ityadi 3 жыл бұрын
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.
@mohsenfaghihy7334
@mohsenfaghihy7334 2 жыл бұрын
I was surprised when the host didn't noticed that
@axaxaxaxaxaxax33
@axaxaxaxaxaxax33 2 жыл бұрын
Another solution would be to add the key as a tuple key[(1,2)] = True
@cafin4908
@cafin4908 Жыл бұрын
Simple and straightforward - DFS from each position on the border if its marked as 1 and mark everything in the dfs as 2. Then remove all 1 from the matrix and convert all 2 back into 1. O(n) time O(1) space.
@TheKy01
@TheKy01 3 жыл бұрын
really love this format! so entertaining! very interesting to see "live" how ppl approach a problem
@ninasinthehaus
@ninasinthehaus 2 жыл бұрын
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.
@crvlwanek
@crvlwanek 3 жыл бұрын
This is my favorite crossover
@mahrezjanati3426
@mahrezjanati3426 2 жыл бұрын
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
@aUCLZlstrBh5upnFr7OmhNHag
@aUCLZlstrBh5upnFr7OmhNHag 3 жыл бұрын
as an ex-Googler, you must interview him in Angular >: )
@cartoons__for__kids_Hindi
@cartoons__for__kids_Hindi 3 жыл бұрын
I think he already did
@SkaiCloud562
@SkaiCloud562 2 жыл бұрын
I'm addicted to these mock interview. Thank you for these quality content.
@TheEW
@TheEW 3 жыл бұрын
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.
@siddarthchalla522
@siddarthchalla522 2 жыл бұрын
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 }
@ron-davin
@ron-davin 3 жыл бұрын
0:55 That Ben's laugh as Clement promoted AlgoExpert 🤣🤣
@rohitkumaram
@rohitkumaram 3 жыл бұрын
ha h a
@saran703
@saran703 3 жыл бұрын
Looking forward to solving hard coding challenge with Ben... that would be fun for sure lol
@akshaylalwani6752
@akshaylalwani6752 3 жыл бұрын
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 } }
@wilhelmngoma9009
@wilhelmngoma9009 3 жыл бұрын
This wasn't easy. Good job Ben. Good job coach Clément
@grichl88
@grichl88 2 жыл бұрын
Clément seems like a really good interviewer which is hugely helpful.
@ogbuzzy1974
@ogbuzzy1974 3 жыл бұрын
I absolutely love these videos! Do more of these interviews !
@ghislaincarrier
@ghislaincarrier 3 жыл бұрын
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
@x32gx
@x32gx 3 жыл бұрын
This is extremely inspiring some how… Well done.
@guillaumedeplus7727
@guillaumedeplus7727 3 жыл бұрын
I am posting this solution I thought of before watching the video so I do not know what Ben came up with. My idea is to remove the outer ones that are connected to the edges of the matrix and then subtract the obtained matrix to the original one. To do that, it’s actually not that bad if you’re familiar with percolation problems. Here is the idea : 1. put all the coordinates of the ones that are on the edges in a stack 2. While the stack is not empty : - take the top coordinate out of it (it is removed) - replace 1 by 0 - look at neighbours, if they are ones, add their coordinates in the stack (so at the top, this is important, otherwise you could add two identical coordinates and it would mess up with the algorithm) To make sure you don’t put two identical coordinates, we can add the condition that it is not possible to add a boarder coordinate to the stack. Thanks for this video, I got once again to find about a nice algorithmic problem :)
@guillaumedeplus7727
@guillaumedeplus7727 3 жыл бұрын
Actually, while going over the neighbours, changing the ones to zero and storing their coordinates would prove to be a lot more efficient. Same when storing the egdes coordinates in the stack
@farhan787
@farhan787 3 жыл бұрын
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.
@sorvex9
@sorvex9 2 жыл бұрын
Ok, do you want us to praise you now?
@manishsharma2211
@manishsharma2211 10 ай бұрын
Love it xd
@_das_19
@_das_19 3 ай бұрын
1. do a bfs(x,y) if current (x,y) is equal to 1 2. if up, right, left, down index is zero and up, right, left, down is in side bound then set the current index as 0
@cibureh2684
@cibureh2684 3 жыл бұрын
“I really hope I don’t refactor and just ruin my code even more” - that always happens 😂 34:16
@JJCUBER
@JJCUBER 3 жыл бұрын
I’m just quickly throwing together this solution, so it might not be 100% right, but here we go: - create a recursive function and call it on every cell - return false if current cell is a 0 - return true if cell is on the edge (we know it is 1 at this point so don’t need to check) - set current cell to 0 temporarily - recurse over all 4 cardinal directions and store if any of them return true - set current cell to 1 if the stored value is true, 0 if false - return the stored value I didn’t code this at all and didn’t spend too much time thinking about this, so it might be a bit flawed. Feel free to let me know if it is and I will attempt to correct it.
@JJCUBER
@JJCUBER 3 жыл бұрын
Oh and I came up with this before a solution was coded (as in, I came up with this right after the problem was explained).
@tommike2548
@tommike2548 3 жыл бұрын
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.
@hotharvey2
@hotharvey2 3 жыл бұрын
exactly what I thought, he should have used tuples as keys
@dimabolgov99
@dimabolgov99 3 жыл бұрын
Yep, there must be a separator, like {}:{}
@mamazu1995
@mamazu1995 3 жыл бұрын
Or just use the correct datatype which would be a set. Then you don't have to assign it a value that is never used.
@clem
@clem 3 жыл бұрын
Great catch! As written, Ben's algorithm would indeed fail for some large matrices. We'd have to add a delimiter (like "-" or "|") between the indices in the key to correctly handle this. I've added a test case on AlgoExpert that would have failed Ben's algorithm!
@martinharris4416
@martinharris4416 3 жыл бұрын
@@clem Did you just call Ben a failure ? 😂
@kroax9720
@kroax9720 Ай бұрын
This interview is so co-operative and patient . The interviews which I have experienced are so brutal . They just kick you out once you answer a question wrong or lose interest and complete the interview for the sake of it . I hope I get an interview like theis , surely I will crack a good package ! Hoping for a better day ❤❤
@mannyioi
@mannyioi 2 жыл бұрын
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.
@brands2131
@brands2131 2 жыл бұрын
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.
@chennn958
@chennn958 3 жыл бұрын
Make a hard coding interview one! These two were so good!
@jrajesh11
@jrajesh11 2 жыл бұрын
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.
@loganrussell48
@loganrussell48 3 жыл бұрын
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.
@pabloshi4863
@pabloshi4863 Жыл бұрын
I noticed this right away. Actually I expected Ben would perform much better than this. If I were the interviewer, my opinion on the aspect of the algorithm would be no/weak hire. But he communicates so well, hence overall I'd give a weak hire / hire.
@AntidotAleks
@AntidotAleks Жыл бұрын
Before watching the video tried to make it. I spent, maybe, half an hour on this. I made a copying of the matrix ('result' matrix). with values -1, 0, 1. -1 -> unknown, 0 -> no land, 1 -> land. Edges are copied and the middle is filled with -1. in "while(true)" it goes through every -1 value and checks if there is value 1 on the original matrix at its location and near it on the result matrix then it puts 1 on the result. When the cycle can't put 1's anymore, it breaks from the cycle and replaces all -1's with 0's on the result. There were faster variants, but this one was simple
@1122slickliverpool
@1122slickliverpool 3 жыл бұрын
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. 😉
@1122slickliverpool
@1122slickliverpool 3 жыл бұрын
FYI Clement that Niagara Fall screen saver is nice. 🙂
@xPussySlayerx69420
@xPussySlayerx69420 10 ай бұрын
1. Do DFS starting at all the 1's along the border, set them all to 0's. Be sure to use a visited matrix to avoid duplicate work. 2. Compare every cell of original matrix with matrix from (1), call it X 3. if origina[i][j] == 1 and X[i][j] == 1 then set original[i][j] = 0. All border connected islands will be 0 from (1) so whatever islands remain are the non-border connected islands. 4. return orignal
@archmad
@archmad 3 жыл бұрын
This is the reason i hate interviews like this. I could solve this for sure just might take a week
@brookei7707
@brookei7707 3 жыл бұрын
It will come to me while I’m washing my hair in the shower
@damf7106
@damf7106 3 жыл бұрын
and this is why you wont work in google
@archmad
@archmad 3 жыл бұрын
@@damf7106 true, but i already have 6 figure salary, so i am good.
@damianrecinski7329
@damianrecinski7329 3 жыл бұрын
@@archmad you work as a programmer?
@rybakostis
@rybakostis 2 жыл бұрын
Here would be my approach: Create a set. Walk the perimeter and call explore() function for each cell of the perimeter. The function would add the cell index to the set and call itself on all adjacent cells. If passed cell is 0 or is already in the set, the explore() function will just return. Once it is done, walk the matrix and convert all 1 that are not in set to 0.
@premthapa9959
@premthapa9959 2 жыл бұрын
That is exactly what i did yesterday :-)
@andrewpersaud4144
@andrewpersaud4144 3 жыл бұрын
Saying I'm not gonna be asked to find max element in an array at my interview
@birinhos
@birinhos 3 жыл бұрын
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 )
@anonymoustv8604
@anonymoustv8604 3 жыл бұрын
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
@drewtrades265
@drewtrades265 2 жыл бұрын
Wow Clements product has come a long way. So awesome!! Keep up the amazing work buddy.
@thesnups
@thesnups 3 жыл бұрын
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).
@prakanshmishra9004
@prakanshmishra9004 3 жыл бұрын
Yep, I was thinking about the same thing as soon as he wrote that. The sizes of the matrix in the test cases must have been small enough that there were no such cases. We will need it as soon as we enter two digits. 110 -> 1,10 or 11,0
@СергейБарсуков-н8у
@СергейБарсуков-н8у 3 жыл бұрын
I`s better to use a tuple as a key here
@MorenoGentili
@MorenoGentili 3 жыл бұрын
@@СергейБарсуков-н8у or a Point
@ehsankabirirahani9733
@ehsankabirirahani9733 3 жыл бұрын
@@СергейБарсуков-н8у tuple is an option or just add a dot in between {}{}. "{}.{}".format(i,j). Is there any advantage for string as a key or tuple in terms of hash collision?
@dane2565
@dane2565 3 жыл бұрын
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.
@avonray9147
@avonray9147 3 жыл бұрын
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.
@clem
@clem 3 жыл бұрын
Great catch! As written, Ben's algorithm would indeed fail for some large matrices. We'd have to add a delimiter (like "-" or "|") between the indices in the key to correctly handle this. I've added a test case on AlgoExpert that would have failed Ben's algorithm!
@Hobolover57
@Hobolover57 3 жыл бұрын
@@clem could also use a tuple of the indices as a key. my world was changed when I learned this was possible.
@nc737
@nc737 3 ай бұрын
These matrix problems are the ones that instantly make me nervous in an interview. "reverse rows or cols so the top left quad has the maximum sum... dead"
@robbyoconnor
@robbyoconnor 3 жыл бұрын
When you do functions with a single boolean expression, just do return boolean expression rather than if/else.
@MichikoHoshi
@MichikoHoshi 2 жыл бұрын
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.
@abhishekm3752
@abhishekm3752 3 жыл бұрын
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
@Randoperson45
@Randoperson45 3 жыл бұрын
Obviously itd be better if you had a 4 year CS degree but if you self teach web dev or something and have some college education, its possible to find a job in this field and make pretty dam good money
@sifiso5055
@sifiso5055 3 жыл бұрын
We waited a lengthy period for this, but it was worth it🙌
@rajatsharma7191
@rajatsharma7191 3 жыл бұрын
You guys are just incredible and an inspiration, that helps me keep on learning. Thanks for sharing!!
@sdcair
@sdcair 2 жыл бұрын
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).
@claudiooliveira698
@claudiooliveira698 3 жыл бұрын
I love how Ben starts randomly laughing without any apparent reason
@Tejbad03
@Tejbad03 10 ай бұрын
I'm new to DSA, but this seems simple to me, step 1 - we could just iterate the border of the matrix instead of whole matrix Step 2- if we find one at the border, start dfs/bfs from that point, and mark them visited After this step, all the 1s that are not visited, we can just remove them by doing one simple traversal Please let me know if this approach is right or not
@HaydenDoingThings
@HaydenDoingThings 3 жыл бұрын
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.
@massimoomodei4552
@massimoomodei4552 2 жыл бұрын
It doesn't work with islands that are for example 2x2. Try for example: [[0, 0, 0, 0], [0, 1, 1, 0], [0, 1, 1, 0], [0, 0, 0, 0]]
@pashakhoshkebari2604
@pashakhoshkebari2604 2 жыл бұрын
I am not sure how efficient this solution would be for the first problem but I almost immediately thought of it when I heard the question. Through a nested for loop in a for loop, go through every index of the two D array. If the index has a value of 0, then carry on to the next one. If the index has a value of one, however, check the value of the index above. If it is equal to one, then that means that it is not an island and we can move on to the next one. If the index above doesn't have a value of 1, then check the one to the bottom, then to the left, and finally to the right. If you go through all the attached indices without finding another one, then turn that one into a zero and carry on to the next index. It seems like a very simple solution that may take a bit of time so I am not sure if it is actually good. Another way we can solve this that is similar to the last solution would be to once again through a double for loop go through all the indices except this time if we find a one, then add it's coordinates to a list. Once we go through all the graph, then go through the list one by one and see where the other other 1 are to figure out if the index at hand is an island or not. I am relatively new to computer science but it seems like both solutions would solve in linear time which is good.
@louiswouters71
@louiswouters71 2 жыл бұрын
I think you made an assumption on what an island is and therefore missed the problem statement. An island can be multiple 1s connected together as long as none of those touch the border.
@josephwilliamcosta
@josephwilliamcosta 3 жыл бұрын
This guy is an incredible programmer and his mind is a logic engine.
@dreerable
@dreerable 3 жыл бұрын
@Anna Meredith he meant these lol
@ronpaul9172
@ronpaul9172 3 жыл бұрын
This was AWESOME. Thank you!
@felipe_ai
@felipe_ai 3 жыл бұрын
I could watch this 2 forever lol, amazing, entertaining and learned a lot :)
@user-hs9dc6rm3v
@user-hs9dc6rm3v 3 жыл бұрын
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.
@rghosthero8093
@rghosthero8093 Жыл бұрын
There's a very simple solution Start at every 1 on the edge and do DFS and mark every 1 you visit After doing this go through the matrix and every 1 that was not marked isn't adjacent to an edge and this solution would be O(n*m) which is literally just going through the matrix twice
@fizzyjoecsgo7154
@fizzyjoecsgo7154 3 жыл бұрын
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 :)
@caiodavi9829
@caiodavi9829 11 ай бұрын
😂
@Nerd-code-do9dn
@Nerd-code-do9dn 6 ай бұрын
Best first approach I think it would be to just pass through the each raw one by one and store in auxilary array the positions of 1s in first row and then would just pass through those arrays and check for each array whether the positions are continuous from beginning or the end and for each check whether they are connected to some position of 1 in previous array so that means in first array we dont remove anything later we remove everything that is not connected to upper array or for either of sides so if it doesn't start from 0 in inner array or its not continuous up to len of inner array -1 and for each of those inner taht are not connected we just check whether the previous array have 1 in the same indices. and after we pass and remove the islands from array_of_arrays[1] we store that second row as a new previous array and we continue that way. We also start from the bottom and have the same approach for storing additional one array so that means that auxilary space would be len of inner array * 2. No need to go around I think.
@dflo34
@dflo34 3 жыл бұрын
Ben laughing at his ratings has me dying lol
@diconicabastion5790
@diconicabastion5790 3 жыл бұрын
First, you already know the width and height of the data once it is passed in. So there is ZERO need to check for if you are on the border. Just check the borders. By doing that alone you reduce the work to n. Worst case is every dot is filled. it checks them once. So work only grows proportional to data being checked. The way he does it he's at least 2n+ Also create an array to determine which one you are keeping and not. You can do this in single pass. Assuming you removed the post because it contained a link for the code proof.
@pb9405
@pb9405 3 жыл бұрын
It's funny how ben always just wants to start programming without fully explaining how his algorithm works
@NikhilDhiman
@NikhilDhiman 3 жыл бұрын
Nice problem: My Solution: Run first loop from i=1,j=1 till N-1,M-1 change cell value to 2 [cell value should be 1] if any border is 1 , or left or top value is 2 Now run loop backwards i=N-1, j= M-1 till i=1,j=1 change cell value to 2 [Cell value is 1] if my right or bottom value is 2 Now run loop again and remove all 1 with 0
@eliashasmidul1071
@eliashasmidul1071 3 жыл бұрын
Do a hard one with Ben Awad
@vaibhavchandra5897
@vaibhavchandra5897 3 жыл бұрын
that sounds so wrong
@coolmangame4141
@coolmangame4141 3 жыл бұрын
we'll allow him to solve in O(n!) or O(n^n)
@wanderygbjcxz
@wanderygbjcxz 8 ай бұрын
I love how ben is just so unstoppable, hardcore coding while dude is literally almost saying "you should stop, i don't wanna say it, but this is not what you think it is"
@wanderygbjcxz
@wanderygbjcxz 8 ай бұрын
but i feel him, when I'm nervous, i also kinda really wanna prove that I'm right, and don't wanna do something else
@stephanejanel3389
@stephanejanel3389 Жыл бұрын
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.
@nik_nsk
@nik_nsk Жыл бұрын
I was just going to write a comment about that too 😀
@BekBrace
@BekBrace 3 жыл бұрын
Great coding interview ! Brilliant stuff, Clément !
@grantmartin2002
@grantmartin2002 3 жыл бұрын
Bro that's super interesting that Ben awad does the same steps trick at 23:35 when dealing with 2d matrices as I do. When needing to check all directions (including diagonal), I usually make a couple for loops to make the directions for me so i dont even have to hard code it. Explanation: Lets say we want to check in all directions (up, down, left, right, upright, downleft, upleft, downright) When we want go up, row changes by -1, and col doesnt change. When we wanna go down, row changes by +1, and col doesnt change. When we wanna go left, row doesnt change but col goes down by 1. etc etc. So, in the format [rowchange, colchange], the ways each direction changes the coordinates is: up: [-1, 0] down: [1, 0] left: [0, -1] right: [0, 1] upright: [-1, 1] downleft: [1, -1] upleft: [-1, -1] downright: [1, 1] This is actually every pair combination of -1, 0, and 1, not including [0, 0] (obviously because 0,0 is no change at all) So instead of hardcoding this, you can just make the combinations in python like so: for rChange in range(-1, 2): for cChange in range(-1, 2): if not (rChange is 0 and cChange is 0): new_row_coord = row_coord + rChange new_col_coord = col_coord + cChange #now do whatever u want with the new coordinates
@yasinnkhann
@yasinnkhann 2 жыл бұрын
is there an official name to this method that I can look up in greater detail?
@matdatN1gg4
@matdatN1gg4 3 жыл бұрын
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.
@cpop6344
@cpop6344 3 жыл бұрын
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 😂
@gJonii
@gJonii 2 жыл бұрын
fuuu, the first question seemed really fun and I immediately got a neat idea, but can't try it in code because not near a computer :( You can create shadow matrix that has same dimensions as input, with all cells initialized with 0. Then, each cell adjacent of edge gets turned into 1 if they're 1 in original image. Then, you take a cells that have 1 in shadow image, and recursively pick their neighbors. If the neighbor is 1 in shadow image, stop. If neighbor is -1 in shadow image, continue. If neighbor is 1 in original, paint shadow image 1. If neighbor is 0 in original, paint it 0 in shadow image and stop. If you didn't stop, apply same logic to all the neighbors this cell sees.
@mexicanmax227
@mexicanmax227 3 жыл бұрын
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?
@Zeegoner
@Zeegoner 3 жыл бұрын
Give up
@mexicanmax227
@mexicanmax227 3 жыл бұрын
I’m currently learning JavaScript and html/css real quick. Picking up some best practices in general (code for scalability and multi-application use, and keep it organized. Also learning that extensions are also best practice (really fun 😂) and help speed up the coding/learning processes/efficiency process. Also I think green text (don’t know what it’s called yet) is good for organizing your code and if you ever need to come back to it later.
@Andre-jp4yt
@Andre-jp4yt Жыл бұрын
Seems like he jumps into coding immediately without without even explaining what he will do in a simple pseudo code.
@technologystalker
@technologystalker 3 жыл бұрын
I have a coding competition tomorrow please wish me luck
@nag0074
@nag0074 3 жыл бұрын
What happened?
@technologystalker
@technologystalker 3 жыл бұрын
@@nag0074 Task1 was fine it was designing a website ,, task 2 they asked me to build a calculator with JS and HTML ,, I am actually a beginner in JS so my = button was almost "functionless" 😂 I wish I could build websites with python it is way better tbh 😂
@massimoomodei4552
@massimoomodei4552 2 жыл бұрын
There is still a bug in the final solution. The keys used for the dictionary can collide. For example, positions row = 11, col = 1 and row = 1, col = 11 (and many others) are mapped to the same string '111'. That would cause weird results and would be hard to debug. Using a template like '{},{}' or using a tuple (row, col) as key would solve the issue
@nonconsensualopinion
@nonconsensualopinion 2 жыл бұрын
Could also create a string key with a separator like row + " : " + column. This string is easily hashable. Some languages make hashing collections difficult and this may be the best option.
@massimoomodei4552
@massimoomodei4552 2 жыл бұрын
@@nonconsensualopinion It's what I proposed with the template '{},{}'. I used the comma as separator
@Kayzewolf
@Kayzewolf 3 жыл бұрын
I suck at coding interviews. Have done a few of them and it's just getting too into your head (focusing on stuff that isn't important yet) and wanting to just solve it on your own instead of vocalizing it. Something I struggle with and likely will not get over cause it's a personality thing. But that's fine cause I'm okay with my hybrid Design/UX Engineer skills instead of going full on frontend, tbh.
@microapple97
@microapple97 3 жыл бұрын
Talking to yourself out loud is helpful
@pavanpspk732
@pavanpspk732 2 жыл бұрын
Adding two values in matrix may solve the problem; for eg 0+0:False condition, 0+1 True condition If TRUE check whether 1 is edge if edge leave else remove. This is as per my understanding
@pavanpspk732
@pavanpspk732 2 жыл бұрын
I am not a programmer just sharing my logic, correct me if I am wrong
Easy Google Coding Interview With Ben Awad
28:00
Clément Mihailescu
Рет қаралды 1 МЛН
Google Coding Interview With A High School Student
57:24
Clément Mihailescu
Рет қаралды 4,1 МЛН
啊?就这么水灵灵的穿上了?
00:18
一航1
Рет қаралды 106 МЛН
Friends make memories together part 2  | Trà Đặng #short #bestfriend #bff #tiktok
00:18
When mom gets home, but you're in rollerblades.
00:40
Daniel LaBelle
Рет қаралды 110 МЛН
I Solved 1583 Leetcode Questions  Here's What I Learned
20:37
ThePrimeTime
Рет қаралды 708 М.
Google Coding Interview With A Facebook Software Engineer
49:59
Clément Mihailescu
Рет қаралды 942 М.
Why I Fail Candidates During Google Interviews.
5:40
Alex Nguyen
Рет қаралды 131 М.
How to Get a Developer Job - Even in This Economy [Full Course]
3:59:46
freeCodeCamp.org
Рет қаралды 3 МЛН
Winning Google Kickstart Round A 2020 + Facecam
17:10
William Lin (tmwilliamlin168)
Рет қаралды 9 МЛН
Most Tech Interview Prep is GARBAGE. (From a Principal Engineer at Amazon)
12:57
React Coding Interview Ft. Clément Mihailescu
47:08
Conner Ardman
Рет қаралды 133 М.
How I Failed the Google Coding Interview (and lessons I learned)
14:24
Software Engineering Job Interview - Full Mock Interview
1:14:29
freeCodeCamp.org
Рет қаралды 1,5 МЛН
I Asked Googlers How To Get Hired
9:44
Namanh Kapur
Рет қаралды 1,6 МЛН
啊?就这么水灵灵的穿上了?
00:18
一航1
Рет қаралды 106 МЛН