Hash code 2026-10-31
View more
A bounded value used to organize entries in a hash table. An equality-based collection requires equal keys to have equal hash codes, while unequal keys may collide. A Java hashCode() override must therefore use information invariant under the chosen value equality. Hashing internal subdivisions is invalid when those subdivisions are deliberately ignored by equality.[ref]
Read the full article
Past exam of the computer science course of the University of Oxford / 2015 / Concurrent programming / 3 / a / Solution 2026-10-31
View more
A counting semaphore holds a nonnegative number of permits. down waits until a permit is available and consumes one; up returns a permit and can release a waiting caller. A binary semaphore restricts the number available to zero or one. Unlike a mutex, a semaphore need not be released by the same software thread that acquired it; this permits producer-to-consumer signalling.
Interpret maxCount as the initial number of permits and, for this bounded implementation, the maximum permitted number of unmatched releases. An up beyond that capacity is a programming error, rather than a blocking operation. Clients obey this release discipline. If an unbounded counting semaphore is desired instead, remove the upper-bound requirement and use a sufficiently wide counter; a capacity-one instance is binary only under the corresponding balanced-use discipline.
class CountingSemaphore(maxCount: Int) extends Semaphore {
  require(maxCount > 0)
  private var count = maxCount
  def down: Unit = synchronized {
    while (count == 0) wait()
    count -= 1
  }
  def up: Unit = synchronized {
    require(count < maxCount, "unmatched semaphore release")
    count += 1
    notify()
  }
}
All accesses to count occur under the same monitor. wait atomically releases that monitor while sleeping, then reacquires it before returning. The while is needed because of spurious wakeups and because another caller can consume the returned permit before the notified caller reacquires the monitor. Only down callers wait here, and they all wait on the same predicate; hence waking one with notify is sufficient. A later up notifies another waiter if necessary. This use of notify will not be safe for the mixed predicates in the next part.[ref]
A binary semaphore initially available is new CountingSemaphore(1). To initialize it unavailable, call its down once during construction, before publishing it to other software threads. Its state obeys
(1)
This implementation provides no first-come-first-served guarantee: a new caller can acquire the monitor before a notified waiter. The following examples assume ordinary successful execution without cancellation or interruption of a partially completed buffer operation.
Read the full article
Past exam of the computer science course of the University of Oxford / 2015 / Object oriented programming / 3 / a / Solution 2026-10-31
View more
For primitive values, Java == compares values, subject to the primitive type's rules. For references, == compares object identity: it asks whether the references designate the same software object, or are both null. The equals(Object) object method permits a software class to define value equality. Its inherited Object implementation still uses object identity, so meaningful content comparison requires an appropriate override.[ref]
For example:
String a = new String("wall");
String b = new String("wall");
boolean sameObject = (a == b);  // false
boolean sameText = a.equals(b); // true
The two allocations have different object identities but equal text. Using separately allocated String data type values avoids relying on literal interning. A null receiver cannot receive an equals call; java.util.Objects.equals(a,b) is a null-safe comparison. An equals implementation should define an equivalence relation and equal software objects must have equal hashCode() results.[ref] The distinction is
(1)
Read the full article
Past exam of the computer science course of the University of Oxford / 2015 / Object oriented programming / 3 / e / Solution 2026-10-31
View more
Brick boundaries are not observable in the requested row equality. Two adjacent red width-one bricks must compare equal to one red width-two brick at the same left coordinate. Comparing the underlying placement lists would therefore give the wrong result.
Instead build each row's unique sequence of maximal occupied colour runs: merge adjacent placements exactly when they touch and have equal colours. Gaps remain gaps, and touching different colours remain separate runs. This is a geometric version of run-length encoding, with explicit start and end coordinates. Insert these members inside Row from part (d):
private static final class Run {
    final long x, end;
    final Color colour;

    Run(long x, long end, Color colour) {
        this.x = x;
        this.end = end;
        this.colour = colour;
    }
}

private List<Run> runs() {
    List<Run> result = new ArrayList<Run>();
    for (Placed b : bricks) {
        int last = result.size() - 1;
        if (last >= 0) {
            Run r = result.get(last);
            if (r.end == b.x && r.colour.equals(b.colour)) {
                result.set(last, new Run(r.x, b.end, r.colour));
                continue;
            }
        }
        result.add(new Run(b.x, b.end, b.colour));
    }
    return result;
}

@Override public boolean equals(Object other) {
    if (this == other) return true;
    if (!(other instanceof Row)) return false;
    List<Run> a = runs(), b = ((Row) other).runs();
    if (a.size() != b.size()) return false;
    for (int i = 0; i < a.size(); ++i) {
        Run r = a.get(i), s = b.get(i);
        if (r.x != s.x || r.end != s.end || !r.colour.equals(s.colour))
            return false;
    }
    return true;
}

@Override public int hashCode() {
    int h = 1;
    for (Run r : runs()) {
        h = 31 * h + Long.hashCode(r.x);
        h = 31 * h + Long.hashCode(r.end);
        h = 31 * h + r.colour.hashCode();
    }
    return h;
}
Color.equals compares colour values rather than object identity. Two row snapshots compare their local horizontal content independently of which wall height supplied them. Empty rows compare equal, even if obtained from different walls. The hash code uses the same canonical runs as equals, so alternative brick subdivisions with equal displayed content also have equal hash codes.[ref]
To prove correctness, observe that a maximal run starts whenever occupancy begins or the colour changes, and ends exactly where that occupancy or colour ceases. Those boundaries are determined by the occupied colour at every coordinate. Thus equal occupied colours give the same runs, and equal runs give equal occupied colours. If rows contain and bricks, generating and comparing their runs has time complexity and additional storage, independent of their widths or the magnitude of their coordinates. This meets the requirement to improve on checking every possible cell:
(1)
Read the full article