My Experience With Google Online Challenge 2021

As a prospective Information Systems student in University, I applied for multiple Software Engineering internships to immerse myself in the tech scene during my long break before matriculation. As neither my portfolio nor relevant experience weren’t particularly prodigious, I did not receive any replies from all the companies that I applied to and started to lose hope. As I was about to give up, I received an email from Google, the company I least expected would get back to me.

The email subject read “Google’s Online Challenge – You’re Invited”, followed by “Thank you for your interest in the Google SWE Internship opportunity (South East Asia). To help better understand your coding capabilities, we would like to invite you to participate in Google’s Online Challenge. We hope you’re excited!”. I was ecstatic, of course. The email laid out the format and details of the competition, as well as providing practice questions and links. I had exactly 5 days till the challenge began, and I got right to work. 

Practice

I am not a prodigy coder by any means, but I have basic to intermediate knowledge in C, Python, Swift, as well as Data Structures after completing HarvardX CS50 Introduction to Computer Science and completing some projects on my own. I would highly recommend people who are interested in trying their hand in coding to take this course. The course has amazing teaching quality, challenging yet satisfying (once you solve them) assignments and heck, it even provides you with a free e-certificate by Harvard once you complete the course.

Anyway, back to the practice questions. Google uses the platform HackerEarth to screen candidates, so we are provided with questions to attempt on the platform to familiarise ourselves with the process. The rules for this challenge were simple:

Practice Question 1

The first question I was faced with is a summation question, where each test case provided through the command line had a query type and relevant parameters. For the first query type, I had to perform a pairwise summation on the array of integers given the range and print it out. For the second query type, I had to replace an element in the array by another element, given the index and the new element.

Sounds simple right? I thought so too, until I happily wrote and ran the program in Python since it was the syntactically simplest one out of all the languages and ran into a problem, time limit exceeded. Turns out there is a time and memory limit for each test case. This question’s time limit is 1.0 second per test case and my Python program took 5.0 seconds for the simplest test case. Each question also came with ranges for each parameter that is given on the command line. For example, the size of array of integers is simply stated as ⋝ 1, which can mean the program is potentially performing summations on millions of elements.

To compound that, I was facing troubles trying to obtain inputs from the command line as I did not have prior experience with that. I only found out that boilerplate code was actually provided for in the editor for Python 3.6 and below but not 3.7 after tinkering around for 20 minutes, great. 

I ended up switching to writing in C, one of the most performant languages. By then, there was only 20 minutes left on the clock. I submitted my solution in C but lo and behold, 50% of my test cases had a run time just shy of 1.0 second (1.02 seconds). I decided there was nothing I could do but move on to the next question.

Practice Question 2

The next question was finding the number of combinations of the letters in the array of 5 different letters for a given length of word with replacement, without repetition of combinations, alphabetically arranged. Again, easy peasy, I thought. I went on to import the standard library Itertools from Python, ran the built in combinations_with_replacement method and calculated the number of combinations. The page loaded for a while, and screamed that I have used about 5x the permitted memory and my program exceeded the runtime limit. I attempted to write it in C, but unfortunately ran out of time.

I racked my brain for the next 5 days during my free time and scoured the web for solutions for practice question 2, but to no avail. I went on to practice some problems online on kickstart and prayed for the best.

Challenge Day

The day of the challenge had arrived. People participating had a 9 hour window to attempt the challenge once. I did some last minute revision on C syntax, data structures and started the challenge at 6 pm.

Question 1

The first question was finding the least amount of cost to connect a new city to a group of cities, given the cost of connecting each city to and from one another. Pairs of integers representing the connections of cities were provided in the command line. I just had to find the eligible cities with no connections to it, connect the new city to it, and calculate the minimum cost required to do so. I didn’t know if it was just me or the stress of seeing the timer countdown, but I took much longer than expected to understand the question.

By the time I finished the question in Python (which was a mistake in hindsight given how I had performance issues for both practice questions), 35 minutes had lapsed and only half the test cases were accepted. I had to move on to the next question.

Question 2

The second question was appending the absolute difference between adjacent pairs of integers in an array into itself until all the absolute differences of integers are present in the same array, then returning the Nth highest element. For example, [1, 2, 3] would give 3 if N was 3, and [3,5,6] would require some sort of loop to expand until 2, 1, 4 are appended into the array. Again, I made the same mistake of using Python, thinking I had time to translate it to C once I got the hang of the question. By the time I completed my solution and ran it for the first time, I had an “index out of range” error, and 5 minutes left on the clock. I tried to salvage it but it did not work out.

Thoughts

Clearly as you can tell from my account, I was not prepared enough for the challenge and will need far more practice with problems and time management. It was not the difficulty of the questions that stumped me, but the level of optimisation and syntactical mastery needed.

I’m also 99.9% sure Google won’t be contacting me for the next round. It was however a great experience in the competitive coding scene, providing with even more motivation to improve. Do you have any thoughts or experiences you would like to share? Leave them in the comments below, I’ll read and reply to every one of them.