logo CodeStepByStep logo

starters

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

Write a function named starters that accepts two parameters: a reference to a vector of strings, and an integer k. Your function should examine the strings in the vector passed and return a set of all first characters that occur at least k times. In other words, if k or more strings in the vector start with a particular character at index 0 of the string (case-insensitively), that character should be part of the set that you return. All elements of your set should be in lowercase. For example, consider a vector variable called v containing the following elements:

{"hi", "how", "are", "He", "", "Marty!", "this", "morning?", "fine.", "?foo!", "", "HOW", "A"}

Two words in the vector start with "a", one starts with "f", four start with "h", two start with "m", one starts with "t", and one starts with "?". Therefore the call of starters(v, 2) should return a set containing:

{'a', 'h', 'm'}

The call of starters(v, 3) on the same vector should return a set containing:

{'h'}

If no start character occurs k or more times, return an empty set. The characters should appear in your set in alphabetical order. Note that some of the elements of the vector might be empty strings; empty strings have no first character, so your code should not consider them when counting. (But your code shouldn't crash on an empty string.)

Constraints: Obey the following restrictions in your solution.

  • You will need to construct your set to be returned, and in addition to that, 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 vector 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 solution 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

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.