Google·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Jun 2026Remote

Summary

Google coding round, one question about server request tracking with a follow-up on ordering. Pretty clean problem but the follow-up tripped me up a bit.

Questions Asked (1)

Design a Server class with begin(requestId) and end(requestId) methods that record timestamps for each request, and a method to print all (start, end) pairs ordered by when requests completed.

Algorithms & Data StructuresSystem Design

Author's notes

The base implementation wasn't bad, two hashmaps, one for start times one for end times, pretty straightforward.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying requirements: are request IDs unique, can begin/end be called out of order, and what should happen if end is called without begin? Then design a data structure that stores start and end timestamps per request, and for printing, collect completed requests and sort them by end time. Discuss trade-offs between sorting at print time versus maintaining a sorted structure.

Pro tip: Mention that you would use a hash map for O(1) begin/end operations and sort only when printing, which is efficient if printing is infrequent. Also, consider thread-safety if the server is concurrent, and discuss how to handle duplicate or missing requests gracefully.

1. Clarify requirements and edge cases

Ask about uniqueness of request IDs, whether begin/end can be called multiple times, and what to do if end is called without begin. Also clarify if the print method should include only completed requests or all.

2. Design data structures

Propose using a hash map (dictionary) to store request records, each with start and end timestamps. For printing, you can either maintain a separate list of completed requests or extract from the map.

3. Implement begin and end methods

In begin, record the current timestamp for the request ID. In end, update the record with the end timestamp, and if the request is now complete, add it to a completed list or mark it as done.

4. Implement print method

Collect all completed requests, sort them by end timestamp, and print the (start, end) pairs. Discuss time complexity: O(n log n) for sorting, where n is number of completed requests.

5. Discuss optimizations and concurrency

Mention potential optimizations like using a balanced BST or priority queue if printing is frequent, and address thread-safety with locks or concurrent data structures if needed.

Key Points to Mention

Use a hash map for O(1) average-case time for begin and end operations.
Store timestamps as integers (e.g., milliseconds since epoch) or high-resolution time objects.
For printing, sort completed requests by end time; time complexity O(n log n).
Handle edge cases: duplicate begin, end without begin, multiple ends, and missing ends.
Consider thread-safety if the server is concurrent; use locks or concurrent collections.
Discuss trade-offs: sorting at print time vs. maintaining sorted order on insertion.

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