eCommerce - Highest Order of the Day

The Problem

Find the highest costing order of the day at any given time during the day.

Restriction

An order may get cancelled, but only if the order(s) placed after it are cancelled.

Example

Orders coming in: A B C D E F G H

Time of day:         ------------------------>

Lets assume the numbers:

Order Price

A        $10

B        $20

C        $15

D        $33

E        $97

F        $56

G        $9

H        $22

Order F can only be cancelled if orders G and H are cancelled before it.

In this case, the highest costing order is E at $97

Approach (using above example)

1. Since orders can be cancelled and due the restriction, lets use a stack as the data structure to organize the information.
2. We only want to retrieve the highest order at any given time.
3. If data is stored in a stack, we can only access the top of the stack.
4. So, lets only insert an order if its value is higher than the value of the order at the top of the stack.
5. At the end of the day, our stack will contain (from bottom to top): A, B, D and E.
6. E is the top of the stack and can easily be retrieved as the highest order of the day

Conclusion

Try your own scenarios to practice such conditions because they are part of commonly occurring themes in eCommerce applications. Stacks, queues, linked lists, etc seem like too unnecessary or too theoritical to new programmers. Exploring real examples is the only way to understand why, how and where to use these data structures.