## Interview Question for Software Developers

Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

Comment hidden because of low score. Click to expand.
0
of 0 vote

@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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

To be more specific this is a Set Cover Problem.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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 = {}

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()

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()
print(n2.getStores('x1', 'x2', 'x3', 'x4', 'x5'))
print("===")
n3 = Net()
print(n3.getStores('x1', 'x2', 'x3', 'y3', 'z3'))
print("===")
n4 = Net()
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'}}

Comment hidden because of low score. Click to expand.
-1
of 1 vote

@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.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.