Quick Overview

This question evaluates proficiency with streaming data handling, stateful data structures, and algorithmic design for identifying unique elements in chronological event streams, and is categorized under Coding & Algorithms.

Find the First Unique IP

Company: Uber

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are processing a chronological stream of server hit records. Each record contains an IP address as a string. Design and implement a component that supports the following operations: - `recordHit(ip: string)`: Add a new server hit from `ip`. - `getFirstUniqueIp() -> string | null`: Return the earliest IP address in the stream that has appeared exactly once so far. If no such IP exists, return `null`. Example: ```text recordHit("10.0.0.1") recordHit("10.0.0.2") recordHit("10.0.0.1") getFirstUniqueIp() -> "10.0.0.2" recordHit("10.0.0.2") getFirstUniqueIp() -> null recordHit("10.0.0.3") getFirstUniqueIp() -> "10.0.0.3" ``` Follow-up: How would you scale the solution if the server receives millions or billions of hit records? Discuss memory usage, throughput, and any trade-offs if exact results are required versus approximate results.

Quick Answer: This question evaluates proficiency with streaming data handling, stateful data structures, and algorithmic design for identifying unique elements in chronological event streams, and is categorized under Coding & Algorithms.

You are processing a chronological stream of server hit records. Each record contains an IP address as a string. Support these operations: - "recordHit": add a new server hit from an IP. - "getFirstUniqueIp": return the earliest IP address in the stream that has appeared exactly once so far. For this coding task, implement a batch processor. You are given two lists, `operations` and `values`, of the same length: - If `operations[i] == "recordHit"`, then `values[i]` is the IP string to add. - If `operations[i] == "getFirstUniqueIp"`, then `values[i]` is `None` and should be ignored. Return a list containing the result of each `getFirstUniqueIp` call in order. Use `None` when no unique IP exists at that moment. Follow-up for interview discussion: If the system receives millions or billions of hits, discuss how you would scale the design, including memory usage, throughput, sharding, and the trade-offs between exact and approximate solutions.

Constraints

  • 0 <= len(operations) == len(values) <= 200000
  • Each operation is either "recordHit" or "getFirstUniqueIp"
  • For "recordHit", the IP string length is between 1 and 45 characters
  • The expected solution should run in O(n) total time across all operations

Examples

Input: (["recordHit", "recordHit", "recordHit", "getFirstUniqueIp", "recordHit", "getFirstUniqueIp", "recordHit", "getFirstUniqueIp"], ["10.0.0.1", "10.0.0.2", "10.0.0.1", None, "10.0.0.2", None, "10.0.0.3", None])

Expected Output: ["10.0.0.2", None, "10.0.0.3"]

Explanation: After the first three hits, only 10.0.0.2 is unique. After 10.0.0.2 appears again, no unique IP remains. After 10.0.0.3 is added, it becomes the first unique IP.

Input: ([], [])

Expected Output: []

Explanation: No operations means there are no query results.

Hints

  1. A hash map can track how many times each IP has appeared.
  2. You also need to preserve the order of candidate unique IPs. Consider a queue/deque with lazy cleanup from the front.

Loading coding console...