Need help with coding-interview-cpp?
Click the “chat” button below for chat support from the developer who created it, or find similar developers for support.

About the developer

meenakshiravisankar
130 Stars 38 Forks 8 Commits 1 Opened issues

Description

A concise preparation material for competitive programming interviews

Services available

!
?

Need anything else?

Contributors list

Introduction

This repository contains a collection of resources helpful for coding interviews which involve competitive programming. The content is currently supported in C++ only. Since vast amount of material is already present online, links to the same are given below. However, there is no concise and easy to understand documentation of STL available currently. You will find detailed STL syntax with examples in this repo.

Contents

  1. Basic Programming
  2. Time Complexity
  3. Standard Template Library
  4. Data Structures
  5. Algorithms
  6. Math and Miscellaneous
  7. Practice
  8. Acknowledgements

Basic Programming

Tutorial - Basic programming introduces the language syntax and related concepts.

Time Complexity

Tutorial - Understanding computational complexity of your code is important. This is especially significant when choosing an efficient method if there are multiple ways to solve a particular problem.

Standard Template Library

Tutorial - STL is the standard template library which contains C++ template classes. STL is a powerful tool and it reduces programming time with rich implementations of freuently used data structures and algorithms. Important parts of the STL are as follows:

  1. Containers - includes container classes to store and manipulate data elements.
  2. Algorithms - includes important techniques like sorting, searching.
  3. Miscellaneous - includes string class and other functions.

Learn STL, save your life

Usage of several STL classes are illustrated. For convenience and ease of learning, examples are also provided along with syntax.

STL Contents

Containers

Following are the important containers provided with example use cases. Some methods support multiple ways of accepting arguments which are also presented. Templates accept both primitive and user-defined data types. For simiplicity, integer data type is used in the below examples.

Vector

A vector is similar to an array but with dynamic size where elements can be added from one end.

Design: The values are stored consecutively in memory like array for O(1) element access. Costly O(n) for insertion/deletion in the middle of vector.

// declaration and initialization
vector vec; // vec is a vector variable
vector vec_1 (5); // vec_1 is a vector of 0, 0, 0, 0, 0
vector vec_2 (4,100); // vec_2 is a vector of 100, 100, 100, 100

vector::iterator vec_iter; // vec_iter is an iterator for vector vec_iter = vec_2.begin(); // vec_2.begin() is the address of its first element, *vec_iter contains 100

vector vec_3 (vec_2.begin(), vec_2.end()); // initializes from another vector vector vec_4 (vec_3); // copies entire vec_3 vector

int arr[] = {1,2,3}; vector vec_5 (arr, arr+2); // initializes from arr array, vec_5 is a vector of 1, 2

// size() - O(1) - returns size of vector int vec_size = vec_5.size(); // vec_size contains 2

// empty() - O(1) - returns 1 if vector is empty, 0 otherwise bool vec_empty = vec.empty(); // vec_empty contains 1

// access - O(1) int value = vec_5[0]; // similar to array, value contains 1

// front() - O(1) - returns reference to first element value = vec_5.front(); // value contains 1

// back() - O(1) - returns reference to last element value = vec_5.back(); // value contains 2

// push_back() - O(1) - inserts new element at the end vec_5.push_back(3); // vec_5 contains 1, 2, 3

// pop_back() - O(1) - removes last element vec_5.pop_back(); // vec_5 contains 1, 2

// insert() - inserts elements at desired positions. Moves the elements after "position" accordingly. // insert(position, value) - O(n-position) - due to moving elements after position vec_5.insert(vec_5.begin()+1, 4); // vec_5 contains 1, 4, 2

// insert(position, repetitions, value) - O(repetitions+n-position) vec_5.insert(vec_5.begin(), 3, 2); // vec_5 contains 2, 2, 2, 1, 4, 2

// insert(position, start, end) - O(end-start+n-position) vec_5.insert(vec_5.begin(), vec_2.begin(), vec_2.begin()+2); // vec_5 contains 100, 100, 2, 2, 2, 1, 4, 2

// assign() - overwrites values from the beginning // assign(repetitions, value) - O(n') where n' is final size vec_5.assign(1, 5); // vec_5 contains 5

// assign(start, end) - O(n') - n' is final size vec_5.assign(vec_2.begin(), vec_2.begin()+3); // vec_5 contains 100, 100, 100

// erase() - erases elements at desired positions // erase(position) - O(n-position) - due to moving elements after position vec_5.erase(vec_5.begin()); // vec_5 contains 100, 100

// erase(start, end) - O(end-start+n-end) - due to elements erased and moving vec_5.erase(vec_5.begin(), vec_5.begin()+1); // vec_5 is 100

// swap() - O(1) - swaps the contents of vectors vec_1.swap(vec_2); // vec_1 contains 100, 100, 100, 100 and vec_2 contains 0, 0, 0, 0, 0

// clear() - O(n) delete the vector vec_5.clear(); // vec_5 is empty

// relational - O(n) bool status; status = (vec_3 == vec_4); // status contains 1 status = (vec_3 != vec_4); // status contains 0 status = (vec_1 < vec_2); // status contains 0, lexicographically compares elements from left

Deque

A deque is double ended queue similar to vector with an additional benefit where elements can be added from both start and end.

Design: Contiguous memory is not guaranteed unlike vector and insertion/deletion in the middle is costly. However the access is still O(1).

// declaration and initialization
deque deq; // deq is a deque variable
deque deq_1 (5); // deq_1 is a deque of 0, 0, 0, 0, 0
deque deq_2 (4,100); // deq_2 is a deque of 100, 100, 100, 100

deque::iterator deq_iter; // deq_iter is an iterator for deque deq_iter = deq_2.begin(); // deq_2.begin() is the address of its first element, *deq_iter contains 100

deque deq_3 (deq_2.begin(), deq_2.end()); // initializes from another deque deque deq_4 (deq_3); // copies entire deq_3 deque

int arr[] = {1,2,3}; deque deq_5 (arr, arr+2); // initializes from arr array, deq_5 is a deque of 1, 2

// size() - O(1) - returns size of deque int deq_size = deq_5.size(); // deq_size contains 2

// empty() - O(1) - returns 1 if deque is empty, 0 otherwise bool deq_empty = deq.empty(); // deq_empty contains 1

// access - O(1) int value = deq_5[0]; // similar to array, value contains 1

// front() - O(1) - returns reference to first element value = deq_5.front(); // value contains 1

// back() - O(1) - returns reference to last element value = deq_5.back(); // value contains 2

// insert() - inserts elements at desired positions // insert(position, value) - O(n-position) due to moving elements after position deq_5.insert(deq_5.begin()+1, 4); // deq_5 contains 1, 4, 2

// insert(position, repetitions, value) - O(repetitions+n-position) deq_5.insert(deq_5.begin(), 3, 2); // deq_5 contains 2, 2, 2, 1, 4, 2

// insert(position, start, end) - O(end-start+n-position) deq_5.insert(deq_5.begin(), deq_2.begin(), deq_2.begin()+2); // deq_5 contains 100, 100, 2, 2, 2, 1, 4, 2

// assign() - overwrites values from the beginning // assign(repetitions, value) - O(n') - n' is final size deq_5.assign(1, 5); // deq_5 contains 5

// assign(start, end) - O(n') deq_5.assign(deq_2.begin(), deq_2.begin()+3); // deq_5 contains 100, 100, 100

// push_front() - O(1) - inserts new element at the start deq_5.push_front(3); // deq_5 contains 3, 100, 100, 100

// pop_front() - O(1) - removes first element deq_5.pop_front(); // deq_5 contains 100, 100, 100

// push_back() - O(1) - inserts new element at the end deq_5.push_back(3); // deq_5 contains 100, 100, 100, 3

// pop_back() - O(1) - removes last element deq_5.pop_back(); // deq_5 contains 100, 100, 100

// erase() - erases elements at desired positions // erase(position) - O(n-position) deq_5.erase(deq_5.begin()); // deq_5 contains 100, 100

// erase(start, end) - O(end-start+n-position) deq_5.erase(deq_5.begin(), deq_5.begin()+1); // deq_5 contains 100

// swap() - O(1) - swaps the contents of deques deq_1.swap(deq_2); // deq_1 contains 100, 100, 100, 100 and deq_2 contains 0, 0, 0, 0, 0

// clear() - O(n) - delete the deque deq_5.clear(); // deq_5 is empty

// relational - O(n) bool status; status = (deq_3 == deq_4); // status contains 1 status = (deq_3 != deq_4); // status contains 0 status = (deq_1 < deq_2); // status contains 0, lexicographically compares elements from left

List

A doubly linked list with discontiguous storage.

Design: Allows constant insertion/deletion anywhere. O(position) time for accessing.

// declaration and initialization
list mylist; // mylist is a list variable
list mylist_1 (4,100); // mylist_1 contains 100, 100, 100, 100
list mylist_2 (mylist_1); // mylist_2 is a copy of mylist_1
int arr[] = {1,4,3};
list mylist_3 (arr, arr+3); // mylist_3 contains 1, 4, 3

// size() - O(1) - returns size of list int mylist_size = mylist_1.size(); // mylist_size contains 4

// empty() - O(1) - returns 1 if list is empty, 0 otherwise bool mylist_empty = mylist.empty(); // mylist_empty contains 1

// front() - O(1) - returns reference to first element int value = mylist_1.front(); // value contains 100

// back() - O(1) - returns reference to last element value = mylist_1.back(); // value contains 100

// assign() - overwrites values from the beginning // assign(repetitions, value) - O(n') - n' is final size mylist_1.assign(1, 5); // mylist_1 contains 5

// assign(start, end) - O(n') - n' is final size mylist_2.assign(mylist_3.begin(), mylist_3.end()); // mylist_2 contains 1, 4, 3

// push_front() - O(1) - inserts new element at the start mylist_3.push_front(2); // mylist_3 contains 2, 1, 4, 3

// pop_front() - O(1) - removes first element mylist_3.pop_front(); // mylist_3 contains 1, 4, 3

// push_back() - O(1) - inserts new element at the end mylist_3.push_back(2); // mylist_3 contains 1, 4, 3, 2

// pop_back() - O(1) - removes last element mylist_3.pop_back(); // mylist_3 contains 1, 4, 3

// insert() - inserts elements at desired positions // insert(position, value) - O(n-position) due to moving elements after position mylist_3.insert(mylist_3.begin(), 2); // mylist_3 contains 2, 1, 4, 3

// insert(position, repetitions, value) - O(repetitions+n-position) mylist_3.insert(mylist_3.begin(), 2, 2); // mylist_3 contains 2, 2, 2, 1, 4, 3

// insert(position, start, end) - O(end-start+n-position) mylist_3.insert(mylist_3.begin(), mylist_1.begin(), mylist_1.end()); // mylist_3 contains 5, 2, 2, 2, 1, 4, 3

// erase() - erases elements at desired positions // erase(position) - O(n-position) mylist_3.erase(mylist_3.begin()); // mylist_3 contains 2, 2, 2, 1, 4, 3

// erase(start, end) - O(end-start+n-position) list::iterator list_iter; list_iter = mylist_3.begin(); list_iter++; // only unary operator works on this iterator as opposed to mylist_3.begin()+1 mylist_3.erase(mylist_3.begin(), list_iter); // mylist_3 contains 2, 2, 1, 4, 3

// swap() - O(1) - swaps the contents of lists mylist_1.swap(mylist_2); // mylist_1 contains 1, 4, 3 and mylist_2 contains 5

// clear() - O(n) - delete the list mylist_3.clear(); // mylist_3 is empty

// relational - O(n) bool status; status = (mylist_1 == mylist_2); // status contains 0 status = (mylist_1 != mylist_2); // status contains 1 status = (mylist_1 < mylist_2); // status contains 1, lexicographically compares elements from left

Stack

A stack is a last-in-first-out container where elements are added and removed from one end only. It is similar to stack of papers where recently added is on the top and is considered the first element of stack.

Design: Underlying container by default is deque.

// declaration and initialization
stack sta; // sta is a stack variable
vector vec (2,100);
stack > sta_1 (vec); // sta_1 is a copy of vec

// empty() - O(1) - returns 1 if stack is empty, 0 otherwise bool sta_empty = sta.empty(); // sta_empty contains 1

// size() - O(1) - returns size of stack int sta_size = sta_1.size(); // sta_size contains 2

// top() - O(1) - returns reference to top element int sta_top = sta_1.top(); // sta_top is 100

// push() - O(1) - pushes new element from the top sta.push(5); // sta is 5 sta_1.push(5); // sta_1 is 5, 100, 100

// pop() - O(1) - removes top element sta_1.pop(); // sta_1 is 100, 100

// swap() - O(1) - swaps the contents of stacks sta.swap(sta_1); // sta_1 is 5, sta is 100, 100

// relational - O(n) bool status; status = (sta == sta_1); // status contains 0 status = (sta != sta_1); // status contains 1 status = (sta < sta_1); // status contains 0, lexicographically compares elements from left

Queue

A queue is a first-in-first-out container where elements are added and removed from one end only. It is similar to a line of people where person who entered first exists first.

Design: Underlying container by default is deque.

// declaration and initialization
queue que; // que is a queue variable
vector vec (2,100);
queue que_1;
for(int i=0; i

Priority Queue

A priority queue is a sorted container with greatest element first by default.

Design: It is implemented as max heap where the root of any sub-tree is the maximum element.

// declaration and initialization
priority_queue pq; // pq is a priority_queue variable
int arr[] = {3,6,4};
priority_queue pq_1 (arr, arr+3); // pq_1 contains 6, 4, 3

// empty() - O(1) - returns 1 if priority_queue is empty, 0 otherwise bool pq_empty = pq.empty(); // pq_empty contains 1

// size() - O(1) - returns size of priority_queue int pq_size = pq_1.size(); // pq_size contains 3

// top() - O(1) - return reference to first element int pq_front = pq_1.top(); // pq_front is 6

// push() - O(log n) - pushes element into priority queue pq.push(5); // pq is 5 pq_1.push(5); // pq_1 is 6, 5, 4, 3

// pop() - O(log n) removes first element pq_1.pop(); // pq_1 is 5, 4, 3

// swap() - O(1) - swaps the contents of priority queues pq.swap(pq_1); // pq_1 is 5, pq is 5, 4, 3

// changing order to least element first priority_queue, greater > pq_2; pq_2.push(5); pq_2.push(3); // pq_2 is 3, 5

Set

A set contains unique elements with least element first by default.

Design: Implemented as binary search trees (Red-black tree).

// declaration and initialization
set myset; // myset is a set variable
int arr[] = {4,2,1,2};
set myset_1 (arr, arr+4); // myset_1 is a set of 1, 2, 4
set myset_2 (myset_1); // myset_2 is a copy of myset_1

// empty() - O(1) - returns 1 if set is empty, 0 otherwise bool myset_empty = myset.empty(); // myset_empty contains 1

// size() - O(1) - returns size of set int myset_size = myset_1.size(); // myset_size contains 3

// insert() - inserts new elements into the set // insert(value) - O(log n) myset.insert(3); // myset contains 3

// insert(start, end) - O(N log(N+n)) where N = end-start int arr_1[] = {4,3,4}; myset_1.insert(arr_1, arr_1+3); // myset_1 contains 1, 2, 3, 4

// clear() - O(n) - delete the set myset.clear(); // myset is empty

// erase() - erase elements at desired positions myset.insert(arr_1, arr_1+3); // myset contains 3, 4 // erase(position) - O(1) set::iterator set_iter; set_iter = myset.begin(); myset.erase(set_iter); // myset contains 4

// erase(value) - O(log n) myset.insert(arr_1, arr_1+3); // myset contains 3, 4 myset.erase(4); // myset contains 3

// erase(start, end) - O(end-start) myset.insert(arr_1, arr_1+3); // myset contains 3, 4 myset.erase(myset.begin(), myset.end()); // myset is empty

// find(value) - O(log n) - returns iterator to element if found, end() otherwise set_iter = myset_1.find(3); // *set_iter outputs 3 set_iter = myset_1.find(5); // set_iter is myset_1.end()

// count(value) - O(log n) returns 1 if the element is present, 0 otherwise int set_count = myset_1.count(4); // set_count contains 1 set_count = myset_1.count(10); // set_count contains 0

// lower_bound(value) - O(log n) - returns iterator to element equal to or immediately greater than value. Returns end otherwise set_iter = myset_1.lower_bound(3); // *set_iter outputs 3 set_iter = myset_2.lower_bound(3); // *set_iter outputs 4

// upper_bound(value) - O(log n) - returns iterator to element immediately greater than value. Returns end otherwise set_iter = myset_1.upper_bound(3); // *set_iter outputs 4 set_iter = myset_2.upper_bound(3); // *set_iter outputs 4

// equal_range(value) - O(log n) - returns pair of iterators to elements equal to value. In other words, returns lower_bound and upper_bound as a pair. pair::iterator,set::iterator> set_iter_pair; set_iter_pair = myset_1.equal_range(3); // *(set_iter_pair.first) outputs 3 and *(set_iter_pair.second) outputs 4

// swap() - O(1) - swaps the contents of sets myset_1.swap(myset_2); // myset_1 contains 1, 2, 4 and myset_2 contains 1, 2, 3, 4

// changing order to greatest element first set > myset_3 (arr, arr+4); // myset_3 contains 4, 2, 1

Multiset

A multiset is similar to set but can contain duplicate elements with least element first by default.

Design: Implemented as binary search trees (Red-black tree).

// declaration and initialization
multiset mulset; // mulset is a multiset variable
int arr[] = {4,2,1,2};
multiset mulset_1 (arr, arr+4); // mulset_1 is a set of 1, 2, 2, 4
multiset mulset_2 (mulset_1); // mulset_2 is a copy of mulset_1

// empty() - O(1) - returns 1 if multiset is empty, 0 otherwise bool mulset_empty = mulset.empty(); // mulset_empty contains 1

// size() - O(1) - returns size of multiset int mulset_size = mulset_1.size(); // mulset_size contains 4

// insert() - inserts new elements into the multiset // insert(value) - O(log n) mulset.insert(3); // mulset contains 3

// insert(start, end) - O(N log(N+n)) where N = end-start int arr_1[] = {4,3}; mulset_1.insert(arr_1, arr_1+2); // mulset_1 contains 1, 2, 2, 3, 4, 4

// clear() - O(n) - delete the multiset mulset.clear(); // mulset is empty

// erase() - erase elements at desired positions mulset.insert(mulset_1.begin(), mulset_1.end()); // mulset contains 1, 2, 2, 3, 4, 4 // erase(position) - O(1) multiset::iterator mulset_iter; mulset_iter = mulset.begin(); mulset.erase(mulset_iter); // mulset contains 2, 2, 3, 4, 4

// erase(value) - O(log n + num) where num is number of occurrences of value mulset.erase(4); // mulset contains 2, 2, 3

// erase(start, end) - O(end-start) mulset.erase(mulset.begin(), mulset.end()); // mulset is empty

// find(value) - O(log n) - returns iterator to element if found, end() otherwise mulset_iter = mulset_1.find(3); // *mulset_iter outputs 3 mulset_iter = mulset_1.find(5); // mulset_iter is mulset_1.end()

// count(value) - O(log n + num) - returns count of element int mulset_count = mulset_1.count(4); // mulset_count contains 2 mulset_count = mulset_1.count(10); // mulset_count contains 0

// lower_bound(value) - O(log n) - returns iterator to element equal to or immediately greater than value. Returns end otherwise mulset_iter = mulset_1.lower_bound(3); // *mulset_iter outputs 3 mulset_iter = mulset_2.lower_bound(3); // *mulset_iter outputs 4

// upper_bound(value) - O(log n) - returns iterator to element immediately greater than value. Returns end otherwise mulset_iter = mulset_1.upper_bound(3); // *mulset_iter outputs 4 mulset_iter = mulset_2.upper_bound(3); // *mulset_iter outputs 4

// equal_range(value) - O(log n) - returns pair of iterators to elements equal to value. In other words, returns lower_bound and upper_bound as a pair. pair::iterator, multiset::iterator> mulset_iter_pair; mulset_iter_pair = mulset_1.equal_range(3); // *(mulset_iter_pair.first) outputs 3 and *(mulset_iter_pair.second) outputs 4

// swap() - O(1) - swaps the contents of multisets mulset_1.swap(mulset_2); // mulset_1 contains 1, 2, 2, 4 and mulset_2 contains 1, 2, 2, 3, 4, 4

// changing order to greatest element first multiset > mulset_3 (arr, arr+4); // mulset_3 contains 4, 2, 2, 1

Map

Map is an associative container that stores key-value pairs with least key element first by default. The key is unique i.e value is overwritten in case the key is already present.

Design: Implemented as binary search trees (Red-black tree).

// declaration and initialization
map mymap;
int keys[] = {3,1};
int values[] = {4,2};
map mymap_1;
mymap_1[keys[0]] = values[0];
mymap_1[keys[1]] = values[1]; // mymap_1 contains {1,2},{3,4} pairs
map mymap_2 (mymap_1); // mymap_2 is a copy of mymap_1

// empty() - O(1) - returns 1 if map is empty, 0 otherwise bool mymap_empty = mymap.empty(); // mymap_empty contains 1

// size() - O(1) - returns size of map int mymap_size = mymap_1.size(); // mymap_size contains 2

// insert() - inserts new elements into the map // insert(pair) - O(log n) returns a pair. First is iterator to inserted element or already existing key and second is boolean - true if inserted or false if present already. pair::iterator, bool> map_insert; map_insert = mymap.insert(pair(1,6)); // map_insert.second contains true, map_insert.first points to element inserted, mymap contains {1,6}

map_insert = mymap_1.insert(pair(1,6)); // map_insert.second contains false, map_intert.first points to the pair {1,2}. mymap_1 contains {1,2},{3,4}

// insert(start, end) - O(N log(N+n)) where N = end-start mymap.insert(mymap_1.begin(), mymap_1.end()); // mymap contains {1,6}, {3,4}

// clear() - O(n) - delete the map mymap.clear(); // mymap is empty

// erase() - erase elements at desired positions mymap_1.insert(pair(5,6)); // mymap_1 contains {1,2}, {3, 4}, {5,6} // erase(position) - O(1) map::iterator map_iter; map_iter = mymap_1.begin(); mymap_1.erase(map_iter); // mymap_1 contains {3,4}, {5,6}

// erase(key) - O(log n) mymap_1.insert(pair(1,2)); // mymap_1 contains {1,2}, {3, 4}, {5,6} mymap_1.erase(1); // mymap_1 contains {3, 4}, {5,6}

// erase(start, end) - O(end-start) mymap.insert(pair(1,2)); // mymap contains {1,2} mymap.erase(mymap.begin(), mymap.end()); // mymap is empty

// find(key) - O(log n) - returns iterator to element if found, end() otherwise map_iter = mymap_1.find(3); // map_iter->first outputs 3, map_iter->second outputs 4 map_iter = mymap_1.find(1); // map_iter is mymap_1.end()

// count(key) - O(log n) returns 1 if the element is present, 0 otherwise int map_count = mymap_1.count(3); // map_count contains 1 map_count = mymap_1.count(1); // map_count contains 0

// lower_bound(key) - O(log n) - returns iterator to element equal to or immediately greater than value. Returns end otherwise map_iter = mymap_1.lower_bound(3); // map_iter->first outputs 3, map_iter->second outputs 4 map_iter = mymap_1.lower_bound(1); // map_iter->first outputs 3, map_iter->second outputs 4

// upper_bound(key) - O(log n) - returns iterator to element immediately greater than value. Returns end otherwise map_iter = mymap_1.upper_bound(3); // // map_iter->first outputs 5, map_iter->second outputs 6

// equal_range(key) - O(log n) - returns pair of iterators to elements equal to value. In other words, returns lower_bound and upper_bound as a pair. pair::iterator,map::iterator> map_iter_pair; map_iter_pair = mymap_1.equal_range(3); // map_iter_pair.first->first outputs 3 and map_iter_pair.second->first outputs 5

// swap() - O(1) - swaps the contents of maps mymap_1.swap(mymap_2); // mymap_1 contains {1,2}, {3, 4} and mymap_2 contains {3, 4}, {5,6}

Multimap

A multimap is similar to map but can contain multiple values for a key with least key first by default. In case of multiple values for a key, they are not sorted according to value and follows the order of initialization.

Design: Implemented as binary search trees (Red-black tree).

// declaration and initialization
multimap mulmap;
int keys[] = {3,1,3};
int values[] = {6,2,4};
multimap mulmap_1;
for(int i=0; i<3; i++)
    mulmap_1.insert(pair(keys[i],values[i])); 
// mulmap_1 contains {1,2}, {3,6}, {3,4}. Unlike in map, operator [] cannot be used here.
multimap mulmap_2 (mulmap_1); // mulmap_2 is a copy of mulmap_1

// empty() - O(1) - returns 1 if multimap is empty, 0 otherwise bool mulmap_empty = mulmap.empty(); // mulmap_empty contains 1

// size() - O(1) - returns size of multimap int mulmap_size = mulmap_1.size(); // mulmap_size contains 3

// insert() - inserts new elements into the multimap // insert(pair) - O(log n) mulmap.insert(pair(1,6)); // mulmap contains {1,6} mulmap_1.insert(pair(1,6)); // mulmap_1 contains {1,2}, {1,6}, {3,6}, {3,4}

// insert(start, end) - O(N log(N+n)) where N = end-start mulmap.insert(mulmap_1.begin(), mulmap_1.end()); // mulmap contains {1,6}, {1,2}, {1,6}, {3,6}, {3,4}

// clear() - O(n) - delete the multimap mulmap.clear(); // mulmap is empty

// erase() - erase elements at desired positions mulmap.insert(pair(5,6)); // mulmap contains {5,6}

// erase(position) - O(1) multimap::iterator mulmap_iter; mulmap_iter = mulmap.begin(); mulmap.erase(mulmap_iter); // mulmap is empty

// erase(key) - O(log n + num) where num is number of occurrences of key mulmap_1.erase(1); // mulmap_1 contains {3,6}, {3,4}

// erase(start, end) - O(end-start) mulmap.insert(pair(1,2)); // mulmap contains {1,2} mulmap.erase(mulmap.begin(), mulmap.end()); // mulmap is empty

// find(key) - O(log n) - returns iterator to element if found, end() otherwise mulmap_iter = mulmap_1.find(3); // mulmap_iter->first outputs 3, mulmap_iter->second outputs 6 mulmap_iter = mulmap_1.find(1); // mulmap_iter is mulmap_1.end()

// count(key) - O(log n + num) returns count of key int mulmap_count = mulmap_1.count(3); // mulmap_count contains 2 mulmap_count = mulmap_1.count(1); // mulmap_count contains 0

// lower_bound(key) - O(log n) - returns iterator to element equal to or immediately greater than value. Returns end otherwise mulmap_iter = mulmap_1.lower_bound(3); // mulmap_iter->first outputs 3, mulmap_iter->second outputs 6 mulmap_iter = mulmap_1.lower_bound(1); // mulmap_iter->first outputs 3, mulmap_iter->second outputs 4

// upper_bound(key) - O(log n) - returns iterator to element immediately greater than value. Returns end otherwise mulmap_iter = mulmap_1.upper_bound(3); // // mulmap_iter is mulmap_1.end()

// equal_range(key) - O(log n) - returns pair of iterators to elements equal to key. In other words, returns lower_bound and upper_bound as a pair. pair::iterator,multimap::iterator> mulmap_iter_pair; mulmap_iter_pair = mulmap_1.equal_range(3); // mulmap_iter_pair.first->first outputs 3 and mulmap_iter_pair.second is mulmap_1.end()

// swap() - O(1) - swaps the contents of multimaps mulmap_1.swap(mulmap_2); // mulmap_1 contains {1,2}, {3,6}, {3,4} and mulmap_2 contains {3,6}, {3,4}

Unordered Set

An unordered set contains unique elements with no particular order and allows faster access.

Design: Implemented as hash map.

// declaration and initialization
unordered_set myset; // myset is an unordered set variable
int arr[] = {4,2,1,2};
unordered_set myset_1 (arr, arr+4); // myset_1 is an unordered set of 2, 1, 4 (random order)
unordered_set myset_2 (myset_1); // myset_2 is a copy of myset_1

// empty() - O(1) - returns 1 if unordered set is empty, 0 otherwise bool myset_empty = myset.empty(); // myset_empty contains 1

// size() - O(1) - returns size of unordered set int myset_size = myset_1.size(); // myset_size contains 3

// insert() - inserts new elements into the unordered set // insert(value) - O(1) on average myset.insert(3); // myset contains 3

// insert(start, end) - O(N) where N = end-start int arr_1[] = {4,3,4}; myset_1.insert(arr_1, arr_1+3); // myset_1 contains 4, 2, 1, 3

// clear() - O(n) - delete the unordered set myset.clear(); // myset is empty

// erase() - erase elements at desired positions myset.insert(arr_1, arr_1+3); // myset contains 4, 3 // erase(position) - O(1) unordered_set::iterator set_iter; set_iter = myset.find(4); myset.erase(set_iter); // myset contains 3

// erase(value) - O(1) myset.insert(arr_1, arr_1+3); // myset contains 3, 4 myset.erase(4); // myset contains 3

// erase(start, end) - O(end-start) myset.insert(arr_1, arr_1+3); // myset contains 3, 4 myset.erase(myset.begin(), myset.end()); // myset is empty

// find(value) - O(1) - returns iterator to element if found, end() otherwise set_iter = myset_1.find(3); // *set_iter outputs 3 set_iter = myset_1.find(5); // set_iter is myset_1.end()

// count(value) - O(1) returns 1 if the element is present, 0 otherwise int set_count = myset_1.count(4); // set_count contains 1 set_count = myset_1.count(10); // set_count contains 0

// equal_range(value) - O(1) - returns pair of iterators to elements equal to value. In other words, returns lower_bound and upper_bound as a pair. pair::iterator,unordered_set::iterator> set_iter_pair; set_iter_pair = myset_1.equal_range(3); // *(set_iter_pair.first) outputs 3 and *(set_iter_pair.second) outputs 4

// swap() - O(1) - swaps the contents of unordered sets myset_1.swap(myset_2); // myset_1 contains 4, 2, 1 and myset_2 contains 4, 2, 1, 3

Unordered MultiSet

An unordered multiset is similar to normal multiset with no order and allows faster access.

Design: Implemented as hash map.

// declaration and initialization
unordered_multiset mulset; // mulset is an unordered multiset variable
int arr[] = {4,2,1,2};
unordered_multiset mulset_1 (arr, arr+4); // mulset_1 is a set of 2, 2, 1, 4 (random order)
unordered_multiset mulset_2 (mulset_1); // mulset_2 is a copy of mulset_1

// empty() - O(1) - returns 1 if unordered multiset is empty, 0 otherwise bool mulset_empty = mulset.empty(); // mulset_empty contains 1

// size() - O(1) - returns size of unordered multiset int mulset_size = mulset_1.size(); // mulset_size contains 4

// insert() - inserts new elements into the unordered multiset // insert(value) - O(1) mulset.insert(3); // mulset contains 3

// insert(start, end) - O(N) where N = end-start int arr_1[] = {4,3}; mulset_1.insert(arr_1, arr_1+2); // mulset_1 contains 4, 2, 1, 2, 4, 3

// clear() - O(n) - delete the unordered multiset mulset.clear(); // mulset is empty

// erase() - erase elements at desired positions mulset.insert(mulset_1.begin(), mulset_1.end()); // mulset contains 4, 2, 1, 2, 4, 3 // erase(position) - O(1) unordered_multiset::iterator mulset_iter; mulset_iter = mulset.find(4); mulset.erase(mulset_iter); // mulset contains 2, 1, 2, 4, 3

// erase(value) - O(num) where num is number of occurrences of value mulset.erase(2); // mulset contains 1, 4, 3

// erase(start, end) - O(end-start) mulset.erase(mulset.begin(), mulset.end()); // mulset is empty

// find(value) - O(1) - returns iterator to element if found, end() otherwise mulset_iter = mulset_1.find(3); // *mulset_iter outputs 3 mulset_iter = mulset_1.find(5); // mulset_iter is mulset_1.end()

// count(value) - O(num) - returns count of element int mulset_count = mulset_1.count(4); // mulset_count contains 2 mulset_count = mulset_1.count(10); // mulset_count contains 0

// equal_range(value) - O(1) - returns pair of iterators to elements equal to value. In other words, returns lower_bound and upper_bound as a pair. pair::iterator,unordered_multiset::iterator> mulset_iter_pair; mulset_iter_pair = mulset_1.equal_range(3); // *(mulset_iter_pair.first) outputs 3 and *(mulset_iter_pair.second) outputs 4

// swap() - O(1) - swaps the contents of unordered multisets mulset_1.swap(mulset_2); // mulset_1 contains 4, 2, 1, 2 and mulset_2 contains 4, 2, 1, 2, 4, 3

Unordered Map

Unordered map is an associative container that stores key-value pairs with no order. The key is unique i.e value is overwritten in case the key is already present.

Design: Implemented as hash map.

// declaration and initialization
unordered_map mymap;
int keys[] = {3,1};
int values[] = {4,2};
unordered_map mymap_1;
mymap_1[keys[0]] = values[0];
mymap_1[keys[1]] = values[1]; // mymap_1 contains {3,4}, {1,2} pairs
unordered_map mymap_2 (mymap_1); // mymap_2 is a copy of mymap_1

// empty() - O(1) - returns 1 if unordered map is empty, 0 otherwise bool mymap_empty = mymap.empty(); // mymap_empty contains 1

// size() - O(1) - returns size of unordered map int mymap_size = mymap_1.size(); // mymap_size contains 2

// insert() - inserts new elements into the unordered map // insert(pair) - O(1) returns a pair. First is iterator to inserted element or already existing key and second is boolean - true if inserted or false if present already. pair::iterator, bool> map_insert; map_insert = mymap.insert(pair(1,6)); // map_insert.second contains true, map_insert.first points to element inserted, mymap contains {1,6}

map_insert = mymap_1.insert(pair(1,6)); // map_insert.second contains false, map_intert.first points to the pair {1,2}. mymap_1 contains {3,4}, {1,2}

// insert(start, end) - O(N) where N = end-start mymap.insert(mymap_1.begin(), mymap_1.end()); // mymap contains {1,6}, {3,4}

// clear() - O(n) - delete the unordered map mymap.clear(); // mymap is empty

// erase() - erase elements at desired positions mymap_1.insert(pair(5,6)); // mymap_1 contains {3, 4}, {1,2}, {5,6} // erase(position) - O(1) unordered_map::iterator map_iter; map_iter = mymap_1.find(3); mymap_1.erase(map_iter); // mymap_1 contains {1,2}, {5,6}

// erase(key) - O(1) - where num is number of occurrences of value mymap_1.insert(pair(3,4)); // mymap_1 contains {1,2}, {5,6}, {3, 4} mymap_1.erase(1); // mymap_1 contains {5,6}, {3, 4}

// erase(start, end) - O(end-start) mymap.insert(pair(1,2)); // mymap contains {1,2} mymap.erase(mymap.begin(), mymap.end()); // mymap is empty

// find(key) - O(1) - returns iterator to element if found, end() otherwise map_iter = mymap_1.find(3); // map_iter->first outputs 3, map_iter->second outputs 4 map_iter = mymap_1.find(1); // map_iter is mymap_1.end()

// count(key) - O(1) returns 1 if the element is present, 0 otherwise int map_count = mymap_1.count(3); // map_count contains 1 map_count = mymap_1.count(1); // map_count contains 0

// equal_range(key) - O(1) - returns pair of iterators to elements equal to value. In other words, returns lower_bound and upper_bound as a pair. pair::iterator,unordered_map::iterator> map_iter_pair; map_iter_pair = mymap_1.equal_range(3); // map_iter_pair.first->first outputs 3 and map_iter_pair.second->first outputs 5

// swap() - O(1) - swaps the contents of unordered maps mymap_1.swap(mymap_2); // mymap_1 contains {3,4}, {1,2} and mymap_2 contains {5,6}, {3, 4}

Unordered Multimap

Unordered multimap is similar to unordered map but can contain multiple values for a key with no order.

Design: Implemented as hash map.

// declaration and initialization
unordered_multimap mulmap;
int keys[] = {3,1,3};
int values[] = {6,2,4};
unordered_multimap mulmap_1;
for(int i=0; i<3; i++)
    mulmap_1.insert(pair(keys[i],values[i])); 
// mulmap_1 contains {3,6}, {1,2}, {3,4}. Unlike in map, operator [] cannot be used here.
unordered_multimap mulmap_2 (mulmap_1); // mulmap_2 is a copy of mulmap_1

// empty() - O(1) - returns 1 if unordered multimap is empty, 0 otherwise bool mulmap_empty = mulmap.empty(); // mulmap_empty contains 1

// size() - O(1) - returns size of unordered multimap int mulmap_size = mulmap_1.size(); // mulmap_size contains 3

// insert() - inserts new elements into the unordered multimap // insert(pair) - O(1) mulmap.insert(pair(1,6)); // mulmap contains {1,6} mulmap_1.insert(pair(1,6)); // mulmap_1 contains {3,6}, {1,2}, {3,4}, {1,6}

// insert(start, end) - O(N) where N = end-start mulmap.insert(mulmap_1.begin(), mulmap_1.end()); // mulmap contains {1,6}, {3,6}, {1,2}, {3,4}, {1,6}

// clear() - O(n) - delete the unordered multimap mulmap.clear(); // mulmap is empty

// erase() - erase elements at desired positions mulmap.insert(pair(5,6)); // mulmap contains {5,6}

// erase(position) - O(1) unordered_multimap::iterator mulmap_iter; mulmap_iter = mulmap.find(5); mulmap.erase(mulmap_iter); // mulmap is empty

// erase(key) - O(num) where num is number of occurrences of key mulmap_1.erase(1); // mulmap_1 contains {3,6}, {3,4}

// erase(start, end) - O(end-start) mulmap.insert(pair(1,2)); // mulmap contains {1,2} mulmap.erase(mulmap.begin(), mulmap.end()); // mulmap is empty

// find(key) - O(1) - returns iterator to element if found, end() otherwise mulmap_iter = mulmap_1.find(3); // mulmap_iter->first outputs 3, mulmap_iter->second outputs 6 mulmap_iter = mulmap_1.find(1); // mulmap_iter is mulmap_1.end()

// count(key) - O(num) returns count of key int mulmap_count = mulmap_1.count(3); // mulmap_count contains 2 mulmap_count = mulmap_1.count(1); // mulmap_count contains 0

// equal_range(key) - O(1) - returns pair of iterators to elements equal to key. In other words, returns lower_bound and upper_bound as a pair. pair::iterator,unordered_multimap::iterator> mulmap_iter_pair; mulmap_iter_pair = mulmap_1.equal_range(3); // mulmap_iter_pair.first->first outputs 3 and mulmap_iter_pair.second is mulmap_1.end()

// swap() - O(1) - swaps the contents of unordered multimaps mulmap_1.swap(mulmap_2); // mulmap_1 contains {3,6}, {1,2}, {3,4} and mulmap_2 contains {3,6}, {3,4}

Algorithms

// comparison function
bool comp(int a, int b)
{
    return a>b; // for descending order
}

// min(a,b), max(a,b) - returns minimum and maximum values respectively int min_num = min(3,5); // min_num contains 3 int max_num = max(3,5); // max_num contains 5

// min_element(start, end), max_element(start, end) - O(n) - returns iterator to the element vector vec ({4,5,1}); // vec contains 4, 5, 1 vector::iterator vec_iter; vec_iter = min_element(vec.begin(), vec.end()); // *vec_iter contains 1 vec_iter = max_element(vec.begin(), vec.end()); // *vec_iter outputs 5

// distance(start, end) - O(n) - returns distance between two iterators int vec_dist = distance(vec.begin(), vec_iter); // vec_dist is 1

// reverse(start, end) - O(n) - reverse the order of elements reverse(vec.begin(), vec.end()); // vec contains 1, 5, 4

// next_permutation(start, end), prev_permutation(start, end) - O(n) - rearranges to lexicographically greater/lesser permutation next_permutation(vec.begin(), vec.end()); // vec contains 4, 1, 5 prev_permutation(vec.begin(), vec.end()); // vec contains 1, 5, 4

// random_shuffle(start, end) - O(n) - rearrange elements randomly random_shuffle(vec.begin(), vec.end());

// sort(start, end) - O(nlog n) int arr_1[] = {4,5,1}; int arr_2[] = {2,3,1};

sort(arr_1, arr_1+3); // arr_1 contains 1, 4, 5 - ascending by default sort(arr_2, arr_2+3, comp); // arr_2 contains 3, 2, 1 - descending using comp function

// binary_search(start, end, value) - O(log n) - returns true if value found in sorted range int status; status = binary_search(arr_1, arr_1+3, 4); // status contains 1 (ascending range by default) status = binary_search(arr_2, arr_2+3, 3, comp); // status contains 1

// merge(start_1, end_1, start_2, end_2, new_iter) vector vec_1(6); // vec_1 contains 0, 0, 0, 0, 0, 0 sort(arr_2, arr_2+3); // arr_2 contains 1, 2, 3 merge(arr_1, arr_1+3, arr_2, arr_2+3, vec_1.begin()); // vec_1 contains 1, 1, 2, 3, 4, 5

// find(start, end, value) - O(n) returns iterator to element otherwise end() vec_iter = find(vec_1.begin(), vec_1.end(), 4); // *vec_iter is 4 vec_iter = find(vec_1.begin(), vec_1.end(), 6); // vec_iter is vec_1.end()

Miscellaneous

Pair

pair mypair; // declaration
pair mypair_1 (3,5); // initialization
mypair = make_pair(2,4); // assign
int first, second;
first = mypair.first; // first contains 2
second = mypair.second; // second contains 4

String

// declaration and initialization
string s;
string s_1 = "random string";
string s_2 (s_1.begin(), s_1.begin()+3); // s_2 contains ran
string s_3 (5,'#'); // s_3 contains #####  
string s_4 (s_1); // s_4 is a copy of s_1

// length() - returns length of string int s_length = s_3.length(); // s_length contains 5

// access char s_char = s_1[0]; // s_char contains r s_4[0] = 'f'; // s_4 contains fandom string

// clear() - deletes the string s_4.clear(); // s_4 is empty

// empty() - returns 1 if empty, 0 otherwise bool s_empty = s_4.empty(); // s_empty contains 1

// concatenate s_2 += "d"; // s_2 contains rand

// append() - concatenates string to the end s_4 = "om"; // append(string) s_2.append(s_4); // s_2 contains random // append(start, end) s_2.append(s_3.begin(), s_3.begin()+1); // s_2 contains random#

// assign() - replaces current string // assign(string) s.assign(s_3); // s contains ##### // assign(start, end) s.assign(s_2.begin(), s_2.end()); // s contains random#

// insert() - inserts string after position // insert(position, string) s.insert(0, s_3); // s contains #####random# // insert(position, start, end) s.insert(s.end(), s_3.begin(), s_3.end()-1); // s contains #####random#####

// erase() - deletes character at the given position(s) // erase(position) s.erase(s.begin()); // s contains ####random##### // erase(start, end) s.erase(s.begin(), s.begin()+4); // s contains random#####

// replace() - replaces from start to end with string // replace(start, end, string) s.replace(s.begin(), s.begin()+3, s_3); // s contains #####dom##### // replace(start, end, start_1, end_1) s.replace(s.begin()+1, s.end(), s_2.begin(), s_2.end()); // s contains #random#

// find() - returns position of occurrence of string, -1 otherwise // find(string) int position; position = s.find("random"); // position contains 1 position = s.find("fandom"); // position contains -1 // find(string, position) - searches for occurrence from position. By default, position is 0 in the above case position = s.find("random", 2); // position contains -1

// swap(string) - swaps contents of the strings s.swap(s_2); // s contains random#, s_2 contains #random#

// relational operators bool status; status = (s_1==s_4); // status contains 0 status = (s_1!=s_4); // status contains 1 status = (s_1 < s_4); // status contains 0

// conversions // stoi - convert string to integer int num = stoi("1998");

// stoll - convert string to long long int long long int num_1 = stoll("19981998");

// stof - convert string to float float num_2 = stof("1998.26");

// stod - convert string to double double num_3 = stod("19981998.26");

// to_string - convert to string s = to_string(num_3); // s contains 19981998.26

You can find detailed documentation on the official website.

Data Structures

Tutorial - Different ways of storing, accessing and manipulating data according to the requirements.

Algorithms

Tutorial - Efficient techniques and paradigms to solve various problems.

Math and Miscellaneous

Tutorial - Math based concepts and ad-hoc problems that involve logic.

Practice

  1. InterviewBit - InterviewBit has topic wise tutorials and good collection of problems.
  2. Leetcode - Leetcode has a great variety of problems with corner and tricky test cases which are beneficial for interviews.
  3. Codeforces, HackerEarth, HackerRank - Competitive programming websites have huge collection of problems.

Acknowledgements

Thanks to Ethan for being a source of inspiration and the reason behind this work.

We use cookies. If you continue to browse the site, you agree to the use of cookies. For more information on our use of cookies please see our Privacy Policy.