#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
struct Cell {
    int r, c;
};
int n, m;
vector<vector<int>> dist;
vector<string> grid;
vector<pair<int, int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
void bfsFromObstacles() {
    queue<Cell> q;
    dist = vector<vector<int>>(n, vector<int>(m, 1e9));

    for (int r = 0; r < n; r++) {
        for (int c = 0; c < m; c++) {
            if (grid[r][c] == '*') {
                q.push({r, c});
                dist[r][c] = 0; 
            }
        }
    }

    while (!q.empty()) {
        Cell cur = q.front();
        q.pop();
        
        for (auto dir : directions) {
            int nr = cur.r + dir.first;
            int nc = cur.c + dir.second;
            if (nr >= 0 && nr < n && nc >= 0 && nc < m && dist[nr][nc] > dist[cur.r][cur.c] + 1) {
                dist[nr][nc] = dist[cur.r][cur.c] + 1;
                q.push({nr, nc});
            }
        }
    }
}

bool canReachWithMinDist(int mid, Cell start, Cell end) {
    if (dist[start.r][start.c] < mid) return false;

    queue<Cell> q;
    vector<vector<bool>> visited(n, vector<bool>(m, false));
    q.push(start);
    visited[start.r][start.c] = true;

    while (!q.empty()) {
        Cell cur = q.front();
        q.pop();

        if (cur.r == end.r && cur.c == end.c) return true; 

        for (auto dir : directions) {
            int nr = cur.r + dir.first;
            int nc = cur.c + dir.second;

            if (nr >= 0 && nr < n && nc >= 0 && nc < m && !visited[nr][nc] && dist[nr][nc] >= mid) {
                visited[nr][nc] = true;
                q.push({nr, nc});
            }
        }
    }

    return false;
}

int findMaximumDistance(vector<string>& gridInput) {
    grid = gridInput;
    n = grid.size();
    m = grid[0].size();
    
    Cell start, end;
    
    for (int r = 0; r < n; r++) {
        for (int c = 0; c < m; c++) {
            if (grid[r][c] == 'S') {
                start = {r, c};
            }
            if (grid[r][c] == 'E') {
                end = {r, c};
            }
        }
    }

    bfsFromObstacles();

    int lo = 0, hi = n + m, ans = 0;

    while (lo <= hi) {
        int mid = (lo + hi) / 2;

        if (canReachWithMinDist(mid, start, end)) {
            ans = mid; 
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }

    return ans;
}

Ebullient ✅
Maximum Distance

def bfs_from_obstacles(g, n, m):
    d = [[-1] * m for _ in range(n)]
    q = [(i, j) for i in range(n) for j in range(m) if g[i][j] == '*']
    for x, y in q: d[x][y] = 0

    dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    while q:
        x, y = q.pop(0)
        for dx, dy in dirs:
            nx, ny = x + dx, y + dy
            if 0 <= nx < n and 0 <= ny < m and d[nx][ny] == -1 and g[nx][ny] != '*':
                d[nx][ny] = d[x][y] + 1
                q.append((nx, ny))

    return d

def bfs_find_max_dist(g, n, m, d):
    s = e = None
    for i in range(n):
        for j in range(m):
            if g[i][j] == 'S': s = (i, j)
            elif g[i][j] == 'E': e = (i, j)

    if s is None or e is None: return 0

    dist_from_S = [[-1] * m for _ in range(n)]
    dist_from_S[s[0]][s[1]] = d[s[0]][s[1]]
    q = [(s[0], s[1], d[s[0]][s[1]])]

    max_min_dist = 0
    while q:
        x, y, min_dist = q.pop(0)
        if (x, y) == e:
            max_min_dist = max(max_min_dist, min_dist)
            continue
        for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            nx, ny = x + dx, y + dy
            if 0 <= nx < n and 0 <= ny < m and g[nx][ny] != '*':
                new_min_dist = min(min_dist, d[nx][ny])
                if dist_from_S[nx][ny] == -1:
                    dist_from_S[nx][ny] = new_min_dist
                    q.append((nx, ny, new_min_dist))

    return max_min_dist

def findMaximumDistance(grid):
    n, m = len(grid), len(grid[0])
    dist_to_obstacles = bfs_from_obstacles(grid, n, m)
    return bfs_find_max_dist(grid, n, m, dist_to_obstacles)

Ebullient ✅
Maximum Distance

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

class Solution {
public:
    vector<vector<long long>> dp;  

    long long solve(int node, int parent, int fact, vector<vector<int>>& adj, int k, vector<int>& coins) {
        if (dp[node][fact] != -1) 
            return dp[node][fact];
        
        long long currValue = coins[node] / pow(2, fact); 
        long long ansHalf = currValue / 2;                  
        long long ansFull = currValue - k;                   
        
        for (int child : adj[node]) {
            if (child != parent) {
                ansHalf += solve(child, node, fact >= 15 ? fact : fact + 1, adj, k, coins);
                ansFull += solve(child, node, fact, adj, k, coins);
            }
        }
        
        return dp[node][fact] = max(ansHalf, ansFull);
    }

    long long treePoints(int g_nodes, vector<int> g_from, vector<int> g_to, vector<int> A, int K) {
        vector<vector<int>> adj(g_nodes); 
        for (size_t i = 0; i < g_from.size(); ++i) {
            adj[g_from[i]].push_back(g_to[i]);
            adj[g_to[i]].push_back(g_from[i]);
        }

        dp = vector<vector<long long>>(g_nodes, vector<long long>(16, -1)); 
        return solve(0, -1, 0, adj, K, A);
    }
};

Tree Value ✅

HPE ✅

#include <iostream>
#include <vector>
#include <set>
#include <cmath>
#include <algorithm>
using namespace std;
vector<int> findPrimes(int limit) {
    vector<int> primes;
    vector<bool> sieve(limit + 1, true);
    sieve[0] = sieve[1] = false;

    for (int num = 2; num <= limit; ++num) {
        if (sieve[num]) {
            primes.push_back(num);
            for (int multiple = num * num; multiple <= limit; multiple += num) {
                sieve[multiple] = false;
            }
        }
    }

    return primes;
}

int dfs(int node, vector<vector<int>>& graph, vector<bool>& visited) {
    visited[node] = true;
    int size = 1;

    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) {
            size += dfs(neighbor, graph, visited);
        }
    }

    return size;
}

int main() {
    int N, M;
    cin >> N >> M;

    vector<vector<int>> graph(N + 1);
    for (int i = 0; i < M; ++i) {
        int U, V;
        cin >> U >> V;
        graph[U].push_back(V);
        graph[V].push_back(U);
    }

    vector<bool> visited(N + 1, false);
    int maxLandmarks = 0;
    for (int i = 1; i <= N; ++i) {
        if (!visited[i]) {
            int size = dfs(i, graph, visited);
            maxLandmarks = max(maxLandmarks, size);
        }
    }
    vector<int> primes = findPrimes(1000);  
    int ticketPrice = primes[maxLandmarks - 1];  

    cout << maxLandmarks << " " << ticketPrice << endl;

    return 0;
}

HP(Intern)✅

#include <iostream>
#include <string>
using namespace std;

string decodeWord(const string& word) {
    string decoded = word;
    int length = word.length();
        for (int i = 0; i < length - 1; i += 2) {
        swap(decoded[i], decoded[i + 1]); 
    }
    
    return decoded;
}

int main() {
    string word;
    getline(cin, word);
    
    string decodedWord = decodeWord(word); 
    
    cout << decodedWord << endl;
    
    return 0;
}

HP(Intern)✅

📌Atlan Is Hiring
Software Engineer - Intern

Remote Opportunity
Internship Duration: 6-month paid, full-time, remote internship.

- Applications Open: 4th October 2024.
- Applications Close: 7th October 2024.

💻 Apply: https://jobs.lever.co/atlan/258b1aad-cef9-4f89-8c66-3aac988de02c

private static long[] miniCost(int[] red, int[] blue, long blueCost) {
    int n = red.length;

    long[][] dp = new long[n + 1][2];
    dp[0][0] = 0; 
    dp[0][1] = blueCost; 
    
    long[] ans = new long[n + 1]; 

    for (int i = 1; i <= n; i++) {
        dp[i][0] = Math.min(dp[i - 1][0] + red[i - 1], dp[i - 1][1] + red[i - 1]);
        dp[i][1] = Math.min(dp[i - 1][1] + blue[i - 1], dp[i - 1][0] + blue[i - 1] + blueCost);
                ans[i] = Math.min(dp[i][0], dp[i][1]);
    }

    return ans; 
}

Visiting Cities
Patym ✅

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int maxTransactions(vector<int>& transactions) {
    priority_queue<int, vector<int>, greater<int>> minHeap;
    
    long long sum = 0;
    int count = 0;     
    for (int i = 0; i < transactions.size(); i++) {
        sum += transactions[i]; 
        minHeap.push(transactions[i]); 
        if (sum < 0) {
            int smallest = minHeap.top(); 
            sum -= smallest; 
            minHeap.pop();     
        } else {
            count++;
        }
    }
    
    return count;
}

Bank Transactions ✅
Patym

Capgemini Interview Experience

Self intro
Project explanation
More than five questions from project
What is SQL
Oops concepts fully explain
Data types
Local variable and global variable
Class and objective in python
Explain full join statement in SQL with example
How you take data of the student from student table based on some condition
How to convert string to integer
About python
Union and union all
What is your role in project
How did you clear error in your project
Difficulties in your project
What is your strength and weakness
How will you overcome your weakness
After five years in which technology you want to see your self
As a team leader what are the challenges you faced in your project
Suppose you are working in team facing challenges there is you have to alot work to some people will not aware of that work how will you handle this situation
Duration 30 minutes

Capgemini Interview Experience

introduce yourself
what subjects you love
what is java
dbms
view
some more sql question
how you distribute task to project members
any question

Capgemini Interview Experience

Self intro
What is oracle SQL (because I mentioned)
Project explanation
Difference between DBMS and RDBMS
Fragmentation in SQL
What is tickets ( I mentioned in my project)
Why you choose capgemini
Do you have any questions to ask
I replied yes then I asked what you think about capgemini for freshers
Then he asked are you comfortable with night shift and relocate to chennai or Bangalore

#include <vector>
#include <algorithm>
#include <iostream>
#include <climits>
using namespace std;
vector<int> solution(vector<vector<int>> m) {
    int r = m.size();
    int c = m[0].size();
    int resR = -1, resC = -1;
    long long minDiff = LLONG_MAX;
    for (int a = 0; a < r - 1; a++) { 
        for (int b = 0; b < c - 1; b++) {
            long long s1 = 0, n1 = 0; 
            long long s2 = 0, n2 = 0;
            long long s3 = 0, n3 = 0; 
            long long s4 = 0, n4 = 0; 
            for (int i = 0; i <= a; i++) {
                for (int j = 0; j <= b; j++) {
                    if (m[i][j] >= 0) {
                        s1 += m[i][j];
                        n1++;
                    }
                }
            }
            for (int i = 0; i <= a; i++) {
                for (int j = b + 1; j < c; j++) {
                    if (m[i][j] >= 0) {
                        s2 += m[i][j];
                        n2++;
                    }
                }
            }
            for (int i = a + 1; i < r; i++) {
                for (int j = 0; j <= b; j++) {
                    if (m[i][j] >= 0) {
                        s3 += m[i][j];
                        n3++;
                    }
                }
            }
            for (int i = a + 1; i < r; i++) {
                for (int j = b + 1; j < c; j++) {
                    if (m[i][j] >= 0) {
                        s4 += m[i][j];
                        n4++;
                    }
                }
            }
            long long avg1 = n1 > 0 ? s1 / n1 : 0;
            long long avg2 = n2 > 0 ? s2 / n2 : 0;
            long long avg3 = n3 > 0 ? s3 / n3 : 0;
            long long avg4 = n4 > 0 ? s4 / n4 : 0;
            vector<long long> avgs = {avg1, avg2, avg3, avg4};
            long long maxAvg = *max_element(avgs.begin(), avgs.end());
            long long minAvg = *min_element(avgs.begin(), avgs.end());
            long long diff = maxAvg - minAvg;
            if (diff < minDiff || (diff == minDiff && (a < resR || (a == resR && b < resC)))) {
                minDiff = diff;
                resR = a;
                resC = b;
            }
        }
    }
    return {resR, resC};
} 

Visa ✅