HRT's Copy-on-Write String C++ Question

Hudson River Trading interviews lean hard on C++ internals. This copy-on-write string is a recurring on-site and phone question that quietly tests reference counting, value semantics, and the subtleties of sharing memory between instances, then makes you reason about threads. Here is the full question, C++ for each stage, and a detailed rubric.

The question

Stage 1 · Shared buffer with reference counting

Put the character data and a reference count in one heap block. Copies share that block and bump the count; destruction drops it and frees only at zero. This gives cheap copies and correct lifetime.

#include <cstring>
#include <cstddef>

class CowString {
    struct Buffer {
        size_t refs;
        size_t len;
        char   data[1];   // flexible-array-style trailing storage
    };
    Buffer* buf_;

    static Buffer* alloc(const char* s, size_t len) {
        Buffer* b = static_cast<Buffer*>(::operator new(sizeof(Buffer) + len));
        b->refs = 1;
        b->len  = len;
        std::memcpy(b->data, s, len);
        b->data[len] = '\0';
        return b;
    }
    void release() { if (buf_ && --buf_->refs == 0) ::operator delete(buf_); }

public:
    CowString(const char* s = "") : buf_(alloc(s, std::strlen(s))) {}

    CowString(const CowString& other) : buf_(other.buf_) { ++buf_->refs; }   // share, do not copy

    CowString& operator=(const CowString& other) {
        if (this != &other) {
            ++other.buf_->refs;   // guard self-assignment by incrementing first
            release();
            buf_ = other.buf_;
        }
        return *this;
    }

    ~CowString() { release(); }

    const char* c_str() const { return buf_->data; }
};

Stage 2 · Copy on mutation

Const access can hand back a reference into the shared buffer. Non-const access might be used to write, so it must detach first: if the buffer is shared, deep-copy it into a private one before returning a mutable reference. That is the whole point of copy-on-write.

    // Detach: if the buffer is shared, make a private copy before mutating.
    void detach() {
        if (buf_->refs > 1) {
            Buffer* fresh = alloc(buf_->data, buf_->len);
            --buf_->refs;        // we still hold a reference to the old one
            buf_ = fresh;
        }
    }

    char  operator[](size_t i) const { return buf_->data[i]; }      // read: no copy

    char& operator[](size_t i) {       // write path: must own the buffer first
        detach();
        return buf_->data[i];
    }

The trap is returning a non-const reference without detaching: a write through it would corrupt every instance sharing the buffer. Note too that the non-const operator pessimistically copies even for a read, which is the known cost of this design.

Stage 3 · Thread safety

An atomic reference count is necessary but not sufficient. It makes share and release race-free, but two threads mutating views of the same logical string still need higher-level synchronization, and detach must atomically check-and-copy.

#include <atomic>

struct Buffer {
    std::atomic<size_t> refs;   // atomic so share/release are race-free
    size_t len;
    char   data[1];
};

// release becomes:
void release() {
    if (buf_ && buf_->refs.fetch_sub(1, std::memory_order_acq_rel) == 1)
        ::operator delete(buf_);
}

Say the quiet part: atomics protect the refcount, not the bytes. Concurrent writers to the same string need a mutex or a redesign, and the read-then-copy in detach has a race unless the count check and the copy are made atomic together.

How HRT scores it

Hudson River Trading interview FAQ