Amazon Interview Question
SDE-2sCountry: United States
Interview Type: In-Person
Kind of challenging to do this from scratch by writing algorithms, but using in-built libraries, we can come up with elegant code that gets the job done! :) For this problem, we need to use a mix of dictionaries/hashmaps + combinations generator + max-heaps. If we were doing this from scratch, obviously, this would amount to a lot of code! Therefore, I have outlined an elegant solution below.
Elegant solution in Python below:
import itertools
from collections import defaultdict
import heapq
class Product:
def __init__(self, aisleId, productId, price):
self.aisleId = aisleId
self.productId = productId
self.price = price
def getKHighestPrices(products, k):
# Structure of the data structure will be as follows:
# Aisle IDs: [Prices]
aisleMap = defaultdict(list)
for product in products:
aisleMap[product.aisleId].append(product.price)
heap = []
for combination in itertools.product(*aisleMap.values()):
# The negation is for max-heaps
heapq.heappush(heap, (-sum(combination), combination))
result = []
while k > 0:
priceList = heapq.heappop(heap)[1]
formattedStringPriceList = ','.join([('$%s' % price) for price in sorted(priceList,reverse=True)])
result.append(formattedStringPriceList)
k = k - 1
return result
Test code:
# Aisle 1 Products
p11 = Product(1,100,4)
p12 = Product(1,101,2)
p13 = Product(1,102,5)
# Aisle 2 Products
p21 = Product(2, 200, 1)
p22 = Product(2, 201, 6)
totalProducts = [p11, p12, p13, p21, p22]
print(getKHighestPrices(totalProducts, 2)) #['$6,$5', '$6,$4']
print(getKHighestPrices(totalProducts, 5)) #['$6,$5', '$6,$4', '$6,$2', '$5,$1', '$4,$1']
- prithvish.mukherjee@techolution.com January 04, 2019