Track the Contiguous Package Frontier and Missing IDs

Question

The candidate is asked to design an algorithm that tracks contiguous package frontiers and identifies any missing IDs within a sequence of package IDs.

Codemia · Accepted Answer

To tackle the problem of tracking contiguous package frontiers and identifying missing IDs, I will first sort the list of package IDs. After sorting, I can iterate through the list to check for any gaps between consecutive IDs. This method ensures that I can efficiently identify any missing IDs in a single pass after sorting.

1. **Sort the list of IDs**: This will allow us to easily identify gaps.
2. **Initialize an empty list** to hold missing IDs.
3. **Iterate through the sorted list**: For each ID, check if the next ID is exactly one greater than the current ID. If not, add the missing IDs to the list.
4. **Return the list of missing IDs** after the iteration is complete.

The time complexity of this algorithm is O(n log n) due to the sorting step, where n is the number of package IDs. The subsequent iteration through the list is O(n), making the overall complexity dominated by the sorting step. The space complexity is O(m), where m is the number of missing IDs stored.

```python
def find_missing_ids(package_ids):
    # Sort the package IDs
    package_ids.sort()
    missing_ids = []
    # Iterate through the sorted list
    for i in range(len(package_ids) - 1):
        current_id = package_ids[i]
        next_id = package_ids[i + 1]
        # Check for missing IDs
        while next_id > current_id + 1:
            missing_ids.append(current_id + 1)
            current_id += 1
    return missing_ids
```
This code sorts the IDs and checks for gaps, storing any missing IDs in a list.

It is important to consider edge cases such as an empty list of package IDs, which should return an empty list of missing IDs. Additionally, if all IDs are contiguous, the output should also be an empty list. I would also ensure that the function can handle negative IDs and non-integer values gracefully.

Track the Contiguous Package Frontier and Missing IDs

Amazon

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

Amazon 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