How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Uber.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Uber during technical interviews.

Find the First Unique IP | Uber Coding Question

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.

Input: (["getFirstUniqueIp", "getFirstUniqueIp"], [None, None])

Expected Output: [None, None]

Explanation: There are no recorded hits, so every query returns None.

Input: (["recordHit", "getFirstUniqueIp", "recordHit", "getFirstUniqueIp"], ["192.168.0.1", None, "192.168.0.1", None])

Expected Output: ["192.168.0.1", None]

Explanation: The IP is unique after the first hit, but not after it appears a second time.

Input: (["recordHit", "recordHit", "recordHit", "recordHit", "getFirstUniqueIp", "recordHit", "getFirstUniqueIp"], ["1.1.1.1", "2.2.2.2", "1.1.1.1", "3.3.3.3", None, "2.2.2.2", None])

Expected Output: ["2.2.2.2", "3.3.3.3"]

Explanation: After 1.1.1.1 repeats, 2.2.2.2 becomes the earliest unique IP. After 2.2.2.2 repeats, 3.3.3.3 becomes the earliest unique IP.

Hints

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

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.