TCS TAG test 12.01.2026

Posted
7 Feb 2026
534 reads

Summary

This post details my experience with a TCS TAG test, which featured two algorithmic challenges: finding prime factors of an integer and identifying a continuous subarray for maximum profit under a cost constraint. I provided multiple approaches and C++ solutions for both problems.

How it went

Problem - 01

Given an integer n, print its prime factors in ascending order. Example:

Input: 36 Output: 2 2 3 3

โœ… Approach 1 โ€” Brute Force (Check Prime First) ๐Ÿ”น Idea โ€ข Try every number from 2 โ†’ n โ€ข Check if it is prime โ€ข If prime โ†’ divide repeatedly ๐Ÿ”น Complexity

O(nโˆšn) โ†’ slow for large inputs

โœ… C++ Brute Force Code

#include <iostream>
using namespace std;

bool isPrime(int x) { if (x < 2) return false; for (int i = 2; i * i <= x; i++) { if (x % i == 0) return false; } return true; }

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

for (int i = 2; i &lt;= n; i++) {
    if (isPrime(i)) {
        while (n % i == 0) {
            cout &lt;&lt; i &lt;&lt; " ";
            n /= i;
        }
    }
    if (n == 1) break;
}

return 0;

}

โœ… Approach 2 โ€” Optimized Trial Division (Best for TCS) ๐Ÿ”น Key Insight No need to check if i is prime.

Just try dividing from 2 โ†’ โˆšn. If i were composite, its smaller prime factor would already have divided n. ๐Ÿ”น Complexity

O(โˆšn) โ†’ safe for large values

โœ… C++ Optimized Code (Recommended)

#include <iostream>
using namespace std;

int main() { long long n; cin >> n;

for (long long i = 2; i * i &lt;= n; i++) {
    while (n % i == 0) {
        cout &lt;&lt; i &lt;&lt; " ";
        n /= i;
    }
}

if (n &gt; 1)
    cout &lt;&lt; n;

return 0;

}

โœ… Extra Optimized Version (Even Faster โ€” Skip Evens) After removing factor 2 โ†’ check only odd numbers. โœ… C++ Faster Variant

#include <iostream>
using namespace std;

int main() { long long n; cin >> n;

// handle factor 2
while (n % 2 == 0) {
    cout &lt;&lt; 2 &lt;&lt; " ";
    n /= 2;
}

// check only odd numbers
for (long long i = 3; i * i &lt;= n; i += 2) {
    while (n % i == 0) {
        cout &lt;&lt; i &lt;&lt; " ";
        n /= i;
    }
}

if (n &gt; 1)
    cout &lt;&lt; n;

return 0;

}

โœ… Edge Cases Covered

n = 1 โ†’ prints nothing n = prime โ†’ prints n n = power โ†’ prints repeated factors n = large โ†’ uses long long

Problem-02

You are given: โ€ข An integer W โ†’ maximum allowed total cost โ€ข An array cost[] of size n โ€ข An array profit[] of size n You must select a continuous subarray such that:

sum(cost in subarray) โ‰ค W

Among all such subarrays, return the maximum total profit. โœ… Example

W = 10 cost = [2, 3, 5, 4] profit = [6, 7, 8, 9]

Check subarrays:

[2,3,5] โ†’ cost=10 โ†’ profit=21 โœ… [3,5] โ†’ cost=8 โ†’ profit=15 [5,4] โ†’ cost=9 โ†’ profit=17

Answer = 21 โœ… Key Observation Because it must be continuous, this is NOT knapsack DP.

This is subarray with constraint โ†’ Sliding Window. โœ… Approach 1 โ€” Brute Force ๐Ÿ”น Idea Check every possible subarray. For each start index: โ€ข keep adding cost & profit โ€ข stop if cost exceeds W โ€ข track max profit ๐Ÿ”น Complexity

O(nยฒ)

Works only for small n. โœ… C++ Brute Force Code

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

int main() { int n, W; cin >> n >> W;

vector&lt;int&gt; cost(n), profit(n);
for(int i = 0; i &lt; n; i++) cin &gt;&gt; cost[i];
for(int i = 0; i &lt; n; i++) cin &gt;&gt; profit[i];

int maxProfit = 0;

for(int i = 0; i &lt; n; i++) {
    int sumCost = 0, sumProfit = 0;

    for(int j = i; j &lt; n; j++) {
        sumCost += cost[j];
        sumProfit += profit[j];

        if(sumCost &lt;= W)
            maxProfit = max(maxProfit, sumProfit);
        else
            break;
    }
}

cout &lt;&lt; maxProfit;

}

โœ… Approach 2 โ€” Optimized Sliding Window (Expected in TCS) ๐Ÿ”น Why Sliding Window Works โ€ข All values are positive (cost & profit) โ€ข Window sum increases when right expands โ€ข If cost exceeds W โ†’ move left pointer ๐Ÿ”น Steps

left = 0
for right in range(n):
    add cost[right], profit[right]
while sumCost &gt; W:
    remove cost[left], profit[left]
    left++

update maxProfit

๐Ÿ”น Complexity: O(n)

Each element enters and leaves window once. โœ… C++ Optimized Code (Recommended)

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

int main() { int n, W; cin >> n >> W;

vector&lt;int&gt; cost(n), profit(n);
for(int i = 0; i &lt; n; i++) cin &gt;&gt; cost[i];
for(int i = 0; i &lt; n; i++) cin &gt;&gt; profit[i];

int left = 0;
int sumCost = 0;
int sumProfit = 0;
int maxProfit = 0;

for(int right = 0; right &lt; n; right++) {
    sumCost += cost[right];
    sumProfit += profit[right];

    while(sumCost &gt; W) {
        sumCost -= cost[left];
        sumProfit -= profit[left];
        left++;
    }

    maxProfit = max(maxProfit, sumProfit);
}

cout &lt;&lt; maxProfit;

}

โœ… Edge Cases TCS Might Include

W smaller than all costs โ†’ answer = 0 Single element fits โ†’ choose it All costs fit โ†’ choose whole array n = 1

Questions asked (2)

  1. 01

    Prime Factors of an Integer

    Data Structures & Algorithms ยท Medium

    Given an integer n, print its prime factors in ascending order.
    Example:

    Input: 36
    Output: 2 2 3 3

  2. 02

    Maximum Profit from Continuous Subarray with Cost Constraint

    Data Structures & Algorithms ยท Medium

    You are given:
    โ€ข An integer W โ†’ maximum allowed total cost
    โ€ข An array cost[] of size n
    โ€ข An array profit[] of size n
    You must select a continuous subarray such that:

    sum(cost in subarray) โ‰ค W

    Among all such subarrays, return the maximum total profit.
    Example
    W = 10
    cost   = [2, 3, 5, 4]
    profit = [6, 7, 8, 9]

    Check subarrays:
    [2,3,5] โ†’ cost=10 โ†’ profit=21 โœ…
    [3,5] โ†’ cost=8 โ†’ profit=15
    [5,4] โ†’ cost=9 โ†’ profit=17

    Answer = 21

Know someone preparing? Send it to them:WhatsAppLinkedInX

Interviewed at TCS recently?

Write up your rounds while you still remember the questions. It helps the next person more than you would think.

Share your experience
Discussion 0

Questions for the author, or how your own interview compared.

Join the discussion

Sign in with Google to comment or ask the author a question.

No comments yet

Be the first to share your thoughts and start the discussion!