Hackerrank Hash Tables: Ransom Note

Given two lists of words, we have to say if the second is a subset of the first. This HackerRank problem is very similar to the previous one.

The given sample, that I converted to a python test, should clarify the point of the problem:
def test_provided_1(self):
    self.assertEqual(True, solution(['give', 'me', 'one', 'grand', 'today', 'night'], ['give', 'one', 'grand', 'today']))
I don't bother to add more tests, being the problem so simple. And I don't even spend much time in thinking on the function design, since the problem name itself gives a huge spoiler on its solution. I would put the words in hash tables (dictionaries, since I am using python as implementation language) and I ensure all the words in the second collection are also present in the first one.
from collections import Counter  # 1


def solution(magazine, ransom):
    available = Counter(magazine)
    needed = Counter(ransom)  # 2

    for word in needed:
        if needed.get(word) > available.get(word, 0):  # 3
            return False
    return True
1. Since it is all about counting items, instead of using naked dictionaries I use Counters, making my script a bit shorter. See my solution to the previous problem to see how the code looks like using dictionaries.
2. Actually, the second dictionary is not strictly required, and a check as implemented in the previous problem would reduce slightly the cost of the algorithm. However, I am not here to write optimized code (otherwise I would have chosen C++ as implementation language), and in this way the code is probably more readable.
3. If I don't have enough of the current word, or even not at all, I can stop looping and return a False. Only if all the words in ransom are also in magazine I'll return True.

Solution accepted, unit test and python script pushed to GitHub.

No comments:

Post a Comment