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][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:

  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[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:

  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][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:

  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.

Leave a Reply

Your email address will not be published. Required fields are marked *