Karat VO 面试真题解析：Shopping List Department Visits

Given an unsorted list of products with their departments and a shopping list, return the time saved in terms of the number of department visits eliminated.

Example:

products = [["Cheese", "Dairy"],
    ["Carrots", "Produce"],
    ["Potatoes", "Produce"],
    ["Canned Tuna", "Pantry"],
    ["Romaine Lettuce", "Produce"],
    ["Chocolate Milk", "Dairy"],
    ["Flour", "Pantry"],
    ["Iceberg Lettuce", "Produce"],
    ["Coffee", "Pantry"],
    ["Pasta", "Pantry"],
    ["Milk", "Dairy"],
    ["Blueberries", "Produce"],
    ["Pasta Sauce", "Pantry"]
]

list1 = ["Blueberries", "Milk", "Coffee", "Flour", "Cheese", "Carrots"]
list2 = ["Blueberries", "Carrots", "Coffee", "Milk", "Flour", "Cheese"]
list3 = ["Blueberries", "Carrots", "Romaine Lettuce", "Iceberg Lettuce"]
list4 = ["Milk", "Flour", "Chocolate Milk", "Pasta Sauce"]
list5 = ["Cheese", "Potatoes", "Blueberries", "Canned Tuna"]

For example, buying the items from list1 in order would take 5 department visits, whereas your method would lead to only visiting 3 departments, a difference of 2 departments.

Return the number of department visits eliminated for each shopping list.

All test cases:

shopping(products, list1) => 2
shopping(products, list2) => 2
shopping(products, list3) => 0
shopping(products, list4) => 2
shopping(products, list5) => 0

这题本质上是把购物清单中的商品映射到所属部门，然后统计“按原顺序购买”与“按部门尽量合并后购买”之间能减少多少次部门切换。做法通常是先用哈希表建立 product -> department 的映射，再遍历 shopping list，记录商品所属部门的变化次数；如果能把同一部门的商品尽量合并到一次访问中，就能得到最少部门访问数，最后用原始访问次数减去优化后的访问次数即可。样例里 list1 的商品分散在 Produce、Dairy、Pantry 之间，因此能节省 2 次访问；而 list3 和 list5 中商品本身已经集中或无法进一步减少，所以答案为 0。