Description
1. Tries (15 points)
https://www.hackerrank.com/contests/cst370-s19-hw4/challenges/hw4-tries
For this problem you will implement a trie (prefix tree) and use it to autocomplete words.
In C++, the trie node and class definitions might look like:
struct TrieNode {
bool isLeaf;
vector
};
class Trie {
TrieNode* root;
};
You will need to implement the following operations:
lookup(string) which returns a boolean indicating whether given word was found.
insert(string) which inserts the given word into the trie.
remove(string) which removes the given word from the trie (really removes it, not just
changing the flag).
info() which prints out the number of nodes and number of words in the trie.
alphabetical() which prints out the words in the trie in alphabetical order.
autocomplete(prefix, k) which prints alphabetically all possible words that can be
formed by the given prefix and k additional characters.
Page 3 of 9
CST 370 Homework 4 March 26, 2019
For example, in C++, the function headers would be the following:
class Trie {
TrieNode *root;
public:
Trie() {
// …
}
bool lookup(string str) {
// …
}
void insert(string str) {
// …
}
void remove(string str) {
// …
}
int info() {
// …
}
void alphabetical() {
// …
}
void autocomplete(string prefix, int k) {
// …
}
};
Page 4 of 9
CST 370 Homework 4 March 26, 2019
Input
• The first line of the input will be an integer n indicating how many commands follow
it.
• The next n lines will consist of one of 5 commands (”insert”, ”remove”, ”lookup”,
”info”, and ”autocomplete”).
• The commands ”insert”, ”remove”, and ”lookup” will be followed by a space, then a
string representing the word to perform the command on.
• The commands ”info” and ”alphabetical” have nothing following it.
• The command ”autocomplete” will be followed by a space, then a string to perform
the command on, then a space, then finally an integer representing the number of
additional characters to consider. The integer may be a special value of ”-1” which
means consider all words without a length limitation.
At the end of the input there will be a blank line. Your program should initialize an
empty trie and perform the commands given by the input, in sequence, on it.
Constraints
You can assume there will be no invalid input. You can also assume the trie will consist of
only lowercase words consisting of characters a-z with no duplicate words.
Output
• For the ”insert” and ”remove” commands, print nothing.
• For the ”lookup” command, print the line ”0” if the string is not found and the line
”1” if it is found.
• For the ”info” command, print a line containing two space separated integers. The
first integer is the number of nodes in the trie, the second is the number of words.
• For the ”alphabetical” command, print all the words contained in the trie in alphabetical order. One word per line.
• For the ”autocomplete” command, print the possible autocompleted words on a single
space-separated line in alphabetical order (the line will end in a space).
See the sample output section and hackerrank for concrete examples
Page 5 of 9
CST 370 Homework 4 March 26, 2019
Sample Input 1 Sample Output 1
17
insert james
insert jackie
lookup ja
insert ja
lookup ja
insert jay
insert jane
lookup jackie
alphabetical
info
autocomplete ja 2
autocomplete ja -1
remove jackie
lookup jackie
lookup ja
alphabetical
info
0
1
1
ja
jackie
james
jane
jay
13 5
ja jane jay
ja jackie james jane jay
0
1
ja
james
jane
jay
9 4
Page 6 of 9
CST 370 Homework 4 March 26, 2019
2. Huffman codes (20 points)
https://www.hackerrank.com/contests/cst370-s19-hw4/challenges/hw4-huffman
For this problem you will implement a Huffman tree to encode and decode strings to and
from variable-width encodings.
Input
• The input will consist of two lines.
• The first line will be the string to derive your codes from and encode. Build your
Huffman tree from this string.
• The second line will consist of a test string of 0s and 1s to decode.
At the end of the input there will be a blank line. Your program should build a huffman
tree encoding from the first line and use that tree to decode the second line.
In order to build a Huffman Tree, you will need a priority queue. You may use the
following priority queues as starter code:
C++ https://repl.it/@dsyang/HuffmanQueue-Cpp
Java https://repl.it/@dsyang/HuffmanQueue-java
Python https://repl.it/@dsyang/HuffmanQueue-py
Constraints
The order in which you insert nodes into your priority queue and the implementation of
the priority queue itself has an impact to the created huffman tree. To achieve the same
encoding as the test cases, build your huffman tree as such:
• Use a MinHeap in the implementation of the priority queue. You can use one of the
MinHeaps provided above or modify your heap from homework 1.
• When initially adding characters into your priority queue, insert the characters in
alphabetical order. For example, if your frequency map is: b:2, c:1, x:1, a:4,
[space]:3 then you would add them into the priority queue in this order: [space],
a, b, c, x.
Output
• The output will consist of two lines.
• The first line will be the encoding of the first input string according to your tree.
• The second line will be the decoding of the second input string according to your tree.
Page 7 of 9
CST 370 Homework 4 March 26, 2019
See the sample output section and hackerrank for concrete examples
Sample Input 1
i love computer science
1100101110101100110111111011100011010101101100100111
Sample Output 1
1100101110100001101111110110000001110001100100 ( line wrap )
11111110100101010110011001110110100111
i live in nice
Page 8 of 9
CST 370 Homework 4 March 26, 2019
3. Radix Sort (15 points)
https://www.hackerrank.com/contests/cst370-s19-hw4/challenges/hw4-radix
For this problem you will be provided an array of integers and asked to sort them using radix
sort. You will be printing the partially sorted array after sorting by each digit.
Input
The input will consist of one line containing space integers. At the end of the input there
will be a blank line.
Constraints
You can asssume the input is valid and falls within the constraints under which it is appropriate to use radix sort.
Output
The output will consist of k lines, where k is the number of calls to counting sort (i.e., the
number of digits in the largest element in the input). Each line will contain a list of space
integers in their partially sorted order after that call (the line will end with ” ”)
See the sample output section and hackerrank for concrete examples
Sample Input 1
12
9 87 199 15 3 214 19 26 58 2 102 23
Sample Output 1
2 102 3 23 214 15 26 87 58 9 199 19
2 102 3 9 214 15 19 23 26 58 87 199
2 3 9 15 19 23 26 58 87 102 199 214
Page 9 of 9
This page is intentionally left blank.
