Difference between revisions of "TADM2E 4.7"
From Algorithm Wiki
(Recovering wiki) |
|||
| Line 1: | Line 1: | ||
| − | + | <math>O(n)</math> Hashing solutions: | |
| + | |||
| + | a. Iterate over all the bills and add the names to a hash table (set). Iterate over the checks, and delete from the hash table every name you find. Could use addresses as a tie-breaker in case of identical names. | ||
| + | |||
| + | b. Iterate over every book and map the publisher as the key to the the count of books, incrementing with every book found. Then just lookup the final totals for each publisher. | ||
| + | |||
| + | c. Hash each persons name from the list of cards and return the size of the hashtable. | ||
| + | |||
| + | |||
| + | <math>O(nlogn)</math> Array solutions using sorting | ||
| + | |||
| + | For all three, sort the input data and iterate over it, counting as you go. | ||
Latest revision as of 22:46, 14 January 2018
$ O(n) $ Hashing solutions:
a. Iterate over all the bills and add the names to a hash table (set). Iterate over the checks, and delete from the hash table every name you find. Could use addresses as a tie-breaker in case of identical names.
b. Iterate over every book and map the publisher as the key to the the count of books, incrementing with every book found. Then just lookup the final totals for each publisher.
c. Hash each persons name from the list of cards and return the size of the hashtable.
$ O(nlogn) $ Array solutions using sorting
For all three, sort the input data and iterate over it, counting as you go.
