Google Interview Question Software Engineer Interns
Country: Brazil
Interview Type: In-Person
1. this question is about out of bound read/writes. For instance, the size is currently 8 and you use 'vector[9] = 1'.
2. correct.
3. logn is the number of reallocations, not number of copies.
@Victor, I think author means that if the size of the vector hits to the capacity, We will immediately increase it to double, instead of when user writes vector[9]. In this way you will never have to be reaching out of bounds.
Initial we can start with size of the array as 10 or more than that.
If it reaches boundary we can double it or we can increase by 1.5 times.
we have to copy all the elements from the old array to new array.
We can maintain a variable which contains the number of elements presently array holding
Considering the size of the Vector gets doubled, every time it exceeds the current size of the array, then the number of copies performed by the vector to insert 'n' elements would be:
Lets say, initial size of Vector is 'm', and number of elements inserted in the Vector totally is 'n', then number of copies = n/m.
For e.g, if initial size of Vector is 3, and 9 elements were inserted, then in total, the number of times the copy() function was performed is 3.
Is this interpretation correct?
Vector is implemented base on array, say size m.
- yangxh92 November 22, 20141. If the array is full, create a new array of size 2m, copy the elements from original array to the new one, and put the to-be-inserted element into the new array
2. The size gets doubled.
3. If the array has size 0 for initialization, then you need log n copies to insert n elements.