2024_Infosys_MRECW_Power_Programmer_Test 1

Test Summary
 No. of Sections: 2
 No. of Questions: 3
 Total Duration: 90 min
Section 1 - Coding
Section Summary
 No. of Questions: 2
 Duration: 60 min
Additional Instructions:
None
Q1.
Problem Statement

There are N people standing in a circle waiting to be executed. The counting out begins at some
point in the circle and proceeds around the circle in a fixed direction. In each step, a certain
number of people are skipped and the next person is executed. The elimination proceeds around
the circle (which is becoming smaller and smaller as the executed people are removed), until
only the last person remains, who is given freedom.

Given the total number of persons N and a number k which indicates that k-1 persons are
skipped and the kth person is killed in a circle. The task is to choose the person in the initial
circle that survives.

Example 1

Input:
N = 5 and k = 2

Output:
3

Explanation:
Firstly, the person at position 2 is killed, then the person at position 4 is killed, then the person at
position 1 is killed.
Finally, the person at position 5 is killed. So the person at position 3 survives.

Example 2

Input:
N = 7 and k = 3

Output: 4
Explanation:
The persons at positions 3, 6, 2, 7, 5, and 1 are killed in order, and the person at position 4
survives.
Input Format
The input consists of two integers, representing the value of n, followed by the value of k,
separated by space.
Output Format
The output prints the person in the initial circle that survives.

Refer to the sample output for the formatting specifications.

Constraints
N, k > 0
Sample Input Sample Output
5 2 3
Sample Input Sample Output
7 3 4
Sample Input Sample Output
7 3 4
Time Limit: - ms Memory Limit: - kb Code Size: - kb

Q2.
Problem Statement

Write a program to find the longest substring with k distinct vowels.

Example:

Input:
artyebui
2

Output:
6

Explanation: The longest substring with only two vowels is "rtyebu" and its length is 6.
Input Format
The first line contains the string s.
The second line contains the integer k.
Output Format
The output displays a single integer representing the length of the longest substring that contains
exactly k distinct vowels. If no such substring exists, output -1.

Refer to the sample output for the formatting specifications.

Constraints
 1 <= |s| <= 10^5 where |s| is the length of the string.
s contains only alphabetic characters (both uppercase and lowercase).
0 <= k <= 5.
Sample Input Sample Output
tHeracEBetwEEntheTwo
1 7
Sample Input Sample Output
string
1 6
Sample Input Sample Output
bcdfghjklmnpqrstvwxyz
1 -1
Sample Input Sample Output
artyebui
2 6
Time Limit: 10 ms Memory Limit: 256 kb Code Size: 1024 kb

Section 2 - Additional Coding

Section Summary
 No. of Questions: 1
 Duration: 30 min
Additional Instructions:
None
Q1.
Problem Statement:

Given an array of integers, find the inversion count in the array.

Inversion Count: For an array, the inversion count indicates how far (or close) the array is from
being sorted. If the array is already sorted, then the inversion count is 0. If an array is sorted in
reverse order, then the inversion count is the maximum.
Formally, two elements a[i] and a[j] form an inversion if a[i] > a[j] and i < j.

Example 1:
Input:
N = 5, arr[] = {2, 4, 1, 3, 5}
Output:
3
Explanation:
Sequence 2, 4, 1, 3, and 5 has three inversions (2, 1), (4, 1), and (4, 3).

Example 2:
Input:
N=5
 arr[] = {2, 3, 4, 5, 6}
Output:
0
Explanation:
As the sequence is already sorted, there is no inversion count.

Example 3:
Input:
N = 3, arr[] = {10, 10, 10}
Output:
0
Explanation:
As all the elements of the array are the same, there is no inversion count.
Input Format
The first line of the input is the size of the array.
The second line of the input is the list of space-separated integer values.
Output Format
The output is the inversion count in the array.
Constraints
1 ≤ N ≤ 5*105
1 ≤ arr[i] ≤ 1018
Sample Input Sample Output
5
2 4 1 3 5 3
Sample Input Sample Output
5
2 3 4 5 6 0
Sample Input Sample Output
3
10 10 10 0
Time Limit: - ms Memory Limit: - kb Code Size: - kb

Answer Key & Solution

Section 1 - Coding

Q1Test Case

Input Output
10 4 5

Weightage – 10

Input Output
16 1 16
 Weightage – 10

Input Output
18 4 9

Weightage – 15

Input Output
22 7 17

Weightage – 25

Input Output
18 3 14

Weightage – 25

Input Output
10 5 3

Weightage – 15

Sample Input Sample Output

5 2 3

Sample Input Sample Output

7 3 4

Solution
#include <stdio.h>
int josephus(int n, int k)
{
if (n == 1)
return 1;
else
return (josephus(n - 1, k) + k-1) % n + 1;
}
int main()
{
int n,k;
scanf("%d%d",&n,&k);
 printf("%d",josephus(n, k));
return 0;
}

Q2Test Case

Input Output
uhtionbgfd
2 9

Weightage – 15

Input Output
redtuni
1 4

Weightage – 10

Input Output
mkihgtd
1 7

Weightage – 10

Input Output
americabhu
2 6

Weightage – 15

Input Output
nihbdtctwwbt
2 -1

Weightage – 25

Input Output
tHeracEBetwEEnthinyf
2 11
 Weightage – 25

Sample Input Sample Output

tHeracEBetwEEntheTwo
1 7

Sample Input Sample Output

string
1 6

Sample Input Sample Output

bcdfghjklmnpqrstvwxyz
1 -1

Sample Input Sample Output

artyebui
2 6

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

#define MAX 128

// Function to check whether a character is

// vowel or not
bool isVowel(char x)
{
return (x == 'a' || x == 'e' || x == 'i' ||
x == 'o' || x == 'u' || x == 'A' ||
x == 'E' || x == 'I' || x == 'O' ||
x == 'U');
}

int KDistinctVowel(string s, int k)

{
// length of string
int n = s.length();

// array for count of characters

int c[MAX];
memset(c, 0, sizeof(c));

// Initialize result to be
// negative
int result = -1;
 for (int i = 0, j = -1; i < n; ++i) {

int x = s[i];

if (isVowel(x)) {
if (++c[x] == 1) {

// Decrementing the K value

--k;
}
}

while (k < 0) {

x = s[++j];
if (isVowel(x)) {
if (--c[x] == 0) {
++k;
}
}
}

if (k == 0)
result = max(result, i - j);
}
return result;
}

// Driver code
int main()
{
string s;
int k;

getline(cin, s);

cin >> k;

cout << KDistinctVowel(s, k);

return 0;
}
 Section 2 - Additional Coding

Q1Test Case

Input Output
10
1 5 4 7 85 6 3 2 1 5 4 24

Weightage – 10

Input Output
15
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 0

Weightage – 30

Input Output
15
23 56 98 75 14 27 65 45 89 20 56 47 55 66 33 52

Weightage – 30

Input Output
10
66 55 44 77 88 99 11 22 33 89 22

Weightage – 20

Input Output
5
11 15 65 87 25 2

Weightage – 10

Sample Input Sample Output

5
2 4 1 3 5 3
 Sample Input Sample Output
5
2 3 4 5 6 0

Sample Input Sample Output

3
10 10 10 0

Solution
import java.util.*;
import java.io.*;
import java.lang.*;
public class Main
{
public static void main (String[] args)
{
Scanner sc = new Scanner(System.in);
long n = sc.nextLong();
long arr[] = new long[(int)n];

for(long i = 0; i < n; i++)

arr[(int)i] = sc.nextLong();

System.out.println(new Sort().inversionCount(arr, n));

}
}
//User function Template for Java
class Sort
{
static long count=0;
static long inversionCount(long a[], long N){
int n=(int)N;
long ct=count;
mergeSort(a,0,n-1);
return count-ct;
}
public static long[] mergeSort(long[] a, int low, int high){
if(low==high){
long[] single=new long[1];
single[0]=a[low];
return single;
}
int mid=(low+high)/2;
long[] left=mergeSort(a,low,mid);
long[] right=mergeSort(a,mid+1,high);
long[] merged=merge2SortedArrays(left,right);
return merged;
}
public static long[] merge2SortedArrays(long[] left, long[] right){
int i=0,j=0,k=0;
 long[] merging=new long[left.length+right.length];
while(i<left.length && j<right.length){
if(left[i]<=right[j]){
merging[k]=left[i];
i++;
k++;
}
else{
count+=left.length-i;
merging[k]=right[j];
j++;
k++;
}
}
while(i<left.length){
merging[k]=left[i];
i++;
k++;
}
while(j<right.length){
merging[k]=right[j];
j++;
k++;
}
return merging;
}
}