logo CodeStepByStep logo


Language/Type: C++ Map collections
Related Links:
Author: Marty Stepp (on 2016/06/16)

Write a function named rarest that accepts a reference to a Map from strings to strings as a parameter and returns the value that occurs least frequently in the map. If there is a tie, return the value that comes earlier in ABC order. For example, if a variable called map containing the following elements:

{"Alyssa":"Harding", "Char":"Smith", "Dan":"Smith", "Jeff":"Jones", "Kasey":"Jones",
 "Kim":"Smith", "Morgan":"Jones", "Ryan":"Smith", "Stef":"Harding"}

Then a call of rarest(map) would return "Harding" because that value occurs 2 times, fewer than any other. Note that we are examining the values in the map, not the keys. If the map passed is empty, throw a string exception.

Constraints: Obey the following restrictions in your solution.

  • You may create one additional data structure (stack, queue, set, map, etc.) as auxiliary storage. (You can have as many simple variables as you like.)
  • You should not modify the contents of the map passed to your function.
    Declare your function in such a way that any caller can be sure that this will not happen.
  • Your solution should run in no worse than O(N log N) time, where N is the number of pairs in the map.
Type your C++ solution code here:

This is a function problem. Write a C++ function as described. Do not write a complete program; just the function(s) above.

You must log in before you can solve this problem.

Log In

Need help?

If you do not understand how to solve a problem or why your solution doesn't work, please contact your TA or instructor.
If something seems wrong with the site (errors, slow performance, incorrect problems/tests, etc.), please

Is there a problem? Contact a site administrator.

© Marty Stepp, all rights reserved.