from collections import defaultdict, Counter

def count_good_edges(n, k, values, edges):
    tree = defaultdict(list)
    for u, v in edges:
        tree[u].append(v)
        tree[v].append(u)
   
    subtree_freq = [Counter() for _ in range(n + 1)]
   
    def dfs(node, parent):
        subtree_freq[node][values[node-1]] += 1
        for neighbor in tree[node]:
            if neighbor != parent:
                dfs(neighbor, node)
                for val, count in subtree_freq[neighbor].items():
                    subtree_freq[node][val] += count
   
    dfs(1, -1)
   
    good_edges_count = 0
   
    for u, v in edges:
        if subtree_freq[v][values[v-1]] > subtree_freq[u][values[u-1]]:
            u, v = v, u
        subtree_values = subtree_freq[v]
        other_subtree_values = subtree_freq[1] - subtree_values
       
        if all(count <= k for count in subtree_values.values()) and all(count <= k for count in other_subtree_values.values()):
            good_edges_count += 1
   
    return good_edges_count

Adobe ✅

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
class Solution {
public:
    int countGoodEdge(int n, int k, vector<int>& values, vector<vector<int>>& edges) {
        vector<vector<int>> adj(n + 1);
        for (auto& edge : edges) {
            adj[edge[0]].push_back(edge[1]);
            adj[edge[1]].push_back(edge[0]);
        }
       
        vector<unordered_map<int, int>> subtreeFreq(n + 1);
        unordered_map<int, int> totalFreq;
        dfs1(1, -1, values, adj, subtreeFreq, totalFreq);
        int goodEdges = 0;
        dfs2(1, -1, values, adj, subtreeFreq, totalFreq, k, goodEdges);
       
        return goodEdges;
    }

private:
    void dfs1(int node, int parent, vector<int>& values, vector<vector<int>>& adj,
              vector<unordered_map<int, int>>& subtreeFreq, unordered_map<int, int>& totalFreq) {
        subtreeFreq[node][values[node - 1]]++;
        totalFreq[values[node - 1]]++;

        for (int neighbor : adj[node]) {
            if (neighbor != parent) {
                dfs1(neighbor, node, values, adj, subtreeFreq, totalFreq);
                for (auto& kv : subtreeFreq[neighbor]) {
                    subtreeFreq[node][kv.first] += kv.second;
                }
            }
        }
    }

    void dfs2(int node, int parent, vector<int>& values, vector<vector<int>>& adj,
              vector<unordered_map<int, int>>& subtreeFreq, unordered_map<int, int>& totalFreq,
              int k, int& goodEdges) {
        for (int neighbor : adj[node]) {
            if (neighbor != parent) {
                bool isGood = true;
               
                for (auto& kv : subtreeFreq[neighbor]) {
                    if (kv.second > k) {
                        isGood = false;
                        break;
                    }
                }
                for (auto& kv : totalFreq) {
                    if (kv.second - subtreeFreq[neighbor][kv.first] > k) {
                        isGood = false;
                        break;
                    }
                }
               
                if (isGood) {
                    goodEdges++;
                }
               
                dfs2(neighbor, node, values, adj, subtreeFreq, totalFreq, k, goodEdges);
            }
        }
    }
};

Count Good Edge ✅
Adobe

what your opinion guys 😂

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
class Solution {
public:
int getMinWeight(int u, int v, const vector<int>& weight, const vector<vector<int>>& adj) {
        if (u == v) return weight[u];
        vector<bool> visited(adj.size(), false);
        vector<int> minWeight(adj.size(), INT_MAX);
        queue<int> q;
       
        q.push(u);
        visited[u] = true;
        minWeight[u] = weight[u];

        while (!q.empty()) {
            int node = q.front();
            q.pop();

            for (int neighbor : adj[node]) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    minWeight[neighbor] = min(minWeight[node], weight[neighbor]);
                    q.push(neighbor);

                    if (neighbor == v) {
                        return minWeight[v];
                    }
                }
            }
        }

        return -1;
    }

    long long goodSubarrays(int n, int x, const vector<int>& weight, const vector<vector<int>>& edges) {
        vector<vector<int>> adj(n);
        for (const auto& edge : edges) {
            int u = edge[0];
            int v = edge[1];
            adj[u].push_back(v);
            adj[v].push_back(u);
        }

        long long totalSum = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                totalSum += getMinWeight(i, j, weight, adj);
            }
        }

        return totalSum;
    }
}; 

// MINIMUM SUM
Adobe ✅

#define ll long long

ll f(vector<int> &a, int n, int x){
    map<ll, ll> mp;
    ll ans = 0, i = 0, j = -1, cur = 0;
    while(i < n){
        while(j + 1 < n && (cur < x || (cur == x && mp[a[j + 1]] != 2))){
            mp[a[++j]]++;
            if(mp[a[j]] == 3) cur++;
        }
        ans += (j - i + 1);

        if(i <= j){
            if(mp[a[i]] == 3) cur--;
            mp[a[i++]]--;
        }else i++, j++;
    }
    return ans;
}
long long goodsub(int n, int x, vector<int> arr){
    return f(arr, n, x) - f(arr, n, x - 1);
}

Good Subarray
Adobe ✅

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

using namespace std;

const int MAXN = 1000;
const int LOG = 20;

vector<int> graph[MAXN];
vector<int> euler, depth, first_occurrence;
vector<vector<int>> min_weight;
int node_weight[MAXN];
int parent[MAXN];
int n;

void dfs(int v, int p, int d) {
    parent[v] = p;
    first_occurrence[v] = euler.size();
    euler.push_back(v);
    depth.push_back(d);
   
    for (int u : graph[v]) {
        if (u != p) {
            dfs(u, v, d + 1);
            euler.push_back(v);
            depth.push_back(d);
        }
    }
}

void build_rmq() {
    int m = euler.size();
    min_weight.assign(m, vector<int>(LOG, -1));

    for (int i = 0; i < m; ++i) {
        min_weight[i][0] = euler[i];
    }

    for (int j = 1; (1 << j) <= m; ++j) {
        for (int i = 0; (i + (1 << j) - 1) < m; ++i) {
            int left = min_weight[i][j - 1];
            int right = min_weight[i + (1 << (j - 1))][j - 1];
            min_weight[i][j] = (depth[first_occurrence[left]] < depth[first_occurrence[right]]) ? left : right;
        }
    }
}

int query_rmq(int l, int r) {
    int j = log2(r - l + 1);
    int left = min_weight[l][j];
    int right = min_weight[r - (1 << j) + 1][j];
    return (depth[first_occurrence[left]] < depth[first_occurrence[right]]) ? left : right;
}

int get_lca(int u, int v) {
    int left = first_occurrence[u];
    int right = first_occurrence[v];
    if (left > right) swap(left, right);
    return query_rmq(left, right);
}

int get_min_weight(int u, int v) {
    int lca = get_lca(u, v);
    int min_w = node_weight[lca];
    int current = u;

    while (current != lca) {
        min_w = min(min_w, node_weight[current]);
        current = parent[current];
    }

    current = v;
    while (current != lca) {
        min_w = min(min_w, node_weight[current]);
        current = parent[current];
    }

    return min_w;
}

int sum_of_min_weights() {
    int total_sum = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            total_sum += get_min_weight(i, j);
        }
    }
    return total_sum;
}

int main() {
    n = 5;
    vector<pair<int, int>> edges = {{0, 1}, {1, 2}, {0, 4}, {2, 3}};
    vector<int> input_weights = {6, 1, 2, 5, 3};

    for (int i = 0; i < n; ++i) {
        node_weight[i] = input_weights[i];
    }

    for (const auto& edge : edges) {
        graph[edge.first].push_back(edge.second);
        graph[edge.second].push_back(edge.first);
    }

    first_occurrence.resize(n);
    depth.reserve(2 * n);
    euler.reserve(2 * n);

    dfs(0, -1, 0);
    build_rmq();

    cout << "Sum of minimum weights: " << sum_of_min_weights() << endl;

    return 0;
}

Minimum Sum ✅
Adobe

Happy Weekend 😂🙈

Affected by Blue 🔵 Screen Error?
Due to the CrowdStrike Update 💀

public static int minTimeToSolvePuzzles(int n, int[] time, int[] search, int k) {
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;

        for (int i = 1; i <= n; i++) {
            dp[i] = dp[i - 1] + time[i - 1];
           
            for (int j = 1; j <= k && i - j >= 0; j++) {
                dp[i] = Math.min(dp[i], dp[i - j] + search[i - j]);
            }
        }
       
        return dp[n];
    }

Minimum Time ✅

void dfs(int node, int parent, const vector<vector<int>>& adj, vector<int>& subtree_sum, vector<bool>& visited) {
    visited[node] = true;
    subtree_sum[node] = node + 1;

    for (int neighbor : adj[node]) {
        if (neighbor != parent && !visited[neighbor]) {
            dfs(neighbor, node, adj, subtree_sum, visited);
            subtree_sum[node] += subtree_sum[neighbor];
        }
    }
}

int minimumDifference(int n, const vector<int>& A, const vector<int>& B) {
    vector<vector<int>> adj(n);
    for (int i = 0; i < n - 1; ++i) {
        adj[A[i] - 1].push_back(B[i] - 1);
        adj[B[i] - 1].push_back(A[i] - 1);
    }

    vector<int> subtree_sum(n, 0);
    vector<bool> visited(n, false);


    dfs(0, -1, adj, subtree_sum, visited);

    int total_sum = n * (n + 1) / 2;
    int min_diff = total_sum;

  removing each edge
    for (int i = 1; i < n; ++i) {
        int sum1 = subtree_sum[i];
        int sum2 = total_sum - sum1;
        int diff = abs(sum1 - sum2);
        min_diff = min(min_diff, diff);
    }

    return min_diff;
}

Split it up ✅

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
#include <tuple>

using namespace std;

// Directions for moving in the grid
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};

int getMaxDistance(int w, int h, const vector<pair<int, int>>& buildings) {
    vector<vector<int>> grid(h, vector<int>(w, INT_MAX));
    queue<tuple<int, int, int>> q;

    for (const auto& building : buildings) {
        int x = building.first, y = building.second;
        grid[y][x] = 0;
        q.push({x, y, 0});
    }

    while (!q.empty()) {
        auto [x, y, d] = q.front();
        q.pop();
        for (int i = 0; i < 4; ++i) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 0 && nx < w && ny >= 0 && ny < h && grid[ny][nx] > d + 1) {
                grid[ny][nx] = d + 1;
                q.push({nx, ny, d + 1});
            }
        }
    }

    int maxDistance = 0;
    for (const auto& row : grid) {
        for (int distance : row) {
            maxDistance = max(maxDistance, distance);
        }
    }

    return maxDistance;
}

int optimalBuildingPlacement(int w, int h, int n) {
    vector<pair<int, int>> allPositions;
    for (int x = 0; x < w; ++x) {
        for (int y = 0; y < h; ++y) {
            allPositions.emplace_back(x, y);
        }
    }

    int minMaxDistance = INT_MAX;
    vector<pair<int, int>> combination;
    vector<bool> v(allPositions.size(), false);
    fill(v.begin(), v.begin() + n, true);

    do {
        combination.clear();
        for (size_t i = 0; i < allPositions.size(); ++i) {
            if (v[i]) {
                combination.push_back(allPositions[i]);
            }
        }
        int maxDistance = getMaxDistance(w, h, combination);
        minMaxDistance = min(minMaxDistance, maxDistance);
    } while (prev_permutation(v.begin(), v.end()));

    return minMaxDistance;
}

Build offices ✅

import math
from collections import Counter
def solve(n, chars):
    if n == 1:
        return 1
    ans = Counter(chars)
    a = [freq for freq in ans.values() if freq > 0]
    if len(a) == 1:
        return a[0]
    sum_gcd = 0
    len_freqs = len(a)
    for i in range(len_freqs):
        for j in range(i + 1, len_freqs):
            sum_gcd += math.gcd(a[i], a[j])
    return sum_gcd

Phone pe ✅

def ok(n, arr):
    acha = sum(arr)
    theekhai = 0
    for i in range(n):
        acha = acha - theekhai - arr[i]
        if theekhai == acha:
            return i
        theekhai += arr[i]
    return -1

Phonepe ✅

def solve(n, plants, k):
    uff = 0
    a = k
    for i in range(n):
        if plants[i] <= a:
            a -= plants[i]
            uff += 1
        else:
            steps += 2 * i + 1
            a = k - plants[i]
    return uff

Phone pe ✅

Split it up ✅

Pitney Bowes is hiring QA Interns

2025/2024/2023 passouts can apply

https://careers.pitneybowes.com/global/en/job/R18422/Intern-QA?rx_job=R18422&rx_medium=post&rx_paid=0&rx_r=none&rx_source=linkedinll&rx_ts=20240718T021606Z&rx_viewer=f31609e0b41311ee90450bb95a3380bef7666ebed64d4e95aade908439480d1d

intern at take you forward https://www.linkedin.com/posts/takeuforward_internship-drive-tomorrow-at-8-pm-if-you-activity-7220012171378798592-zXqN?utm_source=share&utm_medium=member_desktop

NoScrubs is hiring Full-Stack Engineer Intern (previous intern experience is must)

For 2024, 2025, 2026 grads

Location: Remote

Stipend - 40K per month

Apply - https://wellfound.com/jobs/3062383-full-stack-engineer-intern