Katkat
Back

Find the First Unique Log

UberSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to efficiently process a stream or list of logs to identify the first log entry that appears exactly once, emphasizing the use of hash maps and ordered tracking.

Problem Statement

You are given a list of log strings, where each string represents a unique action ID. Your goal is to find the first log entry that appears exactly once in the entire list. If no such log exists, return an empty string.

Function Signature

def find_first_unique_log(logs: List[str]) -> str:

Constraints

  • 1 <= len(logs) <= 10^5
  • Each log string length is between 1 and 50 characters.
  • The logs consist of alphanumeric characters.

Examples

Example 1: Input: logs = ["login", "request_data", "login", "process_data", "request_data"] Output: "process_data" Explanation: "login" and "request_data" appear twice. "process_data" is the only log that appears once.

Example 2: Input: logs = ["error", "error", "warning", "warning"] Output: "" Explanation: Every log entry appears multiple times.

Edge Cases

  • Empty input list.
  • A list where all items are unique (return the first item).
  • A list where every item appears at least twice.

Hints

Hint 1

Consider using a hash map to keep track of the frequency of each log entry as you iterate through the list.

Hint 2

A simple frequency count isn't enough; you also need to remember the relative order of the logs to determine which 'unique' one appeared first.

Hint 3

Could you use two passes: one to build a frequency map and another to iterate through the original list to check counts?

Follow-up questions

  • How would you optimize this if the list of logs was an infinite stream rather than a pre-loaded array?
  • What would be the time and space complexity of your solution, and can you improve the space complexity?
  • How would your approach change if you were asked to find the first unique log within a specific moving time window of size K?