NewPhone

SRM 138 · 2003-03-10 · by schveiguy

Class Name: NewPhone

Return Type: String[]

Method Name: bestNumbers

Arg Types: (vector<string>, vector<int>, int)

Problem Statement

You just got a phone with a speed-dial feature, and you want to determine which numbers to store in the speed-dial memory. To do this, you look at last month's bill, and decide to use the numbers that appear most frequently on the bill.

Create a class NewPhone that contains the method bestNumbers, which takes three arguments:
numbers: A String[] representing all the numbers you called last month. Each String has the form "NNN-NNN-NNNN", where N is a numerical digit ('0'-'9').
frequencies: A int[] indicating how many times each number was called last month. Element i of this int[] maps to element i of numbers.
spaces: The number of memory spaces available to use.

The method should return a String[] of the numbers to program into the memory spaces available, starting with the most frequently called number, and going in decreasing frequency order. If two or more numbers are called the same number of times, they should be returned in the order they were in the original input. The size of the return value should be equal to spaces, discarding any numbers that do not fit into the result. If two or more numbers have the same frequency, but not all of them will fit in the result, add the ones that were first in the original input (See example 3).

Constraints

numbers will have between 1 and 50 elements, inclusive.
Each element in numbers will have the form "NNN-NNN-NNNN", where each N is a digit ('0'-'9').
There will be no repeated elements in numbers.
frequencies will have the same number of elements as numbers.
Each element of frequencies will be between 1 and 100, inclusive.
spaces will be between 1 and length of numbers, inclusive.

Examples

{"123-456-7890", "012-333-4455", "800-825-6699"}
{3,2,1}
3
Returns: { "123-456-7890",  "012-333-4455",  "800-825-6699" }

You made 6 calls last month, three of them were 123-456-7890, two of them were 012-333-4455, and the last was 800-825-6699. Given the frequency of the numbers, they are already in the order of most frequent to least frequent, and there are enough spaces to hold all the numbers.

{"123-456-7890", "012-333-4455", "800-825-6699"}
{3,1,2}
3
Returns: { "123-456-7890",  "800-825-6699",  "012-333-4455" }

Now, the second and third numbers are out of order.

{"123-456-7890", "012-333-4455", "800-825-6699"}
{3,1,2}
2
Returns: { "123-456-7890",  "800-825-6699" }

Now, there are only two spaces available for speed-dial numbers.

{"123-456-7890", "012-333-4455", "800-825-6699", "333-333-3333"}
{3,1,3,3}
2
Returns: { "123-456-7890",  "800-825-6699" }

Three numbers were called with a frequency of 3. Since the first and third elements come before the fourth, they are programmed first, and there is not enough room for the fourth element in the memory spaces.

{"123-456-7891"}
{100}
1
Returns: { "123-456-7891" }

Submissions are judged against all 56 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class NewPhone with a public method vector<string> bestNumbers(vector<string> numbers, vector<int> frequencies, int spaces) · 56 test cases · 2 s / 256 MB per case