SDE GRAPH is BIPARRIATE GRPAH

 class Solution {

  public:

    bool DFS(int node,int cc,vector<vector<int>>&adj,vector<int>&color,vector<bool>&visited)

    {

        visited[node]=1;

        for(int x:adj[node]){

            if(color[x]==cc)return false;

        }

        color[node]=cc;

        int nextc=0;

        if(!cc)nextc=1;

        for(int x:adj[node]){

            if(!visited[x])if(!DFS(x,nextc,adj,color,visited))return false;

        }

        return true;

    }

    bool isBipartite(int V, vector<vector<int>> &edges) {

        // Code here

        vector<vector<int>>adj(V);

        for(auto e:edges){

            adj[e[0]].push_back(e[1]);

            adj[e[1]].push_back(e[0]);

        }

        vector<int>color(V,-1);

        vector<bool>visited(V,false);

        return DFS(0,0,adj,color,visited);

    }

};

SDE GRAPH NO of Islands

 class Solution {

public:

void DFS(int r,int c,vector<vector<char>>&grid,int n,int m,vector<vector<int>>&visited,int color){

int rn[]={0,0,1,-1};

int cn[]={-1,1,0,0};

visited[r][c]=color;

for(int i=0;i<4;i++){

int rnxt=r+rn[i];

int cnxt=c+cn[i];

if(rnxt>=0&&rnxt<n&&cnxt>=0&&cnxt<m)if(!visited[rnxt][cnxt]&&grid[rnxt][cnxt]=='1')DFS(rnxt,cnxt,grid,n,m,visited,color);

//if(cnxt>=0&&cnxt<m)if(!visited[rnxt][cnxt])DFS(rnxt,cnxt,grid,n,m,visited);

}

}

int numIslands(vector<vector<char>>& grid) {

int n=grid.size();

int m=grid[0].size();

vector<vector<int>>visited(n,vector<int>(m,0));

int color=1;

for(int i=0;i<n;i++){

for(int j=0;j<grid[i].size();j++){

if(!visited[i][j]&&grid[i][j]=='1'){

DFS(i,j,grid,n,m,visited,color);

color++;

}

}

}

return color-1;

}

};

SDE GRPAH course schedule

 kanh's algo og topological sort

O(V+E) time Complexity

class Solution { public: vector<int> toposort(vector<vector<int>>&adj,int V){ vector<int>count(V,0); queue<int>q; vector<int>visited; for(int i=0;i<V;i++){ for(int x:adj[i]){ count[x]++; } } for(int i=0;i<V;i++){ if(count[i]==0) q.push(i); } while(!q.empty()){ int x=q.front(); q.pop(); visited.push_back(x); for(int y:adj[x]){ count[y]--; if(count[y]==0)q.push(y); } } return visited; } bool canFinish(int numCourses, vector<vector<int>>& prerequisites) { vector<vector<int>> adj(numCourses); for(auto& e : prerequisites){ adj[e[1]].push_back(e[0]); } vector<int>ans=toposort(adj,numCourses); if(ans.size()==numCourses)return true; return false; } };

my modifie dversion

O(V*V) time complexity

class Solution {

public:

bool canFinish(int n, vector<vector<int>>& prerequisites) {

vector<vector<int>>adj(n);

for(auto e:prerequisites){

adj[e[1]].push_back(e[0]);

}

vector<int>incount(n,0);

for(int i=0;i<n;i++){

for(int x:adj[i])incount[x]++;

}

int n_p_nodes=0;

while(n_p_nodes<=n){

vector<int>toprocess;

for(int i=0;i<n;i++){

if(incount[i]==0){

toprocess.push_back(i);

incount[i]=-1;

}

}

if(toprocess.size()<1)break;

n_p_nodes+=toprocess.size();

for(int x:toprocess){

for(int y:adj[x]){

incount[y]--;

}

}

}

if(n_p_nodes==n)return true;

else return false;

}

};

SDE RECURSION Combination Sum

 class Solution {

public:

void Sum(int idx,int rsum,vector<int>arr,vector<int>temp,vector<vector<int>>&ans){

if(idx<0)return;

if(rsum==0){

ans.push_back(temp);

return;

}

if(rsum<0)return;

vector<int>new_temp=temp;

new_temp.push_back(arr[idx]);

Sum(idx,rsum-arr[idx],arr,new_temp,ans);

Sum(idx-1,rsum,arr,temp,ans);

}

vector<vector<int>> combinationSum(vector<int>& candidates, int target) {

vector<vector<int>>ans;

vector<int>temp;

Sum(candidates.size()-1,target,candidates,temp,ans);

return ans;

}

};

recursion prpblem 1 sde sheet (Subset sum)

 class Solution {

  public:

  

    bool Sum(int rsum,vector<int>&arr,int idx,vector<vector<int>>&dp){

        if(rsum==0)return true;

        if(rsum<0)return false;

        if(idx==0)return(arr[idx]==rsum);

        if(dp[idx][rsum]!=-1)return dp[idx][rsum];

        

        

        bool ans1=Sum(rsum-arr[idx],arr,idx-1,dp);

        if(ans1)return dp[idx][rsum]=ans1;

        bool ans2=Sum(rsum,arr,idx-1,dp);

        return dp[idx][rsum]=ans2;

    }

    bool isSubsetSum(vector<int>& arr, int sum) {

        // code here

        int n=arr.size();

        vector<vector<bool>>dp(n,vector<bool>(sum+1,false));

        //return Sum(sum,arr,arr.size()-1,dp);

        for(int i=0;i<n;i++)dp[i][0]=true;

        if(arr[0]<sum)dp[0][arr[0]]=true;

        for(int i=1;i<n;i++){

            for(int j=1;j<=sum;j++){

                if(j<arr[i])dp[i][j]=dp[i-1][j];

                else dp[i][j]=dp[i-1][j-arr[i]]||dp[i-1][j];

            }

        }

        return dp[n-1][sum];

    }

};

N_QUEEN(BACKTRACKING)

N_QUEEN SOLN(MY WRITTEN BAD SOLn i t hink) 

#include<bits/stdc++.h>

using namespace std;

bool isSafe(int row,int idx,vector<vector<int>>&checksafe){

    if(checksafe[row][idx]==0)return true;

    else return false;

}

void makeUnSafe(int row,int idx,vector<vector<int >>&checksafe){

    int n=checksafe.size();

    for(int i=0;i<n;i++)checksafe[row][i]++;

    for(int i=0;i<n;i++)checksafe[i][idx]++;

    checksafe[row][idx]--;

    int r1=row+1,r2=row-1,r3=row-1,r4=row+1;

    int i1=idx+1,i2=idx-1,i3=idx+1,i4=idx-1;

    while(r1<n&&i1<n){

        checksafe[r1++][i1++]++;

    }

    while(r2>=0&&i2>=0){

        checksafe[r2--][i2--]++;

    }

    while(r3>=0&&i3<n){

        checksafe[r3--][i2++]++;

    }

    while(r4<n&&i4>=0){

        checksafe[r4++][i4--]++;

    }

}

void makeSafe(int row,int idx,vector<vector<int>>&checksafe){

    int n=checksafe.size();

    for(int i=0;i<n;i++)checksafe[row][i]--;

    for(int i=0;i<n;i++)checksafe[i][idx]--;

    checksafe[row][idx]++;

    int r1=row+1,r2=row-1,r3=row-1,r4=row+1;

    int i1=idx+1,i2=idx-1,i3=idx+1,i4=idx-1;

    while(r1<n&&i1<n){

        checksafe[r1++][i1++]--;

    }

    while(r2>=0&&i2>=0){

        checksafe[r2--][i2--]--;

    }

    while(r3>=0&&i3<n){

        checksafe[r3--][i2++]--;

    }

    while(r4<n&&i4>=0){

        checksafe[r4++][i4--]--;

    }

}

void printboard(vector<vector<int>>&board){

    for(int i=0;i<board.size();i++){

        for(int j=0;j<board.size();j++){

            cout<<board[i][j]<<" ";

        }

        cout<<endl;

    }

}

void N_queen(int row,vector<vector<int>>&board,vector<vector<int>>&checksafe){

    if(row==board.size()){

                printboard(board);

                cout<<"----------------"<<endl;

                return;

    }

    for(int i=0;i<board.size();i++){

        

        if(isSafe(row,i,checksafe)){

            board[row][i]=1;

            makeUnSafe(row,i,checksafe);

            N_queen(row+1,board,checksafe);

            makeSafe(row,i,checksafe);

            board[row][i]=0;

            

        }

    }

}

int main(){

    int n=4;

    vector<vector<int>>board(n,vector<int>(n,0));

    vector<vector<int>>checksafe(n,vector<int>(n,0));

    N_queen(0,board,checksafe);

}

OPTIMAL_APPRAOCH(CHECK IN O(1) TIME)

#include<bits/stdc++.h>

using namespace std;

bool isSafe(int row,int col,vector<bool>&checkcol,vector<bool>&checkleft,vector<bool>&checkright){

    int n=checkcol.size()-1;

    if(checkcol[col]||checkleft[row+col]||checkright[col-row+n])return false;

    return true;

}

void makeUnsafe(int row,int col,vector<bool>&checkcol,vector<bool>&checkleft,vector<bool>&checkright){

    int n=checkcol.size()-1;

    checkcol[col]=1;

    checkleft[row+col]=1;

    checkright[col-row+n]=1;

}

void makeSafe(int row,int col,vector<bool>&checkcol,vector<bool>&checkleft,vector<bool>&checkright){

    int n=checkcol.size()-1;

    checkcol[col]=0;

    checkleft[row+col]=0;

    checkright[col-row+n]=0;

}

void printboard(vector<vector<int>>&board){

    for(int i=0;i<board.size();i++){

        for(int j=0;j<board.size();j++){

            cout<<board[i][j]<<" ";

        }

        cout<<endl;

    }

    cout<<"--------------------------------------------"<<endl;

}

void N_QUEEN(int row,vector<vector<int>>&board,vector<bool>&checkcol,vector<bool>&checkleft,vector<bool>&checkright){

    if(row==board.size()){

        printboard(board);

        return;

    }

    for(int i=0;i<board.size();i++){

        if(isSafe(row,i,checkcol,checkleft,checkright)){

            board[row][i]=1;

            makeUnsafe(row,i,checkcol,checkleft,checkright);

            N_QUEEN(row+1,board,checkcol,checkleft,checkright);

            makeSafe(row,i,checkcol,checkleft,checkright);

            board[row][i]=0;

        }

    }

}

int main(){

    int n=4;

    int k=2*n-1;

    vector<vector<int>>board(n,vector<int>(n,0));

    vector<bool>checkcol(n,0),checkright(k,0),checkleft(k,0);

    N_QUEEN(0,board,checkcol,checkleft,checkright);

}

For Infosys

To be eligible, start your learning journey in your selected technology area and complete all recommended courses in the corresponding learning path on or before May 5, 2026. For instance, if you've opted for Artificial Intelligence, proceed with the courses outlined in the 'Artificial Intelligence' Learning Path.

 supervised machine learning:

    is a function maps input variable to output variable: f(x1,x2, ....,xn)=>f(y)

    here we have lebeled data and output

    two types:

     regression and clasification 

    regression does predict discrete values where classification does make classes

Concepts to Remember

23/3/26

  1)If in any problem we are given to try all combinations :

    the go to solution is recursion/backtracking (like-  target-sum problem,0/1 knapsnack,        0/1 unbounded knapsnack),

    we optimize the recursion time complecity then by applying dynamic programming            aprroach

    EXAMPLE WITH A PRBLEM:

  

     

   suppose along the exmaple the rid is size 8,

   SEE IN the Question we can either cut the rod into the n(8)size and take the price,

    we can also do cut into n-1(7) size and 1size and can take both profits , or can cut 1sizes     of n(8) times gives us n pices we can also do that , can also do 4,3,1 or 4,4 or 4,2,1,1 

by for loop we cant decide the size of poitners, we use recursion here and dp 

and solutin becomes:

// User function Template for C++

class Solution {

  public:

    int MaxPrice(int cs,int rsize,vector<int>&price,vector<vector<int>>&dp){

        if(rsize==0)return 0;

        if(cs==0)return 0;

        if(dp[cs][rsize]!=-1)return dp[cs][rsize];

        int nt=MaxPrice(cs-1,rsize,price,dp);

        int take=0;

        if(cs<=rsize){

            take=price[cs]+MaxPrice(cs,rsize-cs,price,dp);

        }

        return dp[cs][rsize]=max(nt,take);

    }

    int cutRod(vector<int> &price) {

        // code here

        

        

        int n=price.size();

        vector<int>pr(n+1);

        for(int i=1;i<n+1;i++){

            pr[i]=price[i-1];

        }

        vector<vector<int>>dp(n+1,vector<int>(n+1,-1));

        return MaxPrice(n,n,pr,dp);

    }

};

Syatem design things to study

 

 

Concurrent IO – Main Summary

These sections explain how a server handles many clients at the same time.

There are three main approaches:

Method	Idea	Scalability
Thread per connection	One thread handles one client	Low
Process per connection	One process handles one client	Low
Event loop	One thread handles many sockets	High

Modern systems like Redis, Nginx, and Node.js use event loops.

---

5.1 Thread-based Concurrency

Idea

Each client connection runs in a separate thread.

Flow:

Server
  |
accept connection
  |
create new thread
  |
thread handles requests

Pseudo idea:

accept()
create thread
thread:
    read request
    process
    write response

Problems

1. High memory usage

Each thread has a stack.

Example:

10,000 clients
→ 10,000 threads
→ huge memory

---

2. CPU overhead

Creating/destroying threads costs:

• CPU

• latency

Especially when connections are short-lived.

---

3. Processes are even heavier

Old servers used:

fork()

One process per client → even slower.

---

5.2 Event-based Concurrency

Instead of many threads, use one thread + event loop.

Important concept:

Sockets have kernel buffers.

Incoming packets:

network
   ↓
kernel TCP stack
   ↓
socket read buffer

When program calls:

read()

It copies data from this buffer.

---

Event Loop Idea

Instead of waiting for one socket:

wait for ANY socket to be ready

Pseudo structure:

while running:
    wait until some sockets are ready

    read from ready sockets
    write to ready sockets

This is called an event loop.

---

3 OS mechanisms required

1️⃣ Readiness notification

Wait until socket is ready.

Examples:

poll()
epoll()
select()

---

2️⃣ Non-blocking read

Read data without waiting.

read()

returns immediately.

---

3️⃣ Non-blocking write

Write data without waiting.

write()

returns immediately.

---

5.3 Non-blocking IO

Normal IO = blocking.

Example:

read(fd)

If no data:

thread waits

---

Non-blocking IO:

read(fd)

If no data:

errno = EAGAIN

Meaning:

try again later

---

Write behavior

If buffer full:

write()

returns:

EAGAIN

or performs partial write.

---

Non-blocking accept

accept() removes connections from a kernel queue.

If queue empty:

accept()
→ EAGAIN

---

Enabling non-blocking mode

Sockets are blocking by default.

Enable using:

fcntl(fd, F_GETFL)
fcntl(fd, F_SETFL)

Add flag:

O_NONBLOCK

---

5.4 Readiness APIs

Servers need to know which socket is ready.

General idea:

wait_for_readiness()

Linux provides several APIs.

---

1. poll()

Simple API.

Structure:

struct pollfd {
    fd
    events
    revents
}

Meaning:

Field	Meaning
events	what we want
revents	what happened

Example flags:

POLLIN  → ready to read
POLLOUT → ready to write

---

2. select()

Old API.

Problem:

max 1024 sockets

So it should not be used in modern servers.

---

3. epoll

Linux high-performance API.

Difference:

poll → pass fd list every time
epoll → fd list stored in kernel

So it scales better.

Used by:

• Redis

• Nginx

---

4. kqueue

Used on:

• BSD

• macOS

Similar to epoll.

---

Readiness APIs Cannot Be Used With Files

They work only for:

sockets
pipes
special kernel objects

Not for disk files.

Reason:

Socket:

kernel buffer exists

So kernel knows if data is available.

File:

data must be read from disk

So readiness cannot be predicted.

---

Solution for file IO

Servers use:

thread pool

Example:

event loop thread
     |
send file read task
     |
worker thread reads file

---

New Linux solution

Linux introduced:

io_uring

Features:

async file IO
async socket IO
high performance

But it is more complex.

---

5.5 Final Comparison

Type	Method	API	Scalability
Socket	Thread per connection	pthread	Low
Socket	Process per connection	fork()	Low
Socket	Event loop	poll / epoll	High
File IO	Thread pool	pthread	Medium
Any IO	Event loop	io_uring	High

BINARY SEARCH IN A 2D MATRIX(accePted 100%tc)

 

class Solution {

public:

bool searchMatrix(vector<vector<int>>& mat, int target) {

int n=mat.size();

int m=mat[0].size();

int start=0;

int end=(n*m)-1;

while(start<=end){

int mid=(start+end)/2;

int row=(mid/m);

int col=mid%m;

if(mat[row][col]==target){

return true;

}

if(mat[row][col]<target){

start=mid+1;

}else end=mid-1;

}

return false;

}

};

Transpose of a matrix and rotate te array in 90 degree clockwise

 class Solution {

public:

void rotate(vector<vector<int>>& matrix) {

int n=matrix.size();

int m=matrix[0].size();

for(int i=0;i<n;i++){

for(int j=0;j<m;j++){

if(i>j){

swap(matrix[i][j],matrix[j][i]);

}

}

}

for(int i=0;i<n;i++){

reverse(matrix[i].begin(),matrix[i].end());

}

}

};