DS Flashcards
(16 cards)
bubble sort
https://www.youtube.com/shorts/y2AghjB4Wxs
Selection sort
https://www.youtube.com/shorts/HRwi5gwlB0U
insertion sort
https://www.youtube.com/shorts/ZZ-Oz1IFfPg
Quick sort
https://www.youtube.com/shorts/MeBYqiehwyQ
System vs User defined datatypes
system -
all primitive types
Collection - List Set Map
class - Scanner, Random, LocalDate
String
Arrays
user -
1. Class
2. Interfaces
3. Enum
4. Records
5. Custom Wrapper Classes
Primitive vs non primitive
Primitive :
byte, short, int, long
float, double
char
boolean
Non-Primitive:
Strings
Arrays
Classes
Interface
Enum
Collection - List Set Map
Linear vs non linear
Linear
linked list
stack queue
Non linear
tree
graph
queue
Abstract data type
List, Stack, Queue, Dequeue, Priority Queue, Set, Map
Big-O
Big-O Name Example Algorithm
O(1) Constant Accessing an array element (arr[i])
O(log n) Logarithmic Binary Search
O(n) Linear Linear Search
O(n log n) Linearithmic Merge Sort, Quick Sort (average case)
O(n²) Quadratic Bubble Sort, Insertion Sort
O(2ⁿ) Exponential Recursion in Fibonacci (naive)
O(n!) Factorial Traveling Salesman Problem (TSP)
Notation for time complexity
omega - best case
Big O - worst case
Hash
hash function changes a key to an integer and helps in storing values
if more than one value falls in same key, it is stored as link list
Operation Average Case Worst Case
Insertion O(1) O(n) (all values in one bucket)
Search O(1) O(n) (in case of many collisions)
Deletion O(1) O(n)
to get ascii value in js
“ABC”.charCodeAt(0)
StringBuilder
mutable
allocates dynamic data space and multi thread allowed
StringBuffer
same as StringBuilder but only one thread is allowed
Java default queue syntax
Queue<Integer> q = new LinkedList<>();</Integer>
greedy algorithm
A greedy algorithm is a problem-solving approach that makes the optimal choice at each step with the hope of finding the global optimum. It selects the best option available at the moment without considering the broader consequences of that choice.
