Karat VO Interview Coding Question: 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

This problem asks you to measure how many department visits can be saved by grouping shopping items by department instead of buying them strictly in list order. The key idea is to map each product to its department with a hash table, then count department transitions across the shopping list and compare that with the minimum number of grouped visits. In the example, list1 saves 2 visits because items from the same department can be combined, while some other lists already have no reducible transitions.