← Google Interview Insights

Google·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
May 2026

Summary

Google SWE interview with an OO design and algorithm question around parsing activity logs to find timed-out events. Not the flashiest problem but there's more to it than the example makes it look.

Questions Asked (1)

Q1

Given a list of activity log records (each with an activity ID, timestamp, and event type like START or END) and a timeout threshold, design appropriate classes and implement a function that returns all activity IDs whose duration exceeds the timeout.

Algorithms & Data StructuresSystem DesignTechnical Trade-offs
Author's notes

Spent the first few minutes just on the class design, which I think was the right call but I overdid it a bit.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying requirements and edge cases, then design classes for Activity and ActivityLog with clear responsibilities. Implement a function that groups records by activity ID, pairs START/END events, computes durations, and returns IDs exceeding the timeout, discussing time/space complexity and potential trade-offs.

Pro tip: Mention that you would handle out-of-order timestamps and incomplete pairs (e.g., missing START or END) gracefully, and consider using a hash map for O(n) time complexity. This shows attention to real-world data issues and efficiency.

1. Clarify requirements and edge cases

Ask about input format, whether events are ordered, how to handle multiple START/END pairs per activity, and what to do with incomplete pairs. Confirm the timeout unit and return type.

2. Design classes

Define an ActivityLog class with fields (activityId, timestamp, eventType) and possibly an Activity class to encapsulate duration calculation. Consider using enums for event types.

3. Outline algorithm

Explain that you'll iterate through logs, group by activity ID, track start times, and compute durations when END is encountered. Use a hash map for O(1) lookups.

4. Implement and test

Write clean code with helper methods, handle edge cases (e.g., END without START, multiple pairs), and test with sample inputs including boundary conditions.

5. Analyze complexity and trade-offs

State time complexity O(n) and space O(n) for the map. Discuss alternatives like sorting if logs are unordered, and trade-offs between memory and speed.

Key Points to Mention

  • Use a hash map to group events by activity ID for O(n) time complexity.
  • Handle edge cases: missing START/END, multiple pairs per activity, out-of-order timestamps.
  • Define clear class responsibilities and use appropriate data types (e.g., enum for event type).
  • Consider whether to return activity IDs or objects, and discuss API design.
  • Analyze time and space complexity, and mention potential optimizations.
  • Discuss trade-offs between different approaches (e.g., sorting vs. hashing).

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.