Brand Filter

TIP103 Unit 4 Session 1 (Click for link to problem statements)

U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Q: What is the structure of the input?

  • A: The input is a list of dictionaries, where each dictionary represents a brand with a "name" key and a "criteria" key containing a list of strings.

• Q: What is the output?

  • A: The output is a list of brand names (strings) that meet the specified criterion.

• Q: What should the function return if no brands meet the criterion?

  • A: The function should return an empty list.

• Q: Are there any constraints on the input, such as the presence of the "criteria" key in each dictionary?

  • A: It is assumed that each dictionary in the list will have both a "name" key and a "criteria" key with corresponding values.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Iterate through the list of brands, checking each brand's criteria to see if it includes the specified criterion. If it does, add the brand's name to the list of sustainable brands.

1) Initialize an empty list called `sustainable_brands`.
2) For each `brand` in `brands`:
   a) If the `criterion` is in the `brand["criteria"]`, append the `brand["name"]` to `sustainable_brands`.
3) Return the `sustainable_brands` list.

⚠️ Common Mistakes

• Forgetting to handle cases where the list of brands is empty.
• Not correctly checking the presence of the criterion in the criteria list.

I-mplement

def filter_sustainable_brands(brands, criterion):
    sustainable_brands = []
    for brand in brands:
        if criterion in brand["criteria"]:
            sustainable_brands.append(brand["name"])
    return sustainable_brands

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Definitions:

• n is the number of brands
• m is the total number of criteria

Using Python's in operator to check if a criterion is in a list requires linear time relative to the list size. The total time will be O(m), where m is the total number of criteria.

• Time Complexity: O(m) where m is the total number of criteria across all brands. It is also correct to say O(n * m) where m is the maximum or average number of criteria per brand.
• Space Complexity: O(n) for the output list, which holds at most n brand names.