Google Coding Interview With A Normal Software Engineer

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: kzbin.info/www/bejne/gHndiWBrbMmapJI
AlgoExpert: www.algoexpert.io/clem
SystemsExpert: www.systemsexpert.io/clem
My LinkedIn: www.linkedin.com/in/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!

[@clem]

“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: kzbin.info/www/bejne/gHndiWBrbMmapJI

[@creationduwal]

myself.

[@samarthparnami]

Current google employee

[@occo5877]

Do more design please, the one you did was awesome

[@vedrathi6592]

you said google coding interview 16 times from what I counted

[@codewithvath7990]

The next one will be Traversy Media

[@Ayoub-adventures]

Acording to Mr. KZbinr, there is a Google Software engineer, a Facebook Software engineer, and a normal Software engineer

[@snowhusk]

These are some weird pokemon types, man

[@averageheightwizard4798]

I'm dead🤣🤣🤣🤣🤣

[@JoanFFF]

LMAO so true

[@AbdulAhad-pj1mj]

Yeah, idk why this is making me sad

[@Doctorchris100]

If you not FAANG, you ain’t gang

[@JohnFarrellDev]

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.

[@pushpakgupta22]

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.

[@troys1426]

In Silicon Valley, not Craigs-list level

[@JohnFarrellDev]

@@pushpakgupta22 most normal software engineers won't even know what the term competitive programming really means.

[@winnumber101]

You’re right-don’t worry about the classifications he uses

[@simpletongeek]

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

[@scottrobinson2284]

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

[@renocarsons9449]

😄

[@GameDevNerd]

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 😂😂😂

[@sunnyg989]

Not me being nervous when I'm not even the one being interviewed😭

[@greentoadboy]

At this rate "Google interview with a garbage can" might be more relatable to me

[@aleksandartomic9048]

Imagine the satisfaction and fulfilment once you actually get to this level though 😲

[@KitchGaming]

@@aleksandartomic9048 feels so far away

[@aleksandartomic9048]

@@KitchGaming 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.

[@alexanderarea6157]

Learn algorithms and discrete maths too

[@kage-musha1702]

lmao my man

[@crjacinro]

If this is already a normal engineer, I don't know what kind of engineer already I am. Maybe abnormal?

[@vetrit1820]

Just curious , are you a his paying software engineer. I am a college student these kind of interviews creep me out

[@crjacinro]

@@vetrit1820 yes i am engineer with 6 year experience

[@trusttheprocess4775]

Ffs I'm a fresher in computer and Communications engineering. These interviews make me so nervous. Idek why.

[@varunmanjunath6204]

Software engineering is competitive. Get into data science or cloud.

[@harishs4214]

@@varunmanjunath6204 even data science or cloud is competitive, for everything in IT,if I'm right you need to be good at problem solving

[@SolarPlayer]

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

[@stewartzayat7526]

And imagine doing this like 5 times a day. Sounds like a mental nightmare for the interviewer!

[@Mb-eo6bg]

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.

[@AaronAsherRandall]

Very good point!

[@drinkarmor]

@@stewartzayat7526 I give interviews for a startup they can be mentally straining but thankfully you never really do more than 3 a week

[@markmd9]

The interviewer can simply get silent and nod 😂😂😂

[@fusion_flicks95]

"Does that sound fine?" - That's all i understood.

[@nastudio405]

Heya I am here to explore from scratch and I am watching this nightmare!!! Omg should I lose my interest here 😌

[@fusion_flicks95]

@@nastudio405 Maybe not.

[@innovativedevelopers4708]

You guys have not watched it properly. It is not that difficult. It was doable if you let go of pre cognitive bias.

[@a_9414]

I'm officially changing my major to business.....

[@adrid.senpai7587]

It looks intimidating for sure. But your school should prepare you no? My school has programs and internships to help with this stuff

[@sakshamdogra]

@@ElonHusky how and where did you prepare for this?

[@shriduttkothari]

@@ElonHusky but you need correct way of how to prepare

[@theyellowflash100]

@@ElonHusky How did you prepare?

[@benkaplun8431]

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

[@jorgevasquezang]

I realized I don't even reach a Normal Software Engineer level

[@travellerrana9978]

Same pinch

[@jerodewert8334]

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.

[@skifast_takechances]

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!

[@chaseblackbeard]

The

[@sherwinbangs]

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.

[@AIschooloftrading]

TBH I found These questions like a piece of cake but still unable to get a job 🙃

[@boacaandrei2187]

It's one of the easiest I've ever seen

[@franciscoalmonte8657]

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.

[@gabrielburgos2533]

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.

[@farazahmed7]

It's not broken. It's just you can't work for it. Accept your failures rather than crying about it

[@rafeeqm]

@@farazahmed7 agreed

[@yougetonthathorseyougottar6126]

@@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”.

[@Janak217]

​@@yougetonthathorseyougottar6126it's not that deep

[@robert8930]

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.

[@dijiflex]

😂

[@smithcodes1243]

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.

[@Jamie-kf2vf]

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.

[@ab123232]

@@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 ?

[@Jamie-kf2vf]

@@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.

[@janehoe531]

"she's not a Olympic competitive programmer, not a one who has won medals..." hold up,,, that's a lot of damage

[@andreycuy6541]

why wtf . why do u think every programer have to won medals ?

[@janehoe531]

@@andreycuy6541 *win

[@richarddaniel7088]

@@janehoe531 lol. Flushing out with this mistake correction instead of answering. What a pure personality.

[@stsinner05]

​@@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.

[@janehoe531]

@@stsinner05 autocorrectExpert!? @clement

[@bensas42]

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!

[@sniGGandBaShoR]

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

[@shriduttkothari]

@@sniGGandBaShoR are ex tech lead 😁

[@suriname9253]

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.

[@nishantverma9169]

So tell us, what other methods are there???? 🙃🙂🙃🙂

[@puneetwasan771]

@@nishantverma9169 Development, Android , IOS, Web, that's what I know. Other trendy things I have heard of are , Machine learning, Data Science, AI, Blockchain.

[@greenapple9204]

So true 🥲

[@steelsteez6118]

@@ElonHusky 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.

[@Pointlessparodys]

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

[@jakariasami]

I'm storing these interviews for the future, at this time they are way above my reach 😂

[@enhalepositivity9431]

Same here 😂😂😁

[@sandeeptottadi]

Same here

[@Gummylongtail]

"storying" I'm sure you meant storing...

[@siddhantswaroop4376]

same hereee

[@aman9267]

😅

[@manasdange8800]

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!

[@sdcair]

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.

[@hanjelly5410]

this video is so great, really similar to the real interview.

[@thaiproud2b12]

I think we should see you do a mock interview- would be interesting!

[@ajaydhingra1982]

Google coding interview with Tech Lead. That would be fun.

[@TheBarinco]

I think they have put their conflicts to rest but don't want to be involved with each other anymore

[@ajaydhingra1982]

Tech lead is a sad guy

[@programmer4047]

A millionaire interviews a millionaire

[@Clockendmo]

He will say "as a millionaire, I will do..." Every time

[@AtriTripathi]

That’d probably bust his myth.

[@sindhumohan1709]

Great mock interview. Loved it. Please keep posting more inspiring content.

[@anonymousstranger3113]

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.

[@xriwarrior4329]

we may settal in the middle of the window. say, window=[gym, empty, settal here, school, market]

[@samatbryan]

Assuming in real life num preferences

[@The7shabir]

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! 😅😄

[@vaalarivanvaalariva1388]

Which clg bro?

[@shaf8200]

@@vaalarivanvaalariva1388 Algo Expert io

[@vaalarivanvaalariva1388]

@@shaf8200lolololol bruh 😂

[@jathins6809]

@@shaf8200 nani??😂😂

[@rudraneelghosh5309]

@@vaalarivanvaalariva1388 NIT calicut.

[@trocks1722]

If I ever receive this type of interview, I'll just shut my computer midway in the interview.

[@checkoverstripes1464]

you're hired!

[@jeffreyko8558]

The questions r hard ngl

[@littlemini39]

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)).

[@davidreviews8413]

Clement : Normal SWE Me : Hug...all SWEs are legends!!

[@chudchadanstud]

My first thought on the 1st one. Check block for 1 of the items item, search for how far the next item is and calculate the distance. Store the index of the smallest block, if it's 0. Just print the index, no need to search. Obviously is can be improved as this is quite slow and intensive. My second step was to grid the data and see if the items will organise themselves in a pattern.

[@techhackz2897]

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

[@slimshady5864]

Or you could just store the max when going back from right to left only!

[@amitvlogs1371]

She tries her best, I also learn a lot of things from this interview.

[@steelsteez6118]

She's also a cutie 😍

[@shriduttkothari]

@@steelsteez6118 when first he said kirti, I heard cutie 🤣🤣🤣😂😂😂

[@kumarvs66]

For your information , she shares her knowledge in her KZbin channel which help people to crack interviews in companies like Google, Walmart etc

[@thecomputerman5042]

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.

[@theebulll]

I have been really enjoying these videos! If you ever want an amateur programmer with no professional experience to try one of these just let me know. I don't have much of a formal education but I believe I could take one of these on 💪

[@kage-musha1702]

Literally No One: Not even Google: Clement: Google coding interview

[@TheHippyHoppyHippo]

lmfao

[@vikasc89581]

🤣😂🤣😂

[@adityadeore4649]

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)

[@CarzyNavi]

whenever I think I have seen everything in my life, youtube is waiting to suggest me a video.

[@aditnegi2577]

=> Iterate over blocks => make a copy of reqs => Start walking towards left and right simultaneously or condition => Iterate over sub-block => if element is true and is in reqs, remove element from reqs and update distance. => repeat till reqs is empty => keep track of minimum this is what my approach would be kinda brute force, should be improved upon

[@ajaydhingra1982]

Clement, banking technology is a different ballgame. how about algo interview with a banker. i volunteer myself.

[@haimmichalashvili8251]

@Keerti Purswani , Actually, in the first for loop(left->right direction), it is not necessary to operate the min function, because if (blocks[i][j]) equals False, dp[i][j] sure equal to INT_MAX , and if (dp[i-1][j] != INT_MAX) then I just need to assign dp[i][j] = dp[i-1][j] + 1, without the operation of min function

[@SchmittySchfin]

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.

[@MathTech83]

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.

[@pratheekbhat9647]

If you're going to use greedy technique then, the time complexity will be higher

[@Ari-jm6xx]

I'm not very good with algorithms, but my first thought was that this was a graph problem. I started thinking about Shortest Path.

[@dineshmohanty9229]

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

[@tommasochiti4237]

the moment he said shortest distance i thought about graphs and nodes too ngl

[@user-wy5es3xx2t]

ok so how will u calculate distance of each building from the apartment(which is the weight basically) without traversing multiple times?

[@jessebroxton8687]

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

[@AG-uu7nm]

No think again she has to carry it

[@tseramed35]

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...

[@plastelina4691]

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)!

[@josiahroa177]

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.

[@xfire3778]

Have you not seen Clement’s two Ben Awad interviews?

[@TheAndre2131]

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.

[@anikets4699]

I'm that normal fullstack developer, I can't even answer language feature questions. 😂😅

[@-Deco]

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.

[@codychaffin9224]

@@anikets4699 I get that man same here 😂

[@napoleonborntoparty8654]

This question was nearly never ending.... There goes my selfconfidence

[@nurkanatkhametov6225]

For the second question the main problem is to find the index of the first false value for each case. Binary search can help us with that. Then we have to divide value of that index by number of tests on this build. Here we can just iterate over all builds and find maximal percentage. Time complexity O(nlogm), space O(1)

[@MyGroo]

You cannot use binary search because there can be true values after the false one. You just need percentages. You need to build a list of percentages by simply counting the true/false items, which is O(n) per list.

[@diya.codes93]

I don’t think you have true after the false in the same list. Look at the samples

[@gabrielbittar2337]

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.

[@Nekroz05]

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.

[@TebiByyte]

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.

[@jay8929]

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.

[@alxolr]

I came up with a video to help people understand more deeply what is going on: kzbin.info/www/bejne/nKemgYeNasiah80

[@swazza3071]

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

[@pratyushkanojia3650]

Imagine replying to a interviewer that I don't know how to do it lol

[@nandanapalchowdhury4588]

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

[@ashutoshtiwari5222]

Just here for a reminder that your probability of getting hit by an algo-expert ad on KZbin is higher than getting yourself a gf .

[@sakandchoudhary2941]

Damn, truth hurts 😂

[@jeedub6142]

+1 to each index (effectively meaning that the count starts at 1, not zero) then, change the value for each key to 0 if it was previously true. (ie, no distance). for working out the distance to the nearest thing (if you don't already have the thing in the block you're in), just do a bit of brute force: (new) index number for building with the thing, minus the index for the building being considered. (If the result is

[@danyloi]

I kinda like watching this being a doctor

[@chiragagrawal3501]

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.

[@haofeifan6322]

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.:)

[@ziedbrahmi4812]

yes, dp is overkill here.

[@VinhLe-yh8rs]

What heading up on my mind for the first question is graph. We can use graph traversal method (bfs/dfs) for calculating the min path. The time complexity should be O(n*(V+E)).

[@shashwatsharma4420]

Waiting for an interview with a psycho software engineer, that'll be fun.

[@krishnavala2748]

😅

[@abhisheksankpal261]

XD

[@Ryan-gq9nr]

"So how I would approach this problem is to repeatedly punch my monitor and type the word SOLVE until I got fired."

[@tessy28]

😂

[@simonfarre4907]

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.

[@jatindersinghaujla]

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.

[@KeertiPurswani]

Thanks Jatinder, I have doubted myself for a long time. You can do much better than you think. You will surprise yourself ✌️✌️😇😇

[@kapilbhardwaj4680]

Kisan Aandolan Zindabad.

[@patronam9396]

@@KeertiPurswani im in my first year of b.tech and im already sh*ttin my pants 😅🙃.

[@chowderwhillis9448]

@@patronam9396 wtf is the matter with you??

[@whonayem01]

Thanks! Would appreciate if you do some more like this, Clem.

[@srivatskrishnamoorthy5948]

I am from a hardcore bpo background, but after seeing this video...I love to learn coding 👍

[@aishat3808]

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.

[@BharCode09]

I was thinking of solving using postfix and prefix dist calculation for each requirements from both directions of linear array. Then having a consolidated calculation of dist (using post and Prefix Dist) to find the one with minimal max dist.

[@anoopkb]

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.

[@preciouscodes1188]

The same I was thinking 👍

[@HTWwpzIuqaObMt]

Thought the same thing

[@d96yt4]

My brain could not process the your sentence

[@HTWwpzIuqaObMt]

@@d96yt4 wtf bro

[@treyshaffer]

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

[@shwackthenoobsac]

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.

[@marcinbukowski7423]

Clement, Everything is nice and beautiful... ...if not for the fact that SHE is NOT a "normal" engineer. She hosts a somewhat popular KZbin 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! 🙏

[@timmy5362]

What is the subproblem here? Is dynamic programming really necessary? What I thought was a sliding window, and where all test cases are matched, and then we could divide the result by 2 for the final result

[@stauber28]

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.

[@SatyamKumar-ts2jh]

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.

[@aurinator]

The approach I was initially thinking was to compute the distance to each one at each square, e.g. [gym, 0], [school, n], and [office, 2], where 'n' is the number of squares to reach the location. Then, you've reduced it to a linear-programming problem that would probably be solved on pen & paper with matrices. And, she appeared to initially tread down this route - still watching.

[@alexnice2221]

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

[@ChongFrisbee]

First idea just having listened to the problem. First, iterate trough the array compiling the distances from initial index to last, for each relevantbuilding type. Some kind of infinity representation must be used until the first of each building type is found Then, make a second pass through the array from last to initial index, updating the previously calculated values when distance is lower. And you can keep track of minimal distance indices in that 2nd pass. There probably is some subtlety there I'm not seeing, because that doesn't seem that hard. EDIT: I don't know why I thought this was ment to be a hard question. It doesn't say that anywhere

[@tonymcfarlan9593]

Just started programming and watching this made me realize I got a long way to go

[@Zenpreneur]

Dp solution was a surprise for me..she did good and it seemed complex code. I would have tried simple DFS approach on each block and try to find minima and may be add memoization to optimize it further.

[@ziedbrahmi4812]

or just go go from left to right, in each index, update the lastIndex you saw the requirement(i), and update the block with min(currentBLock[requirement(i)],(blockIndex-lastIndex+1)) and continue like that , and now from right to left, in each index , update the lastINdex you saw the requirement(i) and update the block with ..

[@sanatani5399]

A DP solution? Didn’t expect that. For me, a BFS solution seems more intuitive. We can start with the block_0 as the source and run it to the block_n as the sink. Along the way, will keep updating the distance to the amenities. Then, for the subsequent blocks, we can use the previous block’s distances to compute this block’s distance to the amenities.

[@tooltooi]

1) reformat data structure as store: indices, school: indices, gym: indices, then sort the building w.r.t number of indices. (least frequent building to most frequent building.) Then, we know that the building with least frequency is the biggest constraint to the solution, so we can find optimality from least two pairs and move up. Runtime O(n*m) where m is the number of buildings

[@heyitsyeh]

Damn she rocked it! Dp always scares me :(

[@franciscov511]

it is not hard, it is just about to remember key things of dp

[@salsaSamuel]

this wasn't dp btw. she just named it that

[@andrewshirley9240]

@@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.

[@aj9706]

She is Intuit software engineer whose salaries are similar to Amazon India salaries therefore level of FAANG.

[@connorg8259]

Just curious, I am almost done my first year of a csc program at the university of Victoria. I have worked with python and java. As far as complexity we have worked with recursion, linked lists, stacks/queues, and will soon be moving into trees and such. Would algoExpert be good for extra practice, or are the questions more targeted toward experienced programmers getting ready for an interview?

[@ericnail1]

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.

[@miscEngineer]

I bled in my Google interviews, the questions were so harsh.. I wish life was so easy 😭😭😭

[@trusttheprocess4775]

:(

[@numseidizer]

Harsh?

[@miscEngineer]

The easiest question I had in my interview involved 2D DP in a DAG after topologically sorting it.

[@andrerhea4168]

@@miscEngineer how did you become better, I recently started coding.

[@miscEngineer]

@@andrerhea4168 I practiced on leetcode and participated in leetcode contests

[@ayushkumarsinha8614]

For this question, my approach would be to traverse both ways and if the present item is true, make value to 0 and then compare to keep the minimum of left and right travel for the ones having value as false. Find max to be, let’s say, the “order” for that block ( we need the minimum order travelling from left). From the final array, find the index of first minimum.

[@jujuburgers4240]

I wrote a function that adds the max distance of each block on the street with the index as the parameter. I then looped up the array starting from that block and found the max distance for gym, school, store. Then I said, for that block, if there is no max distance going up the list, I then got the distance going down the list. I then added the three vals for going up and three vals for going down to an integer array list and added the max value of that list to a maxVals array list. After calling the function for each index, I ran through the maxVals array list and found the minimum

[@davidpulq578]

I think for first question, you just scan twice: left to right and right to left, to build the min. distance. so it can be done O(n) time and len(reqs) x n space with naïve implementation.

[@casperes0912]

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 :)

[@OptiMystic-IN]

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? 😅

[@Haylem]

so hard to follow, what makes a great engineer is making it easy to understand.

[@patrykblu838]

Normal Software Engineer? It's kind of offensive

[@53strat55]

Why, because you want to feel special?

[@patrykblu838]

@@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?

[@53strat55]

@@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.

[@patrykblu838]

​@@53strat55 Thank you for your answer. I don't think there is a term "normal developer" in our industry. Hence my answer ;)

[@53strat55]

@@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.

[@aiswaryajami2841]

Two approaches : 1. Use TreeSet to store all occurrences for each requirement. Iterate the array once, get ceil and floor values for each i, pick the min and assign to block[i][j], and 4th variable in each block to store min dist of all m requirements and a global minSoFar for keeping track of index with min. Extra space for storing tree set's for preprocessing. O(nm) time 2. Use DP array to store distances from left and right in 2 passes, update as you go and return result. Extra space for storing DP array. O(nm) time

[@ujjwalsomani1982]

I think first approach will take O(nmlogm),as insertion,ceil and floor take log n time in treeset(balance bst).

[@nsjdeveloper1123]

Hi jami , could you please explain what the exact requirement of above program. I am unable to understand that and i tried to get under stand but no luck,

[@wasd3108]

1 loop solution have a map of key being unit (e.g. school) and value number which is the previous index the unit was true loop through blocks each iteration/for every block: refresh the map for previous/last index a unit was true loop through map and get maxDistance = max(currentBlockIndex - currentUnitPrevDistance) if maxDistance is lower than the minDistance that we keep track of, set the current building of choice the middle one in the range, floor((currentBlockIndex - maxDistance + currentBlockIndex ) / 2)

[@MomsDailyCorner]

While watching this interview I realize the truth that the MNC interview that I attended was too simple. From a 5yr java developer.

[@talanky]

Wow she nailed it!

[@Yureka-ox5jn]

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.

[@sauravsuman5963]

@Clément Mihailescu , looks like there is a mistake @59:55 , as it will be calculated as max(6,1) , max(6,0) and max(6,1) so it will be 6 over here instead of 1 and then the algo would fail. Still thinking if we can re initialize them to 0 and then compare max(0,1), max(1,0) and max(1,1) as she has done here.

[@AlgosWithKartik]

Really useful videos, great work!

[@em_nikhil_007]

Kartik bhaiya OP 🤩

[@shubho5das]

Wish to see you next on Clement's Video, haha!

[@Kruxxy]

A normal software engineer is a stackoverflow expert. This person is beyond normal.

[@jorgeviana1826]

Really cool that the people in this interview could hold in their brains all the state of the program. To be honest I don't get the how the solution holds, there's lots of loops and indexes. I solved it on my own incrementally with TDD, unfortunately my solution is a bit more on the brute force side... But if I can get a better understanding of a more performant algorithm, perhaps I can apply TDD there too. Thanks for sharing!

[@syednadeembe]

She got me so confused that i almost forgot what i was watching...

[@Southpaw101]

That's a great interview trick .... If you can't solve it ... CONFUSE the interviewer :)

[@Alex-hr2df]

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!