Java Plus DSA Sheet By Shashwat Tiwari

Main Topics Subtopics Details Video Links

Java Basics Programming Language and Memory Management [Link]
What is a programming Language
Machine Language
Assembly Language
High Level Language
Procedural Language
Functional Language
Object Oriented Language
Scripting Language
Stack Memory
Heap Memory
Garbage Collection
Flow of a program [Link]
Flowchart
Psuedocode
Algorithm
How Java Program Compiles [Link]
Byte code
Machine code
why java is platform independent
JDK, JRE, JVM, JIT
Writing your first program [Link]
installation of Java
installation of IDE
"Hello Coder"
entrypoint of program
commandline arguments
generating byte code in style
How computer runs your program?
writing comments in java
Java being Java [Link]
Variables and constants
Literals and keywords
data types
Program to swap two numbers
Type casting Implicit and explicit
Automatic type promotion
Wrapper class
ASCII Values
Unicode style
Inputs and Operators [Link]
Operators in java
How to take input
Organize your code [Link]
Java Packages
Access Specifiers
Control Statements [Link]
if-else
switch case
while loop
do-while Loop
for each loop
Functions in Java [Link]
Functions
Types of functions
create your own functions
call by value and call by reference

Mini Project -1 [Link]

Calculator Application
Temperature convertor

Maths in DSA Mathematics in DSA - Part 1 [Link]

Number system
Conversion from one system to other
Digit extraction
Reverse a Number.
Find even odd
Find Power of a number.
Fast exponentiation

Mathematics in DSA - Part 2 [Link]

count digits
count digits using log
using log formulas
Armstrong Number
Pallindrome Number
Print all divisors
Check if Number is Prime
Sieve Algorithm
Newton Raphson Algorithm for square root
Greatest Common Divisor
Euclidian GCD Algorithm
lcm of two numbers
Modular Arithmetics
fast exponentiation with modular arithmetics
factorial of a number
find trailing zeros in a factorial
ceiling and floor of a number

Bits Manipulation Bits and Binary Operations [Link]

Least Significant Bits
Most Significant Bits
Signed and unsigned Numbers
Calculate range of data type
How to add binary numbers
How to find 1's complement
How to find 2's complement
 Left shift and Right shift
Trick to divide or multiply any number.
Bitwise NOT, Bitwise AND, Bitwise OR

Play with Bits / Bit Manipulation [Link]

Find the i-th Bit
Set the i-th Bit
Toggle the i-th Bit
Unset the i-th Bit
Print the number in binary without conversion
Find if a number is even / odd using bit manipulation
Find if a number is power of 2.
Count the number of set bits.
Unset the right most set bit.

Bit Manipulation [Link]

Bitwise Operators
Bit Manipulation
Bit Masking
Advanced XoR problems of Bit Manipulation

Arrays Arrays in Java [Link]

what are arrays
concept of indexing
Insert, update, delete, traverse
How arrays work in memory
what is a sorted array
How to create a 2d array
Operations on functions
Jagged Array
passing arrays to functions

Searching Algorithms Searching Algorithms - 1 [Link]

Linear Search
Q. search an Element / first occurrence
Q. Find the minimum element in an array (1D/2D)
Q. Find the maximum element in an array (1D/2D)
Q. Find max sum 1D array in a 2D array
Q. Search all occurrences (1D/2D)
Q. Search last occurrence (1D/2D)

Searching Algorithms - 2 [Link]

Binary Search
Sorted in increasing
Sorted in decreasing
Order Agnostic Binary Search
Questions on Binary Search Part 1 [Link]
Q1. Ceiling of a Number
Q2. Floor of a Number
Q3. First and Last Position of element in sorted array
Q4. Count all occurrence of element in an array
Q5. Next smallest letter in sorted array
Questions on Binary Search Part 2 [Link]
Binary Search in range
Q6. Find Minimum Difference in a Sorted array.
Q7. Find an element in an array of Infinite size
Q8. Find first 1 in an infinite and sorted array of 0s and 1s
Questions on Binary Search Part 3 [Link]
Bitonic Array
Q9. Find pivot in bitonic array
Q10. search in bitonic array
Questions on Binary Search Part 4 [Link]
Sorted and Rotated Array (Clockwise and Anticlockwise)
Q11. count number of rotations
Q12. search in rotated sorted array ( with and without duplicates)
Q13 Find min / max (peak) element in rotated and sorted array
Questions on Binary Search Part 5 [Link]
Q14. Allocated minimum number of pages
Q15. Capacity to Ship within D Days

Q16. Koko Eating bananas [Link]

Q17. Smallest Divisor given a threshold [Link]
Q18. Minimize Maximum of products distributed to any store [Link]
Q19. Aggressive cows [Link]
Q20. Median of two sorted arrays [Link]
Q21. Kth element of two sorted arrays [Link]

Questions on Binary Search Part 6 [Link]

Q22. Single Element in a Sorted Array
Q23. Finding square root
Q24. Count Squares
Other Searching Algorithms [Link]
Jump Search
Interpolation Search
Exponential Search
Ternary Search

Q. Median of a Sorted Matrix [Link]

Q. Kth Smallest element of a Matrix [Link]

Matrix Questions on Matrix - 1 [Link]

Q. Search in a row wise and column wise sorted Matrix
Q. Search in a sorted matrix

Questions on Matrix - 2 [Link]

Q. Transpose a Matrix
Q. Rotate a Matrix by 90 degree clockwise
Q. Rotate a Matrix by 90 degree anticlockwise

Questions on Matrix - 3 [Link]

Q. Spiral Matrix - 1
Q. Spiral Matrix - 2
Time & Space Complexity Time and Space Complexity [Link]
What is Algorithm Complexity
Asymptotic Notations
Time Complexity
Space Complexity
Big Oh cheat sheet.
How to calculate time complexity
Algorithm optimizations

Sorting Algorithms Insertion Sort [Link]

Selection Sort [Uni and Bi - directional] [Link]
Bubble Sort and Brick Sort [Link]
Counting Sort [Link]
Radix Sort [Link]
Pigeonhole Sort [Link]
Cyclic Sort [Link]
Q. Find missing element in range of 0 to N [Link]
Q. Given an array [1 to N] return all elements in range [1 to N] that are absent in the array [Link]
Questions on Duplicate Numbers [Link]
Q. Find the duplicate Number in an array [1 to N] ( inclusive )
Q. Given an array [1 to N] with elements appearing once or twice, return all elements that appear twice
Q. Find the missing and repeating element in an array [1 to N] TBD
Q. Return the smallest positive number missing TBD

String Manipulation Strings in Java [Link]

characters
string literals
string constant pool
subsequences
substrings
String comparison
String with new operator
Reference Comparision

More on Strings [Link]

String Builder
String Buffer
Next vs NextLine
Taking string as a user input
compareTo function
trim function
split function
startsWith function
endsWith function
IndexOf function
lastIndexOf function
charAt function
toLowerCase function
toUpperCase function
toCharArray function

Playing with String [Link]

Input Buffer and delimeters
String formatting
String Concatination

Q. Print all substrings [Link]

Q. Reverse a string [Link]
Q. Check if a string is pallindrome [Link]
Q. Reverse words in a String [Link]
Q. Check if two strings are anagram [Link]
Q. Reverse Words in a String -iii [Link]

Stack Stack Data Structure [Link]

Stack
Stack using Arrays
Q. Check parenthesis [Link]
Q. Remove minimum brackets to balance string [Link]
Q. Add minimum brackets to balance string [Link]
Q. Swap minimum brackets to balance string [Link]
Q. Swap adjacent brackets to balance string [Link]
Q. Asteroid Collision [Link]
Q. Stock Span Problem [Link]
Q. Next Greater element [Link]
Q. Next Smaller element [Link]
Q. Next Greater / Smaller element in circular array [Link]
Q. Largest Rectangle in Histogram + Previous smaller element [Link]
Q. Max Rectangle [Link]
Q. Longest Valid Parentheses [Link]

Queue Queue Data Structure [Link]

Queue
Queue using Array
Circular Queue
Double ended Queue
Implement queue using stack [Link]
Implement stack using queue [Link]
Q. LRU Cache TBL
Q. LFU Cache TBL
Q. Rotten Oranges TBL
Q. Sliding Window Maximum TBL
Q. Find Maximum and Minimum of Every Window Size TBL

Object Oriented Programming Classes and Objects [Link]

Pillars of Oops [Link]
Inheritance [Link]
Important Keywords [Link]
Constructor Calling and Access Specifier [Link]
Getters and Setters [Link]
Function Overriding [Link]
Abstract Classes [Link]
 Java Interfaces [Link]
Nested Classes [Link]
Java Generics [Link]
Comparator and Comparable [Link]

Collections Framework Collections in One Shot Introduction [Link]

Need of Data Structure and Algorithms
Data and Object in real world
Need for a framework
What is collection framework?
Modules Vs Framework Vs Library Vs Package
How to Import Collections Framework
Hierarchy of Collections Framework - Interfaces & Classes
Functions in Collection Interface
Java Generics and AutoBoxing
List Interface
ArrayList & its functions
How to Iterate your List using Iterator
Internal Working of ArrayList
Sorting using Comparator
Sorting based on Custom Comparator
How to Iterate your List using ListIterator
Time Complexity of ArrayList
LinkedList & its functions
ArrayList VS LinkedList
Time Complexity of LinkedList
Vectors and their use
Stack & its functions
Time Complexity of Stack
Queue & its functions
Queue using LinkedList
Queue using ArrayDeque
Deque Interface using ArrayDeque & LinkedList
PriorityQueue Implementation of Queue
Map Interface
Hashing Concept
How Map uses Hashing Concept
HashMap & its functions
How to traverse a Map using Entry Interface
Map using LinkedHashMap
Map using TreeMap
BST
Self Balanced BST or Red-Black Tree
TreeMap & its functions
Set Interface
HashSet
How HashSet works Internally
LinkedHashSet
TreeSet

Two Pointers Q. Container with Most Water TBD

Q. Trapping Rainwater TBD
Q. Find Pair with a given sum in sorted Array TBD
Q. Remove Duplicates from Sorted Array TBD
Q. Maximum Consecutive ones TBD
Q. Reverse Pairs TBD
Q. The Celebrity Problem TBD

Recursion Recursion - I playing with function calls

Types of recursion
Q. convert decimal to binary
Q. reverse a number / string
Q. reverse an array inplace
Q. reverse a stack

Recursion - II Leap of Faith

Q. Tower of Hanoi
Q. Count ways in a Matrix

Time and Space Complexity Analysis Notations

Recurrence Relation
Trick

Backtracking and All it's variants Q. Rat in a Maze

Q. All permutations
Q. Pallindrome Partitioning
Q. Letter Combination of a Phone Number
Q. Print Subdequences of a String
Q. Subsequences with sum equal K

Backtracking with Pruning Q. Combination Sum - I

Q. Combination Sum - II
Q. Combination Sum - III
Q. Combination Sum - IV

More Questions on Backtracking Q. Number of islands

Q. Knights tour problem
Q. N Queens problem
Q. Suduko Solver

Q. Josephus problem - Kill in circle

Recursion - III Binary Search using recursion

Divide and Conquer Q. calculating power ( x^n)

 Q. Merge Sort
Q. Quick Sort
Q. Count Inversion
Strassen's Matrix Multiplication

Linked List Linked List Data Structure [Link]

Intro to linked list Data Structure
Types of linked list
All operations of Single linked list
Time Complexity
Applications of linked list
Implementation of linked list data structure

Doubly Linked List [Link]

Intro to Doubly linked list
All operations and their time complexity
Implementation of linked list

Q. Find Middle of Linked List (Hare Tortoise Algorithm) [Link]

Q. Delete Middle of Linked list [Link]
Q. Pairwise swap nodes of Linked List [Link]
Q. Add two numbers using Linked List [Link]
Q. Reverse the linked list (Iterative + Recursive) [Link]
Q. Palindrome linked list [Link]
Q. Detect Cycle in a linked list [Link]
Q. Segregate a linked list into odd and even list [Link]
Q. Reverse Nodes in K Group [Link]
Q. Remove Nth node from the end of linked list [Link]
Q. Sort a linked list of 0's, 1's and 2's [Link]
Q. Intersection of two Sorted linked list [Link]
Q. Intersection point of two linked list [Link]
Q. Insert in a sorted list [Link]
Q. Insertion Sort on Linked List [Link]
Q. Merge Sort on Linked List [Link]
Q. Split a circular linked list into two circular lists [Link]
Q. Clone a linked list with random and next pointer TBL

String Manipulation Q. Longest Pallindrome TBD

Q. Find all Anagrams TBD
Q. K-Anagrams TBD
Q. Roman to Integer TBD
Q. First Repeated word in a string TBD
Q. Isomorphic String checker TBD

Rabin Karp Algorithm TBD

KMP Algorithm TBD
LPS Algorithm TBD

Hashing Hashing [Link]

Components of Hashing
How hashing works?
Types of Hash Functions
Collisions
Collision Resolution Techniques - Separate chaining
Collision Resolution Techniques - Open Addressing
Load Factor
Rehashing
Applications and Advantages

Hashmap Data Structure [Link]

What is hashmap?
How to use custom key-value pair

Implement HashMap in Java [Link]

All Methods
Hashcode function
Rehashing

Q. Most frequent element in an array [Link]

Q. Check if an array is subset of another array [Link]
Q. Count Pairs with given sum [Link]

Hashset Data Structure [Link]

what is hashset data structure
Usage of map keys
Set Iterator

Q. Minimum number of subsets with distinct elements [Link]

Questions on K-SUM Subarray Pattern [Link]
Q. Check if subarray with K sum Exists or Not
Q. Find the starting and ending index of K sum subarray
Q. Find the maximum length subarray with K sum
Q. Find the minimum length subarray with K sum Homework
Q. Count the total subarrays with sum K
Q. Find largest subarray with 0 sum Homework

Q. Longest subarray with sum divisible by K [Link]

Q. Longest increasing concecutive subsequence [Link]
Q. Count distinct elements in every window of size K TBD
Q. Largest subarray with equal number of 0s and 1s [Link]
Q. Find pairs with given sum such that elements of pair are in different rows TBD
Bucket Sort Algorithm [Link]

Sliding Window Sliding Window Technique [Link]

Q. Maximum Sum Subarray of Size K [Link]
Q. First Negative Number in Each Subarray of Size K [Link]
Q. Chocolate Distribution Problem [Link]
 Q. Smallest subarray with sum greater than x [Link]
Q. Longest Substring with K unique Elements [Link]
Q. Longest Substring without repeating elements [Link]
Q. Count Occurances of Anagrams [Link]
Q. Minimum Window Substring [Link]
Q. Sliding Window Maximum [Link]

Trees Linear and Non Linear Data Structures [Link]

Linear Data Structure
Non Linear Data Structure

Intro to Tree Data Structure [Link]

What is a tree Data Structure.
Types of trees.
Binary Trees.
N-ary Trees.
Ternary Trees.
Non Linear Data Strcuture.
Hierarical Data Structure.
Properties of a Tree Data Structure.
Neighbour in Tree.
Siblings in Tree.
Cousin in Tree.
Depth of a Tree.
1Height of a Tree.
Child of a node in tree.
Parent of a node in tree.

Tree Traversal BFS [Link]

BFS on N-Ary Trees [Link]
Tree Traversal DFS - Recursive [Link]
Preorder Iterative [Link]
Inorder Iterative [Link]
Postorder Iterative [Link]
Q. Construct tree using inorder and postorder. [Link]
Q. Maximum Depth of Binary Tree [Link]
Q. Maximum Depth of N-Ary Tree [Link]
Q. Diameter of Binary Tree Q. Size of Binary Tree [Link]
Q. Diameter of N-ary Tree [Link]
Q. Count number of node in compete Binary Tree [Link]
Q. Left and Right View of Binary Tree [Link]
Q. Top and Bottom View of Binary Tree [Link]
Q. Vertical Order Traversal of Binary Tree [Link]
Q. Boundary Traversal of Binary Tree [Link]
Q. ZigZag Level Order Traversal of Binary Tree [Link]
Q. Balanced Binary Tree [Link]
Q. Lowest Common Ancestor of Binary Tree (LCA) [Link]
Introduction to Binary Search Tree [Link]
Delete a Node in BST [Link]
Q. Validate BST [Link]
Q. Two Sum in BST [Link]
Q. Kth Smallest Element in BST [Link]
Q. LCA in BST [Link]
Q. Burn a Tree TBD
Q. BT to DLL TBD
Q. Floor and Ceil in BST TBD
Q. Search in BST TBD
Q. Binary Search Tree Iterator [Link]
Q. Maximum Sum BST in Binary Tree [Link]

Flood fill algorithm in BT TBD

Segment tree TBD
Range query TBD
Red Black Tree TBD

AVL Tree [Link]

1. AVL Trees
2. Balanced Trees
3. Insert in AVL Tree
4. Delete in AVL Tree
5. Balance factor of AVL Tree
6. AVL Tree rotations
7. LL
8. RR
9. LR
10. RL

TreeMap Collections [Link]

Heap & Priority Queue Heap [Link]

1. Heaps
2. Heapify
3. Heapsort
4. Min Heap
5. Max Heap
6. Increase Key
7. Decrease Key
8. Insert in Heap
9. Delete from Heap
10. build heap from array
11. Complete Tree

Priority Queue in one shot [Link]

1. Priority Queue in Java collections
2. Priority Queue on custom classes.
3. [Link]()
4. dsa playlist
5. Equate objects in pq

Q. Top K Frequent Elements [Link]

Q. Sort Characters by frequency [Link]
 Q. IPO [Link]
Q. Design Twitter [Link]
Q. Task Scheduler [Link]
Q. Connect N ropes with Minimum cost TBD
Q. Medium of Running Streams of Integers TBD
Q. Maximum Sum Combination TBD
Q. Merge K sorted Elements TBD

Tries Trie Introduction to Trie

Implement a Trie in java
Insert, Search and delete operations

Questions on TRIE Q. Longest String with All prefixes

Q. Number of Distinct substrings in string
Q. Power Set
Q. Maximum XoR of two Numbers in an Array

Graphs Graph Introduction [Link]

1. Introduction to graphs
2. Directed Graph
3. UnDirected Graph
4. Weighted Graph
5. UnWeighted Graph
6. Vertex and Edges
7. Degree of a node in graph
8. In-degree and Out-degree in graphs

Graph Representation & Application [Link]

1. How to represent graph in memory
2. InDegree of directed graph
3. outDegree of directed graph
4. Adjacency List
5. Adjacency Matrix
6. Degree of a graph
7. Represent Directed graph with weight
8. Represent UnDirected graph with weight

Q. Find the center of star graph [Link]

Q. Maximum Total Importance of Roads [Link]

Connected Components and Path [Link]

1. How to traverse multiple components in a graph
2. TreeTraversal vs Graph Traversal
3. Path in a graph
4. Cycle in a graph
5. Directed Acyclic Graph (DAG)
7. Find if a path is valid or not
DFS Traversal in Graph [Link]
BFS Traversal in Graph [Link]
Q. Flood fill using BFS [Link]
Q. Number of Islands [Link]
Q. Word Ladder -1 [Link]
Q. Word Ladder -2 [Link]
Q. Evaluate Division [Link]
Q. Get Watched Videos by your friends [Link]
Q. Rotting Oranges | Multisource BFS [Link]
Q. Minimum Time to Collect All Apples in a Tree [Link]
Q. Most Stones Removed with Same Row or Column [Link]
Q. Accounts Merge [Link]
cycle detection in undirected graph using BFS [Link]
cycle detection in undirected graph using DFS [Link]
Cycle Detection In Directed Graphs using DFS [Link]
Kahn's Algorithm for Toposort [Link]
Toposort using DFS [Link]
Cycle Detection in directed graph using toposort [Link]
When to apply BFS | Shortest Path using BFS [Link]
Dijkstra Algorithm | Shortest Path [Link]
Floyd Warshall Algorithm | Shortest Path [Link]
Bellmanford Algorithm | Shortest Path [Link]
Q. Network Delay Time [Link]
Q. Cheapest Flights Within K Stops [Link]
Q. Minimum Cost to Convert String I [Link]
Disjoint Sets in one shot [Link]
Q. Redundant Connection [Link]
Q. Satisfiability of Equality Equations [Link]
Q. Number of Operations to Make Network Connected [Link]
Q. Is Graph Bipartite? [Link]
Strongly Connected Components | Kosaraju's Algorithm TBD
Minimum spanning tree [Link]
Prim's Algorithm for minimum spanning tree [Link]
Kruskal's Algorithm for minimum spanning tree [Link]

Greedy Algorithms Greedy Algorithm Introduction TBD

Q. Activity Selection Problem TBD
Q. Eqyption Fraction TBD
Q. Job Sequencing Problem TBD
Q. Policemen Catches Thieves TBD
Q. Assign mice to Holes TBD
Q. Minimum swaps for bracket balancing TBD
Q. Minimum number of Platforms for Railway station TBD
Q. Minimum number of Coins - greedy TBD
Q. Fractional Knapsack - greedy TBD
Q. Text Justification TBD

Dynamic Programming (DP) Dynamic Programming Introduction TBD

Overlapping Subproblems
Optimal Substructures
Q. Coin Change Problem TBD
Q. 0-1 Knapsack Problem TBD
Q. Longest Increasing Subsequence TBD
 Q. Pallindromic Partitioning TBD

Kadanes Algorithm TBD

Q. Maximum Sum Subarray TBD
Q. Maximum Product Subarray TBD
Q. Maximum Sum Rectangle TBD
Q. Edit Distance TBD
Q. Rod Cutting Problem TBD
Q. Word Break Problem TBD

Q. Longest Common Subsequence TBD

Q. Variants of LCS TBD

Multi Threading Java Multithreading and Concurrancy - I TBD

Java Multithreading and Concurrancy - II TBD

Bonus Catalan Number TBD

Permutation and combinations
Trending leetcode contest questions.
All Important pattern printing
Observation and tricks