Coding questions · Yahoo
Use OrderedDict to dedupe stably
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.
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.
Deduplicate Strings Case-Insensitively While Preserving Order
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.
Table items
| column | type | constraints |
|---|---|---|
| position | INT | PRIMARY KEY, NOT NULL |
| value | VARCHAR(10) | NOT NULL |
Sample data:
| position | value |
|---|---|
| 1 | A |
| 2 | b |
| 3 | a |
| 4 | B |
| 5 | c |
| 6 | C |
| 7 | b |
Expected output
One row per distinct value (case-insensitive), keeping the first occurrence (smallest position) and preserving that original casing, ordered by position ascending. For the sample data, this corresponds to the first 'A', the first 'b', and the first 'c'.
| position | value |
|---|---|
| 1 | A |
| 2 | b |
| 5 | c |
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.