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

using namespace std;

int findLIS(vector<int>& s) {
    vector<int> tails;

    for (int x : s) {
        auto it = lower_bound(tails.begin(), tails.end(), x);
        if (it == tails.end()) {
            tails.push_back(x);
        } else {
            *it = x;
        }
    }

    return tails.size();
}  

Swiggy
LIS

Telegram:- @allcoding1_official

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

int numDecodings(string msg) {
    int MOD = 1000000007;
    int n = msg.size();
   
    vector<long long> dp(n + 1, 0);
    dp[0] = 1;
   
    if (msg[0] == '0')
        dp[1] = 0;
    else if (msg[0] == '*')
        dp[1] = 9;
    else
        dp[1] = 1;
   
    for (int i = 2; i <= n; ++i) {
        if (msg[i - 1] == '0') {
           
            if (msg[i - 2] == '1' || msg[i - 2] == '2')
                dp[i] += dp[i - 2];
            else if (msg[i - 2] == '*')
                dp[i] += 2 * dp[i - 2];
        } else if (msg[i - 1] >= '1' && msg[i - 1] <= '9') {
     
            dp[i] += dp[i - 1];
           
            if (msg[i - 2] == '1' || (msg[i - 2] == '2' && msg[i - 1] <= '6'))
                dp[i] += dp[i - 2];
            else if (msg[i - 2] == '*') {
               
                if (msg[i - 1] <= '6')
                    dp[i] += 2 * dp[i - 2];
                else
                    dp[i] += dp[i - 2];
            }
        } else if (msg[i - 1] == '*') {
            dp[i] += 9 * dp[i - 1];
           
            if (msg[i - 2] == '1')
                dp[i] += 9 * dp[i - 2];
            else if (msg[i - 2] == '2')
                dp[i] += 6 * dp[i - 2];
            else if (msg[i - 2] == '*')
                dp[i] += 15 * dp[i - 2];
        }
       
        dp[i] %= MOD;
    }
   
    return dp[n];
}

Number of ways decode

Accenture exam

Telegram:- @allcoding1_official

#include <iostream>
#include <sstream>
#include <string>
#include <vector>

std::string stemmer(const std::string& text) {
    std::stringstream ss(text);
    std::string word;
    std::vector<std::string> stemmed_words;

    while (ss >> word) {
        if (word.size() > 2 && (word.substr(word.size() - 2) == "ed" word.substr(word.size() - 2) == "ly" word.substr(word.size() - 3) == "ing")) {
            word = word.substr(0, word.size() - 2);
        }
        if (word.size() > 8) {
            word = word.substr(0, 8);
        }
        stemmed_words.push_back(word);
    }

    std::string result;
    for (const std::string& stemmed_word : stemmed_words) {
        result += stemmed_word + " ";
    }


    result.pop_back();
    return result;
}

int main() {
    std::string text = "an extremely dangerous dog is barking";
    std::cout << stemmer(text) << std::endl;  // Output: "an extreme dangerou dog is bark"

    return 0;
}

Suffix stripping stemmer

Telegram:- @allcoding1_official

#include <iostream>
#include <string>
#include <unordered_map>

using namespace std;

long getkRepValue(string user_history, long k) {
    long n = user_history.size();
    unordered_map<char, long> count;
    long left = 0, right = 0, ans = 0;

    while (right < n) {
        count[user_history[right]]++;
        while (count[user_history[right]] >= k && left <= right) {
            ans += n - right;
            count[user_history[left]]--;
            left++;
        }
        right++;
    }

    return ans;
} 

Machine learning
Amazon

#include <vector>
#include <unordered_map>
#include <iostream>

using namespace std;

int getMinTransactions(int n, vector<vector<int>>& debt) {
    unordered_map<int, int> balance
    for (const auto& d : debt) {
        balance[d[0]] -= d[2];
        balance[d[1]] += d[2];
    }
   
    vector<int> transactions;
    for (const auto& entry : balance) {
        if (entry.second != 0) {
            transactions.push_back(entry.second);
        }
    }

    int count = 0;
    int i = 0, j = transactions.size() - 1;
    while (i < j) {
        if (transactions[i] + transactions[j] == 0) {
            count++;
            i++;
            j--;
        } else if (transactions[i] + transactions[j] > 0) {
            transactions[i] += transactions[j];
            j--;
            count++;
        } else {
            transactions[j] += transactions[i];
            i++;
            count++;
        }
    }
    return count;
}

Transaction Simplification

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;

long long solution(int n, vector<long long>& a, vector<long long>& b) {
    long long ans = 0;

    int minP = min_element(a.begin(), a.end()) - a.begin();
    int minQ = min_element(b.begin(), b.end()) - b.begin();

    for (int i = 0; i < n; i++) {
        if (i == minP || i == minQ)
            continue;

        ans += min(a[minP] * b[i], b[minQ] * a[i]);
        ans %= MOD;
    }

    if (minP != minQ) {
        ans += a[minP] * b[minQ];
        ans %= MOD;
    }

    return ans;
}.

professor code
Uber

#include<bits/stdc++.h>
using namespace std;
string str, bad_string;
struct node{
    bool end_mark;
    node *next[10];
    node()
    {
        end_mark = false;
        for(int i = 0; i<10; i++)
            next[i] = NULL;
    }
}*root;
bool add(string s)
{
    node *current = root;
    for(int i = 0; i<s.size(); i++)
    {
        int nw = s[i] - 'a';
        if(i == (s.size()-1) && current->next[nw] != NULL)
            return false;
        if(current->next[nw] == NULL)
            current->next[nw] = new node();
        current = current->next[nw];
        if(current->end_mark)
            return false;
    }
    current->end_mark = true;
    return true;
}

int main()
{
    int i, N;
    bool ok = true;
    cin >> N;
    root = new node();
    for(i = 1; i<=N; i++)
    {
        cin >> str;
        if(!ok)
            continue;
        ok = add(str);
        if(!ok)
            bad_string = str;
    }
    if(ok)
        printf("GOOD SET\n");
    else
    {
        printf("BAD SET\n");
        cout << bad_string << endl;
    }
}

Good Bad String
Uber

#include<bits/stdc++.h>
using namespace std;

int main() {
    int n,c,d ;
    cin>>n>>c>>d ;
    int b[n],p[n],t[n] ;
    for(int i=0;i<n;i++)
        cin>>b[i]>>p[i]>>t[i] ;
    vector<pair<int,int>>type_0,type_1 ;
    for(int i=0;i<n;i++)
    {
        if(t[i]==0)
        {
            type_0.push_back({p[i],b[i]}) ;
        }
        else
        {
            type_1.push_back({p[i],b[i]}) ;
        }
    }
    sort(type_0.begin(),type_0.end()) ;
    sort(type_1.begin(),type_1.end()) ;
    // One using coins and one using diamonds
    int max_0=0,max_1=0 ;
    int x=type_0.size() ;
    int y=type_1.size() ;
    for(int i=0;i<x;i++)
    {
        if(type_0[i].first<=c)
            max_0=max(max_0,type_0[i].second) ;
    }
    for(int i=0;i<y;i++)
    {
        if(type_1[i].first<=d)
            max_1=max(max_1,type_1[i].second) ;
    }
    int ans=0 ;
    if(max_0&&max_1)
        ans=max(ans,max_0+max_1) ;  
    // Both using coins
    multiset<int>m;                        
    for(int i=0;i<x;i++)
    {
       m.insert(type_0[i].second) ;
    }
    int j=type_0.size()-1 ;
    for(int i=0;i<x;i++)
    {
        if(j<=i)
            break ;
        auto it=m.find(type_0[i].second) ;
        m.erase(it) ;
        int flag=0 ;   
        while(j>i)
        {
            if(type_0[j].first+type_0[i].first<=c)
            {
                flag=1 ;
                break ;
            }
            auto it=m.find(type_0[j].second) ;
            m.erase(it) ;
            j-- ;
        }
        if(flag==0)
            break ;
        if(m.size())
        ans=max(ans,type_0[i].second+*m.rbegin()) ;  
    }
    // Both using diamonds
    m.clear() ;
    for(int i=0;i<y;i++)
    {
       m.insert(type_1[i].second) ;
    }
     j=type_1.size()-1 ;
    for(int i=0;i<y;i++)
    {
        if(j<=i)
            break ;
        auto it=m.find(type_1[i].second) ;
        m.erase(it) ;
        int flag=0 ;
        while(j>i)
        {
            if(type_1[j].first+type_1[i].first<=d)
            {
                flag=1 ;
                break ;
            }
            auto it=m.find(type_1[j].second) ;
            m.erase(it) ;
            j-- ;
        }
        if(flag==0)
            break ;
        if(m.size())
        ans=max(ans,type_1[i].second+*m.rbegin()) ;
    }
    cout<<ans<<"\n" ;
    return 0;
}

Uber

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

using namespace std;

int minimum_energy_cost_recursive(int index,int idxy, int left_consecutive, int right_consecutive, int N, int X, int Y, int El, int Er, vector<int>& weights) {
    // Base case: if we have reached the end of bags
    if (index > idxy) {
        return 0;
    }
   
    // Calculate the cost of picking from the left and the right
    int cost_left = weights[index] * X + (left_consecutive ? El : 0) +
                    minimum_energy_cost_recursive(index + 1,idxy, 1, 0, N, X, Y, El, Er, weights);
    int cost_right = weights[idxy] * Y + (right_consecutive ? Er : 0) +
                     minimum_energy_cost_recursive(index ,idxy-1, 0, 1, N, X, Y, El, Er, weights);
   
    // Return the minimum of both choices
    return min(cost_left, cost_right);
}

int main() {
    int N, X, Y, El, Er;
    cin >> N >> X >> Y >> El >> Er;
   
    vector<int> weights(N);
    for (int i = 0; i < N; ++i) {
        cin >> weights[i];
    }
   
    cout << minimum_energy_cost_recursive(0,N-1, 0, 0, N, X, Y, El, Er, weights) << endl;
   
    return 0;
}

Amazon Hackon exam

Telegram:-

//Equilibrium path


#include <bits/stdc++.h>

using namespace std;

string trim(string str) {
str.erase(0, str.find_first_not_of(' '));
str.erase(str.find_last_not_of(' ') + 1);
return str;
}

int solve(int N, vector<int> A) {
int total_sum = accumulate(A.begin(), A.end(), 0);
int left_sum = 0;
int equilibrium_count = 0;

for (int i = 0; i < N; ++i) {
int right_sum = total_sum - left_sum - A[i];
if (left_sum == right_sum) {
equilibrium_count++;
}
left_sum += A[i];
}

return equilibrium_count;
}

int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);

string inputline;
getline(cin, inputline);
int N = stoi(trim(inputline));

vector<int> A(N);
for (int j = 0; j < N; j++) {
getline(cin, inputline);
A[j] = stoi(trim(inputline));
}

int result = solve(N, A);
cout << result << endl;

return 0;
}

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

using namespace std;

void dfs(int node, int parent, const vector<vector<int>> &adj, const vector<int> &A, int length, int &maxLength) {
maxLength = max(maxLength, length);
for (int neighbor : adj[node]) {
if (neighbor == parent) continue;
if ((A[node] ^ A[neighbor]) < min(A[node], A[neighbor])) {
dfs(neighbor, node, adj, A, length + 1, maxLength);
}
}
}

int main() {
int N;
cin >> N;
vector<int> A(N), P(N);
for (int i = 0; i < N; ++i) cin >> A[i];
for (int i = 1; i < N; ++i) cin >> P[i];

vector<vector<int>> adj(N);
for (int i = 1; i < N; ++i) {
int parent = P[i];
adj[parent].push_back(i);
adj[i].push_back(parent);
}

int maxLength = 0;
dfs(0, -1, adj, A, 1, maxLength);

cout << maxLength << endl;
return 0;
}
Nodes

#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <algorithm>

using namespace std;

int maxTreeScore(int node_count, int edge_count, vector<pair<int, int>>& edges, vector<int>& colors) {
// Step 1: Parse input and create adjacency list
unordered_map<int, vector<int>> adjacency_list;
for (const auto& edge : edges) {
int start = edge.first;
int end = edge.second;
adjacency_list[start].push_back(end);
adjacency_list[end].push_back(start);
}

// Step 2: Calculate depth of each node using BFS
vector<int> node_depth(node_count + 1, -1);
node_depth[1] = 0;
queue<int> bfs_queue;
bfs_queue.push(1);

while (!bfs_queue.empty()) {
int current_node = bfs_queue.front();
bfs_queue.pop();
int current_depth = node_depth[current_node];

for (int neighbor : adjacency_list[current_node]) {
if (node_depth[neighbor] == -1) { // unvisited
node_depth[neighbor] = current_depth + 1;
bfs_queue.push(neighbor);
}
}
}

// Step 3: Group nodes by depth
unordered_map<int, vector<int>> nodes_grouped_by_depth;
for (int node = 1; node <= node_count; ++node) {
nodes_grouped_by_depth[node_depth[node]].push_back(node);
}

// Step 4: Calculate distinct colors per depth
unordered_map<int, int> distinct_colors_at_depth;
for (const auto& pair : nodes_grouped_by_depth) {
int depth = pair.first;
const vector<int>& nodes = pair.second;
unordered_set<int> unique_colors;
for (int node : nodes) {
unique_colors.insert(colors[node - 1]);
}
distinct_colors_at_depth[depth] = unique_colors.size();
}

// Step 5: Dynamic programming to calculate max score
int max_depth = max_element(nodes_grouped_by_depth.begin(), nodes_grouped_by_depth.end(),
[](const auto& a, const auto& b) {
return a.first < b.first;
})->first;
vector<int> dp_score(max_depth + 2, 0);

for (int depth = max_depth; depth >= 0; --depth) {
// Option 1: Move to the next depth without adding score
dp_score[depth] = dp_score[depth + 1];

// Option 2: Add the distinct colors to score and move to depth depth + unique_colors_count
if (distinct_colors_at_depth.find(depth) != distinct_colors_at_depth.end()) {
int unique_colors_count = distinct_colors_at_depth[depth];
if (depth + unique_colors_count <= max_depth) {
dp_score[depth] = max(dp_score[depth], dp_score[depth + unique_colors_count] + unique_colors_count);
} else {
dp_score[depth] = max(dp_score[depth], unique_colors_count);
}
}
}

return dp_score[0];
}
diving in a tree , all test cases are passing

@allcoding1_official

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

using namespace std;

const int MOD = 1000000007;

int minLampsToLightRoad(int num_positions, int num_lamps, vector<int>& lamp_positions, vector<int>& left_reach, vector<int>& right_reach, vector<pair<int, int>>& queries) {
// Step 1: Create intervals for each lamp
vector<pair<int, int>> intervals;
for (int i = 0; i < num_lamps; ++i) {
intervals.push_back({lamp_positions[i] - left_reach[i], lamp_positions[i] + right_reach[i]});
}

// Step 2: Sort intervals based on starting position
sort(intervals.begin(), intervals.end());

// Precompute the farthest reach for each starting point
vector<pair<int, int>> max_reach_from_start;
int current_max_reach = -1;
for (const auto& interval : intervals) {
int start = interval.first;
int end = interval.second;
if (max_reach_from_start.empty() start > max_reach_from_start.back().first) {
max_reach_from_start.push_back({start, end});
}
current_max_reach = max(current_max_reach, end);
max_reach_from_start.back().second = current_max_reach;
}

auto min_lamps_needed = [&](int query_left, int query_right) {
int count = 0;
int max_reach = query_left;

while (max_reach <= query_right) {
auto it = upper_bound(max_reach_from_start.begin(), max_reach_from_start.end(), make_pair(max_reach, INT_MAX));
if (it == max_reach_from_start.begin() prev(it)->first > max_reach) {
return -1;
}

int next_max_reach = prev(it)->second;
if (next_max_reach <= max_reach) {
return -1;
}

max_reach = next_max_reach + 1;
count++;

if (max_reach > query_right) {
break;
}
}

return max_reach > query_right ? count : -1;
};

// Step 3: Process each query and sum up the results
int result_sum = 0;
for (const auto& query : queries) {
int result = min_lamps_needed(query.first, query.second);
if (result != -1) {
result_sum += result;
result_sum %= MOD;
}
}

return result_sum;
}

lightning lamp code , all cases are passing

@allcoding1_official

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

using namespace std;

void dfs(int node, int parent, const vector<vector<int>>& tree, const vector<int>& A, int depth, int& maxDepth) {
maxDepth = max(maxDepth, depth);

for (int child : tree[node]) {
if (child != parent) {
if ((A[node] ^ A[child]) < A[node] && (A[node] ^ A[child]) < A[child]) {
dfs(child, node, tree, A, depth + 1, maxDepth);
}
}
}
}

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

vector<int> A(N + 1);
vector<int> P(N + 1);
vector<vector<int>> tree(N + 1);

// Read values array
for (int i = 1; i <= N; ++i) {
cin >> A[i];
}

// Read parent array and buildthe tree
for (int i = 2; i <= N; ++i) { // P[1] is root with P[1] = 0, so start from 2
cin >> P[i];
tree[P[i]].push_back(i);
tree[i].push_back(P[i]);
}

int maxDepth = 0;
dfs(1, 0, tree, A, 1, maxDepth);

cout << maxDepth << endl;

return 0;
}

@allcoding1_official

#include<stdio.h>

int main() {
int n;
scanf("%d", &n);

char str[n + 1];
scanf("%s", str);

int count = 0;
char thirdLastConsonant;

for(int i = n - 1; i >= 0; i--) {
if (str[i] != 'a' && str[i] != 'e' && str[i] != 'i' && str[i] != 'o' && str[i] != 'u' &&
str[i] != 'A' && str[i] != 'E' && str[i] != 'I' && str[i] != 'O' && str[i] != 'U') {
count++;
if (count == 3) {
thirdLastConsonant = str[i];
break;
}
}
}

printf("%c\n", thirdLastConsonant);
return 0;
}

#include<stdio.h>
int main()
{
    int n;
    scanf("%d",&n);
    int arr[n];
    for(int i=0;i<n;i++)
    {
        scanf("%d",&arr[i]);
    }
    int count=0;
    int num=arr[0];
    for(int i=1;i<n;i++)
    {
       if(num!=arr[i])
            count++;
    }
    printf("%d",count);
}

C Language
TCS 1st Qsn

---------------------------------------------------------

N=int(input())
K=int(input())
price=list(map(int,input().split()))
vol=list(map(int,input().split()))
maxvol=0
volu=0
maxvol=max(vol)
for i in range(0,N):
    if (maxvol==vol[i] and price[i]<=K):
        K=K-price[i]
        volu=maxvol
for i in range(0,N):
    for j in range(i+1,N+1):
        if (price[i]<=K and price[i]==price[j]):
            if (vol[i]>vol[j]):
                volu=volu+vol[i]
                K=K-price[i]
            else:
                volu=volu+vol[j]
                K=K-price[j]
        elif (price[i]<=K and price[i]!=price[j]):
            K=K-price[i]
            -------

include<stdio.h>
int main()
{
    int n;
    scanf("%d",&n);
    int arr[n];
    for(int i=0;i<n;i++)
    {
        scanf("%d",&arr[i]);
    }
    int count=0;
    int num=arr[0];
    for(int i=1;i<n;i++)
    {
       if(num!=arr[i])
            count++;
    }
    printf("%d",count);
}

Array Code in C language

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

using namespace std;

struct Line {
int x1, y1, x2, y2;
};
int countCells(Line line, pair<int, int> star, bool split) {
if (line.x1 == line.x2) {
if (split) {
return min(abs(star.second - line.y1), abs(star.second - line.y2)) + 1;
}
else {
return abs(line.y1 - line.y2) + 1;
}
}
else {
if (split) {
return min(abs(star.first - line.x1), abs(star.first - line.x2)) + 1;
}
else {
return abs(line.x1 - line.x2) + 1;
}
}
}
bool intersects(Line a, Line b, pair<int, int>& intersection) {
if (a.x1 == a.x2 && b.y1 == b.y2) {
if (b.x1 <= a.x1 && a.x1 <= b.x2 && a.y1 <= b.y1 && b.y1 <= a.y2) {
intersection = {a.x1, b.y1};
return true;
}
}
if (a.y1 == a.y2 && b.x1 == b.x2) {
if (a.x1 <= b.x1 && b.x1 <= a.x2 && b.y1 <= a.y1 && a.y1 <= b.y2) {
intersection = {b.x1, a.y1};
return true;
}
}
return false;
}
int main() {
int N, K;
cin >> N;
vector<Line> lines(N);
for (int i = 0; i < N; ++i) {
cin >> lines[i].x1 >> lines[i].y1 >> lines[i].x2 >> lines[i].y2;
if (lines[i].x1 > lines[i].x2 || (lines[i].x1 == lines[i].x2 && lines[i].y1 > lines[i].y2)) {
swap(lines[i].x1, lines[i].x2);
swap(lines[i].y1, lines[i].y2);
}
}
cin >> K;
map<pair<int, int>, vector<Line>> stars;
for (int i = 0; i < N; ++i) {
for (int j = i + 1; j < N; ++j) {
pair<int, int> intersection;
if (intersects(lines[i], lines[j], intersection)) {
stars[intersection].push_back(lines[i]);
stars[intersection].push_back(lines[j]);
}
}
}

int asiylam = 0;
for (auto& star : stars) {
if (star.second.size() / 2 == K) {
vector<int> intensities;
for (auto& line : star.second) {
intensities.push_back(countCells(line, star.first, true));
}
asiylam += *min_element(intensities.begin(), intensities.end());
}
}
cout << asiylam << endl;
return 0;
}

Magic Star Intensity Code
C++
TCS Exam

#include <bits/stdc++.h>
using namespace std;

int Solution::findRadius(vector<int> &A, vector<int> &B) {
if (B.empty()) return INT_MAX;

sort(B.begin(), B.end());
int radius = 0;
for (int a : A) {
auto it = lower_bound(B.begin(), B.end(), a);

int dist = INT_MAX;
if (it != B.end()) {
dist = min(dist, abs(*it - a));
}
if (it != B.begin()) {
dist = min(dist, abs(*(it - 1) - a));
}

radius = max(radius, dist);
}
return radius;
}

Wifi Router Installation
C++
100% Correct Code

Amazon ML school exam

Telegram:- @allcoding1_official

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
string clearStars(string A) {
string s = A;

priority_queue<char, vector<char>, greater<char>> pq;
vector<vector<int>> ind(26);
unordered_set<int> rs;

for (int i = 0; i < s.size(); ++i) {
if (s[i] == '*') {
rs.insert(i);
char ch = pq.top(); pq.pop();
pq.push(ch);

rs.insert(ind[ch - 'a'].back());
ind[ch - 'a'].pop_back();

if (ind[ch - 'a'].empty()) pq.pop();

continue;
}

if (ind[s[i] - 'a'].empty())
pq.push(s[i]);

ind[s[i] - 'a'].push_back(i);
}

string res = "";
for (int i = 0; i < s.size(); ++i) {
if (!rs.count(i)) {
res += s[i];
}
}

return res;
}
};


Clear stars
Start removal
C++

Kill the enemy
C++
Amazon 1.15 PM


#include <vector>
#include <algorithm>

int solve(std::vector<int> &A, int B) {
long long m1 = 0, m2 = 0;

for (int val : A) {
if (val > m1) {
m2 = m1;
m1 = val;
} else if (val > m2) {
m2 = val;
}
}

long long b = B;
long long s = m1 + m2;

if (s == 0) {
return b > 0 ? -1 : 0;
}

long long k = b / s;
int ans = k * 2;
long long rem = b % s;

if (rem == 0) {
return ans;
} else if (rem <= m1) {
return ans + 1;
} else {
return ans + 2;
}
}