C++ interview questions on STL containers like vector and list

(Last Updated On: May 12, 2010)

C++ interview questions on STL containers like vector and list

Containers:
vector and list difference. complexities of alogrithms.

Vector –
1> Insertion – O(n) /* Resizing the array */
2> Search – O(n) /* Sequential */ , O(logn ) /* Binary */
3> Random Access – Yes .
4> Deletion – O(n) /* Shifting & Resizing */
5> Sequential Memory used .

List –
1> Insertion – O(1)
2> Search – O(n)
3> Deletion – O(n)
4> Random Access – No
5> Linked allocation , hence more memory efficient .
Reply to Comment
Anonymous on April 10, 2010 |Edit | Edit

For list, the complexity of deletion should be O(1).
3> Deletion – O(1)

What is a container class? What are the types of container classes?
A container class is a class that is used to hold objects in memory or external storage. A container class acts as a generic holder. A container class has a predefined behavior and a well-known interface. A container class is a supporting class whose purpose is to hide the topology used for maintaining the list of objects in memory. When a container class contains a group of mixed objects, the container is called a heterogeneous container; when the container is holding a group of objects that are all the same, the container is called a homogeneous container.
how to delete a node in a list
single linked list ? – then save pointer to next node, start from head and go to the node right before the node being deleted, and change it’s “next” pointer to the one you saved.
Now you can delete node.
double linked list ? – no need to start from head, just reassign pointers in neighbor nodes properly to point to each other instead of to the node being deleted, and then delete the node. Of course, special care for first and last nodes, which have some NULL pointers.

NOTE I now post my TRADING ALERTS into my personal FACEBOOK ACCOUNT and TWITTER. Don't worry as I don't post stupid cat videos or what I eat!
This entry was posted in Quant Development and tagged , , , , , , on by .

About caustic

Hi i there My name is Bryan Downing. I am part of a company called QuantLabs.Net This is specifically a company with a high profile blog about technology, trading, financial, investment, quant, etc. It posts things on how to do job interviews with large companies like Morgan Stanley, Bloomberg, Citibank, and IBM. It also posts different unique tips and tricks on Java, C++, or C programming. It posts about different techniques in learning about Matlab and building models or strategies. There is a lot here if you are into venturing into the financial world like quant or technical analysis. It also discusses the future generation of trading and programming Specialties: C++, Java, C#, Matlab, quant, models, strategies, technical analysis, linux, windows P.S. I have been known to be the worst typist. Do not be offended by it as I like to bang stuff out and put priorty of what I do over typing. Maybe one day I can get a full time copy editor to help out. Do note I prefer videos as they are much easier to produce so check out my many video at youtube.com/quantlabs