Posted on 2019-06-16.
For the June 2019 KC Code Challenge Meetup we’re discussing five HackerRank problems.
If you’ve gotten stuck, here are some hints that might help.
I’ve arranged the problems from easiest to hardest (in my personal, subjective estimation).
Remember, you don’t need to solve all (or any) of these to come to the meetup!
Indeed, solving all of them would be a big time investment.
Count Triplets and Maximum Subarray Sums, in particular, are quite challenging.
- This can be solved in O(N) time.
- You should only need to look at each element in the array once.
You just need a way to remember how many times you’ve seen each color of sock before.
There’s a specific data structure that’s great for quickly letting you associate one value (such as a color) with another (such as a count).
If you want to see solutions with explanations for this problem, see this post.
- Break this into three steps:
- Determine what words occur in the magazine and how many times each word occurs.
- Determine what words occur in the note and how many times each word occurs.
- Compare the word counts from the note with the word counts from the magazine to see if there are enough.
- The same data structure that helped you in Sock Merchant can help here.
If you want to see solutions with explanations for this problem, see this post.
- This can be solved in O(N) time.
- There are really two types of “special palindromes”.
You can divide the problem into two problems, finding the count for each type separately.
The two types are:
- Strings consisting of all the same character.
- Strings consisting of all the same character except for the middle character.
- Given a string such as “aaabaaaa” all you really need to know is that there’s a 3-character sequence of ‘a’, a 1-character sequence of ‘b’, then a 4-character sequence of ‘a’.
You might want to build a structure in memory that represents that information, so that afterward you don’t have to look at the input string directly any more.
- If you find a string that is a special palindrome, such as “aaaa” or “aabaa”, there’s a formula you can use to determine how many shorter special palindromes it contains.
The formula depends only on the length of the string.
There is a different formula for each of the two types of special palindromes.
If you want to see solutions with explanations for this problem, see this post.
- This can be solved in O(N) time.
- There’s nothing special about the fact that the problem asked about triplets, aka 3-tuples.
A solution for K-tuples would take O(K * N) time.
- Don’t overlook the fact that the problem says each triplet of indices (i, j, k) must have i < j < k.
This is important for allowing the problem to be solved efficiently.
- You only need to do a single pass through the array.
- As you go along, you’ll want to use a data structure that keeps track of N things for each length of tuple (1, 2, 3).
If you want to see solutions with explanations for this problem, see this post.
- This can be solved in O(N * log(N)) time.
- First, find a way to efficiently determine the sum of a subarray given its start and end indices.
There’s a way to do this that only requires you to make one single pass of the entire input array, and afterward allows you to find the sum between any two indices in constant time.
- Once you have that, you just need a way to figure out which start and end indices could possibly contain the largest sum.
- Notice that if it weren’t for the use of modulo, this would be a trivial problem: the entire array would always be the maximum subarray.
You’ll have to think about exactly how the use of modulo affects things.
- If you have a number, and a bunch of other numbers that you can potentially subtract from it (also using modulo), how would you go about searching for the one that will yield the highest result after modulo?
- Notice that HackerRank lists “Binary Search” as a reference resource for this problem.
Your solution might use binary search directly, or use a data structure that relies on it.
If you want to see solutions with explanations for this problem, see this post.