Google Code Jam practice
I tried the Google APAC practice test today. There were 4 problems totally, and I managed to solve 2 fully and the fourth one’s small input (Not really an achievement, brute force blessed me here). Got a rank of 137(Meh.)
- The first, Lazy Spelling Bee seems to be a simple ad-hoc problem, with a few corner cases. You might want to check for n=1 and also verify if your algo returns 1 for cases like aaaaaa,bbbb,.. etc.
- The second, Robot Rock Band is pretty interesting and delves into bit manipulation here. The first task can be found simply by brute-forcing the values. You can exponentially improve it by making the observation that if a^b^c^d=k ,then a^b^c^d^k=0 , and hence a^b = c^d^k. Now all that’s left is put all values a^b in a map/hashtable and check if any (c,d) exist such that c^d^k is in the map.
For the last two problems, I will update this post soon.
EDIT 1:
3. I couldn’t get the idea during the contest. Looking at Jayam’s solution(that user was placed first), I deduced it was a clever use of DP with bitmasks.
The basic algorithm is that say we have i machines and say we give a single bit to the first machine. Now the second machine gets the output of the first and the whole problem reduces to that (i-1) remaining machines.
IN short, if dp[i][bit] means there are i machines and the initial bit we have given is ‘bit’, then dp[i][bit]=a*dp[i-1][bk&bit]+b*dp[i-1][bk|bit]+c*dp[i-1][bk^bit]. where bk is the bit of k in consideration. We need to loop over all bits in consideration(As max val=100000, atmost 33 bits can be there).
Nice one!
EDIT 2:
4. [UPDATED]
This was a really good problem. It uses a mix of binary search and also the sliding window problem.
Let us say we have a sum ‘x’ . How do we find the number of subarrays whose sum is less than or equal to ‘x’ most efficiently? Brute force sum would yield an inefficient O(n^3) while we need to opt for atleast an O(nlogn) solution. An idea would be to use the sliding window problem which actually introduces the same concept. This can be done in O(n).
As the sums are increasing strictly, and also the the number of subarrays less than or equal to ‘x’ would be increasing with increasing ‘x’( obviously), we can do a binary search for x from 0 to the largest possible(the sum of all elements). O(n) for each subproblem and hence O(nlogn) for the full problem!!
Keep tuned to the blog. :)