Google Coding Interview With A Normal Software Engineer

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

[@greentoadboy]

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

[@alektg1]

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

[@ChristianFure]

@@alektg1 feels so far away

[@alektg1]

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

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

[@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😭

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

[@lost-mar-ble]

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]

@@lost-mar-ble 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

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

[@AdityaSingh-sq6sw]

what about now? did you reach that level?

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

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

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

[@ec8483]

Much clever way, but still got a O(n) time complexity though.

[@solarsystem9156]

I am not sure I got it. Can you explain in a little bit more detail ?

[@jazzymichael]

@@ec8483 O(n) time using sliding window is faster than O(n*m) time used in this video. This is average time even if a "perfect" element is found before accessing them all

[@monsuruokuniyi1234]

isn't this still O(nxm) time complexity? You go through the blocks n times, but go through the keys every time for every block. It's the same complexity of her solution. I came up with a monotonic stack approach with O(nxm) time complexity. And I was just amazed to see her solution and yours. Quite impressive!

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

[@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]

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

[@shriduttkothari]

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

[@theyellowflash100]

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

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

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

[@Josuke217]

​@@yougetonthathorseyougottar6126it's not that deep

[@yougetonthathorseyougottar6126]

@@Josuke217 depends on your perspective. this is mine.

[@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]

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

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

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

[@RyuDouro]

@@innovativedevelopers4708 this did not age well

[@JoshSmith-sr6ks]

@@RyuDouro how so? It's moderately complicated but not very difficult. the first one at least I didn't watch the second question

[@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]

😅

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

[@FutureMillionairesForum]

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

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

[@OusmanBah-f8v]

@@sakandchoudhary2941facts tho

[@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 😁

[@draugno7]

At first I was totally confused by the question but after they discussed it, now I'll be able to solve similar ones. It's also about practice. Smarts don't always matter that much (if you're not a genius then of course). I sometimes come up with a great solution and sometimes don't know how to start. But these different problems train our brains to think in general plus we remember similar solutions and put them to use. I remember doing leetcode for the first time and how I git stuck and got non-optimized solutions. Now I have a better grasp of what could be done to optimize and not ever consider writing a brute force solution

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

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

[@kage-musha1702]

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

[@TheHippyHoppyHippo]

lmfao

[@vikasc89581]

🤣😂🤣😂

[@davidreviews8413]

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

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

[@CarzyNavi]

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

[@kumarvs66]

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

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

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

[@Anchor97]

@@anikets4699 I get that man same here 😂

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

[@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!

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

[@Tessy29k]

😂

[@RizkiFikriansyah]

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.

[@datsrough6217]

Weird

[@najeei7794]

Feels terrifying 😖

[@urugulu1656]

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

[@Haylem]

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.

[@nadeemahmed7622]

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!

[@MyStockz]

Facts! Check his Medium coding interview with Ben Awad

[@littlefluffybushbaby7256]

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

[@ANKRITIPANDEYCSE--]

@@littlefluffybushbaby7256 but that's the point of this comment. They obviously meant the former was more difficult than the latter.

[@marcusaureliusregulus2833]

@@littlefluffybushbaby7256 Yes. The point is he gave Ben such an easy question 😂

[@littlefluffybushbaby7256]

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

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

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

[@KayZZy69]

@@vaalarivanvaalariva1388 NIT calicut.

[@KahaaneeHumari]

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

[@Kruxxy]

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

[@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! 🙏

[@noobguitarist654]

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

[@y_nk]

the amount of time of "google coding interview" is said within the 2 first minutes is crazy.

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

[@SritamNanda-x5h]

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

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

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

[@danyloi]

I kinda like watching this being a doctor

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

[@MomsDailyCorner]

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

[@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]

[@t-zex4650]

yeah I was surprised the dynamic programming was used here.

[@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)

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

[@nishmusic4438]

But it is overdomplicated I’d just do a suffix array for all reqs where I’ll store the min distance for jth req on the right So for each position i it’s just max(prefj,sufj) for all j

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

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

[@Haylem]

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

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

[@samatbryan]

Assuming in real life num preferences

[@aj9706]

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

[@thaiproud2b12]

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

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

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

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

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

[@agmharry]

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.

[@mohammadsolaiman9579]

just watched the video . now i feel the headache. lol 😂

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

[@tonymcfarlan9593]

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

[@sdksfo487]

The optimal solution for qn 1 is with sliding window. We are looking for the smallest window that meets all the requirements.

[@magesRNTcute]

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

[@sarveshchavan4391]

Can u please share me the questions link if you have one or some similar sort of problem ?

[@sdksfo487]

@@magesRNTcute yep, mid point of that window.

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

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

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

[@zhussupov]

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.

[@feuerfawkes]

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.

[@SimonK91]

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}

[@feuerfawkes]

The solution in the video is clearly not O(n). Consider reevaluating.

[@xubowen7778]

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

[@zamfiratosamir8426]

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.

[@kasi31682]

how?

[@shriduttkothari]

How????

[@nicemayi1]

Sliding window? We could find the shortest window size that contains all requirements, the the final solution would be the window size over 2

[@sanjeen2503]

I sense there is iteration needed inside each window, but I might be wrong

[@zamfiratosamir8426]

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.

[@ahmedbashir5012]

Me: see’s title with google and clement in the same sentence Also me:clicks automatically 💀

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

[@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!

[@deathbombs]

Q1 is basically find the building that has minimum travel distance to all requirements 24:45 Q2 is minimize time to fix build runs ("green %, higher is better"), and find greatest number of decreasing %s Also a normal enginer would not know question 1 or 45:20

[@trh786fed]

the second one, find the lolngest decreasing subsequense

[@patrykblu838]

Normal Software Engineer? It's kind of offensive

[@53Strat]

Why, because you want to feel special?

[@patrykblu838]

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

[@53Strat]

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

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

[@53Strat]

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

[@AnkitSaini-ij6wl]

Someone: are you a software engineer? Googler: NO! I’m Google engineer.

[@sandeepnath9504]

How is this possible that she gave the exact same code found in Google including the variable names...

[@edwarddelgado9654]

Loop the blocks, nest the reqs, nest the blocks again until all reqs are found and assigned a distance the highest value belongs to the block and so on return the block with the lowest distance. An accumulated var for the distance. The reqs array can be temp used as a placeholder for the distance var. I would the high value as an element to the block, sort the block array by high value and return the lowest. Probably not the most efficient I'm at 12:28 so let's see.

[@ajaydhingra1982]

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

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

[@hanjelly5410]

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

[@Etcher]

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.

[@BableDaily]

You realise the way she calculated max distance is completely wrong. It won't reduce ,once it's set to int max you can't go lower . Just see about the start of second loop , distance is infinity initially (from first loop) if you do dp[I][m] =max() the value of dp [i][m] can't reduce. Correct me if I am wrong!!

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

[@thecomputerman1]

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.

[@sindhumohan1709]

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

[@shadowspear9639]

Minimum of maximum just use binary search, 1)start off with min value as 0 and max value as size of entire list 2)Then mid and write a check function which iterates thru each element in array for if any is possible or not Time complexity would be O(nlogn) I'm still in my final year uni btw :)

[@asutoshmittapalli]

"Normal Software Engineer". Dude she works at Intuit. How is that normal? -_-

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

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

[@madhurpanwar]

I think the solution to the first problem is (slightly) incorrect. The way she calculated the final value of dp[i][m] was essentially as follows: 1. Compute the max of all requirements' distances considering blocks only to the left of and including i. 2. Find the recurring max of this value with each of the requirements' distances using the updated distance values after considering blocks from the right. And this is not right if you think about it. The value that dp[i][m] retains from the first pass should not be used. We must instead reset it to 0. Let's see it with an example below. Consider a block i for which the distances of the requirements from the left comes out as [1, 2, 1] (distances from gym, school, store respectively). Assume that considering only the blocks on the right, the gym and store are at distance of 2, while the school is at a distance of 1. Therefore, after second pass, dp[i] would be [1, 1, 1]. However, since we compute maximum of each of these updated values with the old dp[i][m], we would end up with the farthest distance of 2, which is incorrect since all the requirements are at most one block away. It is just a coincidence that the provided example doesn't expose this problem in the code. What do you guys think about it? Please let me know if I got it wrong instead.

[@pianotmyforte320]

Right, she had to consider min(right, left) for every requirement and take max over all requirements. She took max over right,left instead so it’s incorrect

[@rajrajesh1669]

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

[@JimmyBob708]

For q1 just write a for loop containing 2 for loops, 1 checking forwards and 2nd checking backwards. If all criteria is met for outer for loop then break the inner for loops and return shortest distance. Have a variable on top level which keeps track of best index for outer for loop... I'm surprised this is a Google question it seems like an easy leetcode question

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

[@premalupadhyay3555]

As in silicon valley series Jared said to Carla "Woman engineer" she replied I am not "Woman engineer", "Just an engineer" here same scenario keerti be like "I am not normal engineer", "Just and engineer" 😁😁 Although great session 👍

[@stevemats]

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.

[@touaxiong5285]

I would have loved to see you do a mock interview with TechLead, but probably not something you’d want to do considering what happened between your company and him.

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

[@MrSemro12345]

36:47 - The moment Clement lost the plot of what she is talking about.

[@jamesward1210]

I waited all video to see what this time stamp is, and honestly? Her explanation was fine at this point. Odd that your comment got so many upvotes. Is it confusing because of her accent?

[@Haylem]

@@jamesward1210 i dont talk to much indian people so her accent makes it hard for me to understand, if i heard it more often, it'd be clear as day i'd imagine.