Katkat
Back

Implement string formatting and request tracking tasks

GoogleSoftware Engineer · Technical Screen
EasySoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This question tests string manipulation, character mapping logic for rotational symmetry, and the ability to manage time-ordered event tracking using appropriate data structures.

Part 1: Strobogrammatic Number Validator

A strobogrammatic number is a number that looks the same when rotated 180 degrees (rotated upside down). For example, "69" becomes "69", and "88" becomes "88". Write a function is_strobogrammatic(num: str) -> bool that determines if a string input represents a valid strobogrammatic number.

Valid pairs: 0-0, 1-1, 8-8, 6-9, 9-6.

Example:

  • Input: "69", Output: True
  • Input: "818", Output: True
  • Input: "25", Output: False

Part 2: Event Log Tracker

Implement a class EventTracker that records events with a timestamp and a message. You must support retrieving the messages in the order they were recorded.

class EventTracker:

  • record(timestamp: int, message: str) -> None: Adds an event to the tracker.
  • get_ordered_messages() -> List[str]: Returns a list of all messages sorted by their associated timestamps. If two events have the same timestamp, maintain the order in which they were recorded.

Constraints:

  • Part 1: Input string length up to 10^5.
  • Part 2: record calls are frequent; optimize for retrieval efficiency.

Example:

tracker = EventTracker()
tracker.record(10, "Login")
tracker.record(5, "Startup")
tracker.record(10, "Welcome")
# get_ordered_messages() returns ["Startup", "Login", "Welcome"]

Hints

Hint 1

For Part 1, use a hash map to store the rotation mapping and a two-pointer approach to check characters from both ends of the string.

Hint 2

For Part 2, consider using a list of tuples to store events and sort them using a stable sorting algorithm or a custom sort key that handles both timestamp and insertion index.

Hint 3

Ensure Part 1 handles edge cases like odd-length strings containing digits that cannot be rotated (e.g., '2', '3', '4', '5', '7').

Follow-up questions

  • In Part 1, how would you modify the function to find all strobogrammatic numbers of length n?
  • In Part 2, if the system is called millions of times per minute, how would you optimize the `get_ordered_messages` method to avoid re-sorting the entire list every time?
  • What data structure would you use if you needed to retrieve messages within a specific time range [start, end]?