Assume two hash-indexed collections and exist and that collection from a previous state must be compared to collection from the current state. The task is to find an efficient method to:

- check if the new collection contains exactly the same elements from the previous state ,
- update collection to contain the elements from the new collection without disposing of the contents of collection

For the exercise you are allowed to use only comparisons, set operations and not allowed to introduce intermediary variables.

(1) Given the two sets, initial set and new set , the intersect can obtained via and the result assigned to such that will contain only the elements common to both and . Since the exercise mentions hash-indexed collections, one can assume that and are proper mathematical sets with no duplicate elements, such that using a simple length comparison between and will reveal whether the sets are equal. (2) Finally, since now contains elements in both and , an union can be performed between and and assigned to which will yield a set that contains the elements of and any new elements in .

Summarized:

For the first point (1), the time complexity would be , the comparison is an operation such that the first point carries an overall complexity of . The second point (2) also requires time complexity.

fuss/computer_science/exercises.txt ยท Last modified: 2019/03/09 00:18 by office

For the copyright, license, warranty and privacy terms for the usage of this website please see the license, privacy and plagiarism pages.