Google Interview Question
Software Engineer / DevelopersCountry: -
Interview Type: In-Person
I would think vector-like containers would have copy semantics (in assignments like vec[i] = value;. After all, if you want to pass things around by pointers, you can always make a std::vector<T*> instead of an std::vector<T>. That's why the standard library is made that way.
iterator design is rather simple: you define a concept which is basically the set of typenames custom iterators should provide
to be eligible as input iterators. Then you also define
iterator_traits to distinguish between C-style pointers and
iterator objects, smth like:
template <class T>
struct iterator_traits { // forward definitions from iterator type T
typedef typename T::data_type data_type;
typedef typename T::ref_type ref_type;
...
};
template <class T>
struct iterator_traits<T*> { // same for pointers
typedef T data_type;
typedef T& ref_type;
...
};
lyra_vega I saw that the questions asked from you were very tough so I wanted to know if you were a fresher (just completed/doing B.Tech) at your time of interview or not? Actually even I have my interview on coming 10th of this month and I am a fresher so I am getting a bit scared by seeing such difficulty level. :)
I tracked down this question to the same question in the question pool. The following is the quote from one of the replies, I think it makes sense
- geliang2008 November 10, 2011You'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.