Coding Practice with Kick Start 2022 – Session #1 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 hi everyone my name is chidara olivier and i'm a software engineer at google i work on chronet a high performance library that brings chrome networking stuff to native apps i'm going to walk you through centauri prime where we tried to discover who wrote the kingdoms in centauri be sure to read through the problem statements carefully and to take note of the important points we note that there are two test cases a kingdom is ruled by alice if the kingdom's name ends with a vow ruled by nobody if it ends with letter y or by bob if it ends with any other consonant take note of the impute and output formats for the input the first line has number of kingdoms and next consecutive lines have the name of each kingdom which each started with a capital letter for the output take note of the full stop and capitalization check out the coding section in the faq on the kickstart site for details on how to read impute and output before writing out the code consider figuring out a sudo code for your solution first this personally helps me concentrate on the solution before thinking about syntax i originally thought to create a high set for both the vowel and the consonants then for each kingdom get the last character check if it's a consonant a vowel or the letter y in that order the problem i noticed with this approach is that y is also a consonant so my solution would fail for kingdoms ending with letter y also i don't need a high set for the consonants looking at my second pseudo code i check for the vowels check for the letter y and the rest which are the consonants what would be the time and space complexity of this implementation let's look at it initializing the set takes a total of 10 time and speeds because you're adding the 10 values this is like constant time for the get ruler method getting the last character of a string in java is constant time and the content method of the high set is also constant time thus the whole method takes a constant time congrats we've arrived at the pretty optimal solution i'm not satisfied with my proposed solution so i move on to the code implementation i used java for the implementation but you can use any of the supported languages on the platform i initialize a high set with the vowels then i created a separate method get ruler that takes in the kingdom as impute gets the last character compares it and returns the ruler don't forget to test for the capital and small letter y since the kingdom's name can be a single letter in the main method i read in the imputed scanner then look through all of the kingdoms for each kingdom i call the ghetto method and print out the output in the specified format remember this is only one way you can solve the problem there are several solutions to this problem be sure to check out the full solution for centauri prime on the dashboard using the link on the screen thanks for watching stay tuned to hear my colleague kanika break down the next problem bye [Music] thanks chidara i'm kadika garwal and i'm a software engineer at google i'm a part of google's ads team i'm working on building a new privacy-centric future on browsers where users get amazing privacy online today i'm going to walk you through the problem edge index from the coding practice with kickstart session so let's jump in we are solving an edge index score calculator problem this is an important metric to measure the citation impact of the author as per the problem statement each index of a researcher is the largest integer edge such that the researcher has etched papers with at least 8 citations each read the problem carefully it's also important to look at the input output format carefully in this problem we need to calculate the h index after each paper written by the author and this makes the problem interesting we get t test cases and for each test case we get two lines as an input the first line tells the value of n the number of papers written by the author and the second line contains the number of citations each paper has received let's look at an example input we have 2 next line 3 next line 5 space 1 space 2 and so on the first line indicates the number of test cases which is 2 so t equals to two the next two lines are the input for the first test case n equals to three which is the number of papers published by the author and then the list of citations received which is five comma one comma two output format for each test case output one line containing case hash x colon y where x is a test case number starting from 1 and y is the space separated list of integers please take note of the space and capitalization of the word important to note we need to calculate h index as each new paper gets added so don't jump straight into writing the code first think about the pseudo code do a dry run to see whether the algorithm works also during the dry run figure out the time complexity of your algorithm after understanding the problem statement the first algorithm that comes to my mind is a brute force approach where you calculate h index for the list seen so far every time a new paper comes brute force approach to calculate h index is straightforward start with the highest possible h index and check whether the condition set is satisfied and the condition is researcher has h papers with at least h citations each and if the condition is satisfied then that's the answer else check for h index with one lesser value and keep on repeating it until you reach one so here is the pseudo code assume we have a function score x which returns the number of papers in the set with at least excitations now for each test case set h index to zero i trade over n check for j value between i plus 1 which is the number of paper published so far and current h index call score function and if score of j is greater than equals to j that is if the number of papers with j citations are greater than the or equals to j if yes then the condition is satisfied and update the h index value to j now this is a brute force approach calculate its time complexity and then think about what you can improve in this approach first instead of checking till 1 we can check until the previous found h index and second we can improve on the maximum h index we want to store so it could be limited by n which is the number of papers published by the author let's look at the implementation we are reading input in the main read input test cases t for each test case read n which is the number of papers published by the author read citations received for each paper and store it in citations list and then call calculate h index function now in calculate h index function first initialize the list a of size n plus one which stores the count of each of the citation numbers we have seen and is used by the score function to calculate cumulative sum for any x initialize an empty answer list set h index to zero i trade over n update list a set j to 1 plus 1 which is the count of papers published by the author so far check for j value until the previously found h index call score function and check if it satisfies the condition and if yes set the h index to j else reduce the j by 1 and check the condition again and finally append h index to the list run the code and check whether it's reading the inputs correctly and also returning the outputs in the right format try to write a modular code because that helps you to modify just the core function and you can use the rest of the code for a more optimized algorithm so let's look at the time complexity of this algorithm time complexity of score x is order of max a that is the maximum citation value that we have seen and we can limit that by n that is the number of papers published by the author and we are calling the score function n times hence the overall time complexity is order of n square now let's think about a more optimized approach think of an algorithm that could improve the score function one important thing to note is once we have a certain h index we don't need to keep papers that have citation value lesser than the current edge index so we need a data structure that could store citations in some order as we receive them and also which allows us to remove the citations easily and we can use min heap for that once you have come up with a better approach follow the same steps as mentioned earlier write a pseudo code execute a dry run to check whether it's working or not and when you're satisfied with it start implementing the algorithm so let's look at the pseudo code first for each test case set h index to zero initialize an empty min heap iterate over range n check current citation value is greater than the current edge index and if yes push the current citation value to the main heap remove all the citation numbers from the mean heap which are not greater than the current answer and finally if the length of the main heap is greater than the current h index plus 1 then increment the h index by 1 and that is the answer so let's look at the implementation we need to modify the calculate h index function min heap is initialized to an empty list initialize an empty answer list set h index to 0 i trade over range n now check if citation of i is greater than h index if yes push a of i to min heap while min heap exists check if the top element is less than or equal to current h index if yes remove it from minheep and repeat these steps until either the main heap is empty or the top element is greater than the current h index now if the length of min heap is greater than equals to h index plus 1 then increment the h index by 1. append the h index to the answer list return answer list once you have iterated over n papers so let's look at the time complexity of this solution mean hip takes order of login time for an insert or remove operation and a number is added or removed at most once in our algorithm so we need to calculate min hip a max of n times and hence the overall time complexity is order of n times log n so that wraps up my explanation of h index i hope you enjoy solving the problem now over to brendan who will walk you through solving the problem hicks thank you [Music] hi everyone my name is brendan and i'm a software engineer at google i help support our mobile developers to deliver awesome user experiences on google's android and ios apps before joining google i always look forward to participating in the google code jam competition every year unfortunately now that i've started working here at google i'm not allowed to compete but that won't keep me away i'm here to walk you through the problem hacks let's get started i'll assume you've already taken a look at the problem statements to me the critical pieces of any problem statement are the inputs outputs and limits in this case the inputs are an n by n array representing the rhombus shaped board and it also includes n the output is one of four possible board states blue winds red wins nobody wins or impossible and the limits indicate that the maximum port size increases between test sets specifically n less than or equal to 10 for test set 1 and n less than or equal to 100 for test set 2. be sure to read the entire problem statement carefully and take a look at the sample inputs and outputs some other key points from the statement that jump out at me are the player to start first is determined randomly the game ends immediately when one player wins and note that the four corners are considered connected to both colors consider what it means for hexes to be connected notice that the square grid input doesn't quite capture the relationship completely we need to use the picture provided in the problem statement as another example consider hexes labeled one through nine in a three by three grid notice the central hex five is only connected to hexes two three four six seven and eight it is not connected to hex one or hex nine try coming up with your own sample inputs to test your solution such as this s-shaped winning path for blue again notice how the text representation of the board looks symmetric for blue and red but it is important to see that the center two hexes with blue stones are connected whereas the redstones are not let's discuss a solution using a graph traversal approach starting from the left edge of the board we can visit each adjacent hex to see if it continues a connected path for blue if it does repeat this process for its adjacent hexes and so on keeping track of which hexes have already been visited this is the flood fill algorithm which is used to map out a connected set of nodes that share a particular attribute after filling out the board check if any hexes on the right edge have been visited to see if there is a fully connected path if there's no connected path for blue we repeat this process for red going from top to bottom note that it is not physically possible for both blue and red to have a winning connection so we don't need to consider that case here are some code snippets in check winner we initiate the recursive flood fill algorithm for the top and left edges when the board has been traversed we check the results the board object here is a two-dimensional n-by-n array represented by a list of lists of characters each of the nested lists corresponds to a row in our original put input in flood we mark the current hex as visited by mutating the board here we replace the entry in the board object with a lowercase letter to represent this then we visit each of the adjacent hexes which match the color of interest by making a recursive call to flood notice that we skip over any hexes that have already been visited since we traversed the entire n by n board the time complexity of this algorithm is big o of n squared but we're not done quite yet as an aside let's think about what makes a board state valid or invalid if there's a connected path for either color try and figure out which stone the winner could have played last in the first case blue could have played their seventh stone in the top right hex to win the game note that before that stone was played there are no connected paths on the board in the second case red has played more stones than blue so red must have gone first also played the final stone but blue already has a connected path after placing their sixth stone so red would not have been able to play their last stone therefore the board state is impossible in the last case blue has a connected path so they must have placed the last stone however removing any of blue's stones does not break the connected path between the left and right sides of the board so blue must have already won before the last stone was placed therefore again the board state is impossible here we bring everything together first we count how many stones have been placed by each player and make sure they've been taking turns properly then we check if there's a connected path note that we make a copy of the original board since our flood fill algorithm mutates this object and will need to refer to the original later on if there isn't a connected path then nobody wins otherwise whichever player has a connected path must have placed the last stone for the sake of discussion let's assume that blue has a connected path for the board state to be valid blue must have placed the last stone and that stone must have changed the board state from nobody wins to blue winds we verify this by recreating the original board with one arbitrary blue stone switched to an empty hex to represent the board state before the last stone was placed and checking again if there is still a connected path this process is repeated for each stone or until a valid board configuration is confirmed this increases the overall time complexity of our approach from n squared for the check winner method to n to the four for the solve method since we need to call checkwinner on the order of n squared times during the verification step this end to the four approach is sufficient if you're using a faster language like c plus or java but if you prefer to use a slower language such as python like i do you might need to run your code using a pi pi interpreter to ensure it completes in the allotted time our flood fill approach ends up processing the same or very similar board many different times this isn't ideal instead i'm going to present a modified approach that results in a faster overall run time we start from the southwest corner where the blue and red board edges meet follow a path between the hexes always keeping blue stones on the left we can treat the edges as colored stones for the purposes of tracing the path we continue to follow the path until the east side is reached then blue has a connected path or until the north side is reached then blue does not have a connected path one of these outcomes must occur at a high level imagine we are standing on a giant board walking between a pair of hexes with a blue stone on our left and a redstone or empty hex on our right and we're looking ahead at a fork in the road with a third hex ahead of us referred to as next hex in the following snippets if the next text has a blue stone in it we go right otherwise we go left again always keeping a blue stone on our left here are some code snippets to demonstrate the revised path tracing algorithm the blue path south method describes the start and end conditions of the path and returns a set of blue stones that were traced it calls the step method which selects the correct hexes to navigate between which in turn invokes the getnexthex method in the interest of time let's not dwell on the detailed implementation but if you're interested in trying out this alternative approach to solve the problem feel free to refer back to these snippets after we get through this walkthrough if blue has a connected path let's call the set of blue stones that were traced on the path south stones before declaring blue the winner we must first check that a connected path could have not existed on the previous turn to accomplish this we trace a similar path on the north side of the board let's call this set of blue stones north stones if south stones and north stones share any common stone then this stone could have been played on blue's last turn and blue is the winner in other words removing the stone would break all connecting paths if the intersection is empty then removing any blue stone would not break both the north and south paths so the board state must be impossible here we simplify the verification process by performing the n squared path tracing algorithm twice and then just comparing the contents of two sets let's go over some examples using this new approach start by padding the board so we can treat the edges of the board as colored stones and also so we always have the same valid start positions for the paths no matter what stones have been played in the first case we construct both connected paths and notice they share a common stone in the top right hex of the original board by removing the stone it is clear that both the north and south paths are broken so this must have been the last stone that blue placed in the second case notice how the connected paths do not share any common stones removing any stone will not break both connected paths as discussed before this is an impossible board state you can convince yourself that inclusion of the edges as stones in the path do not affect the outcome of this approach in the third case we aren't able to reach the east side of the board so there's no connected path for blue again the overall solution is similar to our flood fill approach but we no longer need to loop over each hex to validate the solution i'll leave it to you to come up with the count stones and pad board functions and the modified path functions to find the north path for blue and the east and west paths for red with this simplified method for validating the solution this path tracing approach gives us an overall time complexity of n squared much better than the n to the four flood fill approach thanks for walking through that problem with me the full analysis for this and all of the problems from today's session are on the dashboard at the link here i'm going to hand the mic over to huni who's going to explain our last problem for today happy coding [Music] thanks brendan hi all my name is yani and i'm a software engineer at google search i hope you had fun solving all the problems from our 2021 contests i'm going to walk you through the problem milk tea let's first begin by reviewing the problem statement the milk t problem was asking to find the best matching binary string there were two sets given preferences which contains the binary strings that the result string should be matched to and forbiddens which contains the binary strings that the result string should not be equal to the better matching binary string is the one has the lower number of different bits in the same position for example given the preference is set with 1 1 0 0 one zero one zero and zero zero zero zero and the forbidden set with one zero zero zero the best matching binary string is one zero zero zero which has one diff from all the elements in the preferences set which sums up to three dips however since this binary string is included in the forbidden set the best matching binary string is one of one one zero zero one zero one zero or zero zero zero the answer is the number of differences which is 4 in this example let's have a look at the symbols and the limits n is the size of the preferences set and it mixes to 100 m is the size of the forbidden set and max is to one hundred or two to the power of p minus one we can simply think of this value as max hundred p is the length of the binary string and mixes to one hundred so how can we find the best t finding the single bestie is very simple we can just take the most awkward bit for each position for example given 1 0 1 0 1 0 0 1 and 1 0 1 1 as preferences the most occurring bit for the first position is one with all the preferences having one at the beginning same for the second position zero for the third position two of the preferences have one and only one of the preferences has zero so one takes the third bit position same thing for the last bit positions one of course the best t found by this method might fall into the forbidden group and cannot be trusted but by looking at this approach we can notice something very important each bit decision is independent from each other choosing a bid for one position never affects what bit to choose in another position making use of this idea we can build up bits one by one that is given the binary string of length l minus 1 we can generate the l bit without considering the previous l minus one part we still have to deal with the forbidden set though but this is also very simple the size of the forbidden set is n and if we make m plus one t's at least one t is not in the forbidden set now using what we found let's set up an algorithm that solves the problem our goal is to make the best m plus one t's iteratively to do this we first start with a set s0 with an empty string as its only element in the second step for each binary string b i in s n minus 1 add b i plus 0 and b i plus 1 to s n third we filter out the best n plus one t's in sn we repeat steps two two three until we get sp finally we can have the best d in sp that's not in the forbidden set and its score for example given the preference is set 1 1 1 0 1 1 0 1 and 1 0 1 1 and the forbidden set 1 1 1 1 0 1 1 1 1 0 1 1 and 1 1 0 1 we have to iterate until we reach s4 as 4 is the length of the binary string so we start by s0 which is an empty string this empty string expands to 0 and 1 in s1 then 0 expands to 0 0 and 0 1 and 1 expands to 1 0 and 1 1. in the next step we're supposed to have eight elements in the set as each element in s2 gets expanded with the following 0 and 1 which doubles the set size however m which is the size of the forbidden set is 4 and we only leave n plus 1 which is 5 elements in the set therefore we score all the 8 elements and leave the top 5 elements in the set and that's how we generate s3 same thing for s4 expand each element score them and filter the top n plus 1 elements since the length of the t binary string is 4 we can stop when the s4 is generated now we loop through the elements of s4 from the highest matching to the lowest in this case 1 1 1 1 is the highest matching with the difference of 3 followed by the other strings with the difference of 4. with this order we're going to check if the string is in the forbidden set or not 1 1 1 1 is in the forbidden set so we exclude it same thing for 0 1 1 1 1 0 1 1 and 1 1 0 1. now 1 1 1 0 becomes the first t that's not in the forbidden set and makes the answer of this example 4. let's have a look at the time complexity of this approach it is always a good practice to check the time complexity before getting into coding otherwise you might end up finding yourself pouring all the time writing a code that exceeds that required limit now let's start thinking with the key symbols that i've written down on the top right corner the first step obviously takes a constant time as it's just the declaration and adding a single element the second step loops through all the elements in the set so the time complexity for this step follows the size of the set which is in the order of m for the third step we need to split it into two little steps since we have to find the besties we need to score and sort the t's to score the binary strings we need to look through all the strings in the set which is in the order of m compare it with all the strings in the preferences set which is in the order of n and when comparing we need to look through all the bits in the binary string which is in the order of p this results in the order of m and p the next little step sorting the binary strings and selecting m plus one of them follows the time complexity of the sort algorithm which is in the order of m log m therefore the time complexity of the whole third step becomes the order of m times n p plus log m since the step 2 have the time complexity of o m it is ignorable and the time complexity of the step 3 is dominant we need to repeat this process until we get sp so the order of p is multiplied resulting in the total time complexity of steps 2 to 4 the order of mp times np plus log n in the last step we need to look through the elements in the set and check if it's included in the forbidden set looping through the elements takes o n and checking the forbidden set takes omp resulting in o and mp this makes the time complexity of repeating steps 2 to 4 dominant and the total time complexity of this solution becomes the order of mp times np plus log n normally we calculate the time complexity with the maximum limit of inputs when the result is lower than 100 million we consider it faster than one second in this case the time complexity is calculated exactly to 100 million so we can think that it takes a bit more than one second but is enough as the time limit for the solution is 30 seconds therefore this solution will work with the problems data set and we're good to code i'll be coding with java but the language is not that important here as i'll be using the basic features that most of the other languages also support so please focus on the logic instead of what i write word by word first let's define the t the t itself is obviously a string but we'll have to score and sort the t's so let's group the score and the t into a single score t class and make it comparable by score now we can easily sort the t's using the score as a key next let's implement the method that scores the t as we saw in the algorithm diagram we not only need to score the strings that are fully generated but we also need to score the binary strings during the generation process which will eventually work as a prefix of the complete binary string so we need a method that scores the prefix by comparing it to the preferences set in this code the compare method compares the prefix and the t and returns the number of different bits the score method sums the compare method results by calling the method with the prefix and the elements in the teas array which will be the preferences set now let's implement the algorithm the first four steps in the algorithm can be implemented like this each set in the generation process is implemented in a list so that we can sort with the t score we add a t with an empty string and a zero score as it has nothing to compare it has no differences then we loop until we reach sp which is what the for loop is doing the length variable here is the length of the t string and will allow us to generate the t set towards the peep generation inside the loop we loop through the t's in the previous generation and expand it the expand method is introduced in the next slide but to demonstrate it it simply appends 0 and 1 to the given prefix and adds it to the next generation once the expansion is done we sort the list and only select the first n plus one t's the size variable here is what holds the value of n plus one the expand method is very simple it appends zero and one calculates their scores by using the score method we previously implemented make score t instances and add them to the pest list lastly we can find the best dnsp that's not in the forbidden set by simply iterating through the generated list and check if it's included in the forbidden set or not by implementing the forbidden set in the set data structure the code is simple as this now we're done with coding we have implemented the algorithm and the problem is solved however there is one more thing we can do to reduce the time complexity we know that the bits are independent to another and the differences gained by choosing one bit are always the same if you choose the same bit in the same position with this we can build a 2d array having the number of ones and zeros in a specific position with the preferences that we can build an array like this code now instead of calculating the score of the prefix t on every loop we can simply reference the array and accumulate the score this approach separates the scoring logic from the loop therefore the time complexity becomes p n for preprocessing plus p m log m for looping and sorting resulting in the total time complexity of p times n plus m log n so this is the end of the milky problem walkthrough did you like it i hope you had a wonderful 2021 studying improving your coding skills let us know in the comments if we helped you have a good coding experience now back over to lizzy who is going to close out today's session 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 and 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