FastPrepFastPrep
Problem Brief

Count Groups

INTERNOA

Twilio's IT team is trying to send two new USB Cables to all the Software Engineers. The problem is that there are a lot of USB standards and they are mostly not compatible with each other. For this reason, the team has labeled all the n cables with a numerical tag. They come in a list of tags like tags=[0,1,2,...] where the ith cable has the tags[i]. For example, if tags= [2,3,1,2], the cable number 2 would have the tag 3.

Now we want to group them in pairs taking into account that they must be of the same type. The restrictions for grouping are:

  • Two cables can be formed together if they have the same tag.
  • A group is always formed by 2 cables.
  • One cable can only be in one 1 or 0 groups.

    • To do the most efficient distribution we want to create queries. A query has the form [left, right] and represents an interval in the list of cables. As a result of the query we want to retrieve the number of groups that can be formed. For example, if tags=[2,3,2,1] and the query=[1,3] we would take into consideration only the interval [2, 3, 2] and the number of groups would be 1 because we have two "2".

    The queries come in a list of q queries like [[l1, r1], [l2, r2]...q times]. They are all independent of each other. The result must be in a list of groups formed for each query [r1,r2...q times].

    Function Description

    Complete the function countGroups in the editor.

    countGroups has the following parameters:

    1. int tags[n]: the tags of the cables
    2. int queries[q][2]: the queries in the form (l, r)

    Returns

    int[]: the number of groups that can be formed for each query

    1Example 1

    Input
    tags = [2, 3, 4, 2], queries = [[1, 4], [3, 4]]
    Output
    [1, 0]
    Explanation
    - For the first query, all cables are considered. Cables 1 and 4 can be grouped as their tags are the same.
  • The tag of the cable number 1 is 2 and the tag of the cable number 4 is also 2.
  • There are no other group formations possible. So, the number of groups is 1.
    • - For the second query, cables 3 and 4 are considered, and their tags are [4, 2].
  • The tag of the cable number 3 is 4 and the tag of the cable number 4 is 2.
  • Since they are different, no groups can be formed. So, the number of groups is 0.

    • Hence, the answer is [1, 0].

    2Example 2

    Input
    tags = [2, 2, 2, 2], queries = [[1, 4]]
    Output
    [2]
    Explanation
    - We only have 1 query, all cables are considered.
  • The tag of the cable number 1 is 2, and the tag of the cable number 2 is also 2.
  • The tag of the cable number 3 is 2, and the tag of the cable number 4 is also 2.
  • There are no other group formations possible. So, the number of groups is 2.

    • Hence, the answer is [2].

    Constraints

    Limits and guarantees your solution can rely on.

    Unknown for now
    public int[] countGroups(int[] tags, int[][] queries) {
    // write your code here
}
    Input

    tags

    [2, 3, 4, 2]

    queries

    [[1, 4], [3, 4]]

    Output

    [1, 0]

    Sign in to submit your solution.