resume build at - overleaf website (faang overleaf template)

important blogs -- https://codeforces.com/blog/entry/91363

window-sliding playlist https://www.youtube.com/playlist?
list=PLWcWFcYIVmitXTbQg0TAeCsrEkOjvnVJZ

graph sheet
https://docs.google.com/spreadsheets/d/1GsGN5VbQcEEpDGW1SYgGKgpqV1tbLLwMz4cMo-
cpMfs/edit#gid=0
Trees sheet
https://docs.google.com/spreadsheets/d/
1aXh_ZVkI79_orja9RakwmfQMMSLHi3w6veQ2EjREDg8/edit#gid=0
DP sheet
https://docs.google.com/spreadsheets/d/
1vO1RyO0O0lZoSiI8Ib3QrDovCDdGMq_CmJJ_rhDsTp4/edit#gid=0

cses website
codeforces

TREES

dfs
bfs
zig zag traversal
diameter of a binary tree
path sum
maximum path sum
left-view
right-view
symmetric tree
print nodes in top view(gfg)
bottom view
vertical order traversal(****)
boundary traversal of a binary tree(very good ques)
all nodes at a distance k in a binary tree(***)
burn a binary tree
sum root to leaf numbers
lowest common ancestor(interview common question)
smallest subtree with all the deepest nodes
maximum width of a binary tree
second minimum node in a binary tree
Path Sum III
Path Sum II
Flatten Binary Tree to Linked List
Populating Next Right Pointers in Each Node
Sum of Left Leaves
Binary Tree Pruning

BINARY SEARCH TREE

search in bst
insert in bst
validate the bst
Insert into a Binary Search Tree
Construct Binary Tree from Inorder and Preorder Traversal{while doing this using
PreIndex,map should be passed by Reference}
Construct Binary Tree from Inorder and Postorder Traversal{while doing this using
PostIndex,map should be passed by Reference}
kth smallest element in a BST
minimum distance between BST Nodes
Construct Binary Search Tree from Preorder Traversal
Convert Sorted List to Binary Search Tree(***)
lowest common ancestor of BST
Maximum Sum BST in Binary Tree(********)
AVL Trees(ek baar dekh lena)

GREEDY

highest power(interview bit)

maxmimum cost of ropes
last stone weight
fractional knapsack(**standard)
reduce array size into half
Maximum Ice Cream Bars
Maximum Score From Removing Stones
Best Time to Buy and Sell Stock II using greedy
Increasing Triplet Subsequence
Gas Station(****)
jump game

sort mostly asked algos

quick sort
questions with counting sort
merge sort

HEAP

find kth smallest element

is binary tree heap
Merge k Sorted Arrays
Find median in a stream(gfg)
Find Median from Data Stream(leetcode)
Distant Barcodes

DP

fibonacci number -- simply apply dp from i=2

tribonacci number -- simply apply dp from i=3
climbing stairs -- same as fibonacci series
house robber -- use pick, notPick and get max out of them
house robber II -- use pick, notPick but 2 times , 1st from i=0 to n-2 and 2nd from
i=1 to n-1 then get max of them

unique paths -- travserse from bottom, go top or left and add top+left with i,j
reaching 1 return 1 i,j<0 return 9
unique paths II -- same as unique but to handle obsacle (i>=0 && j>=0 && v[i]
[j]==1) this is obstacle, return 0
Minimum Path Sum -- same as unique path, top,left get min(top,left)+v[i][j]
triangle(****) -- since its not sq two index Rin,in , bottom, bottomRight-
(Rin+1,in),(Rin+1,in+1) get min_v[Rin][in]
minimum falling path sum(**)--apply for loop, since we are supposed to check all
possibilites in row, inside for loop apply recursion (topLeft,top,topRight) get min
Subset Sum Problem -- start from end if sum==0&&n==0 true, else false, now
pick(sum-arr[n-1],n-1) only if sum>=arr[n-1] else notPick(sum,n-1), return pick or
notPick
0-1 knapsack -- same as subset problem excepet values are given here
coin change II(solve this -- recursion) -- here same as subset but since mutiple
picking of coins is allowed we remain pick at (amount-coin[n-1],n) return
pick+notPick
write in notes and do dry run
coin change -- same as coin change II we just want number of possibilties everytime
we pick just add 1 to it
minimum sum partition -- first find totalsum of arr, at index==n return (abs(sum-
(Totalsum-sum))), everytime we pick add arr[index] to our sum

Longest common subsequence -- if s1[x-1]==s2[y-1]) return 1+(x-1,y-1) else return

max of (x-1,y),(x,y-1)
Longest Palindromic Subsequence --- LPS=reverse string s and give it name string t
and apply LCS
Delete Operation for Two Strings -- apply lcs and return n+m-2*lcs
Minimum Insertion Steps to Make a String Palindrome -- reverse string and copy to
new, apply lcs on both, get lcs, return n-lcs
Longest Common Substring(*****) -- bit diff to LCS, we check all possibilties hence
if (s1[x-1]==s2[y-1]) p=1+(x-1,y-1) store max(p), else p=0, and check (x-1,y),(x,y-
1), return p
Distinct Subsequences(*****) -- since s1 will have duplicate char check
possibilities if (s1[x-1]==s2[y-1]) return (x-1,y-1)+(x-1,y) else return (x-1,y)
Edit Distance(*****) -- this goes like (s1[x-1]==s2[y-1]) then we call for (x-1,y-
1) and explore all operations
for detete 1+(x-1,y),insert 1+(x,y-1),replace 1+(x-1,y-1)
get min of them
Printing Longest Common Subsequence(article read) -- apply lcs outside use while
loop to print if (s1[x-1]==s2[y-1]){x--,y--,res+=string} else if(s1[x-1]>s2[y-1])
{x--} else {y--}
Shortest Common Supersequence(*****) --same apply lcs, use while loop and above
while loop conditions but for every condition in if,else loop add char to res,
since total length it req

Longest Palindromic Substring -- (diff type of dp, do it tabulation dont try memo)
--- cant solve by reversing and lcs =, to solve this use all 1 length are
palindrome then check from length k=2ton then inside i=0ton-k(no.of strings with
length k) check if
s[i][j]==1 && dp[i+1][j-1]==1||k==2 thats a valid k length palindrome store length
and start index, here end index j=i+k-1, ans then lastly print use seaparet loop
Palindromic Substrings -- (same as above) just want total no. of palindrome if the
condition satisfies simply res++, initially res=n as 1 length are palindrome

Wildcard Matching (***)-- look notes :(

Regular Expression Matching (*****) -- look notes :(
Minimum Cost For Tickets -- we got three options, for day 1 simply call next index,
but for day 7,30 we need to initialse a variable that goes till days[i]<days[index]
+7,30 hence get
min out of those three options

Best Time to Buy and Sell Stock II(****) - if buy==1 we got pick,notPick if we pick
that mean reduce from amount, -v[i]+Solve(i+1,1-buy), when sold pick=v[i]
+Solve(i+1,1-buy) get max
Best Time to Buy and Sell Stock with Transaction Fee -- since fee is applied after
selling we got to reduce after sold in sold cond v[i]+Solve(i+1,1-buy)-fee , return
max
Best Time to Buy and Sell Stock III -- since 2 transactions everytime we sell -v[i]
+Solve(i+1,count-1,1-buy) and base cond if count reaches 0 return 0;
Best Time to Buy and Sell Stock IV -- since k transactions everytime we sell -v[i]
+Solve(i+1,k-1,1-buy) and base cond if k reaches 0 return 0;
Best Time to Buy and Sell Stock with Cooldown Period -- after sold we have to
cooldown for a day so -v[i]+Solve(i+2,1-buy) with i+2 it exceeds n so base
condition index>=n

Maximal Square -- get max of 1+min(dp[i-1][j],dp[i-1][j-1],dp[i][j-1])

Longest Increasing Subsequence(*****) bhot ganda hai dekhlo saare approaches --

simply maintain prevIn and index if nums[index]>nums[prevIn] update
index=index+1,prevIn=index, return max
also look at binary search approach,
lower_bound
Number of Longest Increasing Subsequence(******)--
Largest Divisible Subset -- look notes (we need to store (1,i) in dp for each indec
then backtrack accoring to the last divisibility index)
Russian Doll Envelopes(do this) -- same as LIS in binary search approach look at
comp func a bit difference, we are finding larger v[i][1]th index then lower_bound
to get smaller values
[Number of Longest Increasing Subsequence
gfg (LIS variations)
maximum deletions to make array sorted
maximum sum increasing subsequence -- simply keep adding the arr[i] to the sum
everytime LIS condition satisifies
maximum length bitonic subsequence -- just finding LIS in both orders and finding
max of dp1[i]+dp2[i]-1 ;
building bridges --
the longest chain

Matrix Chain Multiplication(*****) -- for(int k=start; k<end; k++) -- here we call

for arr[start-1]*arr[end]*arr[k] + rec(start,k) + rec(k+1,end) and get min
Burst Balloons -- same as MCM here
Palindrome Partitioning -- for a loop from j=index to n, check for added string if
palindrome then call for next partition and popback if rec call done (backtrack)
Palindromic Partitioning II -- same goes like above but here we need to optimise
isPalindrome function using map
MCM based to-do questions
Maximal Rectangle
Boolean Parenthesization
Minimum Cost to Cut a Stick

GRAPH
remember to use extra loop if the graph goes like connected components

problems to solve on leetcode and algorithms

https://leetcode.com/discuss/interview-question/3365918/graphs-all-algorithms-
theroy-and-implementation
https://leetcode.com/discuss/study-guide/1326900/graph-algorithms-problems-to-
practice
https://leetcode.com/discuss/general-discussion/655708/graph-for-beginners-
problems-pattern-sample-solutions/

dfs on graph --keep track of visited array and if node is not visited then we call
for dfs for the node untill all visited array ele go true
bfs on graph -- we use queue intially push 0 then using while(!q.empty()) we keep
checking visited array if not visited mark visited then push to queue
Detect cycle in an undirected graph-- same as dfs with extra condition else if (x!
=parent)
Is Graph Bipartite? -- same dfs/bfs with extra condition we alternatively assign
value 1/0 to the nodes and if already visited node get same color as earlier then
not a bipartitie
Detect cycle in an directed graph --visited,dfsvisited when already visited node
goes 1 in dfsVisited then there's a cycle, and everytime we backtrack
dfsVisited[node]=0

grid problems----
Number of Provinces -- for the extra loop we use just increment a variable there
ans++;
Number of Islands -- assuming the grid is surrounding the water,solve dfs in all
four direction with base condition isSafe function and increment ans in extra for
loop we use
Surrounded regions -- here we cant assume to be surrounded in water instead we
traverse in all edges to find O and mark them 1 with their consecutive O's then at
last traversing the
whole gird mark 1's as O ans O's as X, done
Rotting Oranges(***) -- find all rotten oranges push them to queuu<pair> with (i,j)
use while loop inside run a loop c=q.size times
to traverse queue and tranverse a node in all four directions to find new row and
column
check for isSafe func and if safe mark grid[i][j] as 2 ans push to queue
evnentually the no of times while loop runs is the ans
Number of Distinct Islands(not done in class)

Topological Sort -- using stack-dfs -- simply traverse dfs if not visited and keep
push to stack after all calls then separately pop from the stack to print
using Kahn's ALgorithm -- find indegree, push indegree=0 nodes in queue and
traverse through the node and decrement the indgree[node]-- if it goes to 0 push to
queue untill empty then
return res vector where we pushed our node
Course Schedule -- same as kahn's algo just change in making adj list
Course Schedule II -- same as kahn's algo just change in making adj list

shortest path algo-----------weighted graph

Implementing Dijkstra Algorithm -- maintain dist array with all INF, maintain pq
pair(distance,node) for getting min and in while loop for adj[node] check
if(dist[adjNode]>currDist+wt)
if true update dist[adjNode] and push to pq.
Network Delay Time -- same as dijstras algo we just need to make sure if every node
is being directed or not
Path with Maximum Probability - using max pq and condition of multipilcation here
prob[prevNode]*currProb>prob[currNode]
Cheapest Flights Within K Stops(****) -- here k stops is considerd hence dist
vector will have both dist and k, and vector of min pq, now puch dist,sec,k to the
pq and check the condition
of dijstras to update the value also before updating make sure to decrease value of
k by in 1
Shortest Path In A Grid With Obstacle Elimination(****) -- since k is to be looked
at and grid indexes we use dist vectoc<vector<vector>>> since distance is 1 we just
use vector of q also
going in all four direction so moves vector with isSafe func where we also check
for k if k goes 0 false else decrement k and proceed for further operation
condition goes same like in
dijstras if(dist[newRow][newCol][currK]>dist[row][col][prevK]+1) update then return
dist when newRow==n-1&&newColumn==m-1
Shortest path in Undirected Graph having unit distance-- this is simple like prev
since unit dist use queue
Path with Minimum Effort--almost same as grid obstacle but here we get to look at
max absolute of height in consecutive cells with isSafe fun and update

Bellman-Ford Algorithm-- Negative weight cycle--run n-1 times then we get accurate
result in negative weights too

Minimum Spanning Tree-- can be solved using Prim's and Kruskal's algo

Prim's Algorithm -- parent,key,MSTInclude using min pq with pair of(wt,node) if

key[adjNode]>wt we update
DSU(disjoint set union)-***** used in Kruskals -- rank,findParent,setUnion
Number of Provinces -- using DSU
Kruskal's Algorithm -- initialise parent[i]=i, then update accordingly for ultimate
parent, also in getParent we use path compression, edges array {wt,u,v}, sort
if(parU==parV)-continue

based on DSU-Kruskal's Algorithm

Satisfiability of Equality Equations -- same findParent,setUnion here we need to
connect nodes for all '=' second char then check for '!' remaining if parU==parV -
false
Redundant Connection -- same when parV==parU return that array
Min Cost to Connect All Points-- same like kruskals code here we need to update
edges vector<vector<>> as {abs(xpoints)+abs(Ypoints),i,j} sort, add wt to the ans
Count Unreachable Pairs of Nodes in an Undirected Graph-- set union to all nodes
find their parent and count res as count*(n-count) their sum for each ultimate
parent

Maximum Total Importance of Roads-- easier will get tricked thinking of graph
approach instead use simple maths, find degree of each node both ways and the
importance value to it would be
currVal*degree[i] hence use this to get the ans
Minimum Number of Vertices to Reach All Nodes -- this ones simple too just mark
visited to the x[1] in given array and using another loop traverse visited, the not
visited ones push to the
res array, simply indegree

All Paths From Source to Target(*********) check this basic backtracking--

backtracking,dfs,graph use v<v>> res, v<> temp if node goes n-1 then push temp to
res then pop_back to backtrack
Pacific Atlantic Water Flow(OA)-- traverse from the outer row and columns and check
for the node using dfs in all 4 direc, find the node that is visited both from
pacific and atlantic side
Find the City With the Smallest Number of Neighbors at a Threshold Distance -- same
dijtras algorithm
As Far from Land as Possible-- same as dijtras algorithm instead we need to
traverse in all four directions
All Ancestors of a Node in a Directed Acyclic Graph--

Tree-graph hard problems

Sum of Distances in Tree(**)