JP Morgan hiring for SDE l

2024/2023 passouts

Apply Now:-
https://jpmc.fa.oraclecloud.com/hcmUI/CandidateExperience/en/sites/CX_1001/job/210542790

Infosys exam Answer's

Q1: Two Square minimax

You are given a square grid A of size N x N.

Your want to choose two non-intersecting square sub-grids from the grid such that they have no common row or column The objective is to maximize the sum of beauties of both square sub-grids.

The beauty of a sub-grid is defined as the difference betwee the maximum value and the minimum value within that sub- grid.

tikqupta2s

Find the maximum possible sum of beauties for the sel two sub-grids.

Input Format

The next line contains an integer, N, denoting the number o columns in A.

Each line i of the N subsequent lines (where 0 ≤ i < N) com space separated integers each describing the row A[i].

Constraints

2 <= N <= 250

1 <= A[i][j] <= 10^5

Sample Test Cases

Case 1

Input:

2

23

23

Output:

0

Explanation:

Given N 2, A = [[2, 3], [2, 3]].

We take cell (1, 2) and cell (2, 1) and the answer will be 0

Public class solution {
Public static int get_ans(int N, List<List<Integer>> A}}

1Ans) java code

import java.util.ArrayList;
import java.util.List;

public class Solution {
public static int getAns(int N, List<List<Integer>> A) {
// This will store the maximum beauty sum of two non-intersecting squares
int maxSumOfBeauties = 0;

// Precompute the beauty of all sub-grids for quick lookup
int[][] beauty = new int[N][N];
for (int row = 0; row < N; row++) {
for (int col = 0; col < N; col++) {
// Calculate beauty for sub-grid starting at (row, col)
int minVal = Integer.MAX_VALUE;
int maxVal = Integer.MIN_VALUE;
for (int i = row; i < N; i++) {
for (int j = col; j < N; j++) {
minVal = Math.min(minVal, A.get(i).get(j));
maxVal = Math.max(maxVal, A.get(i).get(j));
beauty[i][j] = maxVal - minVal;
}
}
}
}

// Try all possible pairs of non-intersecting sub-grids
for (int r1 = 0; r1 < N; r1++) {
for (int c1 = 0; c1 < N; c1++) {
for (int r2 = 0; r2 < N; r2++) {
for (int c2 = 0; c2 < N; c2++) {
if (r1 != r2 && c1 != c2) {
// Ensure the sub-grids do not share any rows or columns
int beauty1 = beauty[r1][c1];
int beauty2 = beauty[r2][c2];
maxSumOfBeauties = Math.max(maxSumOfBeauties, beauty1 + beauty2);
}
}
}
}
}

return maxSumOfBeauties;
}

public static void main(String[] args) {
// Example usage:
List<List<Integer>> grid = new ArrayList<>();
grid.add(List.of(2, 3));
grid.add(List.of(2, 3));
int N = 2;
System.out.println(getAns(N, grid)); // Output should be 0
}
}

2Q) You are given a permutation P of length N. This permutation represents a graph of N nodes where for each node i from 1 to N there is an ongoing edge from that node to node P[i].

A permutation is an array of length N, consisting of each of the integers from 1 to N in some order.

The longest path in the graph is the path that satisfies the following conditions: تھا

•⁠ ⁠It starts at some node U and ends at some node V.

It visits each node no more than once.

•⁠ ⁠Among all the possible paths, it's the longest one.

Find the total number of possible pairs of indices of the permutation (i, j), such that:

•⁠ ⁠If P[i] and P[j] are swapped, then the resulting graph has the maximum possible longest path among all the possible swaps.

Since the answer is very large, print it modulo 109+7.

Input Format

The first line contains an integer, N, denoting the number of elements in P.

Each line i of the N subsequent lines (where 0 ≤ i < N) contains an integer describing P[i].

Sample Test Cases

Case 1

Input:

3

1

2

3

Output:

3

Explanation:

Given N 3, P= [1, 2, 3].

Here, if we swap "P[1]" and "P[2]" we will get P = [2, 1, 3]", node "1" can go to node "2" and we can consider that the longest path, and also node "2" can go to node "1", we also can generate the following two permutations:


Case 2

Input:

6

2

3

1

S

6

4

Output:

9

Explanation:

Given N 6, P [2, 3, 1, 5, 6, 4].

Here, we have two cycles, the nodes in the first cycle are "[1, 2, 3]" and the nodes in the second cycle are "[4, 5, 6]".

We can show that if we swap any of the first three elements in the permutation with any element from the last three elements, the cycles will be merged, so the answer is "339".

Case 3

Input:

7

2

3

1

5

4

7

6

Output:

12

Explanation:

Given N 7, P [2, 3, 1, 5, 4, 7, 6].

Here, if we swap any element from the first three elements with any element from the last four elements we'll get a longest path of length "6", and from that the number of swaps to obtain that length (the maximum possible reachable length of the graph) is "3 * 4 = 12".

2Q Ans

3Q) General Ali has devised a strategic game to reduce an enemy army of N soldiers to just 1sdier

The game allows the following three types of moves:

1. Reduce the enemy army by 1 soldier.

2. Reduce the enemy army by half of its current soldiers, rounding down to the nearest integer

3. Reduce the enemy army by two-thirds of its current soldiers, rounding down to the nearest integer

Each move must ensure that the resulting number of soldiers is an integer

Find the minimum number of moves required to reduce enemy army to just 1 soldier

Input Format

The first line contains an integer, N, denoting the number of enemy soldiers.

Constraints

1 <= N <= 10^9

Sample Test Cases

Case 1

Input: 5

Output:

3

Explanation:

Given N 5.

Move 1: Reduce by 1 soldier (5 -> 4)

Move 2: Reduce by half (4-> 2)

Move 3: Reduce by half (21)

Hence, the answer for this case is equal to 3.

Case 2

Input:

1

Output:

e

Explanation:

Given N 1.

There is only 1 soldier already, so to moves are required to reduce the umeny soldiers to

Therefore, the minimum number of noves needed is 8.

3Q Ans

4Q) Handson 1: Array Covered Ranges

You are given an array A of length N.

It is given that the number of covered ranges in the subarray from L to R is defined as the minimum number of ranges, such that the following is true

• All the elements of each range appear as elements of the subarray.

• Each element of the subarray appears in exactly one range where 0 < L, R < N+1.

You have to process Q queries given in a 2D array Queries, where each query contains two integers L and R. For each query, you have to find the number of covered ranges in the subarray from L to R in A.

Find the sum of answers to all queries. Since the answer can be very large, return it modulo 109+7

Input Format

The first line contains an integer, N, denoting the number of elements in A.

Each line i of the N subsequent lines (where 0 ≤ i< N) contains an integer describing Ali)

The next line contains an integer, Q, denoting the number of rows in queries.

The next line contains an integer, two, denoting the number of columns in queries.

Each line i of the Q subsequent lines (where 0 ≤ i < Q) contains two space separated integers each describing the row queries[i].

Constraints

1 <= N <= 10 ^ 6

1 <= A[i] <= 10 ^ 6

1 <= Q <= 10 ^ 6

2 <= two <= 2

1 <= queries[i][j] <= N

Sample Test Cases

Case 1

Input:

1

1

1

2

11

P

Output:

1

Explanation:

Given N = 1 A = [1] Q = 1 two = 2, Queries - [[1, 1]] .

The number of covered ranges in (1) is 1 (the range is [1, 1]).

Hence, the sum of answer of queries is equal to 1.

Case 2

Input:

2

1

3

2

2

11

12

Output:

3

Explanation:

Given N = 2 A = [1, 3] Q = 2 two 2, Queries [[1, 1], [1, 2]].
The number of covered ranges in (1) is 1 in range [1, 1], while the number of covered ranges in (1, 3} is 2 in range [1, 2].

Hence, the sum of answer of queries is equal to 3.

Case 3

Input:

2

1

2

2

2

11

12

Output:

2

Explanation:

Given N = 2 A = [1, 2] Q = 2 two. 2, Queries [ [1, 1] [1, 2]].

The number of covered ranges in both (1) and (1, 2} is 1 in range [1, 1] and [1, 2] respectively.

Hence, the sum of answer of queries is equal to 2.

5Q) string trimmetris

Int get ans

// write your code here

18 11 J

13

14

16

30

int meint) (

Insyrm with stateles cin.tiele); cout 10 (8)

string inutise

Test case
HandsOnSquares Beauty

Summary

Questions

You me quen a square grid A of

You want to choose two non intersecting apuate sob-grids with no common row or column such that the sum of both sub grids is maximized.

Return the maximum possible sum

Input Format

The next line contains an integer. 4. denoting the number of columns in A

Each line i of the N subsequent lines (where N) contains N space separated integers each describing the row Ali

Constraints

1N500

-100 <= A[i][j] <= 100

6Q) You are given an integer N and a number

Let's define the cost of a string consisting of lowercase Latin letters as the cyelle distance between any two consecutive characters in that string,

Vadlaa

= Questions

For example, the cost of the string "abzy"

can be calculated as follows:

Minimum Cyclic Distance(a, b) + Minimum Cyclic Distance(b, z) +

Minimum CyclicDistance(z, v) = 1 + 2 + 4 = 7.

It is given that two strings of length N are different if their characters differ in at least one position from 1 to N.

Find the number of the distinct strings $ which satisfies the following two conditions

• The length of S is exactly equal to N.

• The cost of S is divisible by • The length of S is exactly equal to N.

The cost of S is divisible by K. vadlaa

Since the answer can be very large, print it modulo 109+7.

Input Format

The first line contains an N. denoting integ N the length of the required string.

The next line contains an integer, K. denoting the given number K.

Error

Constraints

2 <= N <= 10^5
.1 <= K <= 100

Sample Test Cases

Case 1

Input:

2

2

Output:

338

Explanation:

Given N= 2, K=2

In this case, one of the possible strings is "ac", also "ce". We can show that there are exactly "338" strings that satisfy the conditions.

So, answer is 338.

7Q) you are given a string S with N characters a string T with M characters and an integer K
you can perform the following operation on s atmost K times
change a character at some index in the string to any other character
find the count of maximum number of subsegments in the S that have T as subsequence after applying the operation
Sample input
3
1
1
abc
d

sample output
1

explanation
Given N=3 M=1 K=1 S=abc T=d
we can change s[1] to d and the ans will be 1
give a code such that output for the given input is 1
sample input 2
3
1
1
abc
b

sample output 2
2