TCS NQT Exam 2-Shift Coding Question | TCS NQT Exam 20/03/2026 Coding Question

Q1. Sort Pairs Using Selection Sort

Problem Statement

You are given N pairs of integers. Each pair contains two values (a, b). Your task is to sort the pairs using Selection Sort based on the following rules:

Sorting Criteria

• Sort pairs in ascending order of the first element.
• If the first elements are equal, then sort based on the second element in ascending order.

Input Format

First line contains an integer N — number of pairs.

Next N lines each contain two integers a and b.

Output Format

Print sorted pairs (one per line)

Example

Input

5
10 4
3 2
5 2
3 1
10 5
    

Output

3 1
3 2
5 2
10 4
10 5
    

Explanation

First sort by first element → (3, 2) and (3, 1) come first.

Since the first elements are equal (3), compare the second → (3, 1) comes before (3, 2).

Approach (Selection Sort)

• Iterate through the array
• Select the minimum element based on the condition
• Swap with the current index

Solutions

🔹 C++ Solution

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

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

    vector<pair<int,int>> arr(n);

    for(int i = 0; i < n; i++) {
        cin >> arr[i].first >> arr[i].second;
    }

    for(int i = 0; i < n - 1; i++) {
        int minIndex = i;

        for(int j = i + 1; j < n; j++) {
            if(arr[j].first < arr[minIndex].first ||
              (arr[j].first == arr[minIndex].first &&
               arr[j].second < arr[minIndex].second)) {
                minIndex = j;
            }
        }

        swap(arr[i], arr[minIndex]);
    }

    for(auto &p : arr) {
        cout << p.first << " " << p.second << endl;
    }
}
    

🔹 Java Solution

import java.util.*;

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

        int n = sc.nextInt();
        int[][] arr = new int[n][2];

        for(int i = 0; i < n; i++) {
            arr[i][0] = sc.nextInt();
            arr[i][1] = sc.nextInt();
        }

        for(int i = 0; i < n - 1; i++) {
            int minIndex = i;

            for(int j = i + 1; j < n; j++) {
                if(arr[j][0] < arr[minIndex][0] ||
                  (arr[j][0] == arr[minIndex][0] &&
                   arr[j][1] < arr[minIndex][1])) {
                    minIndex = j;
                }
            }

            int t0 = arr[i][0];
            int t1 = arr[i][1];
            arr[i][0] = arr[minIndex][0];
            arr[i][1] = arr[minIndex][1];
            arr[minIndex][0] = t0;
            arr[minIndex][1] = t1;
        }

        for(int i = 0; i < n; i++) {
            System.out.println(arr[i][0] + " " + arr[i][1]);
        }
    }
}
    

🔹 Python Solution

n = int(input())
arr = []

for _ in range(n):
    a, b = map(int, input().split())
    arr.append([a, b])

for i in range(n - 1):
    min_index = i

    for j in range(i + 1, n):
        if (arr[j][0] < arr[min_index][0] or
           (arr[j][0] == arr[min_index][0] and arr[j][1] < arr[min_index][1])):
            min_index = j

    arr[i], arr[min_index] = arr[min_index], arr[i]

for pair in arr:
    print(pair[0], pair[1])
    

TCS NQT Exam 2-Shift Coding Question

Q2. Minimum and Second Minimum Spanning Tree

Problem Statement

You are given an undirected weighted graph representing cities and connections between them.

Your task is to:

1. Find the Minimum Spanning Tree (MST)

• A spanning tree that connects all vertices with minimum total weight.

2. Find the Second Minimum Spanning Tree

• A spanning tree whose total weight is:
• Strictly greater than MST
• Minimum among all such spanning trees

Input Format:

• The first line contains two integers:
• N → number of cities (vertices)
• M → number of connections (edges)
• Next M lines contain:
• u v w → connection between city u and v with weight w

Output Format

• Print two integers:
• MST weight
• Second MST weight

Constraints

• 1 ≤ N ≤ 100
• 1 ≤ M ≤ 1000
• Graph is connected

Example

Input

4 5
1 2 1
1 3 2
2 3 1
2 4 3
3 4 4
    

Output

5 6

Explanation

MST edges:

(1-2 → 1), (2-3 → 1), (2-4 → 3) → Total = 5

Second MST:

Replace one edge → total = 6

Approach

Step 1: Find MST using Kruskal’s Algorithm

• Sort edges by weight
• Use Union-Find (DSU)

Step 2: Find Second MST

For each edge used in MST:

• Remove one edge at a time
• Recompute MST
• Track minimum valid result > MST

Solutions

C++ Solution

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

struct Edge {
    int u, v, w;
};

bool cmp(Edge a, Edge b) {
    return a.w < b.w;
}

vector<int> parent;

int find(int x) {
    if(parent[x] == x) return x;
    return parent[x] = find(parent[x]);
}

void unite(int a, int b) {
    parent[find(a)] = find(b);
}

int kruskal(int n, vector<Edge>& edges, int skip) {
    parent.resize(n + 1);
    for(int i = 1; i <= n; i++) parent[i] = i;

    int cost = 0, count = 0;

    for(int i = 0; i < edges.size(); i++) {
        if(i == skip) continue;

        if(find(edges[i].u) != find(edges[i].v)) {
            unite(edges[i].u, edges[i].v);
            cost += edges[i].w;
            count++;
        }
    }

    return (count == n - 1) ? cost : INT_MAX;
}

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

    vector<Edge> edges(m);

    for(int i = 0; i < m; i++) {
        cin >> edges[i].u >> edges[i].v >> edges[i].w;
    }

    sort(edges.begin(), edges.end(), cmp);

    int mst = kruskal(n, edges, -1);
    int second = INT_MAX;

    for(int i = 0; i < m; i++) {
        int cost = kruskal(n, edges, i);
        if(cost > mst && cost < second) {
            second = cost;
        }
    }

    cout << mst << " " << second;
}
    

Java Solution

import java.util.*;

class Edge {
    int u, v, w;
    Edge(int u, int v, int w) {
        this.u = u; this.v = v; this.w = w;
    }
}

class Main {
    static int[] parent;

    static int find(int x) {
        if(parent[x] == x) return x;
        return parent[x] = find(parent[x]);
    }

    static void unite(int a, int b) {
        parent[find(a)] = find(b);
    }

    static int kruskal(int n, List<Edge> edges, int skip) {
        parent = new int[n + 1];
        for(int i = 1; i <= n; i++) parent[i] = i;

        int cost = 0, count = 0;

        for(int i = 0; i < edges.size(); i++) {
            if(i == skip) continue;

            Edge e = edges.get(i);

            if(find(e.u) != find(e.v)) {
                unite(e.u, e.v);
                cost += e.w;
                count++;
            }
        }

        return (count == n - 1) ? cost : Integer.MAX_VALUE;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int m = sc.nextInt();

        List<Edge> edges = new ArrayList<>();

        for(int i = 0; i < m; i++) {
            edges.add(new Edge(sc.nextInt(), sc.nextInt(), sc.nextInt()));
        }

        edges.sort(Comparator.comparingInt(e -> e.w));

        int mst = kruskal(n, edges, -1);
        int second = Integer.MAX_VALUE;

        for(int i = 0; i < m; i++) {
            int cost = kruskal(n, edges, i);
            if(cost > mst && cost < second) {
                second = cost;
            }
        }

        System.out.println(mst + " " + second);
    }
}
    

Python Solution

class DSU:
    def __init__(self, n):
        self.parent = list(range(n+1))

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, a, b):
        self.parent[self.find(a)] = self.find(b)

def kruskal(n, edges, skip):
    dsu = DSU(n)
    cost = 0
    count = 0

    for i in range(len(edges)):
        if i == skip:
            continue

        u, v, w = edges[i]

        if dsu.find(u) != dsu.find(v):
            dsu.union(u, v)
            cost += w
            count += 1

    return cost if count == n - 1 else float('inf')

n, m = map(int, input().split())
edges = []

for _ in range(m):
    edges.append(tuple(map(int, input().split())))

edges.sort(key=lambda x: x[2])

mst = kruskal(n, edges, -1)
second = float('inf')

for i in range(m):
    cost = kruskal(n, edges, i)
    if mst < cost < second:
        second = cost

print(mst, second)
    

Join our Telegram group: Click Here

Follow us on Instagram: Click Here

Join our WhatsApp group: Click Here

More Latest Off-Campus Hiring 2025 Jobs:

• Accenture New Mass Hiring 2025 – Click Here
• Naukri Campus Hiring Drive Registration –Click Here