Eco Friendly Materials

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 "materials" key containing a list of strings.

• Q: What is the output?

  • A: The output is a dictionary where the keys are material names, and the values are the counts of how many times each material appears across all brands.

• Q: What should the function return if no brands use any materials?

  • A: The function should return an empty dictionary.

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

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

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Iterate through the list of brands, and for each brand, iterate through its materials. Count the occurrences of each material using a dictionary.

1) Initialize an empty dictionary called `material_count`.
2) For each `brand` in `brands`:
   a) For each `material` in `brand["materials"]`:
      i) If the `material` is already in `material_count`, increment its count.
      ii) If the `material` is not in `material_count`, add it with a count of 1.
3) Return the `material_count` dictionary.

⚠️ Common Mistakes

• Forgetting to correctly initialize the material count when encountering a material for the first time.
• Assuming that all brands will have materials without verifying.

I-mplement

def count_material_usage(brands):
    material_count = {}

    for brand in brands:
        for material in brand["materials"]:
            if material in material_count:
                material_count[material] += 1
            else:
                material_count[material] = 1

    return material_count

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 materials
• p is the number of distinct materials (upper bound: m)

• Time Complexity: O(n + m) — O(n) for iterating over brands, plus O(m) for all the in operations across all materials.
• Space Complexity: O(p) where p is the number of distinct materials, since the dictionary stores one entry per unique material. This is O(m) if p is unknown.