Google Kickstart 2020
2020 Google Kickstart Round B
First time join Google Kickstart experience
Google Kickstart is algorithmic challenges developed by Google engineers anually for coders around the world the chance to develop and hone their programming skills through online-hosted competition rounds.
The three-hour rounds feature a variety of algorithmic challenges, all developed by Google engineers so that you get a taste of the technical skills needed for a career at Google (the top competitors from our Kick Start rounds may be invited to interview at Google!). Our rounds are held regularly throughout the year at different times so they are easily accessible to coders everywhere. Each Kick Start Round is open to all participants, no pre-qualification needed, so you can try your hand at one or give them all a shot.
When each round is open, the three hour countdown begins and you’ll compete on our website solving algorithmic and mathematical problems. Following the round, you can check out your rankings and the round analysis. If you were a top competitor, you may be contacted by Google for a chance to interview.
Kickstart 2020 has passed 2 rounds A, B. Round B 2020 just ended several hours ago. This round I think Google engineer focused more on logical solving and analysis rather than so much hard & fancy algorithms.
The difficulty level is ranging something in between medium level but of course to get good rank, you have to be fast enough than not just solved it.
Started after 10 min the competition started, top 10 rank has already finished 3 problem set, which mean you have to be fast, get a template already there, open necessary tabs and be quick.
Now, let's take a closer look on each problem.
1 is Bike Tour (5pts, 7pts).
This is an easy problem. Time complexity is O(N), space complexity is 0(1). You can keep track of 3 pointers for before, after and current position.
Solution is good for both small & large test set. Analysis solution is now available. We can see this problem is a mix of the ability to tranverse through the array
and ability to know how to keep track of and compare 3 neccessary data to check if it is the peak. We can recall a similar problem "Find a peak element" (https://www.geeksforgeeks.org/find-a-peak-in-a-given-array/) but this Kickstart problem is a little bit easier.
Also, Introduction to Algorithms has a dedicated section for Peak Finding for 1D & 2D, and using Divide & Conquer technique. And of course, we can solve Bike Tour problem in O(Logn) using Divide & Conquer technique
PROBLEM 2 is Bus Routes(10pts, 13 pts)
Problem 2 is not hard to see the logical patterns. On Analysis solution for this solution online, there are brute force and optimized solution. At the first dry run on all sample test case, we can see the logical patterns. Of course you should try edge case as well.
Brute force has time complexity O(DN) and passed for small dataset but time out for large test case. More optimized for naive solution is Binary search on the range from 1 - D to find the largest good starting day P.
Time complexity now reduce to O(N log(D/X1)) which restrict the search to 1X, 2X, 3X, etc. Space complexity is the same.
The more optimized solution is O(n) by working on the problem backwards. Intuition is since we want to find the latest day we can think of taking last bus at the day closest to the last day. Limit is D.
So it is the largest multiple of Xi that before D.
This problem is combination of the ability to think of problem from multiple perspective, forward, backwards, middle, up to one point, etc. Also taking into account of one intuition of reduce the time complexity from O(DN) to O(N log D) and to O(N)
Lastly, the problem test the ability to think the similar patterns which is rather than give you this is the modulo, we will hide the modulo, by give you 1X, 2X, 3X.
PROBLEM 3 Robot Path Decoding (11pts, 16 pts).
I think this is a very good problem that is the combination between many techniques and test a lot of aspect in logical thinking. Not so hard to understand at the first read.
The brute force solution(small test set) is to compute the whole direction string and calculate the position by taking one step at a time.
The optimized solution is linear time complexity. For test set with number of moves is exponential. There is no huge thinking to move from small test case to big test case solution since there is only one state of the problem which has so-called "bottle-neck".
We can not execute the moves one by one. So, expand the whole direction string seems to be the "bottle-neck". Let's now consider back this attributes from solution 2(E), observation is that E is repeated 2 times. So rather than, move one by one, we can just find the position after sub move 2E,
Now how to computer the whole instruction string, we can use recursion to change the robot position after each sub instructions.
"Since the planet is a torus, the first and last columns are adjacent, so moving east from column 109 will move the rover to column 1 and moving south from row 109 will move the rover to row 1. Similarly, moving west from column 1 will move the rover to column 109 and moving north from row 1 will move the rover to row 109"
We will convert to logical algorithms with mod 10(9).
To come up to optimized solution in the problem is not hard, since you just need to solve the "bottle-neck" by optimize the operations.
To solve this problem, you need to get familiar with similar problem is Check for balanced parentheses in an expression (https://www.geeksforgeeks.org/check-for-balanced-parentheses-in-an-expression/). Of course, they also give the link to this, which mean a lot of problems has been modified from GeekForGeek,the ability to make use to data structures like Stack, String, 2D array. Recursion, String processing.
Recursion has been tested in the solution mostly.
PROBLEM 4 Wandering Robot (14pts, 24pts)
I think this round is designed by a Google engineer who works in IoT/ Embedded/ Robotics since there are almost 2 questions related to Robot(JFF).
This is a hard question for large test case. For small test case, this problem is something inbetween medium level.
The problem is typical Dynamic Programming, which should be considered at the last round. Time complexity is O(W × H) but for the large test case, it will fail. My solution is quite similar to Google solution which has the same time complexity. We can use DP to compute all the possible
paths from top left to bottom right of the matrix, and keep track of the path that not include to the area of rectangular subgrid of squares has been cut out from the grid since "The robot will randomly choose to either move to the square directly to the right, or to the square directly below it with equal probability."
The last problem tested your skill in Dynamic Programming & Probability.
I have not been able to come up with the most optimized solution for the large test case although get intuition that this will be a math solution for the most optimized solution for this problem, but using single binomial coefficient (https://www.geeksforgeeks.org/maths-behind-number-of-paths-in-matrix-problem/). Also we have to handle floating point issue to store every huge number in their log representation which again, test your knowledge of not only data structures & algorithms, but also knowledge of computer architecture
The bottleneck of this problem is that you should focus on the fact of moving down and moving right share the same possibility 0.5, at least I have taken into account this attribute fact, but coming up to Binomial coefficient problem has neven been practiced by me, which need to practice in the next round of Kickstart contest.
Solving 3.5/4 get rank after 136, which is good enough to get a call from Google. At least, I need to aim at solving all 4/4 which no time constraint, will for sure enough to pass on site Google interview.
