Frontend School

Myntra Product Catalog Cleanup

DSA
easy

Myntra Product Catalog Cleanup

Easy
Stack
Arrays
String

Overview

Myntra's product catalog system manages millions of product IDs. Periodically, the catalog team performs cleanup operations. Due to various system integrations or manual entry errors, identical product IDs might sometimes appear consecutively in a processing list. These adjacent duplicates need to be efficiently removed to maintain data integrity and optimize downstream processes.

What you need to do / Task

Implement a function cleanCatalog that takes an array of product ID strings. Your task is to process this list and remove all adjacent duplicate product IDs. If removing a pair of duplicates leads to new adjacent duplicates, those should also be removed. This process must continue until no more adjacent duplicates can be found in the list.

Input & output

  • Input: productIds - An array of strings, where each string productIds[i] represents a unique product identifier.
  • Output: An array of strings representing the final, cleaned catalog after all adjacent duplicates have been removed.

Clarifications

  • Empty input: If the input productIds array is empty, the function should return an empty array.
  • Case sensitivity: Product IDs are case-sensitive. For example, "Shirt" is considered different from "shirt".

Examples

1

Example 1

Input:

productIds = ["A", "B", "B", "C", "A"]

Output:

["A", "C", "A"]

Note:

The adjacent 'B's are removed. The list becomes ["A", "C", "A"]. No further adjacent duplicates.

2

Example 2

Input:

productIds = ["M", "Y", "N", "N", "T", "R", "A", "A", "Y"]

Output:

["M", "Y", "T", "R", "Y"]

Note:

  1. ["M", "Y", "N", "N", "T", "R", "A", "A", "Y"] -> Remove 'N','N' -> ["M", "Y", "T", "R", "A", "A", "Y"]
  2. ["M", "Y", "T", "R", "A", "A", "Y"] -> Remove 'A','A' -> ["M", "Y", "T", "R", "Y"] No further adjacent duplicates.
3

Example 3

Input:

productIds = ["P", "P", "Q", "Q", "R", "R"]

Output:

[]

Note:

  1. Remove 'P','P' -> ["Q", "Q", "R", "R"]
  2. Remove 'Q','Q' -> ["R", "R"]
  3. Remove 'R','R' -> []

Constraints

Constraints & assumptions

  • 1 <= productIds.length <= 10^5
  • 1 <= productIds[i].length <= 10
  • productIds[i] consists of alphanumeric characters (a-z, A-Z, 0-9).

Out of scope

  • Error handling for malformed product IDs (assume valid alphanumeric strings).
  • Database interactions or persistence of the cleaned catalog.

What interviewers evaluate

  • Correctness of the algorithm in handling all scenarios, including cascading removals.
  • Efficiency in terms of time and space complexity.
  • Code readability, structure, and adherence to standard coding practices.
  • Ability to articulate the chosen approach and analyze its complexity.

Loading editor...