Coding Practice with Kick Start: Session #2 problem walkthroughs

Key Takeaways

[Music] hi everyone thanks for joining us for coding practice with kickstart my name is lizzy and i am the kickstart program manager we hope you enjoyed practicing our problems during the session and learn something new to kick-start your coding competition journey throughout this video we'll hear from various google engineers on how you can go about solving each of the problems you just attempted regardless of what you solved we hope these walkthroughs will provide some helpful tips and tricks to use for future competitions if you're watching this video live feel free to ask any questions to our google moderators in the chat feature below now let's hear from some of my colleagues who will walk you through the problems from this week's session take it away [Music] hi everyone welcome my name is erico and i'm a software engineer in google play analytics i'm here to talk about the problem sherlock and the parenthesis the problem is a good example of what you can expect from an easy problem from google kickstart the first thing you need to understand is a problem statement let's go through it carefully the problem is about a maximum number of balance strings for this we should focus on what a balance string is according to the problem statement a string is balanced if it matches one of the following conditions a is an empty string b is of the form open patterns s close currents whereas is a balanced string or c it has a form s1 s2 whereas one is a balanced string and let's choose a 1 string as well maybe let's try another solution for this one let's explore this idea maybe we can generate all the permutations which are given number of left and right parentheses for this there are help parameters in all programming languages there will always be some complexity costs for generating these permutations which will be in the order of the possible connotations and for counting the number of balanced substrings we could just start anywhere in the string and start counting how many valence parenthesis there are then try starting on the next position and do the same this will take a list o n square the total time will be o n square times the time to generate the permutations let's continue reading you got t test case okay that's normal and we want to have the maximum number of balanced non-empty substrings should we just go ahead and implement our scenario solution let's look at the limits oh the large test cases they could be up to 10 to the 5 parenthesis even optimizing the nice solution it won't work with this kind of limits it's always important to check the limits i actually think of them as hints for the type of solution that is expected so our name solution is too expensive but what about just calculating the number of banana strings directly yeah i wonder if there's a cross-form solution for this problem at this point i recommend grabbing a pen and a paper and writing down some examples what is the variation of parentheses let's take the case for example of l equals 3 and r equals 2. it was always good to come up with your own examples and try to figure out how to solve them i do this even before reading the provided examples take a look at the slide we can have the first arrangement where we have only one balance of string or we can have a much better arrangement like the second one i think we can imagine this is the best we can do can you prove this is optimal so how many personal parents there are you might learn as cool about the handshake problem i like to think about this one as imagined as a room and there are n people coming in one by one each person is coming in and giving a handshake to everyone in the room the second person will have to shake one hand the last person will have to shake n minus one hands so the total number of handshakes is one plus two plus n minus one hands which evaluates to n times n plus one over two so what is n in our case we want the valence strings to be of the form open parens close parens so basically we need to ensure each left parent has a right variance so we are constrained by the lesser of these two so basically n is the minimum of l and r we now have everything to start calling let's do it let's just do what we did before here we have some value play call to read from input and some wire play code to write from the output i like to write value play code first and then call the solution let's just put our solution together this code is in very simple java language okay one final start what is the time complexity of our solution if you're thinking very fast that is correct we say that the complexity of the solution is of one which means it's constant with respect to the input also the space complexity should be constant now we can submit and it should work okay so to recap it is okay to explore possible solutions take a look at the limits they provide hints on the type of solutions expected make up your own examples always have fun coding the solution now we probably may done we can move forward to the rest of the problems with much more confidence thank you for walking through the problem with me my colleague kata is going to present their next problem building palindromes [Music] thanks federico hi everyone my name is katablanine schwark and i'm a software engineer at google i work on cloud ai and industrial solutions and in my spare time i started to hub with coding competitions we hope you enjoyed trying out all the problems from the practice session today i'm going to walk you through the problem building palindromes let's jump in in this problem given a string we have to count how many of its substrings defined by the input intervals can be rearranged to form a palindrome a palindrome is a word which is the same as its reversed version you could notice that the naive approach rearranging a substring in all possible permutations and checking that palindrome feature wouldn't fit in even for shorter intervals as for example 15 letters would build up 15 factorial strings and this number is way more than 10 to the power 10 but let me highlight that you don't need to create any paradigm you only need to decide whether it is possible to rearrange the letters of the substring so that it yields a palindrome or it's not possible based on the feature of the palindrome you can conclude the following observations letters of an even length syndrome can be paired entirely letters of an odd length palindrome can be paired except exactly one character the middle one the strings that are rearrangeable to palindrome are actually rearranged palindromes so they also have the mentioned feature now we reduce the problem to count all the character occurrences for the substring and if there is at most one of them having an odd sum the substring counts to the result worth to mention that you actually don't need to track the number of occurrences itself only the parities i've wrote my code in python but you can choose any of the available programming languages the time complexity of this solution is big o n times q which is sufficient for the constraints for test set one for the test set two we have a much higher number of characters as well as queries so we have to reduce the calculations further one approach here is to reuse the results on previously calculated intervals and this problem is really suitable to solve using this idea with the very square root decomposition technique i won't explain it in detail as it's still not optimal even if it passes instead let's consider some static precalculations on the input if we know the number of occurrences of a given letter for every prefix we get its count through any interval by the difference of the count until the last letter and the count until before the first letter although this calculation needs bigger and time and also bigger and space in addition the time consumption of a singular query is reduced to constant thus the overall time complexity sums up to big o n plus q times 26 in the code to identify a letter we use its index in the abc with the help of the ord function during the preparation the list scene keeps the arrays of graphic sums by letter indices which is filled during working through the input why the ray act holds the actual number of occurrences after this preparation the evaluation of an interval is done by summing up the corresponding differences modulo 2 which exactly yields the number of different letters with odd occurrences if it is less than or equal to 1 we have found a new substring which is a rearranged palindrome and we count it in that's all from me and thanks for watching sara over to you [Music] hi everyone my name is sarah and i'm a software engineer at google and i work on a team of dataworks where we work with internal googlers and consolidate enterprise data within google i'll be walking you through the problem irregular expressions let's start by looking at the problem statement we're given a spell which is a string of characters and we need to determine if that spell is valid there's a couple definitions that are given each valid spell will contain three words which are start middle and end a string of characters is considered a word if it has at least one syllable and can be one or more letters long a syllable is a string of letters that includes exactly one vowel and the vowels are a e i o and u note that y is not a vowel here so here are some examples of valid and invalid syllables we see that if the string has zero or more than one vowel it's an invalid syllable now that we understand the problem let's look at the constraints first start middle and end must be a word which we defined on the previous slide as a string of letters with at least one syllable second start must equal end and lastly start and end must have at least two syllables there may also be random letters before and after the spell and the string might not contain a valid spell at all so what we're looking for is if there's some substring in the given input string that starts and ends with the same two or more syllable word with at least one vowel between them in the small data set the given string will have at most 20 characters and for the large data set at most 100 let's look at some examples in each example the start and end word is highlighted in green and the middle word is highlighted in blue in the first example notice that the start and end word has two syllables and the syllables themselves can be split in different ways the second example is a string which contains extra letters at the beginning and end of the spell the last example does not contain a valid spell in the given string a common mistake is to think that the first f-r-u-f-r-u is a spell remember that the middle must contain at least one syllable and here it contains none given the constraints and definitions of the problem we can make some observations first we notice that the only constraint on middle is that it has one vowel this means that there may be many random letters before or after the vowel and will still qualify as a valid middle word with this in mind we can also assume that start begins at the first vowel and that what comes before it doesn't matter looking at example one below where the start and end word is highlighted in green and the middle word is highlighted in blue we can see that one valid spell is jabba majaba however if we assume start begins at the first vowel we see when iterating through the string making it abba we see that abba abba would also be a valid spell since when we look for the n word we can push everything before the abba in this case is just the j to the middle word without breaking any constraints second when we're looking for a valid start once we see two vowels we can stop and assume that the rest belongs in middle to see this let's look at example two the top two are valid spells let's assume that we realize that the kaj can't be part of any valid spell now we're looking at the a after the kaj we iterate along we see the second a and now we've seen abba so far we've seen the second vowel and we can stop here this is because we've satisfied the constraints of start already and whatever else comes before we can just stick onto the middle word we can safely do this because there's no constraints on the middle word other than it must have at least one vowel in fact we must do this because if we don't we may miss potentially valid spells as we see in the third line of this example where we don't stop at the second vowel and miss the valid spell abba abba lastly after seeing exactly one vowel in the middle we can begin our search for end again this is because of the one constraint on middle which is that it must have at least one vowel similar to tacking on any extra letters to middle word when looking for start we do the same for end where we search for whether end exists in the rest of the string if there happens to be any letters before n begins we just assume that it belongs to middle looking at example 3 after we decide that the start word is abba we see the next vowel a which is highlighted in blue and then we can look at the rest of the string starting from adsf onwards and see whether abba appears if it does we say that everything before the n word abba is actually part of the middle these excess letters are highlighted in yellow now let's go through the pseudocode because there may be random letters before the spell itself we need to iterate through the spell we first find the first and second vowels we set the start word as a substring from the first vowel to the second vowel inclusive we can see this in the two examples where the start word is highlighted in green then we set the middle word after seeing the third vowel to be everything after start to the third vowel this is highlighted in blue in the examples then we look through the rest of the string starting from the letter right after the middle vowel if it contains the start word then we have a valid spell and we can return otherwise we'll need to reset the start word and continue looking in the first example we see that start exists in the rest of the string so we can stop in the second example however we didn't find the start word which was ae in the rest of the string so we'll need to reset and keep iterating now we reset and start looking at the first e we set the start word to be the first two vowels we see in the string which are now ea which is highlighted in green we then find the middle vowel which is the next e then we look for start in the rest of the string which we do find here and can return if we iterate through all the letters and don't find any valid start then we know there is no valid spell and we can return nothing here's the full solution i used python but you can use any programming language you are comfortable using notice that our code is structured a little bit differently from the pseudocode i presented earlier for simplicity we first find a list of all the vowels and iterate through that instead of the entire string if there's fewer than five vowels we know there cannot be a valid spell so we can immediately return otherwise we iterate through the vowels as we did in the pseudocode now let's look at the runtime complexity of this code let n be the length of the given string we first call find all vowels which requires iterating through the string which takes o of n time after that we have a for loop which iterates through the list of vowels which is also of n in the worst case in each iteration of the for loop we iterate through the entire string once when we look for the start word and check if it exists in the rest of the string after the middle vowel thus the total runtime is o of n squared i just wanted to cover one more alternate solution which is using regex you can use regular expressions to check whether the string conforms to the given format based on the constraints we covered earlier feel free to refer to the regex documentation for more details on how this works the runtime of this is o of n where n is the length of the string note that if we're constructing this for every test case this could take up to o of c to the n construction time and space where c is the size of the regex make sure to check out the full proper analysis on the problem dashboard for more details thanks for tuning in next up is shahed who will walk through the problem parcels [Music] hello everyone i'm shahid and i'm a software engineer at google i'm currently working in network control sre and when i can manage time i try to collaborate with the coding competitions i used to participate in google's coding competitions during my college years today i am going to discuss the problem parcels let's go let's discuss the problem description first you are given an n into n grid which contains either zero or one one means there is a delivery office and 0 means the place is empty distance between two squares is their managing distances which means the summation of the difference between their x axis and y exists for any square the minimum distance to a delivery office is the minimum amount all the distances to delivery offices let's call this mdtd the minimum distance to delivery the minimum overall derivative for the company will be the maximum among all the mdtt additionally we can build an extra delivery office anywhere we want so we want to build the delivery office in such a place so that the overall delivery time can be as minimum as possible let's check some examples in the first example you can see we marked the minimum distance to a delivery office for each square if we build our new delivery office in the blue marketplace that the maximum amount all these values reduces from two to one so for this given grid the final answer will be one [Applause] for the second example you can see that building an extra delivery office does not reduce the maximum value so the final answer is still one and we might want to skip building that extra delivery office let's talk about the solution shall we for a small test the dimension of the grid can be at most 10 by for the larger test it can be at most 250. for a small test we can calculate the distance for each square for every delivery office and find the minimum among them now for every empty square we can build a delivery office and can check whether it minimizes the distance to a delivery office for each square alternatively we can build delivery office in an empty square and run a unique first shortest path algorithm called breadth first search to find the minimum distances to a delivery office for each square for the optimal solution we can do is that we need to find the minimum distances to delivery offices for all these squares so the squares have in the delivery office needs zero inits of time for delivery we can treat the squares as sources and run a break from search algorithm thus will get all the minimum delivery time or distance for all the squares we can build another delivery office that could reduce the maximum of these distances right let's try this way if we can check whether it's possible to build the extra delivery office in such a way that we can reduce the maximum among these distances to at least d if we can do that for particular d then we can definitely do that for our d plus one two so we can do a binary search to find the minimum possibility where it's possible to build the delivery office to achieve that particular answer let's walk through the course this is the breakfast search algorithm to find the minimum distances for all squares to any source here we are passing the sources in a queue and calculating the mdtd the distance from the sources for all squares eventually we are returning the maximum among them which would be the minimum overall delivery time for the company if we don't build another delivery office and here is the binary search code to find the minimum delivery time in the function possible we are checking if it's possible to build another delivery office so that the minimum overhead delivery time is at least mid but how do we check if it's possible to achieve the answer for a particular d we can write the formula for magnetic distance in a bit different way so if a point is fixed let's say the point b is fixed then the ax plus ay the summation of the point x coordinates is contributing to the answer the maximum of the sum can contribute as the largest possible integer and the minimum of the sum can contribute as the smallest possible integer either of them could contribute as the largest integer as we are taking the absolute value value here similar for a x minus a y the difference between the coordinates this is contributing similarly here is the code for checking if a particular d is achievable or not in the first iteration we are calculating the minimum and maximum value for i plus j and i minus j among all the squares whose mdtd is greater than d in the second iteration we are building a new delivery office in each square and checking whether it is possible to decrease the minimum overhead delivery time under the given d the time complexity for the breakfast search is order of n into n if the initial grid contains a single delivery office then the maximum possible answer can be order of maximum between n and m so the complexity of possibility check with the binary search will be order of n into m into log of maximum between n and m the overall memory complexity will be order of n into m the full problem analysis is available on the dashboard check this out this concludes the problem walkthrough for our coding practice with kickstart session for today we hope you had as much fun as we did let us know in the comments and lizzy is going to close us out that's it for problem walkthroughs today thank you for your great engagement and participation if you have any remaining questions be sure to ask your peers in our facebook group where you can connect with the community and receive latest updates about kickstart in addition to this video be sure to check out our full analysis on the dashboard which you can find by clicking on the view dashboard button at the top right of this page when you get to the dashboard select whichever problem you'd like to review and then click on the analysis tab you will also be able to download the input and output files at the bottom of the page finally be sure to check out our schedule page at g.co kickstart and apply what you've just learned in our upcoming rounds in future practice sessions each round starts fresh so you can participate in as many rounds as you're able to the more you practice the more you'll improve so why not give it a try and that's it thank you again for taking part in coding practice with kickstart hope to see you in future rounds we hope you had fun until next time bye you