Google Coding Interview with an ex-Microsoft Software Engineer

I'm also an ex-googler software engineer and you really have to mention that X Google engineer right oh you have to you have to so yeah it's like a rule so hey everyone this is me ratchet and welcome to yet another video today we have with us a very special friend of mine he goes by the name Clement I am really very sorry if I mispronounced it yet again today what we are going to do is a mock interview Clement will be asking me questions and we will basically create a real interview scenario wherein I am giving the interview and I will try to do a data structure algorithm problem and let's see how this goes I know that most of you might be knowing Clement already from his hallo expert work but anyways for new you views in you just introduce yourself to them please sure no problem so first of all thanks for having me here this is gonna be fun hopefully and yes I my name is Clement malesko I'm the co-founder of algo expert which is a website that helps people prepare for coding interviews algorithm interviews by the way if you want to check it out I'll go expertos slash rock sheet and you can get a discount if you use the promo code rock sheet I'm also an ex-googler engineer and I just really like coding interviews so we're gonna put rod sheet to the test today and you really have to mention that ex-google engineer right oh you have to you have to it's like it's like a rule once you leave the company that you have to always introduce yourself like that sure then I'd be giving their interview as an X Microsoft engineer then exactly perfect all right so are you ready ratchet yeah sure okay so the the rules are gonna be simple we're basically going to be imitating what a normal coding interview or phone interview would look like because we're gonna be doing it over Google Hangouts and over Google Docs but so we're gonna give you roughly 45 minutes this is a question that you've never seen before we haven't talked to that this before so it'll be sort of like a the real the real deal and that's that sounds good yeah sure okay share the doc link yes I'm sharing the dark link right now all right so let's get started I'm gonna put a timer for 45 minutes and that's that awesome cool so okay Rocky so have you ever heard of this thing called the Infinite Monkey theorem of course not okay so it sounds very weird right Infinite Monkey theorem a sickness in theory if you were to put a monkey in front of the keyboard and have the monkey type random letters on the keyboard after some humor humor of time that monkey would be able to write basically every word in the English dictionary every word in any dictionary the monkey would be able to type like anything out because because of the laws of sort of probability and statistics and randomness does that sort of make sense yeah okay so now I wanted to introduce that sort of this as a funny intro but if you take the number pi right you know the number pi 3.14 the number is sort of similar to the monkey in the sense that it's a number that never ends it's an infinite there an infinite amount of digits in that in the number pi and the numbers or the digits are random and in theory there are people who say that in theory you could find every word in the English language or every sort of combination of numbers in the the number of pi or somewhere in the digits of pi so now what we're gonna do for this algorithm question is I'm gonna give you the first 10 digits of pi okay so basically it'll be like a string of the numbers of Pi and they're gonna be roughly n numbers of Pi or digits of pi and then I'm gonna give you a list of numbers that are sort of like my favorite numbers and I'm gonna want you to basically tell me what the minimum number of spaces you would have to put in the digits of pi such that all the resulting numbers would be found in my favorite list of numbers and so I'm gonna give you a sample input in that output so that you can sort of understand what I mean and that's gonna give you these this string this is a string what I'm highlighting here these are like the first I don't know 30 digits of pi or something and then I give you a list of these numbers you see these are all again strings and you would have to basically find all the places where you would have to add spaces in the digit so maybe you could add a space here maybe you could add a space here you could add one here right and you want to find all the resulting numbers you want them to be in this list of of like what I'm gonna call my favorite numbers and so here the the sample output would be 3 because if you add just three spaces right one here one here and one here you have these four numbers that happen to be found in my list of favorite numbers does that make sense um how does 793 is occurring over here 793 is not necessarily occurring but the idea is that if you if you add three spaces and these exact areas here the resulting numbers 3 1 4 is in our list of favorite numbers are this big number is here ok yeah that glad if I hit yeah ok so basically I have to split my pie string which is of n characters into some number into some other numbers so that all of them occur in that array your favorite array yes and you want to and you want to minimize the number of stations yeah got it ok so I think it's quite straightforward that we have to start with the initial character which is 3 in this case and we go as long as possible and we find the longest substring or the longest prefix for like in the given case 3 1 4 1 5 will go on and on until we reach a point post which we cannot ever form the string which exists in the array so what I'm trying to do is basically find the longest prefix which exists in the or array you can once I get that I will enter a space over there basically that's my first split and then I will do the same thing for the rest of the shrink so here for this you would say basically you start at the beginning you see that's your you arrive at like three one four you see that this is in the prefix or this isn't our favorites but once you get to three one four one this is not in the things so you stop no basically I will go as long as possible because it might be the case that you do have a three one four one five nine two six five in your favorite list this is possible that this much part is there in your array so I really don't know that when I match the first three one four it's the longest or not I will need to check whether I can go much bigger than that or not I see right so basically once I go in the longest direction I will pick that and then do the same for the rest of the string and so this this is a greedy approach and it's prone to fail like for example this might happen that there is actually three one four one five nine two six five three and then there is also three one four as you can see but if we pick the longest prefix initially then it might happen that in the rest of the string when we are trying to do the same it might happen that we actually end up not even basically we it we make it impossible to solve the problem so going greedy does result in minimization but it comes at a cost and that cost is wrong answer right does that make sense like because it might happen that we picked the longest one but we should not have actually because the first shorter partial match was resulting in a possible solution but since we picked the longer one because you were going greedy we actually failed it definitely yep that was the I was going to give you the example of what if you know this huge number was in the thing but the number nine wasn't but it's that's exactly what you said so so of course we need to ensure that the rest for the rest of the string we can also do this okay okay so what I'm going to think is basically let's say we have a function check which takes care of some in index let's say pause and what it does is it basically checks if it's possible to I would say disintegrate the string from for the suffix which is starting from position pause so let's say the length of your string given s so basically given is s is equal to nothing but this long thing and then let's say the length of that is in right yeah can say more des is in so now what I am saying is check pause returns whether we can solve this problem for s pause in yeah and instead of just checking it actually also returns the minimum steps or the minimum spaces you need to insert let's have a function for that as for now right sure and if this returns minus 1 it means that it's not possible okay yep so essentially what our answer is nothing but check zero if you are using zero-based indexing right because when you do check zero it's from the position zero all the way to the last index and right yeah it's actually n minus one but basically the last position is not include sure so now what I'm trying to do is see how I can reuse the check function to solve the problem for check zero right so basically when you are at check pause right you really do not hear about all the characters which were before pause we are interested in the suffix right suffix s pause till n so what I can do is to solve this I'm just going to just give me a sec yeah so what I'm going to do is iterate on every prefix from starting from pause that exists in our favorite array all right yeah and then let's say right now we are at the prefix let's say a spa still J right so let's say this exists in your array favorite area so if that happens what we can do is basically we have the choice to make a space over here so we do one space which is one space and then for the remaining we've simply called check j plus 1 right all right and we just need to ensure that check J plus 1 does not return minus 1 so this should never be equal to zero right yeah and if we maintain the overall minimum we can basically then assign that to s I mean Chekov pause hello yep yeah I'm falling yeah so I think this should look and so are you thinking of like what would use would you start when you when you first call this check function would you start basically with check of zero or would you start with the very end like check of n minus one I'm not sure or exactly do you mean like when you I suppose maybe maybe if you could could you run me I guess yeah Wilkie can you run me through an example like if we take us maybe a shorter version of this example or even that example you know you can run the first couple of calls okay so let's say we're having this thing sure and I will do that above only because we have everything written in one place yeah no problem so let's say we have this and I called check zero right now yeah so what's going to happen is I iterate on every prefix possible so in this case let's also modify the input array let's also add a three sure so I check that three exists in my favorite array then I would call check one for the for getting the answer for this remaining string that I need to take responsibility for and it will return me maybe two three four or something like that or minus one if it's not even possible to disintegrate the string into the components of wave retiring so that's one case the other case is three one four and then I will call my check function again for this part of the string yeah and this will in this case ideally should return to and since we had added one break for three one for the total becomes three and since we are taking overall minimum for all the possibilities we can basically evaluate that three is the minimum answer for this case data I see okay let's see if we can let's see if we can code something up then sure so what I'm going to do over here is just first I'm using the C++ language and I'll be using a function let's say I really take some time in coming up with some really good names so instead what I'm going to do is use some dummy names and later on if we have time we can modify and increase the code quality for the code sure just give me a second all right let's say end minimum spaces and let's say we are having the string s so then we also have a vector right favorite array Mari and let's call this pie sure so I'm having pie I'm having my favorite array and then what I need to do is basically do something like see out check zero I can have a global variable or shall I okay so right now I'm basically doing a move to the global variable so that my function looks a bit simpler otherwise we can pass in as arguments also so basically this check function would need access to the spy and favorite right you can use the global variables for now if you want yeah sure thanks so basically let's say they are right over here in the global namespace all right I think now let's say we already have them initialized with the values that we wanted right so this check function can do something like this if boss is basically in you can simply return 0 handling the base case and then otherwise what we can do is for in J equals boss J is less than N and then J plus plus we can do something like cool string cur is empty right now we can do so I am building the prefix yeah courage the prefix right so I'm basically trading on all the prefixes possible and if exists in your favorite array this number so you'll come to this part later basically over here what we can do is for string s in your favorite array we can do something like exists s is 1 sure an exists is like a hash table or something or map something yeah yeah so that's basically an unordered map just to get that order one lookup and putting the key into the third so we can have a string to rule exists yeah so now if exists then we have one possibility so if exists we can do something like and other is basically checking for the rest with his day plus one and if other is basically not equal to minus one so it means it was indeed possible to disintegrate the remaining of the string what we can do is something like answer is minimum or answer comma 1 plus other because that's how it has to work and then servicing what is this to make sure that answer if other if if whatever the check of the suffix at this point after J after the prefix I guess is not -1 then the end the current answer is gonna be the minimum of whatever the current answer is or one more space plus other sure yeah yeah and I think the other thing is to basically return the answer over here so this code should work there are few things that you can do with it of course this is a recursive solution and the time complexity looks bad so to handle that what we can do is use dynamic programming over here and to do that what we can do is store a reference to something like DP pause right and then if we have visited this position already then you can simply return the answer otherwise we can say on service hint and disco max and say yeah so now the time complexity has like really increased a lot because you are not doing the same work again and again right and what this DPN wasted are let me just create that as well so we can say pause is something like this it and then BP is also sorry this is DP and then we have wasted like this where n is like the max length of the string s that you can get in the fire and so basically you're essentially like cashing all your answers is what you're saying yeah I'm sorry can you repeat what you said vis n is so since it's a global array it will be initially zero okay and one thing that I have missed over here is just to make that you have this has been wasted so what I do is I am storing a reference in this variable ans answer for the current VP state and if I have already visited this DP state I am pretty much sure that I can simply return answer Carter and if not then we are basically doing this part over here and then I am also marking that we have visited this state so next time don't do that rework I see I see and the answer okay I see but but you do you need the duplicate DP and vis like aren't they basically the same thing yeah of course we can get rid of them basically we can initialize the DP with something like negative 1 right and instead of checking visted pause or something like that we can check that if actually not negative 1 because that's one of the values which we are returning right right but you could you could do some other value and maybe this would make more sense in another language so if an set is basically let's say we have answer is something like an initialized or undefined we return the answer and undefined is something like a constant undefined we can basically use a negative 2 or something in our case right okay so one thing so just let me go through this one so yeah sure with the example because I yeah because I need to take care of some things like we have to return negative 1 which we are not doing right now sure alright so it might happen that this if condition is actually not met and in that case what we can do is that yeah over here so basically we can check if answer is still in max we can return minus 1 otherwise you can return answer yep hello yeah yeah cool yeah this seems to look ok so rocky this is I think we have we have actually exhausted the Infinite Monkey pi theorem whatever you want to call it so I actually want to move on to something else [Music]

Channel: Rachit Jain

Views: 931,373

Keywords: mock coding interview, google interview, microsoft interview, google interview questions, microsoft interview questions, data structures, algorithms, interview prep, mock interview, coding interviews, algoexpert, dailycodingproblem, goldman sachs, flipkart, microsoft, google, interview questions, software engineering, coding interview problems, ds algo, leetcode solutions, coding interview prep

Id: tOD6g7rF7NA

Length: 24min 3sec (1443 seconds)

Published: Sat Aug 24 2019