Sort products by price and attention score
Company: Coupang
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
You are given a list of strings, each formatted as "product,price,attention". Parse the list into records and return the product names sorted to prioritize low price and high attention: sort by price ascending, then by attention descending, and finally by product name lexicographically to break any remaining ties. Assume price and attention are integers. Ignore malformed entries (missing fields or non-numeric price/attention). Describe your approach, data structures used, time and space complexity, and provide working code.
Overview: This question evaluates the ability to parse and sanitize input strings, implement multi-key sorting with numeric and lexicographic tie-breakers, and analyze time and space complexity while correctly handling malformed records.
You are given a list of strings where each string should represent one product record in the format "product,price,attention". Parse the valid records and return only the product names sorted with the following priority: price ascending, attention descending, and product name lexicographically ascending to break remaining ties. Price and attention are integers. Ignore malformed entries, including entries that do not have exactly three comma-separated fields or entries whose price or attention cannot be parsed as an integer. Whitespace around fields should be ignored. Approach: scan the input once, parse valid records into tuples, then sort using a tuple key of (price, -attention, product_name).
Constraints
- 0 <= len(entries) <= 100000
- Each entry has length at most 1000
- A valid entry must have exactly three comma-separated fields
- price and attention must be valid integers
- Each valid record contributes one product name to the output, even if product names are duplicated
Examples
Input: (["phone,699,80", "case,19,40", "charger,29,70", "cable,9,70"],)
Expected Output: ["cable", "case", "charger", "phone"]
Explanation: The records are sorted by increasing price: cable costs 9, case 19, charger 29, and phone 699.
Input: (["alpha,10,5", "beta,10,8", "gamma,10,8", "delta,5,1"],)
Expected Output: ["delta", "beta", "gamma", "alpha"]
Explanation: delta has the lowest price. Among the price-10 products, beta and gamma have attention 8 and come before alpha with attention 5. beta comes before gamma lexicographically.
Hints
- After parsing a valid record, consider storing a tuple that represents the desired sort order.
- Descending attention can be handled in an ascending sort by using the negative of the attention score.
Community answers
Answer by nisargshah1496
def solution(entries):
"" "Parses product entries, filters malformed ones, and returns sorted product names." ""
valid_products = []
for entry in entries:
parts = entry.split(",")
if len(parts) != 3:
continue
product_name = parts[0].strip()
price_str = parts[1].strip()
attention_str = parts[2].strip()
try:
price = int(price_str)
attention = int(attention_str)
except ValueError:
continue
# Using price ascending, attention descending (via negation), product_name ascending
valid_products.append((price, -attention, product_name))
valid_products.sort()
return [p[2] for p in valid_products]