New update is available. Click here to update.

Solve problems & track your progress

Checkout your overall progress in every topic here

Become

Sensei

in DSA topics

Open the topic and solve more problems associated with it to improve your skills

Check out the skill meter for every topic

See how many problems you are left with to solve for cracking any stage. Score more than zero to get your progress counted.

Problem

Submissions

Hotel Rooms

Contributed by

Harshad Aggarwal

Medium

0/80

Avg time to solve 20 mins

Success Rate 20 %

3 upvotes

Problem Statement

You are the manager of a hotel having 10 floors numbered 0-9. Each floor has 26 rooms [A-Z]. You will be given a sequence of strings of the room where ‘+’ suggests the room is booked and ‘-’ suggests the room is freed. You have to find which room is booked the maximum number of times.

Note:

You may assume that the sequence is always correct, i.e., every booked room was previously free, and every freed room was previously booked.

In case, 2 rooms have been booked the same number of times, you have to return Lexographically smaller room.

A string 'a' is lexicographically smaller than a string 'b' (of the same length) if in the first position where 'a' and 'b' differ, string 'a' has a letter that appears earlier in the alphabet than the corresponding letter in string 'b'. For example, "abcd" is lexicographically smaller than "acbd" because the first position they differ in is at the second letter, and 'b' comes before 'c'.

For Example :

n = 6, Arr[] = {"+1A", "+3E", "-1A", "+4F", "+1A", "-3E"}

Now in this example room “1A” was booked 2 times which is the maximum number of times any room was booked. Hence the answer is “1A”.

Detailed explanation ( Input/output format, Notes, Constraints, Images )

Input Format :

The first line of input format contains ‘T’ denoting the number of test cases. Then each testcase follows

The first line of each test case contains an integer ‘n’ Denoting the number of times a room is booked or freed.

The second line of the test case contains an array of ‘n’ strings each string denoting which room was booked or freed.

Output Format :

For each test case, Print a string ‘ans’ denoting the room which was booked maximum number of times.    

Output for every query will be printed in a separate line.

Note :

You are not required to print anything explicitly. It has already been taken care of. Just implement the functions.

Constraints :

1 <= T <= 10
1 <= N <= 10^4

Time Limit: 1 sec

Sample Input 1 :

2
5
+2A +3A -2A +4Z +2A
7
+7B -7B +7B -7B +7B -7B +7B

Sample Output 1 :

2A
7B

Explanation for Sample Output 1 :

In the first test case, room 2A was booked 2 times and 3A, 4Z were booked one time each. Hence the answer is 2A.

In the second test case, room 7B is booked 4 times. Hence the answer is 7B.

Sample Input 2 :

2
3
+6G +8F +3Z
8
+5Q -5Q +9D -9D +5Q +7I +3O -5Q

Sample Output 2 :

3Z
5Q

Auto

Console