Sort products by price and attention score
Company: Coupang
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Quick Answer: 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.
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.