#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
vector<int> solve(vector<int>& direction, vector<int>& strength) {
    int n = direction.size();
    stack<int> st;
    stack<int> in; 
    for (int i = 0; i < n; ++i) {
        int cudr = direction[i];
        int cs = strength[i];
        if (cudr == 1) {
            st.push(i);
        } else {
            while (!in.empty()) {
                int ii = in.top();
                int is = strength[ii];
               
                if (cs > is) {
                    in.pop();
                } else if (cs == is) {
                    in.pop();
                    cs = 0;
                } else {
                    cs = 0;
                    break;
                }
            }
           
            if (cs > 0) {
                st.push(i);
            }
        }
       
        in.push(i);
    }
    vector<int> result;
    while (!st.empty()) {
        result.push_back(st.top());
        st.pop();
    }
    reverse(result.begin(), result.end());
   
    return result;
}.

// BALL COLISION✅

#include <vector>
#include <queue>
#include <climits>
using namespace std;
int getMinimumStress(int graph_nodes, vector<int> graph_from, vector<int> graph_to, vector<int> graph_weight, int source, int destination) {
    vector<vector<pair<int, int>>> adj(graph_nodes + 1);
    for (int i = 0; i < graph_from.size(); ++i) {
        int u = graph_from[i];
        int v = graph_to[i];
        int w = graph_weight[i];
        adj[u].emplace_back(v, w);
        adj[v].emplace_back(u, w);
    }

    vector<int> res(graph_nodes + 1, INT_MAX);
    res[source] = 0;

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.emplace(0, source);

    while (!pq.empty()) {
        auto [cs, node] = pq.top();
        pq.pop();

        if (node == destination) {
            return cs;
        }

        for (auto& [neighbor, weight]: adj[node]) {
            int ns = max(cs, weight);
            if (ns < res[neighbor]) {
                res[neighbor] = ns;
                pq.emplace(ns, neighbor);
            }
        }
    }

    return res[destination] == INT_MAX ? -1 : res[destination];
}.

// MINIMIZE PATH VALUE ✅

#include <iostream>
#include <vector>
#include <unordered_set>
#include <unordered_map>
using namespace std;
vector<bool> processQueries(const vector<vector<int>>& grid, const vector<int>& queries) {
    int n = grid.size();
    int m = grid[0].size();
    vector<vector<unordered_set<int>>> dp(n, vector<unordered_set<int>>(m));
    dp[0][0].insert(grid[0][0]);
        for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (i > 0) {
                for (int sum : dp[i-1][j]) {
                    dp[i][j].insert(sum + grid[i][j]);
                }
            }
            if (j > 0) {
                for (int sum : dp[i][j-1]) {
                    dp[i][j].insert(sum + grid[i][j]);
                }
            }
        }
    }
        vector<bool> results;
    for (int x : queries) {
        if (dp[n-1][m-1].count(x)) {
            results.push_back(true);
        } else {
            results.push_back(false);
        }
    }
   
    return results;
}.

ORACLE PATH SUM ✅

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <limits>
using namespace std;
struct Edge {
    int to;
    int cost;
};
struct Node {
    int vertex;
    int cost;
        bool operator<(const Node& other) const {
        return cost < other.cost;
    }
};

int maxCostRoute(int n, int m, vector<vector<int>>& routes) {
    vector<vector<Edge>> graph(n + 1);
    for (const auto& route : routes) {
        int u = route[0];
        int v = route[1];
        int cost = route[2];
        graph[u].push_back({v, cost});
    }

    priority_queue<Node> pq;
    pq.push({1, 0});
   
    vector<int> maxCost(n + 1, numeric_limits<int>::min());
    maxCost[1] = 0;

    while (!pq.empty()) {
        Node current = pq.top();
        pq.pop();
        int currentVertex = current.vertex;
        int currentCost = current.cost;
        if (currentVertex == n) {
            return currentCost;
        }

        for (const auto& edge : graph[currentVertex]) {
            int nextVertex = edge.to;
            int nextCost = currentCost + edge.cost;

            if (nextCost > maxCost[nextVertex]) {
                maxCost[nextVertex] = nextCost;
                pq.push({nextVertex, nextCost});
            }
        }
    }

    return -1;
}. 

ORCALE  AIRLINE PROBLEM ✅

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
void inorder(TreeNode* root, vector<int>& nodes) {
    if (root == nullptr) return;
    inorder(root->left, nodes);
    nodes.push_back(root->val);
    inorder(root->right, nodes);
}
TreeNode* findKthSmallest(TreeNode* root, int& k) {
    if (root == nullptr) return nullptr;
    TreeNode* left = findKthSmallest(root->left, k);
    if (left != nullptr) return left;
    if (--k == 0) return root;
    return findKthSmallest(root->right, k);
}
void inorderSubtree(TreeNode* root, vector<int>& nodes) {
    if (root == nullptr) return;
    inorderSubtree(root->left, nodes);
    nodes.push_back(root->val);
    inorderSubtree(root->right, nodes);
}
int findMedian(TreeNode* root, int K) {
    vector<int> nodes;
    inorder(root, nodes);
    int k = K;
    TreeNode* kthSmallestNode = findKthSmallest(root, k);
    if (kthSmallestNode == nullptr) return -1;
    vector<int> subtreeNodes;
    inorderSubtree(kthSmallestNode, subtreeNodes);
    int n = subtreeNodes.size();
    if (n % 2 == 1) {
        return subtreeNodes[n / 2];
    } else {
        return (subtreeNodes[n / 2 - 1] + subtreeNodes[n / 2]) / 2;
    }
}.

// ORACLE STRAGE MEDIUM✅

def MonkeyVsHooman(N, H, X, SI):
    if SI[X-1] >= H:
        return 1
    if N == 1:
        return -1
    def help(arr):
        n = len(arr)
        arr.append(float('inf'))
        mxJump = lambda x: arr[x] - min(arr[x - 1], arr[x + 1])
        cur, steps = 0, 0
        res = float('inf')
        for i in range(0, n, 2):
            cur = max(0, cur - (i and arr[i - 1]))
            cur += arr[i]
            steps += (1 if i == 0 else 2)
            jump = mxJump(i)
            if jump > 0:
                moves = (H - cur + jump - 1) // jump
                res = min(res, steps + moves * 2)
        return res

    ans = min(help(SI[X-1:]), help(SI[ :X][ ::- 1]))
    return ans if ans != float('inf') else -1

print(MonkeyVsHooman(5,10,1,[3,1,2,2,5]))


Monkeys vs hoomns ✅

#include <iostream>
#include <string>
using namespace std;
string helper(const string& s, size_t& index) {
    string ans = "";
    int isans = 0;
    while (index < s.length())
    {
        if (isdigit(s[index]))
        {
            isans = isans * 10 + (s[index] - '0');
        } else if (s[index] == '(')
        {
            index++;
            string subResult = helper(s, index);
            for (int i = 0; i < isans; i++)
            {
                ans += subResult;
            }
            isans = 0;
        } else if (s[index] == ')')
        {
            index++;
            return ans;
        } else
        {
            ans += s[index];
        }
        index++;
    }
   
    return ans;
}
string expandString(const string& s) {
    size_t index = 0;
    return helper(s, index);
}

#include <string>
#include <cmath>
#include <algorithm>
#include <iostream>
using namespace std;
int swapAndCount(string s, string t) {
    int swaps=0;
    int flag=1;
    int n=s.size();
    for(int i=0;i<n;i++){
        if(s[i]==t[i]) continue;
        else if(s[i]<t[i]){
            if(flag) {
                swaps++;
                flag=0;
            }
            if(!flag){
                continue;
            }
        }
        else{
            if(flag){
                flag=0;
            }
            else if(!flag){
                swaps++;
            }
        }
    }
    return swaps;
}
int solution(string S, string T) {
    return min(swapAndCount(S, T),swapAndCount(T, S));
}

#include <vector>
#include <array>
#include <algorithm>
#include <numeric>
#include <functional>

long long solve(int N, std::vector<int> from, std::vector<int> to, std::vector<int> weight, int k) {
    std::vector<std::vector<std::pair<int, int>>> adj(N);
    for (int i = 0; i < N - 1; ++i) { // build adj
        adj[from[i]].emplace_back(to[i], weight[i]);
        adj[to[i]].emplace_back(from[i], weight[i]);
    }

    std::function<std::array<long long, 2>(int, int)> dfs = [&](int cur, int parent) {
        std::array<long long, 2> ans{};
        std::vector<long long> take, skip, diff;
        for (auto& [next, w] : adj[cur]) if (parent != next) {
            auto [not_full, full] = dfs(next, cur);
            take.push_back(not_full + w);
            skip.push_back(full);
            diff.push_back(take.back() - skip.back());
        }

        int n = int(diff.size());
        std::ranges::nth_element(diff, diff.begin() + k - 1, std::greater<>());
        ans[0] = std::reduce(diff.begin(), diff.begin() + std::min(k, n)) + std::reduce(skip.begin(), skip.end());
       
        if (n && n >= k) {
            ans[1] = ans[0];
            ans[0] -= *std::min_element(diff.begin(), diff.begin() + k);
        }

        return ans;
    };

    auto ans = dfs(0, -1);
    return std::max(ans[0], ans[1]);
}

Server ✅

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

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
   
    int l = 0, r = n - 1;
    while (l < n && a[l] == 0) l++;
    while (r > l && a[r] == 0) r--;

    int ans = 0;
    if ((r - l + 1) % 2 == 0) {
        if (a[l] > a[r]) {
            ans += a[r];
            r--;
        } else {
            ans += a[l];
            l++;
        }
    }

    int sum = 0, c = 1, max1 = 0, sum1 = 0, max2 = 0, sum2 = 0;
    for (int i = l; i <= r; i++) {
        sum += a[i];
        int tmp = c / 2;
        int god = (tmp * (tmp + 1)) + (tmp + 1);
        if (god <= sum && c % 2 == 1) {
            max1 = c;
            sum1 = sum;
        }
        c++;
    }

    c = 1;
    sum = 0;
    for (int i = r; i >= l; i--) {
        sum += a[i];
        int tmp = c / 2;
        int god = (tmp * (tmp + 1)) + (tmp + 1);
        if (god <= sum && c % 2 == 1) {
            max2 = c;
            sum2 = sum;
        }
        c++;
    }

    int max1h = max1 / 2, max2h = max2 / 2;
    int ans1 = (max1h * (max1h + 1)) + (max1h + 1);
    int ans2 = (max2h * (max2h + 1)) + (max2h + 1);
    cout << min(sum - sum1 + sum1 - ans1, sum - sum2 + sum2 - ans2) + ans << endl;

    return 0;
}


//bitonic array ✅

Onix is hiring for Software Engineers

2024 batch eligibile
Delhi/Hyderabad/Pune/Bangalore
2 sept 2024 is the joining date

Selection Process :
Online Aptitude cum Technical Assessment – 95 minutes
Two Levels of Technical Interviews
HR Interview

Apply Form : https://forms.gle/sanQ1wiQKkZCN1Ss9

Thriving Springs is hiring for SDE (Full time) | MEAN stack | Hyderabad | 4.5 LPA - 9.5 LPA
| 2 openings | 2023/2022/2021/2020 passouts eligible

Apply here - https://forms.gle/ea47rjtc5ZUjQdrU6

Role: Software development Intern
Company: Thriving Springs
Tech stacks, HTML, CSS
Good to know: Angular, Node.js
Location: Hyderabad
Mode of Work: Work from Office
Working Days: Monday to Friday; (Monday to Thursday - WFO, Friday - WFH)
Stipend - 20K/M
Duration - 6 months
Open Positions - 10
Post Completion of the Internship period, PPO offered from 5 LPA to 7.5 LPA based upon performance evaluation.

Apply here - https://forms.gle/ea47rjtc5ZUjQdrU6