Count Complete Highway Journeys from Toll Logs

Question

The question asks the candidate to determine the number of complete highway journeys based on provided toll logs.

Codemia · Accepted Answer

To solve the problem, we need to define what a complete journey is. A complete journey occurs when a vehicle starts at a toll entry point and ends at a toll exit point. We will iterate through the toll logs and count the number of complete journeys based on this definition.

We can use a simple loop to traverse the toll logs. We will maintain a counter for complete journeys and a set to track entry points. Each time we encounter an exit point, we check if there is a corresponding entry point in our set. If there is, we increment our counter and remove the entry point from the set. Here’s a sample implementation in Python:

```python
def count_complete_journeys(toll_logs):
    entry_points = set()
    complete_journeys = 0

for log in toll_logs:
        if log['type'] == 'entry':
            entry_points.add(log['vehicle_id'])
        elif log['type'] == 'exit' and log['vehicle_id'] in entry_points:
            complete_journeys += 1
            entry_points.remove(log['vehicle_id'])

return complete_journeys
```

The time complexity of this solution is O(n), where n is the number of toll logs, since we are iterating through the logs once. The space complexity is O(m), where m is the number of unique vehicles, as we store entry points in a set.

Consider edge cases such as no toll logs, all entry logs without corresponding exits, or multiple entries and exits for the same vehicle. The algorithm should handle these gracefully by returning zero for incomplete journeys.

In summary, this approach efficiently counts complete journeys using a set to track entry points. It is scalable and handles various scenarios, making it a robust solution for the problem.

Count Complete Highway Journeys from Toll Logs

Onepay

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Approach

Algorithm

Submit Your Answer

Onepay Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string