Medium Google Coding Interview With Ben Awad
HTML-код
- Опубликовано: 9 июн 2021
- In this video, I conduct a medium-difficulty Google coding interview with Ben Awad, a software engineer and tech RUclipsr. As a Google Software Engineer, I interviewed dozens of candidates. This is an intermediate coding interview that you could get at Google or any other big tech company.
Want to see me get interviewed by Ben Awad? Check out the intermediate React interview video that we did on his channel: • Intermediate React.js ...
AlgoExpert: www.algoexpert.io/clem
SystemsExpert: www.systemsexpert.io/clem
MLExpert: www.algoexpert.io/ml
My LinkedIn: / clementmihailescu
My Instagram: / clement_mihailescu
My Twitter: / clemmihai
Prepping for coding interviews or systems design interviews? Practice with hundreds of video explanations of popular interview questions and a full-fledged coding workspace on AlgoExpert - www.algoexpert.io - and use the promo code "clem" for a discount on the platform! 
Наука
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! ruclips.net/video/6s0OVdoo4Q4/видео.html
PLEASE DO!!!!
sure 👀
Yes
Absolutely! Por favor!
Yes.
I should stick to inverting binary trees
Time to go back to your root(s)
Thank you for you positive, it was very pleased to watch this video.
Lmao
You did ok
Yesterday I was taking Facebook screening interview and they want you to solve this FAST
There’s something about seeing people being nervous for a mock interview like this that’s so satisfying
😂Loving to witness other people's misery, huh?
@@clem Yeah, I just hope my future interviewers are not seeing this comment 🤫
coding while the whole world is watching your competency and you are in position to prove it. Nah I would rather prefer real interviews.
Sadist😂😂
ruclips.net/video/xLGz4qU_0bA/видео.html
Me after 5 minutes: I don't think I am made for this
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
*le Clement after seeing this
"...and how to make sure that never happens to you,,, ALGOEXPERT"
@@anonymousasdoasidjasd9911 Best comment. lol
Don't worry the guy getting interviewed isn't either.
@@gujeffrey5433 For real. It's hard to stay motivated when interview coding questions are so contrived.
Always love how Ben Awad deduces his problems. 50% Troll 50% Serious
"You know what? I'm being a pleb I think."
He was over-engineering this problem completely.
Donald Duck Coding, is amazing.
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!
Amazing story! Thanks for sharing!
how much was the offer you declined? out of curiosity
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.
Sometimes you just got to man up and work with A-holes.
@@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.
Please keep doing these! This is great and love hearing the thought process
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
^^^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
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
@@ducthinh2412 yup as soon as he showed the question, I knew this was dfs lol
@@ducthinh2412 where you do problems like these ? Gfg, leetcode etc ?
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.
really love this format! so entertaining! very interesting to see "live" how ppl approach a problem
I absolutely love these videos! Do more of these interviews !
Damn, this is a great coding interview question! ;)
I wonder who filmed the video explanation for it on AlgoExpert 👀
@@clem 👀
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.
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!
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.
@@kimgysen10 dont forget actualy coding something thats where you notice a lot of problems and learn how important it is to write clean code
@@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.
@@frankzander6234 right but i'm not sure youre getting his point
@@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.
You guys are just incredible and an inspiration, that helps me keep on learning. Thanks for sharing!!
This is extremely inspiring some how… Well done.
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.
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
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.
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.
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
This is my favorite crossover
Clément seems like a really good interviewer which is hugely helpful.
Wow Clements product has come a long way. So awesome!! Keep up the amazing work buddy.
I could watch this 2 forever lol, amazing, entertaining and learned a lot :)
Well done Ben! Coding when the entire world is watching - it's a nightmare. You're a really brave guy!
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.
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.
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
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 :)
@@razrgu3838 mildly ADHD maybe (i assume)
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.
@@rolfspuler1056 in which company do you work?
This wasn't easy. Good job Ben. Good job coach Clément
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.
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.
Ben laughing when Clement stops him for a second is great cause he knows it's a jank approach.
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
Nice!
That's a smart and out of the box approach.
thats rlly cool approach
So, dfs
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
Love your interview series
This was AWESOME. Thank you!
0:55 That Ben's laugh as Clement promoted AlgoExpert 🤣🤣
ha h a
We waited a lengthy period for this, but it was worth it🙌
I was waiting for this😎🤙
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 )
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!!
Don't give up
This is your 2 week reminder to keep practicing
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.
@@icyrex7893 do you understand it all now?
As a computer scientist with ten years in industry, it was neat but nothing crazy: how is your understanding now?
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. 😉
FYI Clement that Niagara Fall screen saver is nice. 🙂
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.
When you do functions with a single boolean expression, just do return boolean expression rather than if/else.
The "if return True else return False" lines are killing me :)
After getting harassed by teachers all year when someone did this, it also triggers me ^^
@@NirEndal how are you supposed to do it?
@@ButerWarrior44 "return something" with an eventual cast to boolean if it is not a boolean already
@@NirEndal pseudocode please
@@ButerWarrior44
Instead of:
IF condition
THEN RETURN TRUE
ELSE
RETURN FALSE
Use:
RETURN condition
I can't do anything more explicit ^^'
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.
You guys are Awesome! 👏🏻👏🏻👏🏻👏🏻
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'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.
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.
why do you have to set the value to zero in the original matrix
@@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.
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
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
Astonishing interview question!
Really enjoyed it!
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
“I really hope I don’t refactor and just ruin my code even more” - that always happens 😂 34:16
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 :)
😂
I liked the question. Well done, Ben! and Clement, you were very helpful :)
Love this Clem!
Saying I'm not gonna be asked to find max element in an array at my interview
as an ex-Googler, you must interview him in Angular >: )
I think he already did
I tried this one on your website, it was actually suprisingly easy. Basically just a stack based flood fill.
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
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.
I was surprised when the host didn't noticed that
Another solution would be to add the key as a tuple
key[(1,2)] = True
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)
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
This is so cool Clement~! EZ MEDIUM ADVANCE?! XD Thx for a gr8 content!
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).
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
I`s better to use a tuple as a key here
@@user-on1rf1oj9z or a Point
@@user-on1rf1oj9z 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?
I love these data structure problems! Because there's no single unique way to solve them (I do not refer to PvsNP)
These interviews are great for revising topics
I can see an Algo Expert graph-related ad coming :D
Hey Clement! What are your thoughts on quantum computing (Open source or through a provider like AWS)?
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.
exactly what I thought, he should have used tuples as keys
Yep, there must be a separator, like {}:{}
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.
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!
@@clem Did you just call Ben a failure ? 😂
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 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
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.
Ok, do you want us to praise you now?
Love it xd
Ben laughing at his ratings has me dying lol
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
yea thats what I thought too. Going along borders and then recurring along all the 1s will give you the image without the islands
This was so cool to watch!
I love how Ben starts randomly laughing without any apparent reason
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
Same
show your source code to check if it works
I think we can turn the matrix into a graph and check the connected component including "1" if any component does not have any element in the border we can change all the elements into "0"
Basically
We have to go through all the boundary elements and look for the 1 connected with it and change them to 2. Later we will check if element is 2 change it to 1 and element is 1 change it to 0.
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?
Give up
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.
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
Clement is such a good interviewer 👌
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).
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.
I was just going to write a comment about that too 😀
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.
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!
@@clem could also use a tuple of the indices as a key. my world was changed when I learned this was possible.
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
I'm pretty new to programming and I'm using C#, but i managed to solve it by first checking the ones on the border and then creating a new matrix that only had the border ones. Then I went trough every 1 on the border and matched the neighbors with their corresponding value on the first matrix. I put this in a while loop and made it stop running when there had been no changes the last runthrough. (I have not bothered optimising my code)
Do a hard one with Ben Awad
that sounds so wrong
we'll allow him to solve in O(n!) or O(n^n)
This is the reason i hate interviews like this. I could solve this for sure just might take a week
It will come to me while I’m washing my hair in the shower
and this is why you wont work in google
@@damf7106 true, but i already have 6 figure salary, so i am good.
@@archmad you work as a programmer?
I know nothing about coding nor work in the field. However, I did watch the whole thing and found it very interesting.
Thank you guys for honest mock interview!
But not all interviewers are so helpful and eager to hire even when candidate goes in wrong direction at first :)
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 😂
I would go with sets, storing surrounding coordinates too. whole matrix as a set of islands where each has their main land and their surrounding field if it is a 1, by holding the coordinates. Start with set of islands on the border, for each of them iterate over the other sets and merge if overlaps. Iterate while the number of set changes, otherwise terminate. It will result the set of border island coordinates and remain those coordinates which are not connected to border. O(n*m) as the matrix needs to be processed.
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 thought i was bad at problem solving until i saw ben who i thought was pretty good at it being very bad at it
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
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
My approach was to first find and store all locations of 1s in the border. Then create a function tat takes the location of a 1 (i,j) and finds if its a 1 0r a 0 .Then it goes into all 4 possible directions ( maybe lesser if not possible in all 4 ) and sees if there exists a 1 .if 1 den recursion , if 0 stop. It basically will find all the connected ones that exist in the matrix . Then if any point on the matrix where there exists a 1 whose location isnt stored in a 'reference' set , that 1 wil be converted to 0
For every element on inside square recurse search. if it it's boarder send back 1, if after recurse is still 0, "it's an island". Recurse again to pull out / reassemble matrix...