Google Interview Question for Software Engineer / Developers


Country: -
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
2
of 2 vote

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

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.

- geliang2008 November 10, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- eugene.yarovoi November 10, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The focus here was more on the iterator design and the idiosyncrasies of C++ and STL.

- lyra_vega November 11, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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;
...
};

- pavel.em November 11, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

std::vector is implemented by array. My most concerns is how to deal with function like resize, and size increase in push_back and insert

- geliang2008 November 09, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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. :)

- victoriousvishal September 03, 2012 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More