Yahoo·Data Scientist·Technical Phone Screen·Intermediate

Intermediate

Jun 2026

Summary

Yahoo Data Scientist interview with a coding question that looked straightforward but had enough constraints layered on top that it took me a minute to get my footing. One question, but they really dug into the details.

Questions Asked (1)

Write a function that removes duplicates from a list while keeping the order of first appearance, in O(n) time and O(k) space where k is the number of unique elements. It must handle strings case-insensitively but return the original casing of the first occurrence. Then explain the complexity and what breaks if elements are not hashable.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

The case-insensitive part is what tripped me up initially.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the problem: the function must remove duplicates from a list while preserving the order of first appearance, handle strings case-insensitively, and return the original casing of the first occurrence. Then, propose a solution using a hash set to track seen elements (normalized to lowercase for strings) and a result list to maintain order, achieving O(n) time and O(k) space. Finally, discuss the complexity and the limitations when elements are not hashable, suggesting alternatives like sorting or using a custom hash function.

Pro tip: Demonstrate awareness of real-world data by mentioning that case-insensitive comparison should use casefold() for robust Unicode handling, and that for non-hashable elements, you might convert to a hashable form (e.g., tuples) or use a different approach like sorting, but note the trade-offs in time and order preservation.

1. Clarify requirements and edge cases

Restate the problem to ensure understanding: remove duplicates, preserve order of first appearance, handle strings case-insensitively, return original casing, and achieve O(n) time and O(k) space. Ask about edge cases like empty list, non-string elements, and mixed types.

2. Design the algorithm

Use a set to track seen elements (normalized for strings) and a result list. Iterate through the input, and for each element, compute a normalized key (e.g., lowercase for strings, the element itself otherwise). If the key is not in the set, add it to the set and append the original element to the result.

3. Implement the function

Write clean code with appropriate variable names. For strings, use casefold() or lower() for normalization. Ensure that non-string elements are handled correctly (e.g., they are hashable by default). Return the result list.

4. Analyze complexity

Explain that the algorithm runs in O(n) time because each element is processed once, and set lookups are O(1) on average. Space complexity is O(k) where k is the number of unique elements, as the set and result list store at most k elements.

5. Discuss non-hashable elements

Explain that if elements are not hashable (e.g., lists, dicts), the set-based approach fails. Alternatives include sorting (O(n log n) time, may not preserve order) or using a custom hash function if possible. Mention that for unhashable types, you might convert to a hashable representation (e.g., tuple) if the structure allows.

Key Points to Mention

Use a set for O(1) average-time lookups to achieve O(n) time complexity.
Normalize strings to lowercase (or casefold) for case-insensitive comparison, but store the original string in the result.
Space complexity is O(k) where k is the number of unique elements, as the set and result list each hold at most k elements.
Non-hashable elements (e.g., lists, dicts) cannot be added to a set; this breaks the O(n) approach.
For non-hashable elements, consider sorting (O(n log n)) or converting to a hashable form, but note trade-offs in order preservation and time.
Edge cases: empty list, all duplicates, mixed types (strings and non-strings) require careful handling of normalization.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.