Determine Most Frequent Product Color in Carts
Company: Point72
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
##### Scenario
Online store wants to know which color of product appears most frequently in customers’ carts.
##### Question
Implement a function getMaxColor(colors: List[str]) that returns the color occurring most often; if there is a tie, return the lexicographically smallest color.
##### Hints
Count frequencies with a hash map, then find max by count and lexicographic order.
Quick Answer: This question evaluates proficiency in frequency analysis and deterministic tie-breaking for string data, assessing correctness in counting and selection logic.
Given a list of color names representing items in customers' carts, return the color that appears most frequently. If multiple colors share the highest frequency, return the lexicographically smallest color. The list has at least one element.
Constraints
- 1 <= len(colors) <= 100000
- Each color is a non-empty string of lowercase English letters (a-z)
- 1 <= len(color) <= 30
- Lexicographic order is standard string order (e.g., 'blue' < 'red')
Examples
Input:
Expected Output: red
Input:
Expected Output: blue
Input:
Expected Output: magenta
Input:
Expected Output: aaa
Solution
from typing import List
from collections import Counter
def getMaxColor(colors: List[str]) -> str:
freq = Counter(colors)
best_color = None
best_count = -1
for color, count in freq.items():
if count > best_count or (count == best_count and (best_color is None or color < best_color)):
best_count = count
best_color = color
return best_color
Explanation
Count each color using a dictionary (Counter). Then scan the (color, count) pairs, tracking the best answer so far. Update when a higher count is found, or when the count ties and the color is lexicographically smaller. This ensures we return the most frequent color with lexicographic tie-breaking.
Time complexity: O(n). Space complexity: O(k).
Hints
- Use a hash map (dictionary) to count occurrences of each color.
- Track the best (count, color) pair: prefer higher count, and for ties prefer smaller color.
- You can iterate the frequency map once to find the answer in O(k), where k is the number of distinct colors.