Sample Problem: Design a DS for item prices

 Designing an efficient data structure is crucial for applications where large amounts of data need to be processed and retrieved quickly. The problem of designing a data structure for item prices is a common one, especially in e-commerce applications where prices need to be retrieved and sorted frequently. In this article, we will discuss a solution to this problem and provide an implementation using Java's TreeMap.

The problem statement requires the design of a data structure that can perform four operations efficiently. The first operation is to add a new item along with its price, the second operation is to fetch an item based on its price, and the third operation is to print all items in order of their price in increasing order. The fourth operation is to print all items in increasing order of prices with a price greater than or smaller than the price provided in the argument.

A naive solution to this problem would be to use arrays to store the information of items along with their prices. However, the time complexity for some of the operations would be suboptimal. For instance, the operation of adding a new item to a sorted array would take O(N) time, and finding an item in an unsorted array would take O(N) time.

To design an efficient data structure, we can use Java's TreeMap as it maintains keys in sorted order. We can use the price as a key and the corresponding item names as the value. Using this data structure, the add() and find() operations can be performed in O(logN) time. Additionally, the printSorted() operation can be performed in O(N) time as TreeMap already maintains the keys in sorted order.

To perform the printGreaterSorted() operation, we can use the TreeMap's built-in method, tailMap(), which returns a view of the TreeMap containing all items greater than a given item. Using this method, we can implement the printGreaterSorted() function efficiently in O(N) time. Similarly, we can use the TreeMap's built-in method, headMap(), to implement the printSmallerSorted() function in O(N) time.

The implementation of the MyDS class using TreeMap is shown above. The constructor initializes a new TreeMap, and the add() function adds a new item along with its price to the TreeMap. The find() function retrieves the item based on its price. The printSorted(), printGreaterSorted(), and printSmallerSorted() functions print all items in order of their price in increasing order, all items in increasing order of prices with a price greater than the price provided in the argument, and all items in increasing order of prices with a price smaller than the price provided in the argument, respectively.

here's the implementation code for the efficient solution using TreeMap:

java
import java.util.Map;
import java.util.SortedMap;
import java.util.TreeMap;

class ItemPriceDS {
    private TreeMap<Integer, String> itemPrices;

    public ItemPriceDS() {
        itemPrices = new TreeMap<Integer, String>();
    }

    public void add(int price, String item) {
        itemPrices.put(price, item);
    }

    public String find(int price) {
        String item = itemPrices.get(price);
        return item != null ? item : "";
    }

    public void printSorted() {
        for (Map.Entry<Integer, String> entry : itemPrices.entrySet()) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }
    }

    public void printGreaterSorted(int price) {
        SortedMap<Integer, String> greaterItems = itemPrices.tailMap(price, false);
        for (Map.Entry<Integer, String> entry : greaterItems.entrySet()) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }
    }

    public void printSmallerSorted(int price) {
        SortedMap<Integer, String> smallerItems = itemPrices.headMap(price, false);
        for (Map.Entry<Integer, String> entry : smallerItems.entrySet()) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }
    }
}

In this implementation, we use a private TreeMap variable itemPrices to store the item prices. The add() method adds a new item and its price to the TreeMap, the find() method searches for an item based on its price, the printSorted() method prints all items in order of their price in increasing order, the printGreaterSorted() method prints all items in increasing order of prices with price greater than the given price, and the printSmallerSorted() method prints all items in increasing order of prices with price smaller than the given price.

Note that in the printGreaterSorted() and printSmallerSorted() methods, we use the tailMap() and headMap() methods of the TreeMap class, respectively, to obtain a submap of the TreeMap containing the items greater or smaller than the given price. The false parameter in the method call indicates that the given price should be excluded from the submap.

In conclusion, the design of an efficient data structure for item prices is essential for applications that require large amounts of data to be processed and retrieved quickly. Java's TreeMap provides an efficient solution to this problem, and we have discussed its implementation in this article.