HackerRank | 2 Questions | 120 mins
Q1) Given a list of integers, perform cardinality sort, where cardinality of a number is the count of all set bits in that number. If cardinality is same, sort in ascending order. Return the list after sorting.
https://leetcode.com/problems/sort-integers-by-the-number-of-1-bits/
Algorithm:
- Calculate cardinality using hamming weight algorithm
- Traverse list to store number and cardinality as pair in min heap
- Iterate min heap for result.
All test cases passed.
Q2) Given an array of words and an array of sentences, determine which words are anagrams of each other. Calculate how many sentences can be created by replacing any word with one of the anagrams. Return a list containing number of sentences possible for each sentence.
Example
wordSet = ['listen', 'silent, 'it', 'is']
sentence = 'listen it is silent'
Determine that listen is an anagram of silent. Those two words can be replaced with their anagrams.
The four sentences that can be created are:
• listen it is silent
• listen it is listen
• silent it is silent
• silent it is listen
https://leetcode.com/discuss/interview-question/1541093/How-many-sentences-Can-someone-provide-a-python-solution-for-this-question
Intuition
In the given example, anagramns are - { (listen, silent), (it), (is) }
For the given sentence, 'listen it is silent', there can be 2 replacements for both 'listen' and 'silent'.
listen it is silent
Combinations = 2 * 1 * 1 * 2 = 4
Calculate number of anagrams for each word using frequency map.
Iterate each sentence to calculate the combinations.
All testcases passed.