Railway Management

Moderate
0/80
Average time to solve is 30m
12 upvotes
Asked in companies
IntuitZoho CorporationSapiens

Problem statement

Ninja started his new job as a manager in Railways Control Room. His task is to maintain the records of passengers traveling from one place to another. His task is to design a class that performs the following operations:

‘RAILWAY_SYSTEM’() is a function that initializes your data structures.

‘CHECK_IN’( ‘PASS_ID’,’ STATION’, TIME) represents that passenger with passenger ID ‘PASS_ID’ checks in at the station named ‘STATION’ at time ‘TIME’.

 A customer can only be checked into one place at a time.

‘CHECK_OUT’( ‘PASS_ID’,’ STATION’, TIME) represents that passenger with passenger ID ‘PASS_ID’ checks out at the station named ‘STATION’ at time ‘TIME’.

‘GET_AVERAGE_TIME(SOURCE, DEST) returns the average time it takes to travel from SOURCE to DEST.

The average time is computed from all the previous traveling times from SOURCE to DEST  that happened directly, meaning a check-in at SOURCE followed by a check out from DEST.
For Example 
If the functions calls are as follows:
CHECK_IN(1,‘Delhi’,10)
CHECK_OUT(1,‘Noida’,20)
GET_AVERAGE(‘Delhi’,’ Noida’)
CHECK_IN(5,‘Delhi’,12)
CHECK_OUT(5,‘Noida’,17)
GET_AVERAGE(‘Delhi’,’ Noida’)

So, the answers for the GET_AVERAGE calls will be 10 and 7.5 respectively.
For the first call, there is only one trip between Delhi and Noida, so the average is 10.
For the second call, there are two between these stations, so the average is (10+5)/2 = 7.5
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of the input contains an integer, 'T,’ denoting the number of test cases.

The first line of each test case contains a single integer, 'N’, denoting the number of function calls.

Next ‘N’ lines of each test case contain an integer denoting the function type followed by the parameter list.
Type 1 denotes CHECK_IN().
Type 2 denotes CHECK_OUT().
Type 3 denotes GET_AVERAGE().
Output Format: 
For each test case, output the values returned by the GET_AVERAGE() function.

Print the output of each test case in a separate line.
Note: 
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 10
1 <= N <= 100000.
1 <= ‘PASS_ID’ <= 1000 .
2 <= Number of Stations <= 20.
1 <= ‘TIME’ <= 1000. 

Time limit: 1 sec
Sample Input 1:
1
6
1 1 Delhi 10
2 1 Noida 20
3 Delhi Noida
1 5 Delhi 12
2 5 Noida 17
3 Delhi Noida
Sample Output 1:
10.0  7.5
Explanation of sample input 1:
For the first test case,
So, the answers for the GET_AVERAGE calls will be 10 and 7.5 respectively.
For the first call, there is only one trip between Delhi and Noida, so the average is 10.
For the second call, there are two between these stations, so the average is (10+5)/2 = 7.5. Hence, the answer is [10, 7.5].
Sample Input 2:
2
9
1 154 Kota 10
2 154 Chandigarh 50
3 Kota Chandigarh
1 821 Agra 1
2 821 Kota 26
1 79 Agra 37
3 Agra Kota
2 79 Noida 54
1 373 Lucknow 65
6
1 734 Agra 59
2 734 Ahemdabad 69
1 831 Kota 53
2 831 Delhi 89
3 Kota Delhi
1 514 Shimla 62
Sample Output 2:
40.0 25.0
36.0
Hint

Try to store the details of each passenger ID effectively.

Approaches (1)
Using the Hash map.

In this approach, we will implement these functions using two hashmaps ‘CHECK_IN_MAP’ and ‘ROUTE_MAP

CHECK_IN_MAP[ID] will store two values a string corresponding to the check-in station of the passenger and an integer corresponding to the time of check-in.

ROUTE_MAP[route] will store two values the total time between the route and the number of trips between this route.

‘route ’ is a string composed of  StationA + ‘-’ + StationB.For example, if the route is between Delhi and Noida, the ‘route’ will be “Delhi-Noida”.


 

Algorithm:

  • Defining RAILWAY_SYSTEM():
    • Declare hashmap ‘CHECK_IN_MAP’.
    • Declare hashmap ‘ROUTE_MAP’.
  • Defining CHECK_IN(‘PASS_ID’,’ STATION’, TIME):
    • Set CHECK_IN_MAP[PASS_ID] as [STATION,TIME].

 

  • Defining ‘CHECK_OUT’( ‘PASS_ID’,’ STATION’, TIME):
    • Set START_STATION as  CHECK_IN_MAP[PASS_ID][0].
    • Set START_TIME as  CHECK_IN_MAP[PASS_ID][1].
    • Set ‘ROUTE’ as ‘START_STATION’ + ‘-’ + STATION.
    • Updating the total time of the trips between ‘ROUTE’.
    • Set ROUTE_MAP[ROUTE][0] = ROUTE_MAP[ROUTE][0] + (TIME-START_TIME).
    • Updating the total number of trips between ‘ROUTE’.
    • Set ROUTE_MAP[ROUTE][1] = ROUTE_MAP[ROUTE][1] + 1.

 

  • Defining GET_AVERAGE_TIME(SOURCE, DEST):
    • Set ‘ROUTE’ as ‘SOURCE’ + ‘-’ + ‘DEST’.
    • Return ( ROUTE_MAP[ROUTE][0] / ROUTE_MAP[ROUTE][1]).
Time Complexity

O(N), where ‘N’ is the number of functions calls.
 

In this approach, all functions use O(1) time. Hence, the overall time complexity will be O(N).

Space Complexity

O(M*M), where ‘M’ is the maximum number of different stations.

 

In this approach, we are using which is to store the data for all possible pairs of stations. Hence, in the worst case, the space complexity will be O(M*M).

Code Solution
(100% EXP penalty)
Railway Management
Full screen
Console