Use OrderedDict to dedupe stably

Quick Overview

This question evaluates a candidate's ability to implement stable deduplication using Python's ordered mapping types while handling case-insensitive comparisons that preserve original casing, and to reason about algorithmic complexity such as O(n) time and O(k) space.

Company: Yahoo

Role: Data Scientist

Category: Data Manipulation (SQL/Python)

Difficulty: medium

Interview Round: Technical Screen

Implement dedupe_preserve_order(seq) that removes duplicates from a list while preserving the order of first appearance, in O(n) time and O(k) space (k = number of unique items). Use collections.OrderedDict (or dict in Python 3.7+) and do not use nested loops or list.index. The function must treat strings case-insensitively for deduplication but return the original casing of the first occurrence. For example, input ['A','b','a','B','c','C','b'] should return ['A','b','c']. Explain the time/space complexity and how your solution behaves if elements are not hashable.

Overview: This question evaluates a candidate's ability to implement stable deduplication using Python's ordered mapping types while handling case-insensitive comparisons that preserve original casing, and to reason about algorithmic complexity such as O(n) time and O(k) space.

You are given a table that represents a sequence of string elements in a list, with their original order. Write an SQL query that removes duplicates while preserving the order of first appearance. Two strings are considered duplicates if they are equal case-insensitively (e.g., 'A' and 'a' are duplicates), but you must return the original casing from the first occurrence. The output should list the deduplicated elements in the order of their first appearance. Table: items - Each row represents one element of the input list. - position defines the order in the original list (1-based). - value is the string element. Return one row per distinct value (case-insensitive), keeping the row corresponding to the first occurrence (smallest position) for each case-insensitive value, and ordering the final result by position ascending. For the sample data provided, the sequence ['A','b','a','B','c','C','b'] should produce ['A','b','c'] in that order.

Tables

items(position INT, value VARCHAR(10))

Hints

Use LOWER(value) (or a similar function) to compare strings case-insensitively.
Consider a window function like ROW_NUMBER() partitioned by the case-insensitive value, then filter to keep only the first row per partition.