Module assignment: a pointer toolkit

What you will build

In this assignment you write one complete C++ program. It reads a list of stock readings from input, handles them in four ways, and prints the results. Every part uses an idea from this module. You will reverse an array with two pointers, sort a copy, search it with a pointer binary search, build a linked list whose nodes free themselves, and keep the heap memory correct. The program is short, but it touches every lesson, so a clean solution shows that you understand the module, not only that the program runs.

The assignment is a small tool, not a real inventory system. Think of a shop keeper who writes down the change in stock for each item every day. The keeper wants the readings in reverse order, a sorted copy, a list of the distinct values and quick answers to "was this value ever recorded?" Your program does that in one run.

Work through it in order. Do the parts one at a time, and test each part before you start the next. Most students who fail this assignment try to write the whole program at once and then cannot find the bug.

Why this assignment matters

Pointer code is judged on three things: correct output, correct memory and clear ownership. This assignment checks all three. A program that prints the right numbers but leaks memory is not a full solution, and interviewers apply the same three checks.

The input and the output

The program reads from standard input. The first line holds n, the number of readings. The second line holds the n readings, separated by spaces. Readings can be negative or zero. The next line holds q, the number of queries. Each of the following q lines holds one query value.

The constraints are these. n is at least 1 and at most 100000. Each reading is between -1000000000 and 1000000000. q is at least 0 and at most 100000. Your program must handle all of these sizes within a reasonable time, so do not use a method that takes n squared steps for a list of 100000 readings.

The program prints five things, in this order.

The first line starts with reversed: and then lists the readings after you reverse the array in place.

The second line starts with sorted: and then lists a sorted copy of the readings, smallest first.

The third line starts with distinct count: and then gives the number of different values.

The fourth line starts with distinct: and then lists the distinct values, in sorted order, taken from your linked list.

Then the program prints one line per query. Each line reads query X: yes if the value X appears among the readings, and query X: no if it does not. The yes and no answers come from your binary search on the sorted copy.

Every line is terminated by a newline. Notice the spaces. Each value is printed after one space, so the line reversed: has a space before each number and no trailing space at the end.

Example run

Here is the input for a full example.

6
4 -2 9 4 0 7
3
4
5
-2

The expected output is this.

reversed: 7 0 4 9 -2 4
sorted: -2 0 4 4 7 9
distinct count: 5
distinct: -2 0 4 7 9
query 4: yes
query 5: no
query -2: yes

Trace it by hand before you write any code. Reverse the list 4 -2 9 4 0 7 and you get 7 0 4 9 -2 4. Sort a copy of the reversed list and you get -2 0 4 4 7 9. The value 4 appears twice, so the distinct list drops one copy, which leaves five values. The query 4 is in the list, so it prints yes. The query 5 is not in the list, so it prints no. The query -2 is in the list, so it prints yes.

Now try a smaller case, which catches most edge-case bugs.

1
5
1
5

The output is:

reversed: 5
sorted: 5
distinct count: 1
distinct: 5
query 5: yes

A single element is the edge case where two pointers meet at once. Your reversal must do nothing and still print the value.

A third case has all values the same.

3
1 1 1
2
1
2

The output is:

reversed: 1 1 1
sorted: 1 1 1
distinct count: 1
distinct: 1
query 1: yes
query 2: no

Here the distinct list must hold only one node, even though the sorted copy has three values. This case tests your duplicate check.

The four parts

Your program has four parts. Build them in this order, because each later part depends on the earlier ones.

Part 1: read the readings into a heap array

Read n, then allocate an array of n ints on the heap with new int[n]. Read each reading into the array. Do not use a stack array such as int data[n], because n is not known at compile time and that form is not standard C++. You must free this array later with delete[].

This part tests the first lesson's ideas: a pointer that holds an address, and a loop that writes through an index. It also starts the ownership story, because the array is yours to free.

Part 2: reverse the array in place with two pointers

Write a function void reverseInPlace(int* first, int* last). The range is half-open, so last points one past the last element. Inside the function, move last back one step so it points at the last element. Then swap the two ends and move the pointers toward each other until they meet.

Call it with reverseInPlace(data, data + n);. Print the array after the call, in the format shown. The function must not allocate any new array. It works only with the two pointers and the values they point at.

This part tests lesson 2. Check the edge case n = 1, where the loop must not swap anything. Check that the function does not read past either end.

Part 3: sort a copy and search it

Make a second heap array, sorted, of the same size. Copy the reversed values into it. Then sort it with std::sort, passing the two pointers: sort(sorted, sorted + n);. The library function sort accepts pointers as its range, because a pointer behaves like an iterator over an array. You may write your own sort if you prefer, but the standard function is correct and expected here.

Print the sorted array in the format shown. Keep the reversed array unchanged, so the first line of output is still the reversed order.

Then answer the queries with a binary search through pointers. Write int* findValue(int* first, int* last, int target). It returns a pointer to a matching element, or nullptr if the value is not there. Use the half-open range from lesson 2 and compute the middle as first + (last - first) / 2.

This part tests the binary search from lesson 2 and the null-pointer check from lesson 1. A query that finds nothing must print no. A query that matches the first or last element must print yes.

Part 4: build a linked list of distinct values

Make a linked list in which each node holds one distinct value, in sorted order. The node type is given to you:

struct Node {
    int value;
    unique_ptr<Node> next;
    explicit Node(int v) : value(v) {}
};

Each node owns the next node through its unique_ptr. The head of the list is a unique_ptr<Node>. You add nodes to the end, using a raw Node* named tail that points at the last node so far. Walk through the sorted array with a pointer. Skip any value equal to the value in tail, because duplicates must not appear in the list.

Count the nodes with a loop that walks the list from the head, and print the count. Then walk the list again and print the values.

This part tests lesson 5. The tail pointer is a borrowed raw pointer. It must never outlive the node it points at. Because the list owns its nodes, you never call delete on a node yourself.

The requirements checklist

Copy this checklist into your notes and tick each item when it is true. You should be able to justify each tick.

• Reads n and the n readings into an array created with new int[n].
• Reverses that array in place with two pointers, without allocating another array.
• Prints the reversed array with the exact format reversed: ....
• Copies the reversed array into a second heap array and sorts it with sort or your own sort.
• Prints the sorted array with the exact format sorted: ....
• Builds a linked list of distinct values, with each node owned by a unique_ptr.
• Prints the distinct count and the distinct values from a walk of the list.
• Answers each query with a pointer binary search that returns nullptr on a miss.
• Prints query X: yes or query X: no for every query, in input order.
• Frees every new[] block with delete[] exactly once, and has no leaks.
• Runs clean under the address sanitizer: no errors and no leak report.
• Handles n = 1, q = 0 and an array of all equal values.

The grading rubric

The three levels below describe what a solution at each mark looks like.

At 60 percent, the program reads the input and prints the reversed array and the sorted array correctly. It answers the queries, perhaps with a linear search rather than a binary search. It may leak the heap arrays, or it may not build the linked list. The output matches the examples for typical input, but it may fail on n = 1 or on duplicates.

At 80 percent, all five output lines are correct on every test, including the edge cases. The reversal uses two pointers and no extra array. The binary search is written with pointers and returns nullptr on a miss. The linked list is built with unique_ptr and skips duplicates. The heap arrays are freed. The sanitizer run may still show one small leak or one missed delete[].

At 100 percent, the program is correct on every test and clean under the sanitizer. Every heap block has one owner and one free. The code is easy to read, each function does one job, and the names say what each pointer means. The student can explain, without looking, why the list needs no delete, why the tail pointer is safe, why the binary search uses first + (last - first) / 2, and why the reversal stops when the pointers meet.

Two things are not allowed at any level. A solution that uses a vector for the readings is not a pointer solution, and it loses the points for parts 1 and 2, because those parts exist to teach the heap array. A solution that leaks memory cannot score above 80 percent, even when the output is perfect.

Test your program

Write your test inputs before you finish the program. Good tests are the ones that break a wrong answer.

Test 1 is the example in this lesson. The output must match exactly.

Test 2 is the single element 1 and 5. It checks the reversal and the search on an array of one.

Test 3 is all equal values. It checks the duplicate skip in the list.

Test 4 has negative numbers and zero. Use 3 and -5 0 -1, with query -1 and query 7. The reversed line must read reversed: -1 0 -5, and the answers must be yes and no.

Test 5 has no queries, q = 0. The last lines must print nothing after the distinct line.

Test 6 has a query that is the smallest value and one that is the largest value. This catches off-by-one errors in the binary search.

Hints

Work through these hints one at a time. Try each step before you open the next. Each hint is hidden so you can attempt the problem first.

Stretch extension

If you finish all four parts and want more, add one improvement. Lesson 5 warned that a very long linked list can cause deep recursion when it is destroyed, because each node's destructor calls the next one's destructor. Write a function void clearList(unique_ptr<Node>& head) that empties the list in a loop instead. A good approach is to move each node out of the list one at a time, so that its destructor runs with no next left to follow. Test it with 100000 distinct values and check that the program still finishes.

Name the function so the reader knows it empties the list. Keep the main output the same. Explain in one paragraph why the loop avoids the deep recursion.

Check your work

Before you submit, compile your program with extra checks. The command is:

g++ -std=c++17 -Wall -Wextra -g -fsanitize=address,undefined -o prog prog.cpp

Then run it with each test input. A correct program prints the expected output and prints nothing from the sanitizer. A leak shows a line such as Direct leak of 40 byte(s) with a new line number. An out-of-range read shows heap-buffer-overflow. A use after free shows heap-use-after-free. Each message names the line, so fix the line it points at.

Read your code once more and ask four questions of each pointer. Where does it point when it is set? Who owns the memory it points at? Is there a path where it is used after that memory is freed? Does every new[] have one delete[] on every path, including the early exits?

Reference solution

Try the whole assignment before you open this. The solution below is complete and was checked against the examples in this lesson with the address and undefined behaviour sanitizers, and it reports no errors on any of them. Read it to compare your structure, not to copy the lines. Explain each function to yourself before you move on.

The solution works in four stages. Reading fills the heap array. Reversal changes the array with two pointers and no new storage. Sorting a copy keeps the reversed order intact, and the binary search answers each query in logarithmic time on that copy. The linked list is built from the sorted copy, skipping duplicates with the tail pointer, and each node is owned by the one before it, so the list frees itself when head goes out of scope. The two heap arrays are freed by hand, once each, just before the program ends.

Self-review questions

Answer these in writing before you hand the assignment in. They are the questions an interviewer would ask about your code.

What is the time cost of the whole program, and which part dominates it? The sort costs n log n. Everything else is linear, and each query costs log n.

What is the extra space used, and where is it? The sorted copy and the list take extra space. The reversal uses none.

Why is the tail pointer not an owner? It only borrows the node that the previous node owns. Deleting through it would be a double free.

What you now know

• You can allocate an array on the heap with new int[n], use it, and free it with delete[] exactly once.
• You can reverse an array in place with two pointers that move toward each other.
• You can sort a copy and search it with a pointer binary search that returns nullptr on a miss.
• You can build a linked list whose nodes are owned by unique_ptr, and skip duplicates with a tail pointer.
• You can check a program with the address sanitizer and read its messages to find the line at fault.
• You can explain the time and space cost of each part, and the ownership of each pointer.