The tricky part of this test is getting a rectangle with no points. The test
r = rectangle 1 1 2 2 r = difference r r output r
does the trick, which should produce the output 0. The intersection of two disjoint rectangles also works.
new to allocate arrays of class instances.
See Section 10.6.2 in Koenig and Moo.
I think everybody got this one wrong. There were lots of correct answers
("don't forget the [] in delete", for example), but these had nothing to
do with objects specifically.
p and q are pointers, explain how p - q might be negative.
If q points to an element to the right of the element pointed to by
p, then their difference will be negative.
I think everybody got this one right, although the explanations were of varying quality.
a) while vec.size() > 0
vec.erase(vec.end() - 1)
b) while vec.size() > 0
vec.erase(vec.begin())
Make sure you clearly state your realistic assumptions.
For a, vec.end() takes constant time, as does the subtraction. Erasing
from the end of a vector takes constant time (ignoring the possibility that
memory may be recovered when the vector shrinks). The size() member
function for vectors takes constant time, and a reduces to
while O(1)
O(1)
The loop iterates O(n) times where n is the number of elements in the
vector. The final analysis for a is
O(n)*(O(1) + O(1)) = O(n)*O(1) = O(n)
For b, vec.begin() takes constant time. Erasing from the start of a
vector takes O(n) (which may or may not include the possibility that
memory may be recovered when the vector shrinks). The size() member
function for vectors takes constant time, and b reduces to
while O(1)
O(n)
which finally reduces to
O(n)*(O(n) + O(1)) = O(n)*O(n) = O(n2)
Because O(n) is asymptotically faster than O(n2),
a is faster than b.
A number of people got this wrong because they didn't do an asymptotic analysis, but rather guessed without any estimation.
This page last modified on 21 March 2002.