Maximum memory usage increase
Filed under Amazon
Free read 3 of 3Confirm if logs need to be sorted by timestamp before calculating increases.
The question
Given log files containing memory usage and timestamps, find the maximum increase in memory usage between any earlier timestamp and a later timestamp.
Constraints
- Logs may not be strictly sorted by timestamp.
- Memory values are non-negative integers.
Examples
- Input
- Logs = [(1, 100), (3, 50), (2, 200)]
- Output
- 150
- Why
- Memory increases from 50 at timestamp 3 to 200 at timestamp 2? Wait, chronological order: (1, 100), (2, 200), (3, 50). Max increase is 200 - 100 = 100.
Approach
Confirm if logs need to be sorted by timestamp before calculating increases.
Sort logs by timestamp, then check every pair of logs where the first is earlier than the second to find the max difference.
Sort logs by timestamp, then keep track of the minimum memory seen so far while iterating through to find the maximum difference in O(N log N) time.
Empty log list, single log entry, and strictly decreasing memory usage.
Tips
- What they are testing: Test with logs in random order, strictly decreasing memory usage, and large datasets.
- Common mistake: Assuming logs are pre-sorted by timestamp without sorting them first.
Related Amazon questions
Collected from public candidate posts and coding forums. Updated Nov 2026.