Cheatography
https://cheatography.com
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 combination of numbers, letters, symbols). |
Linked List |
A Linked List is a user-defined 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 hierarchic. The tree data structure collects the nodes together to depict and stimulate the sequence. Tree data structure does not store the data sequentially. 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 sequentially arranged. |
|
|
Algorithm
Recursion |
While technically 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 implemented using loops, they tend to be more readable. |
Sorting and searching |
Sorting and searching are two fundamental operations that are performed on most data structures. 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 |
|
Created By
Metadata
Comments
No comments yet. Add yours below!
Add a Comment
Related Cheat Sheets
More Cheat Sheets by nirintsoa