11. Process start and finish logs and output the request intervals.
Given log entries with start and finish times for requests, produce the start and end times for each request sorted by finish time.
I would first build a HashMap from each requestId to its startTime. Then I process every finish log, use the requestId to find the matching start time, and create an interval containing requestId, startTime, and finishTime. After building all matched intervals, I sort them by finishTime and return the list. HashMap lookup is O(1) on average. The total expected time is O(S + F + K log K), with O(S + K) auxiliary space.
See the Code while reading this explanation.
We receive one list that tells us when requests started and another list that tells us when requests finished. Each entry has a request name and a time. For every finish entry, we need to find the start entry with the same request name. We then combine those two times into one result for that request. After all matching results are created, we order them by finish time. The goal is to match each request correctly and return the completed request intervals in the required order.
- Can I assume that each finish entry normally has a matching start entry with the same requestId?
- If two requests have the same finish time, is any order between them acceptable?
- If a finish entry has no matching start entry, should I ignore it, reject the input, or handle it separately?
The input contains startLogs and finishLogs. Each log entry stores a requestId and a timestamp. The output contains one interval for each matched request. Each interval stores requestId, startTime, and finishTime. The final intervals must be sorted by finishTime.
The diagram uses this exact example: startLogs = [(A,1), (B,2), (C,4), (D,6)] finishLogs = [(A,7), (B,5), (C,9), (D,8)]
The expected output is: [(B,2,5), (A,1,7), (D,6,8), (C,4,9)]
I use a HashMap called startById. It stores requestId -> startTime. This lets me quickly find the start time when I process a finish log.
After reading all start logs, the map is: startById = {A:1, B:2, C:4, D:6}
The main invariant is that every interval added to the result uses the start time stored for the same requestId as the current finish log.
I first create an empty HashMap. I process the start logs and put each requestId and startTime into the map. I also create an empty result list.
Initial state: startById = {A:1, B:2, C:4, D:6} result = []
Now every finish log can find its matching start time with an average O(1) HashMap lookup.
Step 1: The finish log is (A,7). The map lookup A -> 1 gives startTime 1. I create (A,1,7). The result becomes [(A,1,7)].
Step 2: The finish log is (B,5). The map lookup B -> 2 gives startTime 2. I create (B,2,5). The result becomes [(A,1,7), (B,2,5)].
Step 3: The finish log is (C,9). The map lookup C -> 4 gives startTime 4. I create (C,4,9). The result becomes [(A,1,7), (B,2,5), (C,4,9)].
Step 4: The finish log is (D,8). The map lookup D -> 6 gives startTime 6. I create (D,6,8). The result becomes [(A,1,7), (B,2,5), (C,4,9), (D,6,8)].
Step 5: I sort the completed intervals by finishTime in ascending order. Their finish times become 5, 7, 8, 9.
The returned result is [(B,2,5), (A,1,7), (D,6,8), (C,4,9)].
For each processed finish log, the HashMap returns the start time stored under the same requestId. Therefore, each created interval contains the matching start and finish times for that request. After all matched intervals are created, sorting by finishTime places them in nondecreasing finish-time order, which is exactly what the question requires.
The Java method first builds startById from startLogs. It then processes finishLogs in their given order. For each finish entry, it looks up the matching startTime. If no startTime exists, the code uses the optional defensive behavior shown in the diagram and skips that malformed finish entry. Otherwise, it creates an Interval and adds it to the result list. Finally, it sorts the intervals using Comparator.comparingInt(Interval::endTime) and returns them.
Let S be the number of start logs, F the number of finish logs, and K the number of matched intervals. Building the map takes expected O(S) time. Processing the finish logs takes expected O(F) time because HashMap lookup is O(1) on average. Sorting K intervals takes O(K log K). Therefore, total expected time is O(S + F + K log K). Auxiliary space is O(S + K).
Relevant edge cases shown in the diagram are empty inputs, finish logs already being sorted, unmatched finish logs when defensive handling is desired, and equal finish times. When finish times are equal, any nondecreasing finish-time order is acceptable unless the interviewer requires a tie-break rule.
The key insight is to use two phases. First, build a HashMap that stores requestId -> startTime. This makes it fast to match each finish log with its start time. Second, create all matched intervals and sort them by finishTime. The central invariant is that every interval added to the result uses the start time stored for the same requestId as the finish log being processed. The HashMap handles matching efficiently, while the final sort handles the required output order.
import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class Main {
// A log entry contains one request ID and one timestamp.
record LogEntry(String requestId, int time) {}
// A completed interval contains its request ID, start time, and finish time.
record Interval(String requestId, int startTime, int endTime) {}
public static List<Interval> buildIntervals(
List<LogEntry> startLogs,
List<LogEntry> finishLogs
) {
// Store requestId -> startTime so each finish log can find its matching start quickly.
Map<String, Integer> startById = new HashMap<>();
// Build the lookup map from all start logs.
for (LogEntry start : startLogs) {
startById.put(start.requestId(), start.time());
}
// Collect every successfully matched request interval here.
List<Interval> result = new ArrayList<>();
// Process finish logs in their given order and pair each one with its start time.
for (LogEntry finish : finishLogs) {
Integer startTime = startById.get(finish.requestId());
// Optional defensive handling for an unmatched finish log.
if (startTime == null) {
continue;
}
// Create the interval only after finding the matching start time.
result.add(new Interval(finish.requestId(), startTime, finish.time()));
}
// The required final order is ascending finish time.
result.sort(Comparator.comparingInt(Interval::endTime));
// Return the matched intervals in finish-time order.
return result;
}
public static void main(String[] args) {
// Use the exact example from the approved diagram.
List<LogEntry> startLogs = List.of(
new LogEntry("A", 1),
new LogEntry("B", 2),
new LogEntry("C", 4),
new LogEntry("D", 6)
);
List<LogEntry> finishLogs = List.of(
new LogEntry("A", 7),
new LogEntry("B", 5),
new LogEntry("C", 9),
new LogEntry("D", 8)
);
// Run the same HashMap-plus-sort algorithm shown in the diagram.
List<Interval> intervals = buildIntervals(startLogs, finishLogs);
// Format the result using the same interval notation as the diagram.
String output = intervals
.stream()
.map(
interval ->
"(" +
interval.requestId() +
"," +
interval.startTime() +
"," +
interval.endTime() +
")"
)
.reduce((left, right) -> left + ", " + right)
.map(text -> "[" + text + "]")
.orElse("[]");
System.out.println(output);
}
}Let S be the number of start logs, F the number of finish logs, and K the number of matched intervals. Building the HashMap takes expected O(S) time. Processing the finish logs takes expected O(F) time because a Java HashMap lookup is O(1) on average. Sorting the K intervals costs O(K log K). So the total expected time is O(S + F + K log K). The map and result list use O(S + K) auxiliary space.
This pattern is useful when separate records belong to the same request or job and share an identifier. Examples include matching request-start and request-finish events, job lifecycle logs, transaction events, and service traces. A map connects related records quickly, and a final sort puts completed records into the required reporting order.
This problem tests whether you can connect related records using the right key, choose a suitable Java data structure, and separate matching from ordering. The interviewer can see whether you understand HashMap behavior, build correct intervals, sort by the correct field, handle malformed unmatched entries carefully, and include the sorting cost in the complexity. It also tests whether your explanation, example, code, and returned result stay consistent.
A common mistake is using the wrong mapping direction. The map must store requestId -> startTime. Another mistake is creating an interval from a finish log without first finding the matching start time. Candidates may also forget to sort by finishTime after building the intervals. A frequent complexity mistake is claiming O(S + F) time and ignoring the O(K log K) sorting step. Another mistake is adding an unnecessary tie-break rule when the question only requires nondecreasing finish-time order.
Say the map meaning out loud before coding: requestId -> startTime. Then describe the solution as two phases: match every finish log to its start time, and sort the completed intervals by finishTime. This makes both the code and the complexity easy to explain.
