Module assignment: weekly sales analysis in Python

The project

A small shop records how much it sold each day. The owner wants a program that reads a week (or longer) of daily sales and then answers a set of questions. Some questions need one pass over the data. Others must answer many range questions quickly, which is where prefix sums earn their place. Every part of this assignment comes from the four lessons of this module, so read them again if a step feels unfamiliar.

You will write one program, main.py, that reads from standard input (the text the tester feeds in) and prints to standard output (the text the program shows). The program is tested automatically by feeding it input files and comparing the printed text with the expected text. The output must match exactly, including the spaces and the word at the start of each line.

Start with a simple version that answers only the first question, then add one question at a time. Test after each addition. This is the same habit that the debugging walkthroughs in the lessons demonstrate: one small change, one small test.

The input

The input has three parts, in this order.

The first line holds one integer n, the number of days. n is at least 3 and at most 100,000.
The second line holds n integers, the sales for each day from day 0 to day n - 1. Each sale is between 0 and 1,000,000 inclusive. Values are separated by single spaces.
The third line holds one integer q, the number of range questions. q is between 0 and 100,000.
The next q lines each hold two integers l and r, meaning "the total from day l to day r, both included". Indexes are 0-based, and 0 <= l <= r < n.

Here is a complete example. Read it slowly, and check the first line against the second line: seven days, seven numbers.

7
120 80 150 150 90 200 40
3
0 2
3 5
1 6

The output

The program prints exactly these lines, in this order.

total T where T is the sum of all sales.
best D V where D is the index of the day with the highest sales and V is that value. If two or more days share the highest value, print the first one, which is the smallest index.
window3 S where S is the largest total of any three consecutive days. Because n is at least 3, this window always exists.
profit P where P is the largest profit from one purchase followed by one later sale. Treat each day's value as the price of one item that day. Buying on day i and selling on day j must have i < j. If prices only fall, the answer is 0, because the shop can choose not to trade.
One line per range question, in the same order as the input, printing the total from l to r.

For the example above, the expected output is:

total 830
best 5 200
window3 440
profit 120
350
440
710

Check each line by hand before you trust the program. The total is 120 + 80 + 150 + 150 + 90 + 200 + 40, which is 830. The best day is day 5, with sales of 200, because it is the highest value and no earlier day ties it. Compare two of the windows: days 2 to 4 give 150 + 150 + 90 = 390, and days 3 to 5 give 150 + 90 + 200 = 440. Days 3 to 5 is the best window, so the answer is 440. The best profit comes from buying on day 0 at 120 and selling on day 5 at 200, a profit of 80, or buying on day 1 at 80 and selling on day 5 at 200, a profit of 120. The second choice is larger, so the answer is 120.

Now the range questions. The question 0 2 asks for days 0, 1 and 2, which is 120 + 80 + 150 = 350. The question 3 5 asks for days 3, 4 and 5, which is 150 + 90 + 200 = 440. The question 1 6 covers everything from day 1 to the end, which is 710.

A second example has every day equal, and it tests the tie rule and the zero-profit rule.

The output is:

total 15
best 0 5
window3 15
profit 0
15

Day 0 is the best day, because the tie is broken by the earliest index. The profit is 0, because no sale is ever higher than an earlier purchase.

Requirements checklist

Copy this list into a notes file and tick each item as you finish it. Every item is checked by the tests.

Grading rubric

Your grade depends on which parts of the checklist you finish and how cleanly they run. The three levels below describe what a solution at each level looks like.

60 percent: the core answers are right. The program prints the right total, best and range answers for the sample inputs. It does not crash on n = 3. It may use slow nested loops for the window and the profit, and it may recompute range sums with a loop. A solution at this level passes the first sample but may fail large tests because of time.

80 percent: every printed line is right and the answers run fast. All four summary lines are correct, including the window and profit, with ties and zero-profit cases handled. The range questions use a prefix list, so each question is O(1) after an O(n) build. It passes all the sample inputs and the edge cases in the checklist, and it finishes large inputs in time.

100 percent: correct, fast, clean and explained. Everything at 80 percent is present, and in addition the code is organised. Each question is a small function with a clear name, and the main function reads the input and prints the results in one place. The window uses one running total that adds the new day and removes the day that fell out. The program has short comments that state the time and space cost of each part, and it has been tested with an input of your own design, with the expected output worked out by hand before you ran it.

A grader looks at three things in this order: whether the output is exactly right, whether the program is fast enough, and whether the code is easy to follow. A fast program that prints one wrong line loses the 80 percent level, so run the sample inputs before you tune anything.

Step-by-step hints

Try each step on paper before you read the next hint.

Hint 1: reading the input

Read the whole input with sys.stdin.read().split(), which gives one list of text tokens, and convert each token with int. Keep a position counter that moves past the n sales, then read q, then the pairs. Using input() on each line also works, but it breaks if the numbers are split across lines in a way you did not expect. Python integers are exact, so the total of 100,000 values of 1,000,000 needs no special type.

Hint 2: the total and the prefix list

Build the prefix list first. It has n + 1 entries, the first being 0. The total is the last entry, prefix[n]. You will use the same prefix list for the range questions later, so building it once saves work.

Hint 3: the best day

Start with best_day = 0. Loop from index 1, and replace best_day only when the new value is strictly greater, using >. The strict comparison keeps the first of any tie. Print best_day and sales[best_day].

Hint 4: the three-day window without three loops

The sum of days 0, 1 and 2 is prefix[3] - prefix[0]. To move the window one day to the right, add the day entering the window and subtract the day leaving it. The new window covers days i - 2, i - 1 and i after the step, so the day leaving is i - 3. In code, window_sum += sales[i] - sales[i - 3] for each i from 3 up to n - 1. Keep the largest window sum seen.

Hint 5: the profit, with the same shape as the stock lesson

Keep lowest, the smallest price seen on earlier days, and profit, the best profit so far. For each later day, profit can rise to today's sales minus lowest. Then update lowest. Start profit at 0, not at a negative number.

Hint 6: the range questions

For each question l r, the answer is prefix[r + 1] - prefix[l]. Check the bounds with a small case first: 0 0 should return the first day alone. Collect the answers in a list of text lines and print them once at the end with "\n".join(...). Printing inside a loop of 100,000 lines is slower than printing one block of text.

Hint 7: testing your own inputs

Make three inputs of your own. One with n = 3, one where the best day is the last day, and one where every day falls. Work out each expected line on paper. Only then run the program. If your hand answer and the program disagree, the hand answer is usually right and the program has a bug.

Edge cases to test

These are the cases where most submissions fail. Test each one before you hand in.

The smallest input, n = 3. The window loop starts at index 3, and n is 3, so the loop must not run at all. The first window is still computed before the loop, which is why the first window uses prefix[3].

Ties for the best day. An input such as 4 then 4 9 2 9 must print best 1 9, not best 3 9.

Strictly falling sales. An input such as 4 then 9 7 4 3 has no profitable trade, so profit 0 is the answer. A solution that starts profit at sales[1] - sales[0] prints a negative number, which is wrong.

Large values. Python does not overflow, so the total is exact however large it gets. A solution in a language with 32-bit integers would print a wrong negative total once the sum passes about 2.1 billion.

No range questions. An input with q = 0 must print the first four lines and nothing after them. Make sure your loop over questions does not expect a line.

A question that covers the whole array. 0 n-1 should equal the total. If it does not, check the index in prefix[r + 1].

Reference solution

Try to write your own before you read this. The reference is written in the style of the lessons, with one part per question. It is correct for every input that matches the format above, and you can compare your output with it on any input you design.

Show the reference solution

import sys
 
 
def main():
    data = sys.stdin.read().split()
    pos = 0
 
    n = int(data[pos])
    pos += 1
    sales = [int(x) for x in data[pos:pos + n]]
    pos += n
 
    # Build the prefix list once: O(n) time, O(n) space.
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i + 1] = prefix[i] + sales[i]
    total = prefix[n]
 
    # Best day, first occurrence on ties: O(n) time, O(1) space.
    best_day = 0
    for i in range(1, n):
        if sales[i] > sales[best_day]:
            best_day = i
 
    # Largest three-day window with one running total: O(n) time, O(1) space.
    window_sum = prefix[3] - prefix[0]
    best_window = window_sum
    for i in range(3, n):
        window_sum += sales[i] - sales[i - 3]
        best_window = max(best_window, window_sum)
 
    # Best single trade: buy on an earlier day, sell on a later day.
    # O(n) time, O(1) space.
    lowest = sales[0]
    profit = 0
    for i in range(1, n):
        profit = max(profit, sales[i] - lowest)
        lowest = min(lowest, sales[i])
 
    out = [
        f"total {total}",
        f"best {best_day} {sales[best_day]}",
        f"window3 {best_window}",
        f"profit {profit}",
    ]
 
    # Each range question is one subtraction: O(1) per question.
    q = int(data[pos])
    pos += 1
    for _ in range(q):
        l = int(data[pos])
        r = int(data[pos + 1])
        pos += 2
        out.append(str(prefix[r + 1] - prefix[l]))
 
    print("\n".join(out))
 
 
main()

Run this reference on the first sample input and check that it prints the seven lines shown earlier. The line for best should read best 5 200, and the line for window3 should read window3 440. On a random input with n and q both 100,000, this version finishes in about a fifth of a second on a typical laptop, which is well inside the one-second target. The time depends on the machine, so your number may differ.

Explaining your solution

A strong submission includes a short note, in comments or in a separate text file, that answers four questions. The first is what each part costs in time and space, and why. The second is which pattern each part uses, such as prefix sums, a sliding window or a single pass with a running low. The third is which edge case you found hardest. The fourth is what you would change if the question also asked for the best subarray of any length.

The last question is a good test of understanding. A best subarray of any length is not a fixed window, so the sliding total from this program does not cover it, because the window size would have to change. Kadane's algorithm from the third lesson answers that question in O(n) time and O(1) space, by restarting the running slice whenever it becomes negative. Explaining why the fixed window is not enough, and why Kadane fixes it, shows that you can apply the ideas outside the exact examples.

Common mistakes in this assignment

Reading the whole input as one line. input() reads one line. If you call it once for the sales line and forget the question lines, the questions are never read. Read each line in order, or read all tokens with sys.stdin.read().split().

Starting the best window at 0. The window sums can all be above 0, but a window sum must come from real days. Start from the first window, not from 0.

Printing the first day of the best window instead of the best day. The second line is about one day and its sales, not about three days. Do not mix the two.

Printing a trailing space or a blank line. The checker compares text exactly. Use one print with the lines joined by "\n", so the last line ends with a single newline. A print of an empty string at the end adds a blank line.

Recomputing range totals with a loop. This works for the sample, but on 100,000 questions over 100,000 days it does 10 billion additions. The prefix list turns each question into one subtraction.

Reading q before the sales. The order in the input is fixed. The sales come first, then q, then the questions.

What to hand in

Submit one file named main.py that contains the whole program. Include the short note described above as comments at the top of the file. Keep the program in one file, so that the tests can run it with python3 main.py.

Self-check before you submit

Run through these questions and answer them in writing. If you cannot answer one, go back to the lesson that covers it.

Which lesson gave you the prefix list, and what is its length?
Why is window_sum updated with sales[i] - sales[i - 3] and not rebuilt each time?
Why does the profit loop compare with lowest before updating lowest?
What does best 0 5 mean for the tie input, and why is it not best 2 5?
If n were one million and q were one million, which parts would still be fast, and which would need changing?

What you now know

You can read, change and search a list, and you know how each index error looks and what it means.
You can build a prefix list and answer range questions in constant time each.
You can find the best subarray with one running total, and the best trade with one running low.
You can walk a grid with two indexes and keep track of its bounds.
You can test a program against hand-worked examples and fix the bug that the test shows.

Those skills cover most of the array questions in a technical interview. The next module moves to sorting, which changes the order of an array so that many later questions become faster.