Cheatography

# Programming Interview Live Coding Cheat Sheet by nirintsoa

Practice your live coding skills focusing on one out of the following list of data structures and algorithms per round

### Data Structures

 Array An array is a data structure that collects elements of the same data type and stores them in contiguous memory locations. String A string (or string literal) is an array of characters (i.e. any combin­ation of numbers, letters, symbols). Linked List A Linked List is a user-d­efined data structure that consists of nodes that point to either in one direction (singly Linked List) or both directions (doubly Linked List).

### Linear Data Structures

 Stack The linear data structure stores the data elements in the LIFO or the ‘last-in/ first out’ order. Queue The queue is a linear data structure that follows the FIFO order. FIFO stands for First In and First Out. Linked List The last node of a data structure will be linked to the first node of the next data structure.

### Non-Linear Data Structures

 Tree Tree data structures are hierar­chic. The tree data structure collects the nodes together to depict and stimulate the sequence. Tree data structure does not store the data sequen­tially. It stores the data on multiple levels. Graph In Graph Data Structure, one node is simply connected to the other node through the edge of the graph. The Graph Data Structure obviously uses Non-linear data structures which are not sequen­tially arranged.

### Algorithm

 Recursion While techni­cally not an algorithm, recursion is an algorithm technique used to help break down an algorithm into a base case and recursive cases. While these algorithms can also be implem­ented using loops, they tend to be more readable. Sorting and searching Sorting and searching are two fundam­ental operations that are performed on most data struct­ures. Sorting serves to order elements in a particular way, while searching deals with finding the desired element in a particular data structure.

### Sorting Algorithms

 Algorithm Time complexity Space complexity Selection sort O(n²) O(1) Insertion sort O(n²) O(1) Counting sort O(n + k) O(k) Quicksort O(nlogn) O(logn) Mergesort O(nlogn) O(n)

### Searching Algorithms

 Algorithm Time complexity Space complexity Linear Search O(n) O(1) Binary Search O(logn) O(1) iterative- O(logn) recursive AVL Binary Search Tree O(logn) O(n) BFS and DFS O(V + E), where V is the number of vertices and E is the number of edges O(V)

### Stack Methods

 push Adds a new element at the top of the stack pop Removes an element at the top of the stack

### Queue Methods

 insert Inserts an element at the end of the queue delete Removes an element at the top of the queue toa Gets the time required to retrieve an element in the queue

### Binary Tree in Array (1-based)

 Item Index root 1 left child 2n right child 2n+1 parent n/2

### Binary Tree in Array (0-based)

 Item Index root 0 left child 2r+1 right child 2r+2 parent (r-1)/2