Source: TopCoder Practice Problems: AdvertisingAgency

Description

“You are working in an advertising agency. There are 100 billboards owned by your agency, numbered from 1 to 100.

Your clients send you requests, one after another. Each request is the number of the billboard on which the client would like to place his advertisement.

Initially all billboards are empty. Each time you receive a request, you act as follows. If the corresponding billboard is empty, you satisfy the request and occupy the billboard with the client’s advertisement. If the corresponding billboard is occupied, you reject the request.

You are given a requests containing the requests in the order you receive them. Return the number of rejected requests.”

Definition:

Class: AdvertisingAgency
Method: numberOfRejections
Parameters: int[]
Returns: int
Method signature: int numberOfRejections(int[] requests)
(be sure your method is public)

Limits:

Time limit (s): 840.000
Memory limit (MB): 64

Constraints:

  • Requests will contain between 1 and 50 elements, inclusive.
  • Each element of requests will be between 1 and 100, inclusive.

My solution

One could simply store the number of each occupied billboard, with no ordering, and use in to check for inclusion.

This maps array element indexes to billboard numbers, for convenience in representing all available billboards.

1
2
3
4
5
6
7
8
9
10
11
12

class AdvertisingAgency:
    def __init__(self):
        self.billboards = [0] * 100

    def numberOfRejections(self, requests):
        count = 0
        for r in requests:
            if self.billboards[r - 1]:
                count += 1
            else:
                self.billboards[r - 1] = 1
        return count

Tests

1
2
3
4
5
6
7
8
9
10
11
12

from solution import AdvertisingAgency


def test_provided():
    a = AdvertisingAgency()
    assert a.numberOfRejections((1, 2, 3)) == 0
    a.billboards = [0] * 100
    assert a.numberOfRejections((1, 1, 1)) == 2
    a.billboards = [0] * 100
    assert a.numberOfRejections((1, 2, 1, 2)) == 2
    a.billboards = [0] * 100
    assert a.numberOfRejections((100,) * 50) == 49