Evaluation strategies

https://en.wikipedia.org/wiki/Evaluation_strategy
https://en.wikipedia.org/wiki/Eager_evaluation
https://en.wikipedia.org/wiki/Lazy_evaluation

Binary Tree

http://courses.csail.mit.edu/iap/interview/Hacking_a_Google_Interview_Handout_3.pdf
http://www.mytechinterviews.com/balanced-tree

Card deck shuffling

http://courses.csail.mit.edu/iap/interview/Hacking_a_Google_Interview_Handout_3.pdf
https://blog.codinghorror.com/shuffling/
https://tekpool.wordpress.com/2006/10/06/shuffling-shuffle-a-deck-of-cards-knuth-shuffle/

Linear Regression

What are the types of Gradient Descent?

- batch
- minibatch
- stochastic gradient descent

Git cherry-pick

https://git-scm.com/docs/git-cherry-pick
https://www.kernel.org/pub/software/scm/git/docs/git-cherry-pick.html

Real-life usage example:

https://community.openvpn.net/openvpn/wiki/CodeRepositories:

Release branches do not have any active development and only bug fixes are typically applied to these branches after the release. A new release branch is created for each major release (2.x). All bug fixes should be developed against the master branch, and where it is decided to include such fixes in a minor release (2.1.x, 2.2.x, etc), it will be cherry-picked from the master branch and into the suitable release branches.

Git rebase

https://www.kernel.org/pub/software/scm/git/docs/git-rebase.html

Real-life usage example:
https://community.openvpn.net/openvpn/wiki/CodeRepositories:
"Developers being granted a feature branch must ensure that their branch is regularly ​rebased against the master branch."

C++ Explicit Constructor

List 5 cases when implicit conversion is performed.
List 6 cases when copy initialization is performed.
What is the purpose of explicit constructor?



References:
http://en.cppreference.com/w/cpp/language/implicit_conversion
http://en.cppreference.com/w/cpp/language/copy_initialization

C++ Copy Constructor

What is a difference between copying and cloning an object?
What is a copy constructor? (What is its purpose?)
What are its arguments?
What is implicit and what is user-defined copy-constructor?
When does compiler create copy-constructor?
When is needed a user-defined copy-constructor? Why? What else is then also needed?
What is the Rule of three?
Is there any other way to copy objects apart from using copy-constructor?
Give some examples of copy constructor signatures. Which one is preferred?
Which versions of copy constructor are called in the following code snippet?

a) X x = X(); 

b) const X x1;    

   X x2 = x1;

Why are these constructors not valid copy-constructors?

a) X(X x) 

b) X(const X x)

In which situations is called copy-constructor? (List 5 cases of copy-initialization.)
What is Return value optimization?

TBC...

References:

http://stackoverflow.com/questions/2200409/what-is-the-difference-between-copying-and-cloning
https://en.wikipedia.org/wiki/Object_copying
https://en.wikipedia.org/wiki/Cloning_(programming)
https://en.wikipedia.org/wiki/Copy_constructor_(C%2B%2B)
https://en.wikipedia.org/wiki/Rule_of_three_(C%2B%2B_programming)

Quicksort

Complexity: O(N * logN)
Quicksort (Wikipedia)

Merge Sort

Merge sort (Wikipedia)

Insertion Sort

Complexity: O(N^2)
Insertion sort - Wikipedia

Bubble Sort

Algorithm:
1: start from the beginning of an array
2: compare current and the next element; if current is bigger than the next one, swap them
3: move one place to the right
4: repeat step 2 till you get to the last element (or, more efficiently till you get to the last highest set in its final location; )
5: goto 1

Complexity: O(N^2)
Bubble sort - Wikipedia

Singly Linked List

- Unordered array has fast insertion and slow search and deletion; ordered array has fast search and slow insertion and deletion; arrays have constant size;

Linked lists:
- have fast insertion and deletion
- can be sorted and unsorted
- can be singly or doubly linked
- are memory efficient: they use as much memory as needed, not more, not less;

Element of a singly linked list is usually called node and it has two parts: data and pointer to the next element.
Head is a pointer that points to the first node.
Tail is a pointer that points to the last node.

Unordered (unsorted) Singly Linked List

Operations:

Insertion to the front (push_front):

- Algorithm: item is added at the front of the list
- Complexity: O(1)

Insertion to the back (push_back):

- Algorithm: item is added at the  back  of the list
- Complexity: O(1) if tail pointer is maintained; O(N) if not because we need to go through all nodes in order to get to the last one - the more nodes - the more steps;

Removal from the front (pop_front):

- Algorithm: remove the item from the front of the list
- Complexity: O(1)

Removal from the end (pop_back):

- Algorithm: remove the item from the  back of the list
- Complexity: O(N) - even if we maintain (use) tail pointer - it is not of a help here as we cannot access to the node which precedes the last node through it in the case of  singly linked list (if we had doubly linked list that would be possible); we need to go through all nodes in order to get to the last one - the more nodes - the more steps;

Search for the item with specific value (key):

- Algorithm: go from the first node and traverse through the list until the item with the specified value is found
- Complexity: O(N)

Ordered (sorted) Singly Linked List

Operations:

// TBD

Circular Queue (Ring Buffer)

Priority Queue

- has front and rear and items are inserted in the rear and removed from the front
- items are ordered by key value, so that the item with the lowest key (or the highest key) is always at the front; items are inserted in the proper position to maintain the order

Deque

Deque is Double Ended Queue: items can be added/removed from the either end of the queue.

Operations:

Insertion to the front (push_front):

- Algorithm: item is added at the front of the queue
- Complexity: O(1)

Insertion to the back (push_back):

- Algorithm: item is added at the  back  of the queue
- Complexity: O(1)

Peek at the front:

- Algorithm: return a value of the item from the front of the queue
- Complexity: O(1)

Peek at the back:

- Algorithm: return a value of the item from the back of the queue
- Complexity: O(1)

Removal from the front (pop_front):

- Algorithm: remove the item from the front of the queue
- Complexity: O(1)

Removal from the end (pop_back):

- Algorithm: remove the item from the  back of the queue
- Complexity: O(1)

Queue

- FIFO concept - First In First Out
- opposite to arrays, only one item can be read or removed at a given time - the oldest item inserted
- its size is predefined: only limited number of items can be added (pushed)
- underlying data structure can be array, vector, linked list

Usage:
- e.g. when performing tasks is slower than the rate tasks are received we want to save tasks in the same order they are received and we want first to execute the oldest tasks: we will put them in the queue

Operations:

Insertion (enqueue):

- Algorithm: item is added at the end (rear) of the queue
- Complexity: O(1)

Peek:

- Algorithm: return a value of the item from the front of the queue (the oldest item in the queue)
- Complexity: O(1)

Removal (dequeue):

- Algorithm: remove the item from the front of the queue (the oldest item in the queue)
- Complexity: O(1)

Stack

- LIFO concept - Last In First Out
- opposite to arrays, only one item can be read or removed at a given time - the last item inserted
- its size is predefined: only limited number of items can be added (pushed)
- stack overflow occurs when a new item is being added but underlying buffer is full
- underlying data structure can be array, vector, linked list

Usage:
- to check whether parentheses ({ }), braces ([ ]) and brackets (( )) are balanced
- to parse arithmetic expressions
- in algorithms applied for other data structures (e.g. traversing binary trees)

Operations:

Insertion (push):

- Algorithm: item is added on the top of the stack
- Complexity: O(1)

Peek:

- Algorithm: return a value of the item from the top of the stack (item that has been added last)
- Complexity: O(1)

Removal:

- Algorithm: remove the item from the top of the stack (item that has been added last)
- Complexity: O(1)

Ordered (sorted) array

- data is ordered (sorted) in ascending (or descending) key order which enables fast search algorithm - binary search (this is the main reason why we want to keep data sorted)
- can be searched with linear search as well

Binary Search Algorithm

Take the idem from the middle of the range (array of sorted elements). If its value is smaller than the searched value then take right sub-array as a new range and repeat this step.

The range will eventually drop to only one member and if its value matches the searched one - item is found.

As in each new iteration range size is halved, the complexity of the algorithm is O(logN). If we double the number of elements, we would need only one extra iteration.

Operations

Insertion:

- Algorithm: linear search is needed to find the first element smaller than the one to be inserted; item is inserted after it and all bigger items are shifted one place towards the end

- Complexity: O(N) (linear search) + O(N) (shifting) = 2 * O(N) ~ O(N)

Search:

- Algorithm: binary search

- Complexity: O(logN) 

Deletion:

- Algorithm: binary search to find the element; once it's found it is removed and all subsequent elements are shifted towards the array beginning

- Complexity: O(logN)(binary search) + O(N) (shifting) ~ O(N)

Unordered (unsorted) array

Array:
-  is a collection of data items (its elements) of the same type arranged contiguously in memory
- can be sorted or unsorted
- can accept or not duplicate values

Array is created with predefined size =>
   - if there are less elements than the array size is => memory waste
   - if there are more elements that the array size is => program fails

Implementations:
- C-style array
- std::vector

Unordered arrays with no duplicates

Operations:

Insertion

- Algorithm: always at the end (at the first vacant position); it must be checked whether item already exists in the array - a search is performed
- Complexity: O(N) (because of the search)

Search for a given item (lookup)

- Algorithm: linear search - starts at the beginning and goes through all items till item is found
- Complexity: O(N)

Deletion of a given item

- Algorithm: item must be found first; once its found and removed, all subsequent elements must be shifted down one position (towards the beginning of the array) in order to fill the gap and maintain contiguity of elements in memory
- Complexity: O(N) for search + O(N) for shifting = 2 * O(N) ~ O(N)

Unordered arrays with duplicates

Operations:

Insertion

- Algorithm: always at the end (at the first vacant position)
- Complexity: O(1)

Search for a given item (lookup)

- Algorithm: linear search - starts at the beginning and goes through all items till item is found
- Complexity: O(N)

Deletion of a given item

- Algorithm: item must be found first; once its found and removed, all subsequent elements must be shifted down one position (towards the beginning of the array) in order to fill the gap and maintain contiguity of elements in memory
- Complexity: O(N) for search + O(N) for shifting = 2 * O(N) ~ O(N)