C++ Questions

Data structures internal to STL containers

	Vector	Set	List	Map	Hash-Set
Data Structure	Dynamic Array	Self-Balancing BST	Doubly-Linked List	Self-Balancing BST	Hash Table

	Abstract Class
Data Structure	Virtual Method Table (vtable)

How does dynamic array allocate memory dynamically (growing & shrinking in run time)?

Binary Tree	Binary Search Tree
A tree data structure in which each node has at most two child nodes.	An ordered or sorted binary tree, with no duplicate nodes.

Vector	List
A dynamic array, like C array (i.e., capable of random access) with the ability to resize itself automatically when inserting or erasing an object. Inserting and removing an element to/from back of the vector at the end takes amortized constant time. Inserting and erasing at the beginning or in the middle is linear in time.	A doubly linked list; elements are not stored in contiguous memory. Opposite performance from a vector. Slow lookup and access (linear time), but once a position has been found, quick insertion and deletion (constant time).

Different types of traversal in Binary trees
1 Depth-first traversal
1a. pre-order traversal
1b. post-order traversal

2 Breadth-first traversal

	Best Performance, O(1)	Average Performance, O(log n)	Worst Performance, O(n)
Binary Tree Structure	When one searches the root node	When you search a normal BST	When the unbalanced tree resembles a linked list (degenerate tree).

	Abstract Class	Singleton Class
Use

Example scenarios why & when would we need derived classes

Because we have access to the source code of the Base class, we could add functionality directly to Base. However, there may be times when we do not want to, or can not. Consider the case where you have just purchased a library of code from a 3rd party vendor, but need some extra functionality. You could add to the original code, but this isn’t the best solution. What if the vendor sends you an update? Either your additions will be overwritten, or you’ll have to manually migrate them. It’s also common to for developers to release header files containing class definitions, but release the implementation code precompiled — this means you can use the code, but you won’t have the ability to modify it directly.
In either case, the best answer is to derive your own class, and add the functionality you want to the derived class.