Google Python Challenge - He cake is not a lie
The other day I was googling some Python stuff and an invitation to a Google code challenge appeared, (the so called**_foo.bar challenge_**), I am not fond of code challenges or leetcode interviews for a number of reasons, but curiosity got the best out of me and I decided to check it out, here’s a guide through the interesting setup and first challenge.
⚠️ Spoilers/Warnings: If you get an invitation and decide to partake, I encourage you to try your best to solve the challenges by yourself, least you ruin your opportunity for an interview, having said that, the challenges do get progressively harder, I myself only reached level 3 (out of 5) before running out of time and admitting to myself that I'd need to become really good at certain advanced Python and CS aspects to sail through the later parts, so if anything it's an interesting way of measuring where you are at in your coding career or skills as seen by Google, this first problem is really just an introduction and is probably bound to change in the future.
The Setup:
You get an admittedly cool looking IDE that behaves like your regular terminal, type help and the relevant commands appear, you can open a code editor on the right after requesting a challenge and navigating to the solution file solution.py …
NOTE: You don't need to code your solution in the web IDE, I did all of my coding on Atom and then copy pasted into the web IDE, be aware that your development environment must match what they require or else you might not have a valid solution, so in this case they were asking for Python 2.7 and I was running Python 3, my solution was to make a new environment with python 2.7 and use that, I was using Anaconda where it's pretty easy, but you might need to follow other routes.
The Premise:
The whole challenge is wrapped in a scifi-ish story that you might or might not find amusing, regardless it’s an extra layer that you have to go through to understand the code questions, here’s the first one ( we’ll revisit it later ):
You are additionally given 2 test cases and the corresponding solutions:
# solution('abcabcabcabc')
# 4
# solution('abccbaabccba')
# 2
A big gotcha is that there are other Hidden Test cases that you must pass in order to solve the question, what kind and what they are is up to you to find out or imagine, this along with the confusing problem descriptions is in part what makes this challenge difficult, once you have a potential solution you can **verify** it and see how it does, your final solution won’t be accepted unless it passes all tests.
One last but critical constraint is **Time**, you are given a set amount of time and a counter ( a couple of days in this case), if you decide to leave the challenge and close your window, the timer will keep on ticking, so you also need to sign in so you don’t loose your progress, you can find the challenge page again by googling for it or saving a link to it.
The Problem
Let’s now turn to this specific problem, let’s reiterate (bolded the relevant bits) and restate :
The cake is not a lie
=====================
Commander Lambda has had an incredibly successful week: she completed the first test run of her LAMBCHOP doomsday device, she captured six key members of the Bunny Rebellion, and she beat her personal high score in Tetris. To celebrate, she's ordered cake for everyone - even the lowliest of minions! But competition among minions is fierce, and if you don't cut exactly equal slices of cake for everyone, you'll get in big trouble.
The cake is round, and decorated with M&Ms in a circle around the edge. But while the rest of the cake is uniform, the M&Ms are not: there are multiple colors, and every minion must get exactly the same sequence of M&Ms. Commander Lambda hates waste and will not tolerate any leftovers, so you also want to make sure you can serve the entire cake.
To help you best cut the cake, you have turned the sequence of colors of the M&Ms on the cake into a string: each possible letter (between a and z) corresponds to a unique color, and the sequence of M&Ms is given clockwise (the decorations form a circle around the outer edge of the cake).
Write a function called solution(s) that, given a non-empty string less than 200 characters in length describing the sequence of M&Ms, returns the maximum number of equal parts that can be cut from the cake without leaving any leftovers.
I don’t know about you, but my brain works better when things are presented ( and I do the figuring out ) graphically, since we already have a couple of test cases, we can do just that, here’s the first pattern and how it looks on a cake seen from a top view:
This might not make sense yet, so let’s show the divisions for each letter:
And finally the division for the repeating pattern:
We’ll talk about the edge cases later, but now that we have more or less a good idea of the problem let’s start coding, we need a function that takes some letters, finds a pattern and spews out the number of repeating occurrences of said pattern , this was my initial solution:
def solution(s):
sub = s[0:len(set(s))]
return(s.count(sub))
print(solution('abcabcabcabc'))
>> 4
print(solution('abccbaabccba'))
>> 2
This works for this 2 examples because set(s) gets the repeating characters abc and then finds the occurrences in both strings, but...
This method unfortunately did not pass all the tests so we need to go deeper and create a number of extra edge cases to find the remaining solutions, the fact that the exact pattern is also not being extracted _abccba_in the second solution is something that also needs to be addressed.
Divide and conquer
In order to move forward, we need to first find out if the pattern has an odd or even number of characters, this might seems counterintuitive, but it’s a simple way of starting to find edge cases, consider this one :
Given an even number of slices, there should be an even number of divisions with no extra slices, but given an uneven number of slices like in this case, you could have some extra slices, remember that the problem asks for **the maximum number of equal parts,**2 in this case. Identifying odd/even should be easy using the modulo operator:
def solution(s):
if (len(s) % 2 != 0):
print('Odd')
else:
print('Even')
solution('abcabcN')
>> ODD
solution('abcabc')
>> EVEN
The next item on the list is to find the full pattern, which can be done by finding the index at which the pattern repeats, which in turn can be found doubling the string, finding the index and then extracting the pattern at said index:
def solution(s):
print('INPUT:' + s)
i = (s+s).find(s,1, -1)
sub = s[:i]
print('Substring:', sub)
solution('abccbaabccba')
>> INPUT:abccbaabccba
>> Substring: abccba
solution(‘xyztxyztxyzt')
>> INPUT:xyztxyztxyzt
>> Substring: xyzt
The only weird thing here is the -1 index on the find() method, this will be used to catch the situation in which the pattern is not EVEN, consider the following 2 cases:
def solution(s):
print('INPUT:' + s)
i = (s+s).find(s,1, -1)
sub = s[:i]
print("i:", i)
print('Substring_1:', sub)
s2 = s
s2 = s2[:-1]
sub2 = s2[0:len(set(s2))]
print('Substring_2:' + sub2)
solution('wewewe')
>> INPUT:wewewe
>> i: 2
>> Substring_1: we
>> Substring_2:we
solution('weweweT')
>> INPUT:weweweT
>> i: -1
>> Substring_1: wewewe
>> Substring_2:we
Check: https://www.programiz.com/python-programming/methods/string/find for more on find()
Another edge case that needs to be considered is a single character repeating pattern like this one:
This is simply done by measuring the pattern length after the previous step:
if len(set(s)) == 1:
Cobbling the script:
So at this point we should have enough to make a final script with all the cases and conditions we’ve gone through, here’s a very verbose take:
def solution(s):
print('-------')
print('INPUT:' + s)
i = (s+s).find(s, 1, -1)
print (i)
if (len(s) % 2 != 0):
print('ODD')
if(len(set(s)) == 1):
print("CASE: ODD SINGLE CHARACTER")
print('pattern:' + (s[0]))
print('Divisions:' + str(len(s)))
return
else:
s = s[:-1]
if len(set(s)) == 1:
print('pattern:' + (s[0]))
print("CASE: ODD SINGLE CHARACTER EXTRA CHARACTER")
print('Divisions:' + str(len(s)))
return
elif i == -1:
sub = s[0:len(set(s))]
print('pattern:' + sub)
print('Divisions:' + str(s.count(sub)))
print("CASE: MULTI CHARACTER EXTRA CHARACTER")
return
else:
sub = s[:i]
print('pattern:' + sub)
print('Divisions:' + str(s.count(sub)))
print("CASE: ODD MULTI CHARACTER")
return
else:
print('EVEN')
if len(set(s)) == 1:
print('pattern:' + (s[0]))
print('Divisions:' + str(len(s)))
print("CASE: EVEN SINGLE CHARACTER")
return
else:
sub = s[:i]
print('pattern:' + sub)
print('Divisions:' + str(s.count(sub)))
print("CASE: EVEN MULTI CHARACTER")
return
There are 6 test cases :
solution('a')
solution('aa')
solution('abcabc')
solution('abcabcabc')
solution('aaT')
solution('ababT')
And the corresponding output:
------
INPUT:a
-1
ODD
CASE: ODD SINGLE CHARACTER
pattern:a
Divisions:1
-------
INPUT:aa
1
EVEN
pattern:a
Divisions:2
CASE: EVEN SINGLE CHARACTER
-------
INPUT:abcabc
3
EVEN
pattern:abc
Divisions:2
CASE: EVEN MULTI CHARACTER
-------
INPUT:abcabcabc
3
ODD
pattern:abc
Divisions:2
CASE: ODD MULTI CHARACTER
-------
INPUT:aaT
-1
ODD
pattern:a
CASE: ODD SINGLE CHARACTER EXTRA CHARACTER
Divisions:2
-------
INPUT:ababT
-1
ODD
pattern:ab
Divisions:2
CASE: MULTI CHARACTER EXTRA CHARACTER
Once refactored into a smaller less verbose script all the tests passed; you then get greeted with a bunny and you can progress further down the challenge.
Caveat Emptor (Buyers Beware) :
The eagle eyed might have noticed the incorrect 4th caseabcabcabc where my script states that 2 is the maximum number of slices where 3 is the expected output, I chose to leave this error here because I only discovered it while writing this post 🙃, (you can fix it as an exercise ). It also shows how you can pass these tests and still be wrong, which leads us to our next issue…
You can skin this cat in any number of ways, I can’t remember precisely which Stack Overflow answers I used, but I remember at one point I was overwhelmed with options, and this is another problem with code challenges, your knowledge of the domain (both the language and the problem itself) improves as time goes by and your answer becomes better, ( unless you run out of time like me ). This and many other challenges put a premium on fast coding specific problems which you might or not have been primed for.
I’ll probably make a separate post dealing with this aspect, but as the deadline nears, or even before that your stress levels are bound to rise, and stress affects your memory and comprehension in negative ways…
Whats more, if you had put me in front of a terminal without internet I probably would have failed, perhaps because my day to day does not involve strings ( it currently involves Neuroscience research, Python GUIs and Quant stuff so thats fresh in my memory ), in any case, it is both an interesting observation and a roadmap for solving and preparing for these types of challenges (don’t get stressed and practice) :
Conclusions
I still dislike coding challenges, even if they are wrapped in a cool IDE and come dangling a potential Google interview, regardless of my opinion these are the norm and I fully understand that most people want to learn more about them and how to better prepare for them.
This short article hopefully showed you my experience and what to expect if you get an invitation to the Google challenge (keep on googling python stuff to improve your chances of getting one), but perhaps more interestingly showed how to dissect a Python coding challenge (or many other problems) and the obvious yet overlooked situation where you get better the more time you spend on any problem or language as well as the tricky situation where stress plays against you solving new problems.
tl;dr: Don’t get discouraged if you can’t a) understand a coding challenge at first and b) come up with an optimized solution fast, these things sometimes take time and the system is far from ideal.
Thank for reading !
Suggest:
☞ Python Tutorials for Beginners - Learn Python Online
☞ Learn Python in 12 Hours | Python Tutorial For Beginners
☞ Complete Python Tutorial for Beginners (2019)
☞ Python Programming Tutorial | Full Python Course for Beginners 2019