Quick Overview

Given a store map listing the department of each product and a shopping list that may repeat items, compute the minimum number of department visits needed to buy everything when items may be bought in any order. It tests turning a word problem into a precise counting rule and handling large inputs efficiently.

Minimum Department Visits to Buy a Shopping List from a Store Map

Company: Whatnot

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

A store map lists every product in a store together with the department where it is shelved. You have a shopping list of products to buy. Walking into a department and buying any number of items there counts as one department visit. If you shopped strictly in list order, you could leave a department and later come back to it, and each return would count as another visit. You are free to buy the items in any order. Return the minimum number of department visits needed to buy every item on the shopping list. ### Function Signature ```python def min_department_visits(store_map: list[list[str]], shopping_list: list[str]) -> int: ``` ### Rules - `store_map[i] = [product, department]`. Each product appears in exactly one entry of `store_map`. - Every item on `shopping_list` appears as a product in `store_map`. An item may appear on the list more than once, and every copy must be bought. - Product and department names are compared exactly, as case-sensitive strings. - A department that holds no item on the list is never visited. ### Constraints - `1 <= len(store_map) <= 10^5` - `1 <= len(shopping_list) <= 10^5` - Every product and department name is a non-empty string of at most 30 characters made of letters, digits, spaces and hyphens. ### Examples **Example 1** ```text Input: store_map = [["milk", "Dairy"], ["cheddar", "Dairy"], ["apple", "Produce"], ["bread", "Bakery"], ["yogurt", "Dairy"], ["banana", "Produce"]], shopping_list = ["milk", "apple", "cheddar", "banana", "milk"] Output: 2 ``` Shopping in list order would take 5 visits (Dairy, Produce, Dairy, Produce, Dairy). One Dairy visit for both copies of milk and the cheddar plus one Produce visit for the apple and the banana needs only 2. **Example 2** ```text Input: store_map = [["milk", "Dairy"], ["cheddar", "Dairy"], ["apple", "Produce"], ["bread", "Bakery"], ["yogurt", "Dairy"], ["banana", "Produce"]], shopping_list = ["apple", "bread", "yogurt", "banana"] Output: 3 ``` Shopping in list order would take 4 visits (Produce, Bakery, Dairy, Produce). Buying the apple and the banana in one Produce visit leaves one visit each to Produce, Bakery and Dairy. **Example 3** ```text Input: store_map = [["tent", "Camping"]], shopping_list = ["tent"] Output: 1 ```

Overview: Given a store map listing the department of each product and a shopping list that may repeat items, compute the minimum number of department visits needed to buy everything when items may be bought in any order. It tests turning a word problem into a precise counting rule and handling large inputs efficiently.

Read the full Whatnot Software Engineer interview experience this question came from

A store map lists every product in a store together with the department where it is shelved. You are given `store_map`, where `store_map[i] = [product, department]`, and a shopping list `shopping_list` of products to buy. Walking into a department and buying any number of items there counts as one department visit. If you shopped strictly in list order, you could leave a department and later come back to it, and each return would count as another visit. You are free to buy the items in any order. Return the minimum number of department visits needed to buy every item on the shopping list. **Rules** - Each product appears in exactly one entry of `store_map`. - Every item on `shopping_list` appears as a product in `store_map`. An item may appear on the list more than once, and every copy must be bought. - Product and department names are compared exactly, as case-sensitive strings. - A department that holds no item on the list is never visited. The answer is an integer between 1 and 10^5, so it fits in a signed 32-bit integer in every language. **Constraints** - `1 <= len(store_map) <= 10^5` - `1 <= len(shopping_list) <= 10^5` - Every product and department name is a non-empty string of at most 30 characters made of letters, digits, spaces and hyphens. **Example 1** ```text Input: store_map = [["milk", "Dairy"], ["cheddar", "Dairy"], ["apple", "Produce"], ["bread", "Bakery"], ["yogurt", "Dairy"], ["banana", "Produce"]], shopping_list = ["milk", "apple", "cheddar", "banana", "milk"] Output: 2 ``` Shopping in list order would take 5 visits (Dairy, Produce, Dairy, Produce, Dairy). One Dairy visit for both copies of milk and the cheddar plus one Produce visit for the apple and the banana needs only 2. **Example 2** ```text Input: store_map = [["milk", "Dairy"], ["cheddar", "Dairy"], ["apple", "Produce"], ["bread", "Bakery"], ["yogurt", "Dairy"], ["banana", "Produce"]], shopping_list = ["apple", "bread", "yogurt", "banana"] Output: 3 ``` Shopping in list order would take 4 visits (Produce, Bakery, Dairy, Produce). Buying the apple and the banana in one Produce visit leaves one visit each to Produce, Bakery and Dairy, so 3 visits suffice.

Constraints

  • 1 <= len(store_map) <= 10^5
  • 1 <= len(shopping_list) <= 10^5
  • store_map[i] = [product, department]; each product appears in exactly one entry of store_map
  • Every item on shopping_list appears as a product in store_map; an item may appear more than once and every copy must be bought
  • Every product and department name is a non-empty string of at most 30 characters made of letters, digits, spaces and hyphens
  • Product and department names are compared exactly, as case-sensitive strings

Examples

Input: ([['milk', 'Dairy'], ['cheddar', 'Dairy'], ['apple', 'Produce'], ['bread', 'Bakery'], ['yogurt', 'Dairy'], ['banana', 'Produce']], ['milk', 'apple', 'cheddar', 'banana', 'milk'])

Expected Output: 2

Explanation: Source Example 1: one Dairy visit covers both milks and the cheddar, one Produce visit covers apple and banana; list-order shopping would take 5.

Input: ([['milk', 'Dairy'], ['cheddar', 'Dairy'], ['apple', 'Produce'], ['bread', 'Bakery'], ['yogurt', 'Dairy'], ['banana', 'Produce']], ['apple', 'bread', 'yogurt', 'banana'])

Expected Output: 3

Explanation: Source Example 2: Produce, Bakery and Dairy once each; list-order shopping would take 4.

Hints

  1. You may buy the items in any order. Does the order of shopping_list change the answer at all?
  2. Once you walk into a department, how many of the listed items shelved there can you pick up during that single visit?
  3. Which departments must you enter at least once, and which ones can you skip entirely?

Loading coding console...

Show the approach

Approach

Because the items may be bought in any order, the order of shopping_list does not affect the answer. Lower bound: every department that shelves at least one listed item must be entered at least once, so the answer is at least the number of such departments. Upper bound: entering each of those departments exactly once and buying every listed item shelved there (all repeated copies included) buys the whole list, so that many visits suffice. Departments that hold no listed item are never entered. The answer is therefore the number of distinct departments among the listed items. The algorithm builds a product-to-department map from store_map, looks up the department of each list item, collects those departments in a set, and returns the set's size. Edge cases: repeated list items and several listed items in one department add no visits; names are compared exactly, so departments that differ only by case, spaces or hyphens are distinct; the list is non-empty, so the answer is at least 1, and it is at most 10^5, which fits a signed 32-bit integer. Name length is at most 30, so each hash operation is treated as constant time.

Time complexity:
O(n + m)
Space complexity:
O(n)