# Algorithm To Process Purchases Efficiently and Apply Constraint

I am working on a problem where I have to completely scan a large unordered log file which contains purchasing details of customers. The file structure is as follows:

customerId  itemId  cost


The customer could have purchased the same item more than once in a day and at different times so there will be multiple entries for a customer and item combination. At the end of the processing, the program should print the customerId and the total cost of all their purchases, but with a discount applied so that the cost of the most expensive item is removed.

My algorithm is as follows:

1. Create a map, call it M-1, with the customerId as key and a running total cost as the value i.e. customerid -> running_total_cost.
2. Create another map, call it M-2, with the key as (customerId and itemId) and for the value the running subtotal. That is, it keeps a tab on how much of this item this customer has bought.
3. For each line in the file, upsert into M-1 the customerId and add the cost of this item to the running total. Also upsert an entry in M-2 containing the running total of this customer and item purchased. So M-1 has this structure:
customerId  RunningTotal


And M-2 has this structure

customerId ItemId RunningTotal

1. After the file has been completely processed in step 3, for each entry in M-1, get the customerId and look-up the customer in M-2. In M-2, run a loop so that it finds the most expensive purchase this customer made. This can be done by creating a temporary variable and looping through the purchases the customer made and comparing the current value of this variable with the next value. Replace the value of the variable with the new highest total At the end, the highest value will remain.
2. Print table

My question is whether this can be processed any faster than this?

UPDATE

I believe I have an optimal solution for this now. The algorithm is as follows:

1. Make one pass through the file. For each line, create a map with the following structure
Map[CustomerId, Map[ItemId, subtotal]]

1. After processing the file completely and making the above map, then do the following loop
for each customerId
count = 0
total = 0
highestSubtotal = 0
for each itemId
total += subtotal
highestSubtotal = max(highestSubtotal, subtotal)
count += 1
print CustomerId, if count > 1 then total - highestSubtotal else total


I don't think I can optimise that anymore unless anybody can think of something else.

• I suppose that when inserting into M-2 I could use an efficient data structure that will maintain some order. This will eliminate the need to loop through M-2 in step 4. What would be the best data structure to do this in? What I would need to do is just pop the highest value element and discard the rest of the values. – C.S May 4 at 20:06