CareerCup

1. Maintain list of stores for each product
2. Scan list of stores for x items and get the store that has maximum number of items.
3. Again scan the remaining list of items and get the store that has maximum number of items.
4. Repeat 3 until the number of items remaining becomes 0.

Complexity:
Number of items = x
Number of stores that have each item = y
Complexity worst case = (x^2)y

Can you please write Code for your solution

@Alok
Counter example:

items =  x1 x2 x3 x4 x5
store_1: x1 x2 x3 x4
store_2: x1 x2 x5
store_3: x3 x4

The optimal set of stores is store_2 and store_3 but your algorithm with pick them all starting from store_1.

To be more specific this is a Set Cover Problem.

This algo won't work for few cases, one such case like -

Store 1 = x1, x2, x3
Store 2 = x1, x2, y3
Store 3 = x3, z1, z2, z3


Customer List = x1, x2, x3, y3, z3

Per above algo, you'll have to go to all 3 stores to get all items in customer list.
But here, Store 2 and Store 3 has all items in the list. No need to go to Store 1 at all.

def trace(*args):
    traceOn = False
    if traceOn:
        print(*args)

class Net:
    '''
    Allows finding a minimal set of stores which can serve an order.
    Returns these stores and the products of interest that they have.
    The same product might be shown for several stores if they all
    have that. Nethertheless, the list of stores will be optimal.
    '''
    
    def __init__(self):
        self._s = {}
    
    def addStore(self, name, *prods):
        print("Store %10s has  %s"%(name, prods))
        self._s[name] = set(prods)
    
    def getStores(self, *prods):
        res = {}
        matched_prods = {} # set of (product tuples)->store name
        count_prods = {p:[] for p in prods}
        search = set(prods)
        for s,p in self._s.items():
            match = p & search
            # perfect match
            if len(match) == len(search):
                return 'prods: %16s  %s'%(search, str({s:search}))
            # quickly skip stores which have exactly the same products
            if tuple(match) in matched_prods:
                # this store is not any better than the one we already found
                continue
            matched_prods[tuple(match)] = s
            res[s] = match
            for p in match:
                count_prods[p].append(s)
        
        trace("count_prods=",count_prods)
        
        # prepare to drop stores with less number of useful products
        # 1. we will for take stores with unique products and as a result all other their products
        # 2. now we need to care only about all other products when dropping excessive stores
        # We will sort stores in order of remaining useful products
        # and drop those which have all products covered by stores below them in the list
        uniq = {p for p,stores in count_prods.items() if len(stores)==1}
        trace("uniq=", uniq)
        uniq_and_related = set()
        for s,p in res.items():
            if len(p & uniq)>0:
                uniq_and_related |= p
        trace("uniq_and_related=", uniq_and_related)
        
        noof_matches_exc_uniq = {s:len(res[s]-uniq_and_related) for s,k in res.items()}
        stores_sorted = sorted(noof_matches_exc_uniq.items(), key=lambda x: x[1])
        trace("stores_sorted=", stores_sorted)
        
        # drop out stores which have less of requested products
        for store in stores_sorted:
            s = store[0]
            # drop the store if all its items are covered by other stores together
            cumulative_os = set()
            for os in list(res.keys()): # os is other store
                if s == os:
                    continue
                # check because we drop stores on the go
                if s not in res.keys() or os not in res.keys():
                    continue
                s_specials = res[s] - res[os]
                os_specials = res[os] - res[s]
                if len(os_specials) == 0:
                    del res[os]
                elif len(s_specials) == 0:
                    del res[s]
                else:
                    cumulative_os.update(res[os])
            # drop if these products are covered by other stores
            if s in res.keys() and len(res[s] - cumulative_os) == 0:
                del res[s]
        return 'prods: %16s  %s'%(search, str(res))

n = Net()
n.addStore('Amazon', 1,2,3)
n.addStore('Ozon', 3, 4)
n.addStore('Wallmart1', 5)
n.addStore('Wallmart2', 5)
n.addStore('Wallmart3', 5)
n.addStore('AliExpress', 3, 6)
n.addStore('Ebay', 1,2,5)

print(n.getStores(1))
print(n.getStores(1,3))
print(n.getStores(1,5))
print(n.getStores(3,4,5))
print(n.getStores(1,3,5))
print(n.getStores(1,2,3,4,5))
print(n.getStores(3,5))
print(n.getStores(1,2,4,6))

print("===")
n2 = Net()
n2.addStore('st_1', 'x1', 'x2', 'x3', 'x4')
n2.addStore('st_2', 'x1', 'x2', 'x5')
n2.addStore('st_3', 'x3', 'x4')
print(n2.getStores('x1', 'x2', 'x3', 'x4', 'x5'))
print("===")
n3 = Net()
n3.addStore('st_1', 'x1', 'x2', 'x3')
n3.addStore('st_2', 'x1', 'x2', 'y3')
n3.addStore('st_3', 'x3', 'z1', 'z2', 'z3')
print(n3.getStores('x1', 'x2', 'x3', 'y3', 'z3'))
print("===")
n4 = Net()
n4.addStore('st_1', 1,2)
n4.addStore('st_2', 1,'a')
n4.addStore('st_3', 2,'a')
n4.addStore('st_4', 3,'a','z')
print(n4.getStores(1,2,3,'a','x','z'))

Output

Store     Amazon has  (1, 2, 3)
Store       Ozon has  (3, 4)
Store  Wallmart1 has  (5,)
Store  Wallmart2 has  (5,)
Store  Wallmart3 has  (5,)
Store AliExpress has  (3, 6)
Store       Ebay has  (1, 2, 5)
prods:              {1}  {'Amazon': {1}}
prods:           {1, 3}  {'Amazon': {1, 3}}
prods:           {1, 5}  {'Ebay': {1, 5}}
prods:        {3, 4, 5}  {'Ozon': {3, 4}, 'Wallmart1': {5}}
prods:        {1, 3, 5}  {'Amazon': {1, 3}, 'Ebay': {1, 5}}
prods:  {1, 2, 3, 4, 5}  {'Ozon': {3, 4}, 'Ebay': {1, 2, 5}}
prods:           {3, 5}  {'Amazon': {3}, 'Wallmart1': {5}}
prods:     {1, 2, 4, 6}  {'Amazon': {1, 2}, 'Ozon': {4}, 'AliExpress': {6}}
===
Store       st_1 has  ('x1', 'x2', 'x3', 'x4')
Store       st_2 has  ('x1', 'x2', 'x5')
Store       st_3 has  ('x3', 'x4')
prods: {'x4', 'x5', 'x3', 'x2', 'x1'}  {'st_1': {'x3', 'x4', 'x2', 'x1'}, 'st_2': {'x5', 'x2', 'x1'}}
===
Store       st_1 has  ('x1', 'x2', 'x3')
Store       st_2 has  ('x1', 'x2', 'y3')
Store       st_3 has  ('x3', 'z1', 'z2', 'z3')
prods: {'y3', 'x3', 'x2', 'z3', 'x1'}  {'st_2': {'x2', 'x1', 'y3'}, 'st_3': {'z3', 'x3'}}
===
Store       st_1 has  (1, 2)
Store       st_2 has  (1, 'a')
Store       st_3 has  (2, 'a')
Store       st_4 has  (3, 'a', 'z')
prods: {1, 2, 3, 'x', 'a', 'z'}  {'st_1': {1, 2}, 'st_4': {'a', 3, 'z'}}

@Alok you are right. you missed a step. Once, you fix the store with the maximum products, you have to remove those products from all the stores.