Google Coding Interview With A Normal Software Engineer
HTML-код
- Опубликовано: 9 сен 2024
- In this video, I conduct a mock Google coding interview with a normal software engineer, Keerti Purswani, who's a software developer based in India. As a Google Software Engineer, I interviewed dozens of candidates. This is exactly the type of coding interview that you would get at Google or any other big tech company.
Check out the other Google coding interview that we filmed on Keerti's channel: • Google Coding Intervie...
AlgoExpert: www.algoexpert...
SystemsExpert: www.systemsexp...
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!
“Google Coding Interview With A __________” - what should the next one be? And be sure to check out the other Google coding interview that we filmed on Keerti’s channel here: ruclips.net/video/JHzX-57dgn0/видео.html
myself.
Current google employee
Do more design please, the one you did was awesome
you said google coding interview 16 times from what I counted
The next one will be Traversy Media
Acording to Mr. RUclipsr, there is a Google Software engineer, a Facebook Software engineer, and a normal Software engineer
These are some weird pokemon types, man
I'm dead🤣🤣🤣🤣🤣
LMAO so true
Yeah, idk why this is making me sad
If you not FAANG, you ain’t gang
Is someone still considered "normal" when they have a channel dedicated to soliving algorithmic problems similar to the style asked in Google interviews. Isn't a normal software engineer someone who works as an engineer, probably knows commonly used languages/frameworks but hasn't spent any time working on these types of problems. For example they might be an excellent full stack web developer with experience in React, Vue, Node and Spring but not know how to traverse binary trees because that has never been required in their job.
there's my man...the true normal/average software engineer 😉. Most of the people fall in this range...and feel insecure about not knowing competitive programming or cloud computing or AI and what not. Unfortunate.
In Silicon Valley, not Craigs-list level
@@BcomingHIM most normal software engineers won't even know what the term competitive programming really means.
You’re right-don’t worry about the classifications he uses
I think that the average professional computer programmer is expert at browsing StackOverflow. That should be the skill tested in job interview. Here are some examples:
1. Should Dihydrogen Monoxide be banned?
2. Is filtered water safe to drink?
3. What is the proper way to use GOTO?
But my favorite interview question is:
Are you Mensa? :p
If this is already a normal engineer, I don't know what kind of engineer already I am. Maybe abnormal?
Just curious , are you a his paying software engineer. I am a college student these kind of interviews creep me out
@@vetrit1820 yes i am engineer with 6 year experience
Ffs I'm a fresher in computer and Communications engineering. These interviews make me so nervous. Idek why.
Software engineering is competitive. Get into data science or cloud.
@@varunmanjunath6204 even data science or cloud is competitive, for everything in IT,if I'm right you need to be good at problem solving
Not me being nervous when I'm not even the one being interviewed😭
"Does that sound fine?" - That's all i understood.
Heya I am here to explore from scratch and I am watching this nightmare!!! Omg should I lose my interest here 😌
@@nastudio405 Maybe not.
You guys have not watched it properly. It is not that difficult. It was doable if you let go of pre cognitive bias.
At this rate "Google interview with a garbage can" might be more relatable to me
Imagine the satisfaction and fulfilment once you actually get to this level though 😲
@@aleksandartomic9048 feels so far away
@@ChristianFure I wouldn’t put myself down about that, there’s no rush, even if it takes you 10 years to become a very proficient engineer, it would still pay off in the end when you start solving massive problems and teaching others. For the record I’m not a software engineer I’m just someone who has recently started learning to code and am trying to have a positive mindset because personally if I stress, I freeze and slow myself down.
Learn algorithms and discrete maths too
lmao my man
I realized I don't even reach a Normal Software Engineer level
Same pinch
You are likely both fine, I have been in industry for 10 years, problems like these are quite rare in reality and we solve it over hours.
what about now? did you reach that level?
Imo a normal software engineer is one that hasn't touched algorithms in the last X years and don't remember to do anything similar to this. I was expecting something like that.
😂
Normal software developers just use different languages, tools and frameworks to solve a given problem. They don't really need to implement any fancy algorithms in their day to day work. They just need to know how to use data structures effectively, at least that is my experience in the industry.
Exactly. I have 11 years experience in software and there's no way I would've solved this in the allotted time. In fact I probably would've melted. I've built out multi-million pound applications from scratch though. I haven't touched low level algorithms and data structures in many, many years. I would need to practice them again if I was ever deranged enough to want to work for FAANG.
@@Jamie-kf2vf so after 11 years of experience are u still looking want to be a sw developer, coz i thought that i would be at the manager level after 10 years ?
@@ab123232 I've helped build a startup and I'm currently founding a new one so I'm building the MVP. The manager thing is unusual because I've done for it a short while but prefer to engineer the application myself (ideally with a team if there's resources).
It's true that the longer you work as an engineer, the further removed you become from the underlying algorithms and data structures. Frameworks and tools etc provide abstractions over these, so even easy coding interview exercises can be difficult if you're not familiar with the concepts any more. The question is SHOULD you be familiar with these concepts? Ideally yes, but time is finite and I've never had a job where I've had to reverse a linked list, traverse a binary tree etc and I've worked in many industries (big pharma, fintech, telecoms, real estate). Hell, even 2d arrays haven't made an appearance! It's crazy, but it's the real world and these coding interview questions simply don't reflect that. I'd probably get a basic understanding of them (as I have no interest in applying or working for FAANG) but that's it. I've interviewed people in the past and would never ask anything like these questions. I provided scenarios for the applicant to build incrementally "add a button to do x", "update redux state and show result" etc as they mimic the day-to-day job.
Man it seems difficult for an interviewer as well trying to follow along with someone forming a nebulous idea into a real solution. And this is with an excellent candidate I can imagine how hard it is if you're interviewing me instead
And imagine doing this like 5 times a day. Sounds like a mental nightmare for the interviewer!
It’s not that hard. There’s only so many topics and ways of doing things in computer science - the interviewer is bound to have an idea of whatever solution the candidate is trying to do.
Very good point!
@@stewartzayat7526 I give interviews for a startup they can be mentally straining but thankfully you never really do more than 3 a week
The interviewer can simply get silent and nod 😂😂😂
As a former Facebook, Google, Amazon tech lead, millionaire *sarcasm*..... I didn't even understand the question. "Google coding interview with a rock" would be up my alley
😄
I just look at them and ask: "Are you even qualified to be asking me this question?" 🤔
Lmao _this_ comment wasn't the one the world deserved, but it was the one it needed 😂😂😂
I'm officially changing my major to business.....
It looks intimidating for sure. But your school should prepare you no? My school has programs and internships to help with this stuff
@@BondJFK how and where did you prepare for this?
@@BondJFK but you need correct way of how to prepare
@@BondJFK How did you prepare?
I honestly thought the questions would’ve been harder. I came up w a different solution tho w plenty of room for tweaks and optimizations
I'm storing these interviews for the future, at this time they are way above my reach 😂
Same here 😂😂😁
Same here
"storying" I'm sure you meant storing...
same hereee
😅
"she's not a Olympic competitive programmer, not a one who has won medals..." hold up,,, that's a lot of damage
why wtf . why do u think every programer have to won medals ?
@@andreycuy6541 *win
@@janehoe531 lol. Flushing out with this mistake correction instead of answering. What a pure personality.
@@janehoe531 if you are correcting people. At least correct completely and properly.
Why? Do you think that every programmer has to have won medals?
Why do you think that every programmer has to win medals?
Why do you think that every programmer has to have won medals?
Why do you think that all programmers have to have won medals?
Why do you think that all programmers have to win medals?
No one likes a person who shows off limited knowledge.
@@stsinner05 autocorrectExpert!? @clement
Definitely slightly harder than the interviews I did for SWE internships since this is (presumably) for a full-time role, but Keerti solved it amazingly!
The
Actually, I find this technical interview much easier than the ones in (let's say) somewhat big, mid, and not-so-big companies in the CIS area. They all ask questions from the university textbooks. Here I see that the really important things are tested like problem-solving and communication. I always (apparently for absolutely no reason) thought that big companies hire only the absolute monster super coders, which I'm not yet. But now I realize that it's not the case and I even might try landing a job somewhere "big". These videos let me understand that you don't have to be an all-around beast to be just the right person for the position at Google for example.
TBH I found These questions like a piece of cake but still unable to get a job 🙃
It's one of the easiest I've ever seen
Wow, this question is the one that made me fail the Google interviews a couple of years ago, it was a weird flashback seeing it again!
i dont get why people have so struggle with it the solutions are kinda easy... i had like 10min to solve it in an more efficient way wtf
@@sniGGandBaShoR are ex tech lead 😁
Google coding interview with Tech Lead. That would be fun.
I think they have put their conflicts to rest but don't want to be involved with each other anymore
Tech lead is a sad guy
A millionaire interviews a millionaire
He will say "as a millionaire, I will do..." Every time
That’d probably bust his myth.
Kudos to Keerti. It takes guts to take a coding interview, let alone publishing video of it for all to see.
It was a painful reminder of how broken technical interviews are.
Most engineers, especially ones far removed from college, would struggle with this problem.
My one critique/takeaway, and I'll phrase it in a positive light:
- Ask high quality clarifying questions as early as possible; and
- Use that early opportunity to put your interviewer at ease about heading in the right direction, before coding (pseudo or otherwise).
For example, I would've asked early on "the problem might have more than one solution, do I only return the first one or return them all?"
Again, it's so sad that excellent engineers who "just get s&*t done" would likely fail to adequately answer this question.
If anything, Engineers who display good attitudes while attempting to solve these problems should be considered a pass.
Interesting how you say this, does it depend on the company, or is "just getting shit done" not ever the attitude to show? Coming from all the testing in American education, I'm used to going for speed in most assessments.
It's not broken. It's just you can't work for it. Accept your failures rather than crying about it
@@farazahmed7people with the attitude you have are like a blessing and a curse. On one hand, it’s a benefit to be brutally honest with yourself sometimes so that one can “get shit done”. But I hope you can take what you dish out. On the other hand, it shows that the world is designed to constantly try and tear you down and rip your dreams apart.
I willingly opt to encourage people despite how I might feel about their shortcomings, because there are enough of people like you trying to be “honest”.
@@yougetonthathorseyougottar6126it's not that deep
@@Josuke217 depends on your perspective. this is mine.
For the first one, this as a simple sliding window problem. The question is essentially “What is the smallest sub-array that contains a value of ‘true’ for each requirement? Return the midpoint of that sub-array.” A variable size sliding window algorithm solves this with time O(n) and space O(k), with k being the requirements size.
For those unfamiliar with the algorithm:
Store two positions - left and right (both ints, start at 0). Create a map where we will store the amount of “true” values we’ve seen as we go across. Look at the right position and, for each requirement, add the requirement as a key and the index’s bool cast to an int as the value into the map. If any of the requirements are still zero, increment the right position and add that new index’s values to the map. Continue incrementing the right position until every requirement is greater than 0. If that distance is a better solution than you’ve seen, store it. Shrink the window by incrementing the left position, subtracting the values of the position you just cut out. Keep going until you have a zero. If the last distance to have non-zero’s is better than what you’ve found, store it. Go back and repeat the whole process until the right position hits the end.
Much clever way, but still got a O(n) time complexity though.
I am not sure I got it. Can you explain in a little bit more detail ?
I coded the following solution: 1) maintaining the map for list of indexes where each of the required building is placed so eg map mp;// where key could be "office" or "gym" and vector would contain the list of the blocks where the specific building appears. this loop will take me o(block array size*req array size) also the vector list would be in pre sorted order 2) I would look through each block and then loop through each requirement then I would do a binary search to find the nearest index where this required building appears and store max_idx (maximum of all of the nearest indexes where the required building is found) and min_idx(minimum of all the nearest indexes where the required building is found) and my result would be max(result,max_idx-min_idx+1) such that I would be then return result. the time complexity for this one o(block array size*req array size* log(req array size)).
If I ever receive this type of interview, I'll just shut my computer midway in the interview.
you're hired!
The questions r hard ngl
OMG Keerti in Clement's channel! 😱😱😱
She was my senior in college and I got super excited to see her in Clement's thumbnail. Yet to watch the full video! 😅😄
Which clg bro?
@@vaalarivanvaalariva1388 Algo Expert io
@@shaf8200lolololol bruh 😂
@@shaf8200 nani??😂😂
@@vaalarivanvaalariva1388 NIT calicut.
The first question seems really good, would be really helpful if anyone can provide the link to the actual question with all the test cases and constraints!
Literally No One:
Not even Google:
Clement: Google coding interview
lmfao
🤣😂🤣😂
Life is too short for coding interviews.
If you really enjoy doing them, okay, do it. But if you hate them, there are plenty of other nice jobs and options, just because FAANG decided that this is the way software engineers are measured doesn't mean this is truly reflecting your skills and abilities.
So tell us, what other methods are there???? 🙃🙂🙃🙂
@@nishantverma9169 Development, Android , IOS, Web, that's what I know. Other trendy things I have heard of are , Machine learning, Data Science, AI, Blockchain.
So true 🥲
@@BondJFK in my company you just need to know how to build sand castles with bucket and sand shovel. And we are top Forbes 500. All depends on your company.
Seriously this shit is so stupid. Why can't I just go back to google and find the applicable algorithm I learned and forgot about in college
Just here for a reminder that your probability of getting hit by an algo-expert ad on RUclips is higher than getting yourself a gf .
Damn, truth hurts 😂
@@sakandchoudhary2941facts tho
Clement : Normal SWE
Me : Hug...all SWEs are legends!!
She tries her best, I also learn a lot of things from this interview.
She's also a cutie 😍
@@steelsteez6118 when first he said kirti, I heard cutie 🤣🤣🤣😂😂😂
Waiting for an interview with a psycho software engineer, that'll be fun.
😅
XD
"So how I would approach this problem is to repeatedly punch my monitor and type the word SOLVE until I got fired."
😂
I'd love to see you do one of these interviews with a software developer/full-stack developer that is good with frameworks like React, Vue, Angular, Node, Spring, .Net, etc... but doesn't really see these kind of 'google' problems at their job. That seems like more of a regular software engineer to me at least.
Have you not seen Clement’s two Ben Awad interviews?
lol most likely google engineers themselves don't see these kind of problems in their jobs. Software development is an artform which is so much more than just spamming the most optimal solution in a pressured 45 minute time period.
I'm that normal fullstack developer, I can't even answer language feature questions. 😂😅
Interview questions like this are a painful reminder that underlying knowledge for problem solving is required. The first question in particular if the candidate can think of the problem in a assumptions based approach, it becomes much easier to solve.
There will be an assumption that "true" = 1, and "false" = 0, and there can be a second assumption made the number of elements in the array will match the requirements. (3 requirements will mean there is 3 elements per block), and with these we can break it down to a pretty simple solution.
Fetch the number of requirements from the list and it will be represented as an integer. Take the total amount of indexes in the array, and divide them by the requirements (e.g. 12 elements and 3 requirements will be 12/3 resulting in 4 blocks).
A third assumption can be made that the requirements and array indexes will match each other in their order set.
Knowing this, initialise a loop e.g. (for the total number in the list, when an index of (the maximum number (4) is hit), take the total sum, and assign it to a unique counter in a subloop increment the loop by one, till the maximum number (4) counters are present.
Once you've broken it down this far, the solution becomes relatively straightforward to solve as you have everything you need. Simply loop the for each element in the index with the counter, and output the result (e.g. "counter1 = 2, counter2 = 1, counter3=3, counter 4=0").
You now have the result per block in the array, meaning to find the smallest distance of each block, simply find the lowest integer of each counter. Now to find the smallest possible distance out the entire array, you will take the smallest counter, with whichever index (in a -1/+1 iteration) is the next smallest index from each other, you've now got the shortest possible distance.
Alternatively for those curious these types of questions are excellent for parallelism. We can take the same approach and stream each block to calculate it's minimum, then apply the last approach, skipping the need for 40 different loops.
@@anikets4699 I get that man same here 😂
whenever I think I have seen everything in my life, youtube is waiting to suggest me a video.
Imagine replying to a interviewer that I don't know how to do it lol
Actually thats what you should do if you truly have no idea. Thats the way real interviews work, to show people that you might not know everything under the sun but you are ready to learn and grow. And all good companies or boards don’t want a robot, of course u have to be skilled but u dont have to be perfect
For your information , she shares her knowledge in her RUclips channel which help people to crack interviews in companies like Google, Walmart etc
I'm using these videos to prepare for any future coding interviews I get, and for the most part it's been helpful in learning some strategies for problem solving, but man it's difficult to follow the logic here. Nothing really gets explained and it hurts.
I think it's better to fix problems on leetcode one by one for diving into these algorithm details. As to this video, it works better for those person who just want to know what the real interview feel like.
I came up with a video to help people understand more deeply what is going on:
ruclips.net/video/fvCPTW5cgQk/видео.html
This question was nearly never ending.... There goes my selfconfidence
5 mins of thinking: Sliding window works. Here's how it work: [left, right] be the minimum length includes all reqs, then left++,find smallest right include all reqs again, repeat this procedure. Every window you find is the candidates, just find the window with smallest length and the middle block should be the answer. I give this question medium level.
we may settal in the middle of the window. say, window=[gym, empty, settal here, school, market]
yeah I was surprised the dynamic programming was used here.
A normal software engineer is a stackoverflow expert. This person is beyond normal.
I bled in my Google interviews, the questions were so harsh.. I wish life was so easy 😭😭😭
:(
Harsh?
The easiest question I had in my interview involved 2D DP in a DAG after topologically sorting it.
@@miscEngineer how did you become better, I recently started coding.
@@andrerhea4168 I practiced on leetcode and participated in leetcode contests
so hard to follow, what makes a great engineer is making it easy to understand.
Honestly I watched the first 5 minutes and went for a brute force immediately. Dynamic programming is fine and I suppose at google I would be filtered out because of it, but brute force is easier to grasp *and* less code - add to that, that if I wanted some short optimization (not as fast as DP) one can argue that the task is "ridiculously parallellizable", since the original data (blocks and reqs) are immutable, so you can spit out a thread per block, or max amounts of threads per cpu and re use the threads. But obviously DP is more optimal on an abstract level, we won't know if it is faster in real life terms, until one measures it. Pseudo code for those interested;
Vector results;
for (block, blockIndex) in blocks {
// first create a map, for each block where we store the distance to nearest requirement, map is a map
req_dist = reqs.map((req_key) => {
if(block[req_key]) return (req_key, 0);
else return (req_key, int.MAX);
});
// For each requirement
for((key, val) in req_dist) {
If(v == 0) continue;
// scan backwards in list
For(j = blockIndex -1; j =>0; j--) {
if(blocks[j][key]) {
val = min(blockIndex - j, val);
Break;
}
}
// scan forwards until found or we have looked further than closest found in other direction
For(j = blockIndex+1; j < blocks.length && j - blockIndex < val; j++) {
if(blocks[j][key]) {
val = min(j - blockIndex, val);
Break;
}
}
}
longest_dist = Int.MIN;
for((requirement, distance) in req_dists) {
longest_dist = max(longest_dist, distance);
}
// each block stores its longest distance to meet all requirements here
Results.push(longest_dist);
}
Some of the pseudo code is redundant here but written for "clarity". I tend to go for these solutions first. Then try others. Sometimes you can be surprised by how brute force is even faster than abstract solutions, depending on scale of course. But the DP solution is better and faster - but if you are going on an interview for the first time, go for what you can do and leave caveats about better solutions.
I had coding interview where I had to solve the problem by explaining it step by step to the interviewer, while he's the one who writes the code. It's really frustrating.
Weird
Feels terrifying 😖
actually makes sense. peer programming is a thing and also businesses needs people that really really can write code and come up with algorithmns and communicate with other people. when you can explain the solution well and precise enough that not only shows technical skill but also softskills which are also high priority usually. also could be a test on whether you could be not only a developer but also a system architect at some point
That seems like a nightmare... Only if the interviewer is a complete idiot, other-wise that's a perfect team if ya'll think alike.
I kinda like watching this being a doctor
She got me so confused that i almost forgot what i was watching...
That's a great interview trick .... If you can't solve it ... CONFUSE the interviewer :)
My solution would have been to have a stack for every requirement, where each stack has the indices of blocks in which that requirement is true. We fill the stacks by iterating in reverse over the blocks. Now iterate over the blocks forward, and maintain for each requirement the index of the last blocks, where that requirement has been true. At every index, for every requirement, the minimum distance is the max of the "last seen true index" and the top of the stack. Take the max over all requirements, and pop the stack when we pass the top index. Minimize over the answer values for each index. Time complexity O(n * m), space complexity O(n * m), where n is number of blocks, and m is number of requirements.
Stop showing your ads to me, I do not want to be a software engineer at Google.
Clement,
Everything is nice and beautiful...
...if not for the fact that SHE is NOT a "normal" engineer. She hosts a somewhat popular RUclips channel where she teaches algorithms, data structures and difficult programming concepts + where she does mock coding interviews.
So... all is good and well, but she doesn't count as an "ordinary" engineer in my book 😉😉
Anyway, cool interview.
Thanks Clement! 🙏
Q1 (I think this is a really good question): To solve this, I started from some simple examples:
Simple case: Suppose reqs.size() = 1. One can choose any block with the reqs[0].
Suppose reqs.size() = 2.
Set X^0 = (x^0_i) is the coordindate of blocks with reqs[0], Set X^1 = (x^1_i) is the coordindates blocks with reqs[1]. When we draw some colored dots on the line, one can see clearly, the goal is to find the minimal distance between the two sets X^0 and X^1(This is a famous topic in discrete math/CS). If the dots are sorted, we just have to walk from top block to bottom block. Cache the block with req0 and block with req 1, update the cache when some block has req0 or req1. ......Well, now, I find out, this can be applied to any number of requirements.
In general, one can even make this problem harder: i.e. thinking of the block are in 2d place, the coordinates (double, double) are given, find the optimal location. Then the question is a computational geometry question.
So I think one of the best way to solve a coding question is to study the cases. Make simple case, generalize your idea, then try a more complex case, generalize idea, continue this circle. One may not solve the problem in an optimal way, but we can definitely do better. At least, as an interviewer, I'd like to see more on critical thinking.:)
yes, dp is overkill here.
Normal Software Engineer?
It's kind of offensive
Why, because you want to feel special?
@@53strat55 What I mean is that, yes, there are several types of developers (in experience). We have for example Junior/Regular/Senior developer. It is not known what this term means. As you say, normal... So she doesn't have much skills?
@@patrykblu838 Well normal is a relative concept. It all depends on a persons skill level so I don't really understand how people get offended by such a statement. I'm nowhere near a developer myself lol btw.
@@53strat55 Thank you for your answer.
I don't think there is a term "normal developer" in our industry. Hence my answer ;)
@@patrykblu838 Makes sense seeming its a relative concept but I understand. It does imply there is some special type of developer, only makes me wonder what that would be according to this channel.
He could have left it out imo, but I was simply wondering why people felt offended by it. Thanks for your explanation.
Have not seen her solution yet but I would
1. loop through and keep a list for each required building at which index it exists O(N)
2. for each index where a building does not exist do a binary search for the closest building on the list. The list would be sorted by index and save the values in another list. o(kNlogN)
3. finally loop thorough the list and find the minimum O(N)
You loop once, then inside, a second loop starting from the current index increments an offset that checks both forwards and backwards in the array simultaneously until each key is found or the distance of any key is greater than the current max.
Damn she rocked it! Dp always scares me :(
it is not hard, it is just about to remember key things of dp
this wasn't dp btw. she just named it that
@@salsaSamuel It's technically DP, because you're using the solution from a previous subset to construct the answer for the current one. That's all DP is, is a fancy name for finding base cases, storing them, and building the solution base-case-up.
I think we should see you do a mock interview- would be interesting!
Assuming in real life num preferences
Dude she's a software engineer at Intuit. I still am in my 3rd year B.Tech, but honestly that is pretty impressive, and not just "Normal" software engineer. But yeah, google still wins.
As a software engineer I don't even waste my time applying with companies that "test" me this way. Solving this "puzzle" is not that hard, but 99.99% of such challenges are never going to be real cases at work. Big companies blackmail poor young developers with their money and names. Arrogance and narcissism through the roof!
The optimal solution for qn 1 is with sliding window. We are looking for the smallest window that meets all the requirements.
And the result that you would store is the mid point between the left and right of the window - as it has the minimum distance
Can u please share me the questions link if you have one or some similar sort of problem ?
@@magesRNTcute yep, mid point of that window.
I think she was suppose to set dp[i][m] to zero again in second set of nested for loops because she would be carrying the previous max value over when the updated could possibly be smaller
No think again she has to carry it
Her algo does not work because in the second iteration (from end to begin), some dp[i][m] have INT_MAX value from the first iteration, so that the max function cannot return something smaller anymore...
I tested her program with the debugger and in the end, the dp[i][m] have these values:
- dp[0][m]: INT_MAX
- dp[1][m]: INT_MAX
- dp[2][m]: INT_MAX
- dp[3][m]: INT_MAX
- dp[4][m]: 2
So clearly, it cannot work and return index 3 as the best solution... I wonder whether Clément did not see the problem or if he didn't want to tell her...
My background is not in software development (about to head down that path), but I have had a great deal of exposure to graph theory. I believe the first problem could be modeled with a complete graph with the blocks as nodes and the edges weighted with distances between them. Then use an algorithm like Kruskal’s to find the minimum-weighted spanning tree connecting the nodes.
If you're going to use greedy technique then, the time complexity will be higher
I'm not very good with algorithms, but my first thought was that this was a graph problem. I started thinking about Shortest Path.
In prims or kruskal one will have to traverse the entire graph I.e we are supposed to include all the blocks in our spanning tree.. That is a bit different and wouldn't work in this case... modified Floyd warshall might have worked in this case I guess
the moment he said shortest distance i thought about graphs and nodes too ngl
ok so how will u calculate distance of each building from the apartment(which is the weight basically) without traversing multiple times?
This is a O(NlogN) solution.
The idea will be, for each building, the requirement with the max distance (left or right) from this building will be the effective time for this building to reach all its requirements. So
1) We find the minimum or shortest distance to reach each requirement( if it is a false) for each requirement in each building
2) We will end up with a dictionary like so
Distances = "building1:[1,0,4], building2: [0,1,3], building3: [0,0,3],
building4: [1,0,1], building5 : [2,0,0] etc
3) Next we find the maximum distance in each building distance array above i.e as explained earlier
MaxDistances = [4,3,3,1,2]
4) Finally, we return the minimum value in MaxDistances i.e 1
The answer will be 1 at index 4, which is building 4.
if a requirement is false, we use binary search across a list of requirements at true, to find the closest requirement at true
seriously after watching this video I realize where I am standing right now way too far. she has done quite well I can imagine how difficult it was to face such a coding interview. But need a lot more practice to achieve such kind of level. Thanks for making such kind of video. At the initial time, I was thinking it's easy to do but when I reached around 11:30 minutes of video things are going over my head. Head off to those people who face such kinds of interviews. I think she is far better.
Thanks Jatinder, I have doubted myself for a long time. You can do much better than you think. You will surprise yourself ✌️✌️😇😇
Kisan Aandolan Zindabad.
@@KeertiPurswani im in my first year of b.tech and im already sh*ttin my pants 😅🙃.
@@patronam9396 wtf is the matter with you??
the amount of time of "google coding interview" is said within the 2 first minutes is crazy.
Just started programming and watching this made me realize I got a long way to go
This was intimidating but I finally solved it with JavaScript after a few hours of trying. Hopefully one day I can get to this level.
This problem is similar to rain water trapped problem of leetcode, we can use montonic stack overall time complexity would be O(n) and space complexity will be O(n). Cheers...
I really like Keerti's approach to this problem. Also, kudos to Clément for taking a moment towards the end to acknowledge that jumping into a second challenge on the same call may not have been the best use of time. A class act from the interviewer and the interviewee.
I think the easiest and best approach ( in my way ) would be to run a euclidean algorithm ( with each need as a feature ) which automatically calculates the distance between every block. Which will return the best route.
The same I was thinking 👍
Thought the same thing
My brain could not process the your sentence
@@d96yt4 wtf bro
Your solution, if I understand it correctly, is suboptimal. It would be O(n^2 * m) time while her solution is O(n + m) time
Someone: are you a software engineer?
Googler: NO! I’m Google engineer.
She is Intuit software engineer whose salaries are similar to Amazon India salaries therefore level of FAANG.
In the first problem just make a binary array with '1' where the requirement = false (!!!) and '0' where it = true, so we'd have
````
1 0 1
0 1 1
0 0 1
1 0 1
1 0 0
````
then make two arrays (for counting upwards and downwards), in which every nonzero number from the above is replaced by itself plus whatever is in the previous row at that same position, but only if there is a zero somewhere in one of the previous rows because if there isn't, replace with -1:
````
-1 0 -1
0 1 -1
0 0 -1
1 0 -1
2 0 0
````
and
````
1 0 4
0 1 3
0 0 2
-1 0 1
-1 0 0
````
Then replace the '-1' with the corresponding element from the other table and for each row calculate the maximum:
````
4
3
2
1
2
```
Now calculate the minimum.
for n=4==>
right iteration (n=0,1,2,3,4)
==> [max 0 max] [0 1 max] [0 0 max] [1 0 max] [2 0 0]
left iteration (done to remove max and get exact distance) (n=4,3,2,1,0)
==> [2 0 0] [1 0 1] [0 0 2] [0 1 3] [1 0 4].
Idea is to add/subtract from previous temp value. Add the sum at each iteration. Find the minimum. N= 4 or 3 or 2 will give equal distance to full fill requirement.
Me: see’s title with google and clement in the same sentence
Also me:clicks automatically 💀
I got to a correct brute force before she did, but hadn't thought of dynamic programming until she mentioned it, which was rather clever :)
Honestly, I was able to think of that O(nnm) brute force approach as well. I have little knowledge of DP. But what she said after that how it became O(nm), I have no idea... suggestions? 😅
While watching this interview I realize the truth that the MNC interview that I attended was too simple. From a 5yr java developer.
We can solve the first problem using sliding window approach. Basically, what we need is the shortest subsequence that has all of the requirements and just put an apartment in the middle of it.
I am 40 and back in school for cs. After watching lots of video on programming jobs and such I believe I may have made a mistake. I don't think I'm half as smart as I need to be.
Hey don't belittle yourself you are good enough. Believe in yourself 😊
There is a bug in first part of interview. While doing right to left traversal that is i=n-2 to 0, she must set if(dp[i][m]==INT_MAX) dp[i][m]=0. Otherwise if dp[i][m] is set to INT_MAX while left to right traversal the following line dp[i][m] = max(dp[i][m], dp[i][j]) won't get updated as it is storing INT_MAX which is highest value already.
Left to right Right to left as per her code
Dry run : // 1 * 0 * * 1 0 4 *
// 2 0 1 * * 0 1 3 *
// 3 0 0 * * 0 0 2 *
// 4 1 0 * * 1 0 1 *
// 5 2 0 0 2 2 0 0 2
As per her code answer will be 5th instead of 4th
Great mock interview. Loved it. Please keep posting more inspiring content.
Clement I think for the level of probably most of the people that subscribe to your channel, a "normal software engineer" would be probably someone who has some experience coding and developing software and starting to learn about algorithms etc. I think a lot of people that look for videos like this fall into that category. The ideal person should not be someone too experienced like this or it defeats the purpose.
she is not only coder she is work on intuite
It is proved, she is "NORMAL software engineer". She is having very poor logic for these questions.I am extremely good at logic. You can have interview with me. I swear google will rush to hire me at any cost!!!
Ideal interview should be like below -
1. This needs to be ensured that candidate has understood question exactly by means of sample input and output scenarios
2. Candidate should be given 15 to 30 minutes for building logic in his mind alone
(no disturbance, no watch, completely alone)
(Candidate generally starts talking immediately after question with partial preparation for logic which he drops after 2 minutes. This makes no sense)
this video is so great, really similar to the real interview.
My am I seeing this when I don't even know what exactly is going onnnnn... 🙄🙄🙄
Maybe in future cauze am a student...
Wouldn't optimal distance solution be to store last index for each location as you go. Once you find all locations, find distance halfway between min and max indexes. Only re-calculate and check against existing distance when you find a new location.
This optimized distance problem can be solved in O(n)x3 => O(n) . One main loop with two independent (non-nested) loops for searching both directions. So O(n)!
keerti explained the approach very beautifully. really liked how she was able to show that dp part that was awesome.
my thoughts :
so when u are going from the right to left what I was thinking is create another dp(dp2). find the max of that block and then compare dp1 and dp2 for min of the block and return the index.
but we don't have to do another loop and compare both dps in keerti's approach so keerti really optimize the program
Or you could just store the max when going back from right to left only!
Clément: (Gives me a question)Imagine ...
Also Clément: Are you following me so far?
Me: (waggles the head)Yes sir
Also me: Pastes the question on Stalk Overflow and waits for the first quick answer to understand what he was saying.
"Normal Software Engineer". Dude she works at Intuit. How is that normal? -_-
Kind of question he asks to his normal software engineer:
Calculate shortest distance between sun, moon and earth and print it on console without using any programming language!
Kind of question he asks to Ben awad:
invert the binary tree!
Facts! Check his Medium coding interview with Ben Awad
Sorry to be nerdy but the "normal" problem may be more difficult than the "invert a tree" one. Your first answer might be to think of an eclipse (Moon is between Earth and Sun) but the orbits are eliptical and also include a wobble.
There is also the question of time. Do you mean now, or any time, what about when the Sun super-novas (at which point it will be zero)? The gravitational pull of other planets may also make the difference of a millimeter here or there if you have two alternatives. There's is the question of which moon. People are still debating how many moons Earth has. Am I over-thinking this? Ha ha
@@littlefluffybushbaby7256 but that's the point of this comment. They obviously meant the former was more difficult than the latter.
@@littlefluffybushbaby7256 Yes. The point is he gave Ben such an easy question 😂
@@marcusaureliusregulus2833 Ah. Got it. Not seen any of these before so wasn't getting the context. I guess I failed the watching a google interview test.
The idea here in my opinion is to find the block that travel no more than 1 from the above/below blocks. Index 3 which is the correct answers, allows you to be between or in the center of the block 2 and block 4 which have at least one of the requirements as true. So you need to travel only one from block 3 to block 4 and at same time you also travel only one from block 3 to block 2. Therefore index 3 is the most optimal choice in order to travel the minimum distance between blocks and meet the requirements. Let’s say if you chose index 2 as the correct answer you gonna travel twice from index 2 to index 4 in order to meet the requirements ( the store is true ). Both index 3 and index 1 which is above/below index 2, have the store as false. Therefore index 2 is not the Optimum choice in order to get to travel at the minimum distance which is 1. I’m very new to coding and I don’t know any programming language to solve this problem technically. I’m just giving my logical solutions to this problem so please correct me if I got anything wrong.
9 mo late, but if i perceive it correctly
If you just check a block with 1 distance to be completed, what if there are block that need 4 distance for gyms and 1 for store, while any other blocks need at least 2 for both.
Or what if there are no block that needs 1 distance.
I'm also not an expert at this, so please correct me too if i'm wrong.
Really enjoyed the mock interview. Hopefully, I have learned some things from it. Keerti does look like has done serious practice with Algorithmic problem-solving.
The first solution is not optimal. It can be done in liniar time. You need to find the shortest interval that contains all the requirements(this can be done in O(n) with two pointers) and then choose the middle of that interval.
how?
How????
Sliding window? We could find the shortest window size that contains all requirements, the the final solution would be the window size over 2
I sense there is iteration needed inside each window, but I might be wrong
Now I have seen that this comment got some replies that I have missed so here is the solution:
For each index i find the index j such that the interval i-j covers all the required buildings and ij is the minimal such interval.
This can be done with sliding window and keeping at each step a set of the visited buildings and updating the set in O(1)
After we have the minimal interval in the array that covers all buildings the smartest thing to do is just to build your house at the middle of that interval.
So if the interval is 1234 you will build your house at 2 and if it is 23456 you will build your house at 4
Hope this is clear.
Please make a seprate playlist that contains all these coding interviews. Sometimes if I get stuck on some question there is nobody to answer those... A discord group would be enough I guess.
First question: A simple binary OR problem.
Each block represents three binary numbers.
1) 010
2) 100
3) 110
4) 010
5) 011
req = 111
Starting with ORing three blocks at a time with the interested block in the middle:
Blocks 1, 2, 3 OR'd together = 110
Blocks 2, 3, 4 OR'd together = 110
Blocks 3, 4, 5 OR'd together = 111
Hi, good approach. I initially had this approach in mind before checking the video for solution. What made me give up on the OR approach is, how would you extrapolate this logic to say, twenty blocks with no nearby gyms or stores? Choosing sets of three would work only because the gym and the store are in adjacent columns, isn't it? What if there is only one gym every five blocks? In that case, all sets of three would return a result of 0 and the solution would be missed. What interests me in the solution Keerthi deduced is how she arrived at it. That's what I wish to learn, if that makes sense. For instance, we tried the OR approach and know it doesn't work. How does one go from there to the solution Keerthi arrived at? Any thoughts?
but the number of rounds will grow exponentially with the number of blocks in q1. think about cases where say there are 100 blocks and the min distance is larger than 10.
This dude really worked at facebook for 3 months and knows it all lmao.
I watched this video for entertainment before and now I am watching it just 2 days before my Google Interview.
so how was it? just curious :) did they ask similar questions?
@@bndissanayaka actually questions depends on the interviewer but the way the interview is conducted is quite similar to this video . They send you a Google meet link and a Google doc link and then the whole interview is on Google doc and the interviewer is very helpful would help you if you are stuck . It's like discussing a problem with someone you know. One of my best interview experience.
@@xanushkasrivastavax hmm! thanks for the reply. I see a lot of negative and discouraging answers and yours made me feel a bit positive.
I'm not a programmer. I did watched this channel last time and it made me headache lol. Somehow, I did finish python for the beginner course about a year ago. After watched this video, I'm also impressed with this Keerti.
just watched the video . now i feel the headache. lol 😂
The first problem can be reframed as finding the smallest window of blocks that consists of all the requirements. The required distance will be half of this window. It's very intuitive for me to solve this using the sliding window approach in O(n*m) time and O(m) space. The two way DP solution also works, but I find it a little convoluted and unnecessary, also it has worse space complexity.
Isn't your proposed solution having a worse time complexity?
The sliding window approach have the time complexity O(n^2), since you'd have to iterate through the blocks at most n times.
The loop:
for n in range(0,len(blocks)):
for m in range(0, len(blocks)-n):
...
is still O(n^2)
The given solution from Keerti has time complexity O(n)
Having a sliding window would require you to fully explore the following sample input:
[1,0,0], // {"gym": True, "school": False, "store": False}
[0,1,0], // {"gym": False, "school": True, "store": False}
[0,1,0], // {"gym": False, "school": True, "store": False}
[0,1,0], // {"gym": False, "school": True, "store": False}
...
[0,1,0], // {"gym": False, "school": True, "store": False}
[0,0,1] // {"gym": False, "school": False, "store": True}
The solution in the video is clearly not O(n). Consider reevaluating.
@@SimonK91 in a sliding window solution each item (block here) is accessed at most twice. Moving the faster pointer to increase the distance when the blocks in the window do not cover all requirements, and moving the slower pointer to decrease the distance when blocks in the window covers all requirements.
It's a shortest path algo problem. We can use bfs on every grid index where an appartment is. Find it's distance to a location that's not 1. Put it in a matrix. After traversing from all the nodes, we can run a mxn for loop to determine which apartment is the closest, that's our answer.
What the time complexity of such solution would be?
Is Keerti helping or hurting herself by not writing that much in the google doc?
this may work I may be wrong so don't get mad
solution goes here :
for each block we can represent each one building as bits like in given eg Block B1(gym,school,store)=010 => '2'
B2(gym,school,store)=100 => '4'
B3(gym,school,store)=110 => '6'
B4(gym,school,store)=010 => '2'
B5(gym,school,store)=011 => '3'
reqs[gym,school,store]=111 => '7'
now for min distance we need to keep on oring for each block on both up and down O(b*r)