11
\$\begingroup\$

Challenge from Hacker Rank -

Monica wants to buy a keyboard and a USB drive from her favorite electronics store. The store has several models of each. Monica wants to spend as much as possible for the items, given her budget.

Given the price lists for the store's keyboards and USB drives, and Monica's budget, find and print the amount of money Monica will spend. If she doesn't have enough money to both a keyboard and a USB drive, print -1 instead. She will buy only the two required items.

For example - with a budget of 10, two keyboards costing 3,1 & finally three drives available costing 5,2,8, the answer should be 9 as she is only able to purchase the keyboard for 3 and a drive for 5.

I've attempted to solve this logically and with good performance in mind. I'm not sure if I should be happy with my solution. I would appreciate any feedback.

My solution (which works) or my GitHub repo -

using System;
using System.Collections.Generic;
using System.Linq;

namespace ElectronicsShop
{
    class Program
    {
        static void Main(string[] args)
        {

            Console.WriteLine(GetMoneySpent(new int[] { 3, 1 }, new int[] { 5, 2, 8 }, 10));
            Console.WriteLine(GetMoneySpent(new int[] { 5}, new int[] { 4 }, 5));
            Console.ReadLine();
        }

        static int GetMoneySpent(int[] keyboards, int[] drives, int budget)
        {
            if (budget == 0)
                return -1;

            // sort the two arrays so the highest values are at the front
            keyboards = SortArrayDescending(keyboards);
            drives = SortArrayDescending(drives);

            // delete any that are over our budget
            var affordableKeyboards = GetAffordableItems(keyboards, budget);
            var affordableDrives = GetAffordableItems(drives, budget);

            // make a list to contain the combined totals
            var combinedTotals = new List<int>();

            foreach (var keyboard in keyboards)
            {
                foreach (var drive in drives)
                {
                    combinedTotals.Add(keyboard + drive);
                }
            }

            // sort the list & delete anything over budget
            combinedTotals.Sort();
            combinedTotals.Reverse();
            combinedTotals.RemoveAll(n => n > budget);

            return combinedTotals.Count == 0 ? -1 : combinedTotals[0];
        }

        static int[] SortArrayDescending(int[] array)
        {
            Array.Sort(array);
            Array.Reverse(array);

            return array;
        }

        static int[] GetAffordableItems(int[] array, int budget)
        {
            return array.Where(n => n < budget).ToArray();
        }
    }
}
\$\endgroup\$
  • 6
    \$\begingroup\$ Regarding the sample in the problem description, if Monica buys items costing \$3\$ and \$5 ,\$ wouldn't that just be \$8 ?\$ I think you meant that she buys the keyboard for \$1\$ and the USB-drive for \$8 ,\$ yielding the total of \$9 .\$ \$\endgroup\$ – Nat Jul 14 at 9:33
  • \$\begingroup\$ @Nat good spot! Yes you're right - I've fixed that now. Turns out I can't do basic Maths :) \$\endgroup\$ – Webbarr Jul 14 at 10:12
  • 1
    \$\begingroup\$ Before going for good code you should go for a good algorithm. It seems your algorithm has $O(nk)$ runtime and memory. The problem can however be solved in $O(n\log n+k\log k)$ time with $O(n+k)$ memory \$\endgroup\$ – Hagen von Eitzen Jul 14 at 21:11
  • \$\begingroup\$ What you may and may not do after receiving answers \$\endgroup\$ – Jamal Jul 14 at 22:37
7
\$\begingroup\$

3 good answers already, but there's more!


I don't like that you modify the array you are given. This sort of thing would need to be documented, and generally creates confusion for all. You don't need arrays as inputs, so you could take IEnumerables instead without any added cost, which makes the code easier to reuse and communicates to the consumer that you aren't modifying anything. I'd consider making the parameter names a little more explicit:

public static int GetMoneySpent(IEnumerable<int> keyboardPrices, IEnumerable<int> drivePrices, int budget)

Your SortArrayDescending modifies the array given, and then proceeds to return it: this is how to really annoying people, because they will assume that because the method returns something that it won't be modifying the input.


You've clearly thought about edge cases, which is good. You might consider some parameter validation (e.g. checking the budget makes sense, the arrays should not be null):

if (budget < 0)
    throw new ArgumentOutOfRangeException(nameof(budget), "Budget must be non-negative");
if (keyboardPrices == null)
    throw new ArgumentNullException(nameof(keyboardPrices));
if (drivePrices == null)
    throw new ArgumentNullException(nameof(drivePrices));

At the moment the program would print -1, which is sort of makes sense, but could easily be the first clue that something has gone wrong higher-up.


As implied by J_H, you should discard before the sort. The following also clones the arrays immediately so we don't modify them:

// filter to within-budget items, sort the two arrays (ascending)
keyboards = keyboards.Where(k => k < budget).ToArray();
Array.Sort(keyboards);

drives = drives.Where(d => d < budget).ToArray();
Array.Sort(drives);

J_H has already described how you can get the optimal time complexity, but you can perform the loops at the end very simply, without needing nesting or binary search or any of that.

You also don't need to record a list of all the candidates, just keep track of the current best, as Henrik Hansen has already demonstrated:

// maximum within budget price
int max = -1;

If we start by looking at the most expensive keyboard and cheapest drive and simultaneously iterate through both, we can do this bit in linear time.

int ki = keyboards.Length - 1; // drive index
int di = 0; // drive index

while (ki >= 0 && di < drives.Length)
{
    int candidate = keyboards[ki] + drives[di];
    if (candidate <= budget)
    {
        max = Math.Max(candidate, max);
        di++;
    }
    else
    {
        ki--;
    }
}

Suppose we are looking at keyboard ki and drive di: candidate is the sum of their costs. If this candidate cost is no more than the budget, then it is a candidate for the max. We also know that we can check for a more pairing by looking at the next most expensive drive, di + 1. If instead the candidate was out of the budget, we know we can find a cheaper candidate by looking at the next cheapest keyboard ki - 1.

Basically, we look at each keyboard in turn, and cycle through the drives until we find the most expensive one we can get away with. When we find the first drive that is too expensive, we move onto the next keyboard. We know that we don't want any drive cheaper than the last one we looked at, because that could only produce a cheaper pair, so we can continue our search starting from the same drive.

At the end, we just return max: if we didn't find any candidates below budget, it will still be -1:

return max;

Concerning dfhwze's comment about buying more than 2 items: this process is essentially searching the Pareto front, which is done trivially and efficiently for 2 items, but becomes nightmarish for any more, so I would certainly forgive you for sticking to 2 lists ;)


The above code all in one, with added inline documentation to make the purpose explicit (useful for the consumer, so that they know exactly what it is meant to do, and useful for the maintainer, so that they also know what it is meant to do):

/// <summary>
/// Returns the maximum price of any pair of a keyboard and drive that is no more than the given budget.
/// Returns -1 if no pair is within budget.
/// </summary>
/// <param name="keyboardPrices">A list of prices of keyboards.</param>
/// <param name="drivepricess">A list of prices of drives.</param>
/// <param name="budget">The maximum budget. Must be non-negative</param>
public static int GetMoneySpent2(IEnumerable<int> keyboardPrices, IEnumerable<int> drivePrices, int budget)
{
    if (budget < 0)
        throw new ArgumentOutOfRangeException(nameof(budget), "Budget must be non-negative");
    if (keyboardPrices == null)
        throw new ArgumentNullException(nameof(keyboardPrices));
    if (drivePrices == null)
        throw new ArgumentNullException(nameof(drivePrices));

    if (budget == 0)
        return -1;

    // filter to within-budget items, sort the two arrays (ascending)
    var keyboards = keyboardPrices.Where(k => k < budget).ToArray();
    Array.Sort(keyboards);

    var drives = drivePrices.Where(d => d < budget).ToArray();
    Array.Sort(drives);

    // maximum within budget price
    int max = -1;

    int ki = keyboards.Length - 1; // keyboard index
    int di = 0; // drive index

    while (ki >= 0 && di < drives.Length)
    {
        int candidate = keyboards[ki] + drives[di];
        if (candidate <= budget)
        {
            max = Math.Max(candidate, max);
            di++;
        }
        else
        {
            ki--;
        }
    }

    return max;
}

J_H's solution (using a BinarySearch) could well be better in practise, because you only need to sort (and binary search) the shortest input: you can scan the other however you like. Implementation of that, since I too enjoy the sport:

/// <summary>
/// Returns the maximum price of any pair of a keyboard and drive that is no more than the given budget.
/// Returns -1 if no pair is within budget.
/// </summary>
/// <param name="keyboardPrices">A list of prices of keyboards.</param>
/// <param name="drivepricess">A list of prices of drives.</param>
/// <param name="budget">The maximum budget. Must be non-negative</param>
public static int GetMoneySpent3(IEnumerable<int> keyboardPrices, IEnumerable<int> drivePrices, int budget)
{
    if (budget < 0)
        throw new ArgumentOutOfRangeException(nameof(budget), "Budget must be non-negative");
    if (keyboardPrices == null)
        throw new ArgumentNullException(nameof(keyboardPrices));
    if (drivePrices == null)
        throw new ArgumentNullException(nameof(drivePrices));

    if (budget == 0)
        return -1;

    // filter to within-budget items
    var keyboards = keyboardPrices.Where(k => k < budget).ToArray();
    var drives = drivePrices.Where(d => d < budget).ToArray();

    // determine which list is shorter
    IReadOnlyList<int> longList;
    int[] shortList;

    if (keyboards.Length < drives.Length)
    {
        shortList = keyboards;
        longList = drives;
    }
    else
    {
        shortList = drives;
        longList = keyboards;
    }

    // special case of empty short-list
    if (shortList.Length == 0)
        return -1;

    // sort shortList, to facilitate binary search
    Array.Sort(shortList);

    // maximum within budget price
    int max = -1;

    foreach (var k in longList)
    {
        // filter faster
        if (k + shortList[0] > budget)
            continue;

        // find most expensive drive no more than budget - k
        int i = Array.BinarySearch(shortList, budget - k);
        i = i >= 0
            ? i // found
            : ~i - 1; // not found, consider next smallest

        // if such a drive exists, consider it a candidate
        if (i >= 0)
        {
            int candidate = k + shortList[i];
            max = Math.Max(max, candidate);
        }
    }

    return max;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Now that's an answer! I'll be honest - quite a bit of that is over my head, but the exciting part of that is it's given me a lot of things to research & develop upon. I really appreciate the time you put into it, thank you. \$\endgroup\$ – Webbarr Jul 15 at 19:24
10
\$\begingroup\$

early pruning

This is very nice:

        // delete any that are over our budget

Doing it before sorting can slightly speed the sorting operation. I say slightly because "items over budget" is determined by the input, and it will be some fraction f of an input item category, so the savings is O(f * n * log n).

early discard

This is a bigger deal.

        // sort the list & delete anything over budget

For k keyboards and d drives, the sort does O(k * d * log k * d) work. Discarding within this loop would be an even bigger win.

consistent idiom

It was a little odd that you used

        combinedTotals.RemoveAll(n => n > budget);

and

        array.Where(n => n < budget).ToArray();

to accomplish the same thing. There's no speed difference but consider phrasing the same thing in the same way.

reversing

If you pass into Sort something that implements the IComparer interface, you can change the comparison order and thus skip the Reverse step entirely.

arithmetic

Arbitrarily choose one of the categories as the driving category, perhaps keyboard. Sort the drive prices, while leaving the keyboards in arbitrary order. Note the min drive price, and use that along with budget for immediately pruning infeasible keyboards.

Loop over all surviving keyboards. Target price is budget - kb_price. Do binary search over drives for the target, finding largest feasible drive, and use that to update "best combo so far". No need to sort them, you need only retain the "best" one.

\$\endgroup\$
  • 1
    \$\begingroup\$ The LINQ Where should be array.Where(n => n <= budget). But your key point is made. \$\endgroup\$ – Rick Davin Jul 14 at 16:10
  • 1
    \$\begingroup\$ This answer has given me a lot to reflect upon. I mentioned further down to someone who quoted you, some of the things in terms of binary search & IComparer (the latter I've used very briefly) are things I've been researching today. I'm honestly looking forward to implementing what I've learned into future projects. Thank you \$\endgroup\$ – Webbarr Jul 15 at 19:27
8
\$\begingroup\$

The good thing first:

You divide and conquer the problem by creating some reasonable (and well named) methods. You could have gone all in by making methods for combining and final selection as well:

  ...
  var combinedTotals = Combine(affordableKeyboards, affordableDrives);
  return SelectMaxBuy(combinedTotals, budget);
}

But as shown below, dividing the code into such small methods can sometimes obscure more useful approaches.


It must be a mind slip that you find the affordable keyboards and drives, but you forget about them and iterate over the full arrays of keyboards and drives:

        // delete any that are over our budget
        var affordableKeyboards = GetAffordableItems(keyboards, budget);
        var affordableDrives = GetAffordableItems(drives, budget);

        // make a list to contain the combined totals
        var combinedTotals = new List<int>();

        foreach (var keyboard in keyboards)
        {
            foreach (var drive in drives)
            {
                combinedTotals.Add(keyboard + drive);
            }
        }

I suppose that the loops should be:

        foreach (var keyboard in affordableKeyboards)
        {
            foreach (var drive in affordableDrives)
            {
                combinedTotals.Add(keyboard + drive);
            }
        }

Some optimizations:

  return array.Where(n => n < budget).ToArray();

Where has to iterate through the entire array, even if it is sorted. A better approach would have been to sort ascending first, then take untill n > budget, and then reverse:

array.OrderBy(n => n).TakeWhile(n => n <= budget).Reverse();

Making the almost same considerations with the combined totals:

  int result = combinedTotals.OrderByDescending(n => n).FirstOrDefault(n => n <= budget);

Your entire method could be refined to this:

static int GetMoneySpent(int[] keyboards, int[] drives, int budget)
{
  if (keyboards == null || keyboards.Length == 0 || drives == null || drives.Length == 0 || budget <= 0)
    return -1;

  keyboards = keyboards.OrderBy(n => n).TakeWhile(n => n <= budget).Reverse().ToArray();
  drives = drives.OrderBy(n => n).TakeWhile(n => n <= budget).Reverse().ToArray();

  // make a list to contain the combined totals
  var combinedTotals = new List<int>();

  foreach (var keyboard in keyboards)
  {
    foreach (var drive in drives)
    {
      combinedTotals.Add(keyboard + drive);
    }
  }

  int result = combinedTotals.OrderByDescending(n => n).FirstOrDefault(n => n <= budget);
  return result == 0 ? -1 : result;
}

Just for the sport I made the below solution, that sorts the data sets in ascending order and iterate backwards to avoid reversing the data:

int GetMoneySpent(int[] keyboards, int[] drives, int budget)
{
  if (keyboards == null || keyboards.Length == 0 || drives == null || drives.Length == 0 || budget <= 0)
    return -1;

  int result = -1;     

  Array.Sort(keyboards);
  Array.Sort(drives);

  int istart = keyboards.Length - 1;
  while (istart >= 0 && keyboards[istart] > budget) istart--;
  int jstart = drives.Length - 1;
  while (jstart >= 0 && drives[jstart] > budget) jstart--;

  for (int i = istart; i >= 0; i--)
  {
    int keyboard = keyboards[i];

    for (int j = jstart; j >= 0; j--)
    {
      int drive = drives[j];

      int price = keyboard + drive;
      if (price < result)
        break;

      if (price > result && price <= budget)
      {
        result = price;
      }
    }
  }

  return result;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Well that's embarassing. Definitely a slip of the brain in terms of forgetting to loop through the affordableKeyboards & affordableDrives arrays! Appreciate the feedback though, definite +1 from me. \$\endgroup\$ – Webbarr Jul 13 at 20:20
  • 2
    \$\begingroup\$ @Webbarr: I think, most of us know the feeling. You're not the first and won't be the last :-) \$\endgroup\$ – Henrik Hansen Jul 14 at 6:25
7
\$\begingroup\$

General Guidelines

  • You have coded everything in a single class Program. Take advantage of the fact C# is an object oriented language. Create at least one custom class that defines this problem.
  • Your current implementation is very strict and specific to 2 types of items. What if Monica needs to buy from n item types? It is up to you to decide the scope of your implementation, so what you have done is not wrong, but it is something to consider when building reusable code blocks. We can argue reusability of this exercise though.
  • When providing a method for consumers to use, make sure to include a handful of unit tests. This is an excellent way to get to know the outcome given any input. In this case, you are providing us GetMoneySpent, but we have to write our own unit tests to verify correctness of this method.

Review

  • You are using Array for a problem where IEnumerable could have also been used. Prefer the latter because you don't want to depend on fixed sized collections. You are converting ToArray(), this overhead should not be required when working with IEnumerable.
\$\endgroup\$
  • 1
    \$\begingroup\$ In terms of your first point, you're 100% correct. I tend to fall into a bad habbit of writing procedural code when I'm doing these types of challenges. I really shouldn't, kind of defeats the purpose. I get what you mean for point 2, I guess I kinda limited it because it was for a one time use in this specific challenge. It's a good idea to look at reusability for exercises though. Sorry about the lack of unit tests - I need to spend some more time improving my understanding of how they work, especially if I'm going to be posting stuff on code review. \$\endgroup\$ – Webbarr Jul 13 at 20:21
  • 1
    \$\begingroup\$ Well, it is tempting and easy to do it that way :) \$\endgroup\$ – dfhwze Jul 13 at 20:23
3
\$\begingroup\$

As others have pointed out, the code should be object oriented. It’s OK to start with procedural code as you have, but if you do, you should get in the habit of writing a quick test in your main entry point. Once you’ve written the first test, it can help you start seeing objects more clearly (and drive you to further unit tests.)

For example: an ElectronicsShop would only have a catalog of items, but it has nothing to do with your spending habits. In your case, it would serve only as a data store for items.

I’d really expect to see a Shopper class. The shopper would have both Money and a BuyingStrategy. The money could be a simple amount, but the strategy would be what you’re really working on. Finally, the strategy would expose a method Shop(Store, Items[], Budget).

Inside Shop(), you’d retrieve the items from the store that meet your criteria: they’d be only keyboards and drives, and they’d be within budget. The shopper would add only eligible items to their comparison lists. Then comes time to evaluate them , so you’d add an Evaluate(Budget, ItemLists[]) method that would be called from within Shop(). Inside Evaluate() you can order results by price. But what happens when you get multiple answers that meet the same amount? A budget of 10 would be met by any of {9,1}, {1,9}, {6,4}, or even {5,5}! Which is more important, expensive drives or expensive keyboards? (In the real world, you’d go back to your product owner at this point and ask them about their priorities: “do you prefer the most expensive drive, the most expensive keyboard, or should it try to split the difference somehow?”) This might lead you to conclude that Evaluating is really the strategy, not Buying.

I could go on, but I think I’ve made my point. Notice how once I’ve defined just a few relevant objects that the process I’m describing begins to mirror the real world act of shopping? And once you start down this path of viewing coding problems as models of real objects interacting in the real world, you’ll see the ease of defining objects and writing tests for them, and using them to recognize shortcomings in the specs and completing your specifications. (Pro tip: specifications are always incomplete.)

Performance isn’t always the best starting point. Object oriented programming is less about finding the most mathematically efficient solution; it’s about building understandable components and proving that they meet your clients’ needs. Getting to the right answer is much more important than quickly getting to some answer that you can’t prove is correct. If performance is an issue after you’ve solved the problem, then start optimizing; but don’t start there.

\$\endgroup\$
  • 1
    \$\begingroup\$ Thank you! I really appreciate your answer. It's given me quite a lot to think about (especially going back over this particular challenge) but also in my job today. I've definitely fallen into a nasty habbit of writing procedural code & releasing it, it's something I need to stop. Your answer just makes sense I guess. Again, thank you. \$\endgroup\$ – Webbarr Jul 15 at 19:21
2
\$\begingroup\$

I'd like to advocate for a more functional programming style. We all know object orientation can provide clarity over procedural programming, but if you can replace for loops and if statements with Select and Where? I'd say that's even better.

Here's how:

public static int GetMoneySpent(int budget, int[] keyboards, int[] drives)
{
    var affordableCombinations = keyboards
        .SelectMany(keyboard => drives
            .Select(drive => keyboard + drive))
        .Where(cost => cost <= budget);

    return affordableCombinations.Any()
        ? affordableCombinations.Max()
        : -1;
}

Is this as efficient as your solution? Not in terms of CPU cycles, no. In terms of what the person reading the code must do, in order to understand the desired behavior? I'll argue yes.

If you believe you'll see large performance gains by filtering out keyboards and drives that exceed the budget on their own, before adding any prices together, there's a concise way to do that with LINQ also:

public static int GetMoneySpent(int budget, int[] keyboards, int[] drives)
{
    Func<int, bool> affordable = cost => cost < budget;

    var affordableCombinations = keyboards
        .Where(affordable)
        .SelectMany(keyboard => drives
            .Where(affordable)
            .Select(drive => keyboard + drive))
        .Where(affordable);

    return affordableCombinations.Any()
        ? affordableCombinations.Max()
        : -1;
}

Is this as efficient as a solution involving manual iteration can be? Again, no. I think the approach in Henrik's answer is about the best you'll do. But this is easily readable, and probably efficient enough.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.