Google Interview Question Software Engineer / Developers
actually this is a pretty good question .. seems easy but when u implement u'll get stuck on all issues. esp the part where u resize the vector. insert of an array shud be O(1), so think abt how u will realloc, u cant simply realloc and copy over, u have to do it efficiently. think of large vectors. copying is very expensive
Isn't vector a contiguous memory sequence? How can insert be O(1)? Vector is also meant to be C compatible. Not sure about the insert O(1), but random access iterator is needed..basically indexing into array.
vector pre-allocates memory and maintains a pointer to the last filled position, so when you insert it inserts after that, its O(1). but when pre-allocated memory gets full, it needs to pre-allocate again by twice the previous size(and copy over existing members). so sometimes insert will be O(n), bcos of this. but u can assume such cases are rare. or i think the goal of the question maybe to address or avoid copying in such cases, by preallocating in de-fragmented way, but it has its own issues as well
@Anonymous Nov 18,
You're right about memory allocation for vectors - amortized doubling is used. ie, start with some initial capacity. Once the initial capacity is exceeded, double the current capacity in a new memory block, copy all the old values, and delete the old block. The advantage of this method is that although once in a while, you face a lot of expense, on average, you have O(1) inserts and deletes.
For push_back, you need an iterator to the current last element. But you also need to check at each insert if the size(length) of the vector equals its capacity. If so, resize it.
You need to write iterators that can access the data within the class - vectors use random access iterators, which means you have to define every operation involved in pointer arithmetic: *, ->, ==, ++, --, +(int) and -(iterator). You also need to define the standard begin() and end() functions, which return iterators to the beginning and end of the vector respectively. You also need a const_iterator, which is basically the same as an iterator, but it means you can't modify the vector thru it.
The most important part (for me) is that you need to think about for your design is how you want to handle copies and references. You can choose to lazily have all vectors reference the same location with reference counting, or have a copy-on-write mechanism with reference counting, or simply make copies each time.
I'm pretty sure you won't be asked to write too much code for a question like this, because a vector is an industrial-strength data structure. I guess at most you'd need to discuss all these concepts and possibly write either an outline, or a few select functions.
use allocator object and resize strategy to manage memory, shouldn't be hard. In fact, I think C++ Primer has existing example.
- geniusxsy November 10, 2009Any other tricky thing that I missed?