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:

- 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.
- My current total budget amount for next month: n dollars.
- 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:

- If the sum is smaller than target, remove nothing.
- If multiple choices, any one would be acceptable.
- If remove one item can make the sum smaller than target, and make the sum biggest, just remove one.
- 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][0] + l[-2][0] < total-target: return [] # need to remove two items left, right = 0, len(l)-1 while left<right: v = l[left][0] + l[right][0] if v == total-target: return [l[left][1], l[right][1]] if v < total-target: left += 1 else: # evaluate the candidate if v < min_remove: min_remove = v res = [l[left][1], l[right][1]] 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.

- Add event notification for business requirements.

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:

- If we have better solutions to remove less then 3 items, remove that one.
- If we have multiple solutions, return any one would be acceptable.
- 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[1] == item: min_remove += x[0] 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][0] + l[left][0] + l[right][0] if v == total-target: return sorted([l[i][1], l[left][1], l[right][1]]) if v < total-target: # need bigger items left += 1 else: if v < min_remove: min_remove = v res = [l[i][1], l[left][1], l[right][1]] # 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][0] + l[-2][0] < total-target: return [] # need to remove two items left, right = 0, len(l)-1 while left<right: v = l[left][0] + l[right][0] if v == total-target: return [l[left][1], l[right][1]] if v < total-target: left += 1 else: # evaluate the candidate if v < min_remove: min_remove = v res = [l[left][1], l[right][1]] right -= 1 return sorted(res)

Q: What if I want to remove K items?

Clarification/Assumptions:

- If we have multiple solutions, return any one would be acceptable.
- 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][1] 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][0] 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][0] + l[right][0] 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][0] >= offset: continue index_list = self.myBudgetAdvisingKItems(l, offset-l[i][0], K-1, i+1) if index_list != []: index_list = [i] + [k for k in index_list] sum_removed = sum([l[k][0] 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:

- Show all combinations with the optimal values.
- 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