Google Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
class RingBuffer {
public:
RingBuffer(int size)
{
if (size > 0) {
// adjust size to support the read/write pointers overflow
int pow = 0;
while (size != 0) {
++pow;
size >>= 1;
}
size = 1 << pow;
data_.resize(size);
}
w_ = r_ = 0;
}
int Write(vector<int> const &block)
{
int written_count = min(block.size(), data_.size() - (w_ - r_));
for (int i = 0; i < written_count; ++i) {
data_[w_++ % data_.size()] = block[i];
}
return written_count;
}
int Read(int count, vector<int> &out)
{
out.clear();
int read_count = count > 0 ? min(count, w_ - r_) : 0;
for (int i = 0; i < read_count; ++i) {
out.push_back(data_[r_++ % data_.size()]);
}
return read_count;
}
private:
int w_, r_;
vector<int> data_;
};
Take two pointers, read and write.
Read points to the next read index
Write points to the next write index
- sheva July 28, 2017