Finding Maximum Profit in Item Sales Based on Categories and Prices

I recently came across a Reddit post where someone shared an interview experience in which the interviewer asked for the logic to find the maximum profit. You can view the post by searching ‘Reddit maximum profit HackerRank‘. In this article, I will explain the algorithm behind finding maximum profit in category-based items and will solve it using the best approach in python and c#, so stay tuned until the end to ensure you’re prepared to solve this technical interview question if you encounter it.

FREE : If you’re a new visitor preparing for an interview and need help or want to request a new question, you can use the form on the right side to ask your question. It’s free and doesn’t require signing in. Alternatively, you can ask in our Quora space, which is also free, and you’ll receive a response within 24 hours. Go ahead and check it out! do check Master the Stock Span Problem by 3 Easy Steps in Python, Master Abstract Factory Design Pattern for Programming Interviews with 5 easy steps ,Mastering Object-Oriented Programming in C++ , Method Overloading vs. Method Overriding in C#

Moreover, the original question is published on the HackerRank platform, so you can also prepare for more interview questions there.

Introduction of Maximum Profit Problem

Let’s first understand the question. It’s always a good idea to create a basic logic to grasp the problem, so keep this tip in mind for your next interview.

In the competitive marketplace of Hackerland, a shop owner must carefully strategize the order in which items are sold to maximize profits. The profit from selling an item is determined by both its price and the diversity of categories that have already been sold. In this post, we’ll explore an algorithmic approach to finding the maximum possible total profit that can be made by selling items in the optimal order.

Problem Statement of Hacker Rank

Given n items, each with a category and a price, the task is to determine the order of sales that yields the highest total profit. The profit for selling an item is calculated as the product of its price and the number of different categories whose items have been sold before it (including its own category).

Feeling nervous? Yes, that’s common when you encounter an interview question for the first time. Let me simplify it for you, and then I’ll provide an example so you can understand it in depth.

You’re given n items, each belonging to a specific category and having a price. Your goal is to figure out the best order to sell these items to make the most profit. The profit from selling an item is calculated by multiplying its price by the number of different categories that have already been sold, including the item’s own category.

Example Walkthrough

Let’s consider an example to understand Category-based item profit problem better.

Example:

• Number of Items (n): 4
• Categories (category): [3, 1, 2, 3]
• Prices (price): [2, 1, 4, 4]

One possible optimal order to sell these items is as follows:

Sell the 2nd item (category[2] = 1, price[2] = 1):
Profit = 1 * 1 = 1
(Only 1 unique category has been sold so far.)
Sell the 1st item (category[1] = 3, price[1] = 2):
Profit = 2 * 2 = 4
(Now, 2 unique categories have been sold.)
Sell the 3rd item (category[3] = 2, price[3] = 4):
Profit = 4 * 3 = 12
(Three unique categories have been sold.)
Sell the 4th item (category[4] = 3, price[4] = 4):
Profit = 4 * 3 = 12
(The number of unique categories remains 3.)

Total Profit = 1 + 4 + 12 + 12 = 29

Solution Approach for Find Maximum Profit

I believe you now have an idea of what we’re trying to solve—correct? If not, please read through it again and review the example. If you still have questions, feel free to comment, and an expert will respond promptly. Let’s start address this problem and discuss solution.

To solve this problem efficiently, we need to consider the following steps:

Sort Items by Price: The first step is to sort the items by their prices in descending order. This ensures that the highest-priced items are sold when the number of unique categories is higher, maximizing the profit.

Track Unique Categories: As we iterate through the sorted items, we need to track the number of unique categories that have been sold.

Calculate Profit: For each item, calculate the profit based on its price and the number of unique categories that have been sold up to that point.

Optimize the Order: The optimal order is derived by ensuring that items from new categories are sold earlier, with higher-priced items taking precedence.

Don’t worry—in the next section, I’ll be sharing the pseudocode in python as well.

Code Implementation

def findMaximumProfit(category, price):
    # Pair the categories with their respective prices
    items = list(zip(category, price))
    
    # Sort items by price in descending order
    items.sort(key=lambda x: -x[1])
    
    # Track the number of unique categories sold
    unique_categories = set()
    total_profit = 0
    
    for cat, prc in items:
        # Add the category to the set of sold categories
        unique_categories.add(cat)
        
        # Calculate the profit
        profit = prc * len(unique_categories)
        total_profit += profit
    
    return total_profit

Let’s implement this code in C# so you can better understand it. You can also use this pseudocode python code to create your own logic in your preferred programming language.

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

public class MaximumProfitCalculator
{
    public static int FindMaximumProfit(int[] category, int[] price)
    {
        // Pair the categories with their respective prices
        var items = category.Zip(price, (cat, prc) => new { Category = cat, Price = prc }).ToList();
        
        // Sort items by price in descending order
        items = items.OrderByDescending(item => item.Price).ToList();
        
        // Track the number of unique categories sold
        var uniqueCategories = new HashSet<int>();
        int totalProfit = 0;
        
        foreach (var item in items)
        {
            // Add the category to the set of sold categories
            uniqueCategories.Add(item.Category);
            
            // Calculate the profit
            int profit = item.Price * uniqueCategories.Count;
            totalProfit += profit;
        }
        
        return totalProfit;
    }

    public static void Main()
    {
        int[] category = { 3, 1, 2, 3 };
        int[] price = { 2, 1, 4, 4 };
        
        int maxProfit = FindMaximumProfit(category, price);
        Console.WriteLine($"Maximum Profit: {maxProfit}");
    }
}

Explanation:

• category.Zip(price, (cat, prc): Combines the category and price arrays into a list of objects with Category and Price properties.
• OrderByDescending(item => item.Price): Sorts the items by their price in descending order.
• HashSet uniqueCategories: A set to track unique categories that have been sold.
• int profit = item.Price * uniqueCategories.Count: Calculates the profit for each item by multiplying its price by the number of unique categories sold.

Summarizing How to Find Maximum Profit in categories based items.

To find the maximum profit when selling items based on their categories and prices, first pair each item’s category with its price. Sort these items in descending order of price. Track the number of unique categories sold using a set. For each item, calculate the profit as its price multiplied by the count of unique categories sold up to that point, including the item’s own category. Sum these profits to get the total maximum profit. Implementing this logic in C# involves sorting the items, tracking unique categories with a set, and calculating the cumulative profit.

Good luck with your interview preparation, and stay tuned for more insights in interviewspreparation.com