🪔 Diwali offer: from ₹99 till 8 NovSee prices →

Infosys and Accenture coding questions (2026): practice problems with solutions

Updated 17 October 2026

Ten practice problems in the style of the coding rounds students report from Infosys and Accenture. Each one has the idea in plain words, a solution in Python, C++ and Java that we ran against the examples and extra edge cases, and its time and space complexity.

Problems 1 to 4 are short maths, string and array problems of the kind students report from Accenture's coding round. Problems 5 to 10 cover greedy algorithms and dynamic programming, the two topics Infosys's own preparation guide names for its medium and hard questions. We wrote every problem ourselves, so none of them are official questions. Use them to learn the patterns, then take the real test on your own.

The problems

  1. Add the rest, subtract the multiplesMaths · Easy
  2. Check a passwordStrings · Easy
  3. Shorten a string with countsStrings · Two pointers · Easy
  4. Count the pairs that add up to KArrays · Hashing · Medium
  5. Fit the most meetings into one roomGreedy · Sorting · Medium
  6. Fewest jumps to the last stoneGreedy · Medium
  7. Best earnings without neighbouring stallsDynamic programming · Medium
  8. Spend a budget on the most useful gadgetsDynamic programming · 0/1 knapsack · Hard
  9. Longest common subsequenceDynamic programming · Strings · Hard
  10. Longest increasing subsequenceDynamic programming · Binary search · Hard

Accenture: what its campus portal says

Accenture's India campus hiring portal describes these steps for freshers. You'll get an email invitation if you're eligible, and you need to clear a cut-off in each section to move ahead.

StepWhat it coversTime
Mock assessmentA required practice run that checks your computer, software and internet10 minutes
TechnicalCommon applications and MS Office, pseudocode, basics of networking, security and cloud, and basic programming concepts45 minutes
Coding3 questions, solved in Java, Dotnet, Python, C++, C#, SQL, or HTML, CSS, React.js or Vue.js60 minutes
Behavioural and cognitivePersonality questions, plus puzzles and numerical equations40 minutes
CommunicationSpoken and written English: pronunciation, fluency, listening, vocabulary, grammar and more (sent in a separate email)About 30 minutes
InterviewWith one panel memberAbout 30 minutes

Source: Accenture's India campus hiring portal (support page). Checked on 11 October 2026.

Infosys: what its HackWithInfy pages say

We couldn't find the format of Infosys's regular fresher test on Infosys's own site, so we haven't described one. What Infosys does publish is the format of HackWithInfy, its coding contest for engineering students, which can lead to pre-placement interviews for Specialist Programmer and other roles.

Sources: Infosys's HackWithInfy page, its 2026 terms and conditions, its preparation guide and its 2026 sample questions. Checked on 11 October 2026. Look out for the next edition's dates on the HackWithInfy page.

How to practise with this page

1Add the rest, subtract the multiples

MathsEasy

Given N and M, add up every number from 1 to N that is not divisible by M, and subtract every number from 1 to N that is divisible by M. Print the result.

Input
N and M (1 ≤ N, M ≤ 109).
Output
One number. It can be negative and as big as about 5 × 1017, so use 64-bit integers.

Example input

10 3

Output

19

1 + 2 + 4 + 5 + 7 + 8 + 10 = 37 and 3 + 6 + 9 = 18, so the answer is 37 − 18 = 19.

Approach

A loop from 1 to N is fine for small N but too slow for 109, so use formulas. The sum of 1 to N is N(N + 1) / 2. There are K = N div M multiples of M, and they add up to M × (1 + 2 + … + K) = M × K(K + 1) / 2.

The other numbers add up to (total − multiples), and you subtract the multiples once more, so the answer is total − 2 × multiples.

Solution

Python
import sys

n, m = map(int, sys.stdin.read().split())

total = n * (n + 1) // 2          # 1 + 2 + ... + n
k = n // m                        # how many multiples of m are in 1..n
multiples = m * k * (k + 1) // 2  # m + 2m + ... + km
print(total - 2 * multiples)      # add the others, subtract the multiples
C++
#include <iostream>
using namespace std;

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

    long long total = n * (n + 1) / 2;              // 1 + 2 + ... + n
    long long k = n / m;                            // how many multiples of m are in 1..n
    long long multiples = m * (k * (k + 1) / 2);    // m + 2m + ... + km
    cout << total - 2 * multiples << '\n';          // add the others, subtract the multiples
}
Java
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong(), m = sc.nextLong();

        long total = n * (n + 1) / 2;              // 1 + 2 + ... + n
        long k = n / m;                            // how many multiples of m are in 1..n
        long multiples = m * (k * (k + 1) / 2);    // m + 2m + ... + km
        System.out.println(total - 2 * multiples); // add the others, subtract the multiples
    }
}

Time: O(1) · Extra space: O(1)

2Check a password

StringsEasy

A sign-up form accepts a password only if all of these are true: it has at least 8 characters; it has at least one digit, one capital letter and one small letter; it has no spaces; and it doesn't start with a digit. Print Valid or Invalid.

Input
One line: the password, up to 100 characters (it may contain spaces).
Output
Valid or Invalid.

Example 1 input

Savyly2026

Output

Valid

Example 2 input

9lives Cat

Output

Invalid

The second password starts with a digit and contains a space.

Approach

Read the whole line, not just one word, or a password with a space in it gets cut short and wrongly passes. Walk through the characters once and set a flag for each kind you see: digit, capital, small letter, space. Then check all the rules together.

Check the length before you look at the first character, so an empty line can't cause an error.

Solution

Python
import sys

pw = sys.stdin.readline().rstrip("\r\n")

valid = (
    len(pw) >= 8
    and any(ch.isdigit() for ch in pw)
    and any(ch.isupper() for ch in pw)
    and any(ch.islower() for ch in pw)
    and " " not in pw
    and not pw[0].isdigit()
)
print("Valid" if valid else "Invalid")
C++
#include <cctype>
#include <iostream>
#include <string>
using namespace std;

int main() {
    string pw;
    getline(cin, pw);
    if (!pw.empty() && pw.back() == '\r') pw.pop_back();

    bool digit = false, upper = false, lower = false, space = false;
    for (unsigned char c : pw) {
        if (isdigit(c)) digit = true;
        if (isupper(c)) upper = true;
        if (islower(c)) lower = true;
        if (c == ' ') space = true;
    }

    bool valid = pw.size() >= 8 && digit && upper && lower && !space
                 && !isdigit((unsigned char)pw[0]);
    cout << (valid ? "Valid" : "Invalid") << '\n';
}
Java
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String pw = br.readLine();
        if (pw == null) pw = "";

        boolean digit = false, upper = false, lower = false, space = false;
        for (char c : pw.toCharArray()) {
            if (Character.isDigit(c)) digit = true;
            if (Character.isUpperCase(c)) upper = true;
            if (Character.isLowerCase(c)) lower = true;
            if (c == ' ') space = true;
        }

        boolean valid = pw.length() >= 8 && digit && upper && lower && !space
                        && !Character.isDigit(pw.charAt(0));
        System.out.println(valid ? "Valid" : "Invalid");
    }
}

Time: O(L), where L is the length · Extra space: O(1)

3Shorten a string with counts

StringsTwo pointersEasy

Write each run of the same letter as the letter followed by the length of the run, so aaabccdddd becomes a3b1c2d4. If the result isn't shorter than the original, print the original instead.

Input
One line of small letters (1 to 105 characters).
Output
The shorter of the two strings (the original if they're the same length).

Example 1 input

aaabccdddd

Output

a3b1c2d4

Example 2 input

abc

Output

abc

In the second example, a1b1c1 would be longer than abc, so abc stays as it is.

Approach

Use two markers. i is the start of a run; move j forward while the letter stays the same. The run's length is j − i. Add the letter and the length to the result, then jump i to j.

A run can be longer than 9, so add the whole number, not a single digit. Build the result with a list (Python) or a StringBuilder (Java), because adding to a string piece by piece can get slow.

Solution

Python
import sys

s = sys.stdin.readline().strip()

parts = []
i = 0
while i < len(s):
    j = i
    while j < len(s) and s[j] == s[i]:   # find the end of this run
        j += 1
    parts.append(s[i] + str(j - i))
    i = j

packed = "".join(parts)
print(packed if len(packed) < len(s) else s)
C++
#include <iostream>
#include <string>
using namespace std;

int main() {
    string s;
    cin >> s;

    string packed;
    size_t i = 0;
    while (i < s.size()) {
        size_t j = i;
        while (j < s.size() && s[j] == s[i]) j++;   // find the end of this run
        packed += s[i];
        packed += to_string(j - i);
        i = j;
    }

    cout << (packed.size() < s.size() ? packed : s) << '\n';
}
Java
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine().trim();

        StringBuilder packed = new StringBuilder();
        int i = 0;
        while (i < s.length()) {
            int j = i;
            while (j < s.length() && s.charAt(j) == s.charAt(i)) j++;   // find the end of this run
            packed.append(s.charAt(i)).append(j - i);
            i = j;
        }

        System.out.println(packed.length() < s.length() ? packed.toString() : s);
    }
}

Time: O(L) · Extra space: O(L)

4Count the pairs that add up to K

ArraysHashingMedium

Given N numbers and a target K, count the pairs of positions (i, j), with i < j, whose numbers add up to K.

Input
N and K on the first line (1 ≤ N ≤ 105, |K| ≤ 2 × 109), then N numbers, each between -109 and 109.
Output
The number of pairs. It can be up to about 5 × 109, so use 64-bit integers.

Example input

6 8
1 7 3 5 4 4

Output

3

1 + 7, 3 + 5 and 4 + 4.

Approach

Checking every pair takes O(N²), about 5 × 109 checks when N is 105. Instead, walk through the numbers once and keep a map from each number to how many times you've seen it so far.

For each new number x, every earlier copy of K − x makes a pair with it, so add that count, then record x. Because you only look back, each pair is counted exactly once, and 4 + 4 works without pairing a number with itself.

Solution

Python
import sys

data = list(map(int, sys.stdin.read().split()))
n, k, nums = data[0], data[1], data[2:]

seen = {}    # value -> how many times it has appeared so far
pairs = 0
for x in nums[:n]:
    pairs += seen.get(k - x, 0)   # each earlier (k - x) pairs up with x
    seen[x] = seen.get(x, 0) + 1
print(pairs)
C++
#include <iostream>
#include <unordered_map>
using namespace std;

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

    unordered_map<long long, long long> seen;   // value -> times seen so far
    long long pairs = 0;
    for (int i = 0; i < n; i++) {
        long long x;
        cin >> x;
        auto it = seen.find(k - x);
        if (it != seen.end()) pairs += it->second;   // each earlier (k - x) pairs up with x
        seen[x]++;
    }
    cout << pairs << '\n';
}
Java
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long k = sc.nextLong();

        Map<Long, Integer> seen = new HashMap<>();   // value -> times seen so far
        long pairs = 0;
        for (int i = 0; i < n; i++) {
            long x = sc.nextLong();
            pairs += seen.getOrDefault(k - x, 0);    // each earlier (k - x) pairs up with x
            seen.merge(x, 1, Integer::sum);
        }
        System.out.println(pairs);
    }
}

Time: O(N) on average · Extra space: O(N)

5Fit the most meetings into one room

GreedySortingMedium

One meeting room has N requests, each with a start and an end time. Two meetings can't overlap, but one may start at the exact moment another ends. What is the largest number of meetings the room can hold?

Input
N (1 ≤ N ≤ 105), then N lines, each with a start and an end time (0 ≤ start < end ≤ 109).
Output
The largest number of meetings.

Example input

5
1 4
3 5
0 6
5 7
8 9

Output

3

1–4, then 5–7, then 8–9.

Approach

Greedy: always pick the meeting that finishes first. Finishing early leaves the most time for everything else, and swapping any other first choice for the earliest-finishing meeting never makes the plan worse.

So sort the meetings by end time, walk through them, and take a meeting whenever it starts at or after the end of the last one you took.

Solution

Python
import sys

data = list(map(int, sys.stdin.read().split()))
n = data[0]
meetings = [(data[1 + 2 * i], data[2 + 2 * i]) for i in range(n)]

meetings.sort(key=lambda m: m[1])   # earliest finish first
count, free_at = 0, -1
for start, end in meetings:
    if start >= free_at:            # the room is free when this one starts
        count += 1
        free_at = end
print(count)
C++
#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<pair<long long, long long>> m(n);   // stored as (end, start)
    for (auto &[end, start] : m) cin >> start >> end;

    sort(m.begin(), m.end());                  // earliest finish first
    int count = 0;
    long long freeAt = -1;
    for (auto &[end, start] : m) {
        if (start >= freeAt) {                 // the room is free when this one starts
            count++;
            freeAt = end;
        }
    }
    cout << count << '\n';
}
Java
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[][] m = new long[n][2];
        for (int i = 0; i < n; i++) {
            m[i][0] = sc.nextLong();   // start
            m[i][1] = sc.nextLong();   // end
        }

        Arrays.sort(m, (x, y) -> Long.compare(x[1], y[1]));   // earliest finish first
        int count = 0;
        long freeAt = -1;
        for (long[] meeting : m) {
            if (meeting[0] >= freeAt) {   // the room is free when this one starts
                count++;
                freeAt = meeting[1];
            }
        }
        System.out.println(count);
    }
}

Time: O(N log N) for the sort · Extra space: O(N)

6Fewest jumps to the last stone

GreedyMedium

N stones lie in a row, numbered 0 to N − 1. From stone i you can jump forward to any stone up to a[i] places ahead. Starting on stone 0, find the fewest jumps needed to reach the last stone, or print -1 if it can't be reached.

Input
N (1 ≤ N ≤ 105), then a[0] to a[N − 1], each from 0 to 105.
Output
The fewest jumps, or -1.

Example 1 input

6
2 3 1 1 2 0

Output

3

Example 2 input

5
3 2 1 0 4

Output

-1

In the first example: 0 → 1 → 4 → 5. In the second, every route gets stuck on stone 3, which can't jump at all.

Approach

Think in layers, like a breadth-first search, but without building a graph. end is the farthest stone you can reach with the jumps used so far, and far is the farthest you could reach with one more jump.

Walk from left to right, updating far. When you reach end, you have to jump again: count it and set end = far. If far hasn't moved past the current stone by then, you're stuck, and the answer is -1.

Solution

Python
import sys

data = list(map(int, sys.stdin.read().split()))
n, a = data[0], data[1:]

jumps, end, far = 0, 0, 0
for i in range(n - 1):
    far = max(far, i + a[i])   # farthest stone reachable with one more jump
    if i == end:               # we've used up the range of the current jump
        if far <= i:           # stuck: nothing reaches past this stone
            jumps = -1
            break
        jumps += 1
        end = far
        if end >= n - 1:
            break
print(jumps)
C++
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<long long> a(n);
    for (auto &x : a) cin >> x;

    long long jumps = 0, end = 0, far = 0;
    for (int i = 0; i < n - 1; i++) {
        far = max(far, i + a[i]);   // farthest stone reachable with one more jump
        if (i == end) {             // we've used up the range of the current jump
            if (far <= i) {         // stuck: nothing reaches past this stone
                jumps = -1;
                break;
            }
            jumps++;
            end = far;
            if (end >= n - 1) break;
        }
    }
    cout << jumps << '\n';
}
Java
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] a = new long[n];
        for (int i = 0; i < n; i++) a[i] = sc.nextLong();

        long jumps = 0, end = 0, far = 0;
        for (int i = 0; i < n - 1; i++) {
            far = Math.max(far, i + a[i]);   // farthest stone reachable with one more jump
            if (i == end) {                  // we've used up the range of the current jump
                if (far <= i) {              // stuck: nothing reaches past this stone
                    jumps = -1;
                    break;
                }
                jumps++;
                end = far;
                if (end >= n - 1) break;
            }
        }
        System.out.println(jumps);
    }
}

Time: O(N) · Extra space: O(1) beyond the input

7Best earnings without neighbouring stalls

Dynamic programmingMedium

N stalls stand in a line at a fair, and stall i would earn a[i] rupees. You can run any stalls you like, but never two that stand next to each other. What is the most you can earn?

Input
N (1 ≤ N ≤ 105), then N earnings, each from 0 to 109.
Output
The largest total (use 64-bit integers).

Example input

6
5 1 1 5 7 2

Output

13

Run stalls 1, 3 and 5 (counting from 1): 5 + 1 + 7 = 13.

Approach

Each stall is either run or not. Keep two numbers: take, the best total if the previous stall was run, and skip, the best total if it wasn't.

For a new stall worth x: running it means the previous one must have been skipped, so the new take is skip + x. Not running it leaves you free either way, so the new skip is max(take, skip). The answer is the bigger of the two at the end.

Solution

Python
import sys

data = list(map(int, sys.stdin.read().split()))
n, earn = data[0], data[1:]

take, skip = 0, 0   # best total so far if the previous stall was taken / skipped
for x in earn[:n]:
    take, skip = skip + x, max(take, skip)
print(max(take, skip))
C++
#include <algorithm>
#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    long long take = 0, skip = 0;   // best total so far if the previous stall was taken / skipped
    for (int i = 0; i < n; i++) {
        long long x;
        cin >> x;
        long long newTake = skip + x;
        skip = max(take, skip);
        take = newTake;
    }
    cout << max(take, skip) << '\n';
}
Java
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long take = 0, skip = 0;   // best total so far if the previous stall was taken / skipped
        for (int i = 0; i < n; i++) {
            long x = sc.nextLong();
            long newTake = skip + x;
            skip = Math.max(take, skip);
            take = newTake;
        }
        System.out.println(Math.max(take, skip));
    }
}

Time: O(N) · Extra space: O(1)

8Spend a budget on the most useful gadgets

Dynamic programming0/1 knapsackHard

You have W rupees and a list of N gadgets, each with a price and a usefulness score. You can buy each gadget at most once. What is the highest total usefulness you can get without spending more than W?

Input
N and W (1 ≤ N ≤ 100, 0 ≤ W ≤ 104), then N lines, each with a price (1 to 104) and a usefulness (1 to 106).
Output
The highest total usefulness.

Example input

5 10
4 30
3 20
5 45
2 10
6 50

Output

80

Buy the ₹6 and ₹4 gadgets: 50 + 30 = 80.

Approach

This is the 0/1 knapsack. Greedy by "usefulness per rupee" fails here: it buys the ₹5 gadget first (9 per rupee), can't fit the ₹6 one after that, and ends with 75.

Instead, let best[w] be the most usefulness you can get for at most w rupees. Add the gadgets one at a time: for each budget w, either skip the gadget or buy it, which gives best[w − price] + value. Go through w from high to low, so that best[w − price] still describes the choices before this gadget; that stops you from buying the same gadget twice.

Solution

Python
import sys

data = list(map(int, sys.stdin.read().split()))
n, budget = data[0], data[1]

best = [0] * (budget + 1)   # best[w] = most usefulness for at most w rupees
for i in range(n):
    price, value = data[2 + 2 * i], data[3 + 2 * i]
    for w in range(budget, price - 1, -1):   # go downwards so each gadget is bought once
        best[w] = max(best[w], best[w - price] + value)
print(best[budget])
C++
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

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

    vector<long long> best(budget + 1, 0);   // best[w] = most usefulness for at most w rupees
    for (int i = 0; i < n; i++) {
        int price;
        long long value;
        cin >> price >> value;
        for (int w = budget; w >= price; w--)   // go downwards so each gadget is bought once
            best[w] = max(best[w], best[w - price] + value);
    }
    cout << best[budget] << '\n';
}
Java
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), budget = sc.nextInt();

        long[] best = new long[budget + 1];   // best[w] = most usefulness for at most w rupees
        for (int i = 0; i < n; i++) {
            int price = sc.nextInt();
            long value = sc.nextLong();
            for (int w = budget; w >= price; w--)   // go downwards so each gadget is bought once
                best[w] = Math.max(best[w], best[w - price] + value);
        }
        System.out.println(best[budget]);
    }
}

Time: O(N × W) · Extra space: O(W)

9Longest common subsequence

Dynamic programmingStringsHard

Given two words, find the length of the longest sequence of letters that appears in both of them in the same order. The letters don't have to be next to each other.

Input
Two lines, each a word of 1 to 1,000 small letters.
Output
The length of the longest common subsequence.

Example input

placement
planet

Output

5

"plant" appears in both words in order, and no 6-letter sequence does.

Approach

Let dp[i][j] be the answer for the first i letters of the first word and the first j letters of the second. If those two last letters match, they can end the common sequence: dp[i][j] = dp[i − 1][j − 1] + 1. If they don't, drop one of them and keep the better result: max(dp[i − 1][j], dp[i][j − 1]).

The answer is in the last cell. Each row only uses the row above it, so you can keep just two rows if memory is tight.

Solution

Python
import sys

a, b = sys.stdin.read().split()
n, m = len(a), len(b)

# dp[i][j] = longest common subsequence of a[:i] and b[:j]
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
    for j in range(1, m + 1):
        if a[i - 1] == b[j - 1]:
            dp[i][j] = dp[i - 1][j - 1] + 1
        else:
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
print(dp[n][m])
C++
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
    string a, b;
    cin >> a >> b;
    int n = a.size(), m = b.size();

    // dp[i][j] = longest common subsequence of the first i letters of a and first j of b
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (a[i - 1] == b[j - 1])
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);

    cout << dp[n][m] << '\n';
}
Java
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String a = sc.next(), b = sc.next();
        int n = a.length(), m = b.length();

        // dp[i][j] = longest common subsequence of the first i letters of a and first j of b
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                if (a.charAt(i - 1) == b.charAt(j - 1))
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                else
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);

        System.out.println(dp[n][m]);
    }
}

Time: O(N × M) · Extra space: O(N × M), or O(M) with two rows

10Longest increasing subsequence

Dynamic programmingBinary searchHard

Given N numbers, find the length of the longest subsequence (numbers picked in their original order, not necessarily next to each other) in which every number is bigger than the one before it.

Input
N (1 ≤ N ≤ 105), then N numbers, each between -109 and 109.
Output
The length of the longest increasing subsequence.

Example input

8
3 10 2 1 20 4 6 7

Output

4

For example 3, 4, 6, 7.

Approach

The simple DP looks back at every earlier number for each number, which is O(N²) and too slow for 105. The faster idea keeps a list tails, where tails[k] is the smallest number that can end an increasing run of length k + 1.

tails is always sorted, so for each new x, binary-search for the first tail that is at least x. If there is none, x makes the longest run one longer; otherwise x replaces that tail, because a smaller ending leaves more room to grow. The answer is the length of tails. (The list itself isn't always a real subsequence; only its length matters.)

Solution

Python
import sys
from bisect import bisect_left

data = list(map(int, sys.stdin.read().split()))
n, nums = data[0], data[1:]

# tails[k] = smallest possible last number of an increasing run of length k + 1
tails = []
for x in nums[:n]:
    pos = bisect_left(tails, x)   # first tail that is >= x
    if pos == len(tails):
        tails.append(x)           # x makes the longest run one longer
    else:
        tails[pos] = x            # x is a better (smaller) ending for that length
print(len(tails))
C++
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

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

    // tails[k] = smallest possible last number of an increasing run of length k + 1
    vector<long long> tails;
    for (int i = 0; i < n; i++) {
        long long x;
        cin >> x;
        auto it = lower_bound(tails.begin(), tails.end(), x);   // first tail >= x
        if (it == tails.end())
            tails.push_back(x);   // x makes the longest run one longer
        else
            *it = x;              // x is a better (smaller) ending for that length
    }
    cout << tails.size() << '\n';
}
Java
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        // tails[k] = smallest possible last number of an increasing run of length k + 1
        long[] tails = new long[n];
        int len = 0;
        for (int i = 0; i < n; i++) {
            long x = sc.nextLong();
            int lo = 0, hi = len;          // find the first tail >= x
            while (lo < hi) {
                int mid = (lo + hi) / 2;
                if (tails[mid] < x) lo = mid + 1;
                else hi = mid;
            }
            tails[lo] = x;                 // replace it, or add x at the end
            if (lo == len) len++;
        }
        System.out.println(len);
    }
}

Time: O(N log N) · Extra space: O(N)

Questions

How long is Accenture's coding assessment?

Accenture's India campus hiring portal lists a 60-minute coding assessment with 3 questions, which you can solve in a backend language (Java, Dotnet, Python, C++ or C#), in SQL, or with front-end technology (HTML, CSS, React.js or Vue.js). We checked this on 11 October 2026.

What does Infosys's coding test look like?

Infosys's HackWithInfy preparation guide (from the 2024 edition) describes a test that usually has 3 questions in 3 hours: an easy one on basic aptitude, algorithms and data structures, a medium one usually based on greedy algorithms, and a hard one usually based on dynamic programming, in C, C++, Java, Python or JavaScript. We couldn't find the format of Infosys's regular fresher test on Infosys's own site, so we haven't described one.

Are these real Infosys or Accenture questions?

No. We wrote them ourselves in the style of the question types students commonly report and the topics the companies' own pages name. Learning these patterns helps far more than memorising answers.

Were these solutions tested?

Yes. We ran every solution in Python, C++ and Java on the examples, on extra edge cases, on random inputs checked against a slow but simple answer, and on the largest inputs the limits allow.

More placement prep