pandya electronics: C++ STL and data structures

Please share it with your friends who are preparing for interview , and comment down your suggestions , or any mistake in the post.

code snippets are hosted on ideone.com. you can run code there as well.

Before moving ahead, I would highly recommend going through following video from google interview preparation, to understand about how coding interviews are conducted. Remember coding interviews are also about understanding your thought process. So, whatever you think during a coding interview just speak it out. If you found a raw solution like brute force or O(n^2) even start with that. But keep it going.

PS: One my friend got straight asked this question during interview :-)

1) O(1) , O(longn) , O(n), O(nlogn), O(n^2):

These are ways to measure space and time complexity. O(1) is a constant time so it takes constant time to process irrepective of input for example :

int square( int n )

{

return n*n;

}

O(n) is also called linear time for example searching an element in unsorted array,

O(n^2) is quadratic time , a bubble sort ( sorting using double for loops ) is quadratic time.

Binary search takes O(logn) time , as input gets half at each itration.

And most of good sorting algorithams ( Quick sort , merge sort ) have best case complexity of O(nlogn).

I have used this website to create some chart. remeber that importance of big O notation is with large input size , but to just visualise I have kept input size smaller.

remember in big O notations we drop constant times.

Ref :

< https://developerinsider.co/big-o-notation-explained-with-examples/ >

< fooplot chart >

2) Linked list:

< https://www.geeksforgeeks.org/linked-list-set-1-introduction/ >

< https://www.geeksforgeeks.org/linked-list-set-2-inserting-a-node/ >

< https://www.geeksforgeeks.org/delete-a-linked-list-node-at-a-given-position/ >

< https://www.geeksforgeeks.org/linked-list-set-3-deleting-node/ >

< https://www.geeksforgeeks.org/check-if-a-linked-list-is-circular-linked-list/ >

< https://www.geeksforgeeks.org/count-duplicates-in-a-given-linked-list/ >

< https://www.geeksforgeeks.org/remove-duplicates-from-an-unsorted-linked-list/ >

< https://www.geeksforgeeks.org/remove-duplicates-from-a-sorted-linked-list/ >

3) Hashtables in C++ :

remember correct selection of your data structure is necessary as each have different space and time complexity.

1. Do you want to store only keys ?

a. only uniques are allowed ?

set < type > var_name ; => if ordering is needed

unordered_set < type > var_name; => if ordering is not needed

b. duplicate keys allowed ?

multiset < type > var_name ;

unordered_multiset < type > var_name;

2. Do you want to store keys and as well as values ?

a. only uniques are allowed ?

map < type > var_name ; => if ordering is needed

unordered_map < type > var_name; => if ordering is not needed

b. duplicate keys allowed ?

multimap < type > var_name ;

unordered_multimap < type > var_name;

4) Unordered_set in C++ :

difference between set and map : < https://www.geeksforgeeks.org/set-vs-map-c-stl/ >

5) Vectors in C++ :

Vectors are widely used as they are exactly dynamic array. So for any operation on vector you can think of array.

Traversing vector is easy , but inserting/deleting element at front or in middle is difficult.

Doing push_back is O(1).

It is contagious memory.

vector tutorial : < https://www.geeksforgeeks.org/passing-vector-function-cpp/ >

vector passing : < https://www.geeksforgeeks.org/vector-in-cpp-stl/ >

difference between pointer and referance : < https://www.geeksforgeeks.org/pointers-vs-references-cpp/ >

6) List in C++ :

The list in C++ is doubly link list. you can add at front as well as back. and you can travese from front as well as back.

As list is doubly link list, 2 pointers are stored , if you need signly linked list use forward_list which was introduced in C++ 11.

Travesing list takes time.But insert/delete is easy once element is found.

push_back and push_front is O(1).

It can be non contagious memory.

sort() for sorting and reverse() to reverse the list.

7) Queue in C++ :

STL Queue provide addition at back ( push ) and deletion at front ( pop ).

With deque ( double ended queue ) you can do push and pop at both ends.

Priority queues are a type of container adapters, specifically designed such that the first element of the queue is the greatest of all elements in the queue and elements are in non increasing order (hence we can see that each element of the queue has a priority {fixed order}).

< https://www.geeksforgeeks.org/priority-queue-in-cpp-stl/ >