Interview Question
Software DevelopersCountry: United States
Interview Type: In-Person
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'}}
1. Maintain list of stores for each product
- Alok September 18, 20182. 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