Coding Exercise

Requirement:

I am creating my budget for the next month. Besides regular spending, I also added a list of extra items I want to buy. I added my budget amount and realized that it has exceeded my planned spending amount, so I want to eliminate some items in order to cut down my budget.

You are a developer at Mint. In order to help me manage my personal finance better, you are giving me suggestions of what items I should remove from my budget. What you are given is:

1. A list of extra items I want to buy. Each item has a name and an amount. (Ex. Name: “Backpack”, amount: 50.00). There are no duplicate items.
2. My current total budget amount for next month: n dollars.
3. My target total budget amount for next month: m dollars. (m < n)
Ex. - Name: "Backpack", amount: \$55.00
- Name: "Monitor", amount: \$100.00
- Name: "Water bottle", amount: \$10.00
- Name: "Tent", amount: \$150.00
- Name: "Headphone", amount: \$123.00

current total budget: \$1200.00
target total budget: \$1000.00

returning pair: "Backpack", "Tent"

If I only want to remove 2 items to lower my budget to target budget, is it possible? If so, which 2 items should I remove?

Q: How to get the biggest number which is smaller than the target, after removing no more than 2 items?

Clarification/Assumptions:

1. If the sum is smaller than target, remove nothing.
2. If multiple choices, any one would be acceptable.
3. If remove one item can make the sum smaller than target, and make the sum biggest, just remove one.
4. If remove the 2 biggest items still don’t work, return an empty list.
#!/usr/bin/env python3
## Complexity: Time O(n*log(n)), Space O(n)
class Solution(object):
def budgetAdvising2Items(self, items, prices, target):
"""
:type items: List[string]
:type prices: List[float]
:type target: float
:rtype: List[str]
"""
total = sum(prices)
# no need to remove items
if total <= target: return []
diff = total-target

# sort the list
l = sorted(zip(prices, items))

res = []
min_remove = total
# only need to remove one item
for (price, item) in l:
if price == total-target: return [item]
if price > total-target:
if price < min_remove:
min_remove = price
res = [item]
break

# if removing any two items won't work, we return []
if l[-1] + l[-2] < total-target: return []

# need to remove two items
left, right = 0, len(l)-1
while left<right:
v = l[left] + l[right]
if v == total-target:
return [l[left], l[right]]
if v < total-target:
left += 1
else:
# evaluate the candidate
if v < min_remove:
min_remove = v
res = [l[left], l[right]]
right -= 1
return sorted(res)

Q: How do you want to test your code?

• 1. Design testcases for normal cases
Normal case with 5 items

Normal cases with huge records, say 100+ items. This may happen for SMB.
But it's unlikely that we have tens of thousands of records in this scenario.

Target is bigger than the total

Removing one item instead of two would be the best choice
• 2. Design testcases for invalid input
The list is empty

The counts of of items and prices are not the same.

Some prices are not valid positive float

Duplicate names in the items
• 3. Enable code check for git push hook.
Static lint tests
Unit tests

Q: What changes you want to make, in order to get your code ready for production?

• Define exceptions, and throw exceptions for unexpected input or errors.
Thus the caller won't get false positive
• Provide lint checks and unit tests for integration.
As the code keeps changing, we might bring in regression issues.
Unit tests can help.
• Add logging for critical errors.
If any unexpected errors or exceptions have happened, write critical
log. Based on that, we can get proper notification via ELK, or even
*Slack* messages.
• Provide REST API for people to integrate the function.
People can design end-to-end tests based on the REST API. Monitoring
can also be built on top of this. This helps maintenance.
• If you use the functionality as a service, wrap up the solution as a microservice or a container.
Much easier to deploy and maintain.
Easy to scale, and more reliable.
We might want to do data mining to know more about our customers.
Say how often the individuals may run out of budget, by what ratios.

Thus we can send out notifications to another data store or a queue
for off-line data analysis.
• Do we need to support family shared accounts? If so, we might encounter concurrent writes.
Let's say we need to support that.
The husband has added many items, which leads to out of budget.
When our application try to give suggestions, the wife has deleted some items.

This means our suggestions might be out-of-date.
It could be misleading or confusing.

So how we can solve this? (Note: this is very unlikely to happen).

Though we might have coflicts, but they are unlikely to happen.

- So we simply add a validation check, when we propose the
suggestions. If the items have changed, we discard our
suggestions. Sort of CAS(Compare-And-Set) logic.

- Or use optimistic locking.

- Or use lock-free model. The program is a worker thread with its own
queue.

Q: What if I want to remove 3 items, if there are no 2 items that satisfy the requirement?

Clarification/Assumptions:

1. If we have better solutions to remove less then 3 items, remove that one.
2. If we have multiple solutions, return any one would be acceptable.
3. If we remove 3 largest items and it still doesn’t work, return an empty list.
#!/usr/bin/env python3
## Description :
##    Basic Ideas: Sort the list. Then use two pointers
##
##    Complexity: Time O(n*n), Space O(n)
class Solution(object):
def budgetAdvising3Items(self, items, prices, target):
"""
:type items: List[string]
:type prices: List[float]
:type target: float
:rtype: List[str]
"""
total = sum(prices)
# no need to remove items
if total <= target: return []

# sort the list
l = sorted(zip(prices, items))

# remove one or two items
res = self.budgetAdvising2Items(items, prices, target)
if res != []:
min_remove = 0
for item in res:
for x in l:
if x == item:
min_remove += x
break
else:
min_remove = total
for i in range(len(l)-2):
left, right = i+1, len(l) - 1
while left < right:
v = l[i] + l[left] + l[right]
if v == total-target:
return sorted([l[i], l[left], l[right]])
if v < total-target:
# need bigger items
left += 1
else:
if v < min_remove:
min_remove = v
res = [l[i], l[left], l[right]]
# need smaller items
right -= 1
return sorted(res)

def budgetAdvising2Items(self, items, prices, target):
"""
:type items: List[string]
:type prices: List[float]
:type target: float
:rtype: List[str]
"""
total = sum(prices)
# no need to remove items
if total <= target: return []
diff = total-target

# sort the list
l = sorted(zip(prices, items))

res = []
min_remove = total
# only need to remove one item
for (price, item) in l:
if price == total-target: return [item]
if price > total-target:
if price < min_remove:
min_remove = price
res = [item]
break

# if removing any two items won't work, we return []
if l[-1] + l[-2] < total-target: return []

# need to remove two items
left, right = 0, len(l)-1
while left<right:
v = l[left] + l[right]
if v == total-target:
return [l[left], l[right]]
if v < total-target:
left += 1
else:
# evaluate the candidate
if v < min_remove:
min_remove = v
res = [l[left], l[right]]
right -= 1
return sorted(res)

Q: What if I want to remove K items?

Clarification/Assumptions:

1. If we have multiple solutions, return any one would be acceptable.
2. If we have better solutions to remove less then K items, we still choose K items
#!/usr/bin/env python3
##  Basic Ideas:
##    Sort the list. Then use the idea of two pointers
##
##  Complexity: Time O(pow(n, K-1)), if K>=3.
##           Time O(n*log(n)), if K == 2
##           Time O(n), if K == 1
##           Time O(1), if K == 0
##           Space O(n)
class Solution(object):
def budgetAdvisingKItems(self, items, prices, target, K):
"""
:type items: List[string]
:type prices: List[float]
:type target: float
:type K: int
:rtype: List[str]
"""
total = sum(prices)
# no need to remove items
if total <= target: return []

if K <= 0: return []
if K >= len(items): return sorted(items)
if K == 1:
# linear check
res = []
min_remove = total
for i in range(len(items)):
# need bigger item
if prices[i] < target - total: continue
if prices[i] == target - total: return [items[i]]
# find a better candidate
if prices[i] < min_remove:
min_remove = prices[i]
res = [items[i]]
return res

# sort the list
l = sorted(zip(prices, items))
index_list = self.myBudgetAdvisingKItems(l, total-target, K, 0)
return sorted([l[i] for i in index_list])

def myBudgetAdvisingKItems(self, l, offset, K, start_index):
"""
:type l: List[(string, float)]
:type offset: float
:type K: int
:type start_index: int
:rtype: List[int]
"""
assert(K>=2)
if start_index == len(l): return []
total = sum([l[i] for i in range(start_index, len(l))])

res, min_remove = [], total
if K == 2:
left, right = start_index, len(l)-1
while left<right:
v = l[left] + l[right]
if v == offset:
return [left, right]
if v < offset:
# too small
left += 1
else:
# evaluate the candidate
if v < min_remove:
min_remove, res = v, [left, right]
right -= 1
return res

# K>=3
for i in range(start_index, len(l)-1):
if l[i] >= offset: continue
index_list = self.myBudgetAdvisingKItems(l, offset-l[i], K-1, i+1)
if index_list != []:
index_list = [i] + [k for k in index_list]
sum_removed = sum([l[k] for k in index_list])
if sum_removed < min_remove:
min_remove, res = sum_removed, index_list
return res

Q: I don’t have number of item limit, show me all the possible combinations of items I can remove to lower my budget.

Clarification/Assumptions:

1. Show all combinations with the optimal values.
2. Not showing all combinations whose sum is no bigger than the budget. If we remove everyting, it could work. But it’s not what we want.
#!/usr/bin/env python3
## Description :
##    Basic Ideas: Sort the list. Then BFS
##
##    The worst case: the budget is so low that we have to remove almost all items
##
##    Complexity: Time O(pow(2, n))
##                Space O(pow(2, n))
import sys
class Solution(object):
def budgetAdvisingItems(self, items, prices, target):
"""
:type items: List[string]
:type prices: List[float]
:type target: float
:rtype: List[str]
"""
import collections
if len(items) == 0: return []
total = sum(prices)
# no need to remove items
if total <= target: return []

min_diff, res = total, []
l = sorted(zip(prices, items))
queue = collections.deque([([], total-target)])

for i in range(len(l)):
(price, item) = l[i]
for j in range(len(queue)):
(item_list, diff) = queue.popleft()
# get the neighbors
# don't select current item
queue.append((item_list, diff))
# select current item
if price < diff:
queue.append((item_list+[item], diff-price))
else:
# we get candidates
if (price-diff) == min_diff: res.append(item_list+[item])
if (price-diff) < min_diff:
res, min_diff = [item_list+[item]], (price-diff)
return res

Share It, If You Like It.