Quick Overview

Remove repeated lines globally while preserving first-occurrence order, exact case, spaces, and empty lines.

Keep the First Occurrence of Every Globally Unique Line

Company: Vanta

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Implement global line uniqueness: keep only the first occurrence of each distinct input line, even when duplicates are not adjacent. ### Function Signature `unique_lines(lines: list[str]) -> list[str]` ### Rules - Compare complete strings exactly and case-sensitively. - Preserve the input order of first occurrences. - An empty string is a valid line and may appear once in the output. - Do not trim spaces or normalize the contents. - Input strings represent lines without their terminating newline characters. These comparison and order rules are explicit conventions for the global-uniqueness task. ### Constraints - `0 <= len(lines) <= 200000`. - Each line contains printable ASCII characters with code points 32 through 126, or is empty. - Total input character count is at most 2000000. - Do not mutate the input. ### Examples Input: `lines = ["alpha","beta","alpha","beta","gamma"]` Output: `["alpha","beta","gamma"]` Input: `lines = ["","A","a",""," A","A"]` Output: `["","A","a"," A"]` Input: `lines = []` Output: `[]`

Overview: Remove repeated lines globally while preserving first-occurrence order, exact case, spaces, and empty lines.

Read the full Vanta Software Engineer interview experience this question came from

You are given a list of text lines. Implement global line uniqueness: keep only the first occurrence of each distinct input line, even when duplicates are not adjacent. Return a new list containing the kept lines. Rules: - Compare complete strings exactly and case-sensitively. - Preserve the input order of first occurrences. - An empty string is a valid line and may appear once in the output. - Do not trim spaces or normalize the contents. - Input strings represent lines without their terminating newline characters. - Do not mutate the input. Example 1: Input: lines = ["alpha", "beta", "alpha", "beta", "gamma"] Output: ["alpha", "beta", "gamma"] The second "alpha" and the second "beta" are repeats of lines seen earlier, so only their first occurrences are kept. Example 2: Input: lines = ["", "A", "a", "", " A", "A"] Output: ["", "A", "a", " A"] The empty line is kept once at its first position; "a" differs from "A" because comparison is case-sensitive, and " A" differs from "A" because leading spaces are not trimmed. The final "A" is a repeat. Example 3: Input: lines = [] Output: []

Constraints

  • 0 <= len(lines) <= 200000.
  • Each line contains printable ASCII characters with code points 32 through 126, or is empty.
  • Total input character count is at most 2000000.
  • Do not mutate the input.
  • Input strings represent lines without their terminating newline characters.

Examples

Input: ([],)

Expected Output: []

Explanation: Minimum valid input: no lines, so nothing can occur first and the result is empty.

Input: ([''],)

Expected Output: ['']

Explanation: Singleton whose only line is the empty string, which is a valid line and is kept once.

Hints

  1. A duplicate can appear arbitrarily far from its first occurrence, so comparing each line only with the line immediately before it is not enough.
  2. As you move through the input, what do you need to remember about everything you have already emitted in order to answer 'have I seen this exact line before?' quickly?
  3. Equality is on the complete string: no trimming, no case folding, and the empty line is an ordinary value that can be kept once.

Loading coding console...

Show the approach

Approach

Scan the input once from left to right, maintaining a hash set of every line value already emitted and an output list built by appending.

Invariant: before processing index i, the output list contains exactly the distinct values among lines[0..i-1], each in the position of its first occurrence, and the set contains exactly those same values. Processing lines[i] preserves the invariant: if lines[i] is already in the set it occurred earlier, so its first occurrence is already in the output and it must be skipped; otherwise index i is by definition its first occurrence, so it is appended to the output and inserted into the set. After the final index, the invariant over the whole input is exactly the required answer: every distinct line kept once, ordered by first occurrence.

Comparison is plain string equality on the complete value, which is case-sensitive and whitespace-sensitive and treats a prefix such as 'ab' as different from 'abc'. Nothing is trimmed, lowercased, or otherwise normalized, and the empty string is an ordinary value that participates like any other line.

Edge cases: an empty input yields an empty output because the loop body never runs; a singleton always survives; an all-identical input collapses to one element; an all-distinct input is returned unchanged; a repeated empty line is emitted only at its first position. Non-adjacent duplicates are handled because membership is tested against every previously seen line, not just the previous one, so a pattern like a, b, a, b correctly collapses to a, b. The input list is only read, never written, so it is not mutated; the returned list is a fresh list. With at most 200000 lines and at most 2000000 total characters, hashing every line once is comfortably within the bounds.

Time complexity:
O(T) where T is the total number of characters across all lines (each line is hashed and compared a constant number of times); this is O(n) line operations for n lines.
Space complexity:
O(T) in the worst case, for the set of distinct lines seen plus the output list of at most n references.