InfyTQ Advantage Coding Round Question 2022-21

InfyTQ Advantage Round Coding
Question with Solutions PDF 2022-21

Infosys conducts its Infosys Competition Test through InfyTQ. In this test there are 2 different rounds, i.e; Qualifying round and Final round, if you clear both the round successfully then you get the chance to sit in the Advantage round, clearing which you get a pretty good raise in your offer. The difficulty level of this round is very high then the other rounds

InfyTQ Advantage Round coding questions 2022-21

Pattern for InfyTQ Advantage Round

  • There will be 3 coding questions in this round, with varied difficulty level.
  • Each question will have a different weight-age of marks, depending upon the difficulty level of that question.
  • You will be able to solve the questions only either in Java or Python, depending upon the language that you would have chosen at the time of booking the slots.
  • Clearing the Advantage round will give you a chance for a pre-replacement interview either for the post of Power Programmer or System Engineer Specialist based on their performance in the interview.

Detailed analysis for InfyTQ Advantage Coding Round

TopicsNo. of Questions
Number of Questions2
Time Limit2 hrs(combined with MCQ)
Difficulty levelvery high
Package Offered5 LPA – 7.5 LPA

InfyTQ Practice Coding Questions

Question 1: TOR

Problem Statement-: Lets define Ternary numbers to be the positive integer numbers that consist of digits 0,1,2 only. Let’s also define the operation TOR(x,y) to be the following operation on two Trenary numbers x and y (its output is z = TOR(x,y)).

  1. Go through the digits one by one .
  2. For each digit i, the digit i in the output will be z[i] = (x[i] + y[i]) % 3

You are given a positive integer n, and a long positive integer c, your job is to find two Ternary   numbers a,b (of length n) where c = TOR(a,b) and max(a,b) is as minimum as possible. After finding that pair output max(a,b). If there’s no such pair, output -1.

 

  • Note 1: the given numbers won’t have any leading zeros.
  • Note 2: a,b should be of length n without leading zeros.
  • Note 3: since the answer can be very large, output it modulo 1000000007 (10^9 +7).

 

Function Description:

Complete the TOR function in the editor below. It has the following parameters(s):

Parameters:

NameTypeDescription
nintegerThe length of a and b
cstringThe number which should satisfy the equation c=TOR(a,b).

The function must return an INTEGER denoting the max(a,b) when it’s minimized.

 

Constraints: 

  • 1 <= n <=  10^5
  • 1 <=  len(c) <= 2*n

 

Input Format

  • The first line contains an integer, n, denoting the length of a and b .
  • The next line contains a string, c, denoting the number which should satisfy the equation c=TOR(a,b).

 

Sample Cases:

  • Sample input 1  
    2                                            
    22
  • Sample output
    11
#include <bits/stdc++.h>
using namespace std;
string s;
int n;
bool ch;
int fun(int i,int num)
{
if(i==s.length()) return num;//cout<<num<<endl;
if(ch) return fun(i+1,num*10);

if(s[i]=='0') return fun(i+1,num*10);
if(s[i]=='2') return fun(i+1,num*10 + 1);

if(i==0) return fun(i+1,2);
ch=true;
return fun(i+1,num*10+1);

}

int main()
{
cin>>n;
ch=false;
cin>>s;
cout << fun(0,0)%1000000007;
}
ch=False
n=int(input())
s=input()
def fun(i,num,ch):
if i==n:
return num
if ch:
return fun(i+1,num*10,ch)
if s[i]=='0':
return fun(i+1,num*10,ch)
if s[i]=='2':
return fun(i+1,num*10+1,ch)
if i==0:
return fun(i+1,2,ch)
ch=True
return fun(i+1,num*10+1,ch)

print(fun(0,0,ch))

Question 2 : Special LIS

Problem statement-:  Given an array of N integers. Find the length of the longest increasing subsequence such that the difference between adjacent elements of the longest increasing subsequence is also increasing.

Note: It’s not required that the sequence should have strictly increasing numbers and the differences are also not required to be strictly increasing.

Ex: [1,2,3,4,5]. The longest increasing subsequence will be [1,2,4,5] but the difference array in this case is [1,2,1] which is not increasing. If we consider [1,2,4] or [1,2,5] then the numbers as well as the differences are in increasing order.

Function Description:

Complete the specialLIS function in the editor below. It has the following parameter(s):

Parameters:

NameTypeType
sizeIntegersize of array
arrInteger arrayarray

Return:

The function must return an INTEGER denoting the length of the longest increasing sub sequence with increasing differences.

Constraints:

  • 1 <= size <= 500
  • 1 <= arr[i] <= 10^5

Input Format:

  • The first line contains integer, size, denoting the size of the array.
  • Each line i of the size subsequent lines (where 0 <= i < size) contains an integer describing the ith elements of the array.

Sample Cases

  • Sample Input 1
    5
    1
    2
    3
    4
    5

 

  • Sample Output 1
    5
#include <bits/stdc++.h>
using namespace std;
int n;
map<int,map<int,map<int,map<int,int>>>> m;

int fun(int i,int le,int d,int i1,vector<int> a)
{
if(m[i][le][d][i1]) return m[i][le][d][i1];
if(i==n) return m[i][le][d][i1]=le;
if(le==0) return m[i][le][d][i1]=max(fun(i+1,1,0,i,a),fun(i+1,0,0,i+1,a));
if(a[i]-a[i1]>=d) return m[i][le][d][i1]=max(fun(i+1,le+1,a[i]-a[i1],i,a),fun(i+1,le,d,i1,a));

return m[i][le][d][i1]=fun(i+1,le,d,i1,a);
}

int main()
{
cin>>n;
vector<int> a(n);
for(int i=0;i<n;i++) cin>>a[i];

cout<<fun(0,0,0,0,a);
}
n=int(input())
a=[]
for i in range(n):
a.append(int(input()))

dp=[[[[-2 for i in range(n+1)] for j in range((max(a)-min(a)+2))] for k in range(n+1)] for l in range(n+1)]

def answer(i,le,d,i1):
if dp[i][le][d][i1]!=-2:
return dp[i][le][d][i1]
if i==n:
dp[i][le][d][i1]=le
return dp[i][le][d][i1]

else:
if le==0:
dp[i][le][d][i1] = max(answer(i+1,1,0,i),answer(i+1,0,0,i+1))
return dp[i][le][d][i1]
else:
if (a[i]-a[i1])>=d:
dp[i][le][d][i1]= max(answer(i+1,le+1,(a[i]-a[i1]),i),answer(i+1,le,d,i1))
return dp[i][le][d][i1]
else:
dp[i][le][d][i1]= answer(i+1,le,d,i1)
return dp[i][le][d][i1]

print(answer(0,0,0,0))

Question 3: Alisa In the Library

Problem Statement -:  Alisa is in the library, she wants to buy some different books, there are “nm” different chemistry books and k different science books. In how many different ways can Alisa select a book of mathematics, two books of chemistry, and some books of science?

Function Description:

  • Complete the books function in the editor below. It has the following parameter(s):

Parameters:

NameTypeDescription
nIntegerthe number of mathematics books
mIntegerthe number of chemistry books
kIntegerthe number of science books
xIntegerthe number of books of science Alisa needs

Return: The function must return an INTEGER denoting the number of ways Alisa can buy the books she needs.

Constraints:

  • 1 <= n <= 10^6
  • 1 <= m <= 10^6
  • 1 <= k <= 10^6
  • 1 <= x <= 10^6

Input Format:

  • The first line contains an integer, n, denoting the number of mathematics books.
  • The next line contains an integer, m, denoting the number of chemistry books.
  • The next line contains an integer, k, denoting the number of science books.
  • The next line contains an integer, x, denoting the number of books of science Alisa needs.

OUTPUT DESCRIPTION

We have 5 different mathematics books, four different chemistry books, and two different science books which we have to choose all of them (d=2) so, we can choose 1 book out of five mathematics books in 5 ways, 2 out of 4 chemistry books in 6 ways, and we have only one way to choose 2 out of 2 science books, total: 5*6*1 = 30 ways. 

Sample Test Cases

  • Sample Input 1
    5
    4
    2
    2
  • Sample Output 1
    30
#include <bits/stdc++.h>
using namespace std;
int comb(int c,int d,int cc,int dd)
{
if(d==1) return cc*c/dd;
return comb(c-1,d-1,cc*c,dd*d);
}

int main()
{
int a,b,c,d;
cin>>a>>b>>c>>d;
if(a<1||b<2||c<d) {cout<<0;return 0;}
int ans=1;
ans*=a;
ans=ans*b*(b-1)/2;
ans*=comb(c,d,1,1);
cout<<ans;
}
def comb(c,d,cc,dd):
if d==1:
return cc*c//dd
return comb(c-1,d-1,cc*c,dd*d)

a=int(input())
b=int(input())
c=int(input())
d=int(input())
if a<1 or b<2 or c<d:
print(0)
else:
ans=1
ans*=a
ans=ans*b*(b-1) // 2
ans*=comb(c,d,1,1)
print(ans)

Question 4: Palindromic Paths

Problem Statement-:  You are given a grid of size of N*M (1-based indexing). Each cell in the grid contains a lower case English alphabet (a-z). You have to replace some letters of the grid such that any path from (1,1) to (N,M) is a palindromic path. A path is palindromic if the string obtained by joining letters from the corresponding cells of a traversed path is a palindrome i.e. reads the same forward and backward. You are only allowed to move Right or Down in the grid.

Calculate the minimum number of letters that you need to replace such that any valid path from (1,1) to (N,M) is palindromic.

 

Function Description:

Complete the palindromicPaths function in the editor below. It has the following parameter(s):

Parameters:

NameTypeDescription
nIntegerNumber of rows in the grid
mIntegernumber of columns in the grid
gridstring 2D arraythe given grid

Return: The function must return an integer denoting the minimum number of letters.

 

Constraints:

  • 1 <= N <= 10^3
  • 1 <= M <= 10^3
  • a <= grid[i][j] <= z

 

Input format for Custom Testing:

  • The first line contains an integer, N, denoting the number of rows in the grid.
  • The next line contains an integer, M, denoting the number of columns in the grid.
  • Each line i of the N subsequent lines (where 0 <= i <N) contains a string of lower-case English Alphabets of size M.

Sample Test Cases

  • Sample Input
    2
    2
    ac
    bc
  • Sample Output
    1
  • Explanation
    Change the letter at (2,2) to ‘a’, such that both paths become palindromes.
    Path1: (1,1) -> (1,2) -> (2,2)
    Path2: (1,1) -> (2,1) -> (2,2)

 

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

int func(vector<vector<int>> mat)
{
int ans=0;
int n=mat.size(),m=mat[0].size();
map<int,map<int,int>> mp;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
{
int ind =i+j;
mp[ind][mat[i][j]]++;
}

int r=m+n-2,l=0;
while(l<r)
{
int t=0,mx=0;
for(auto x:mp[r])
{
mp[l][x.first]+=x.second;
}
for(auto x:mp[l])
{
t+=x.second;
mx=max(x.second,mx);
}
ans+=t-mx;
l++;
r--;
}
return ans;
}

int main()
{
int N,M;
string s;
cin>>N>>M;
vector<vector<int>> mat(N,vector<int>(M));
for(int i=0;i<N;i++)
{
cin>>s;
for(int j=0;j<M;j++)
mat[i][j]=s[j]-'a';
}
cout<<func(mat);

}
def m(lis,n):
d1=dict()
for i in lis:
if i in d1:
d1[i]+=1

else:
d1[i]=1

m1=0
for i in d1:
m1=max(m1,d1[i])

return (n-m1)

r=int(input())
c=int(input())
a=[]
for i in range(r):
b=list(input())
a.append(b)

d=dict()

t=r+c-2
d=dict()
for i in range(r):
for j in range(c):
t1=min((i+j),(t-(i+j)))
if t1 in d:
d[t1].append(a[i][j])

else:
d[t1]=[a[i][j]]

ans=0
for i in d:
if (i*2)!=t:
lis=d[i]
n=len(d[i])
ans+=m(lis,n)

print(ans)

Question 5: Divisible by K

Problem Statement-: Alice has a non-negative integer x written in the base y (a numeral system where 2 <= y <= 16). The number x has distinct digits. Bob has a number k written in the decimal numeral system. Alice wanted to check if the number x is divisible by the number k. However, Bob thinks it’s a very easy task. That’s why he proposed another problem: count the number of permutations of x which result in a number divisible by k.

Alice is confused and doesn’t know how to solve Bob’s problem, can you help her?

 

Notes:

  1. y is given in decimal.
  2. The possible digits for x start with the usual digits (0-9), and then with the letters (A – F), depending on the value of y. For example, if y = 12 then the digits are [0,1,… 9, A, B]. Also when y = 3, the possible digits are [0,1,2].
  3.  Since x may contain letters, it’s inputted as a string.
  4.  It’s guaranteed that the number x is a valid number in the base y, and that it doesn’t contain leading zeroes.
  5. Since the final answer can be very large, output it modulo 1000000007 (10^9+7).

 

Function Description:

Complete the divisible_k function in the editor below. It has the following parameter(s):

Parameters:

NameTypeDescription
yIntegerthe base which x is written in
kIntegerthe number which bob has
xStringAlice number written in the base y

Return: The function must return an INTEGER denoting the number of permutations of x which result in a number divisible by k.

 

Constraints:

  • 1 <= y <= 16
  • 1 <= k <= 20
  • 1 <= len(x) <= y

 

Input Format for custom testing:

  • The first line contains an integer, y, denoting the base which x is written in.
  • The next line contains an integer, k, denoting the number which Bob has.
  • The next line contains a string, x, denoting Alice’s number written in the base y.

 

Sample Cases:

  • Sample Input 1
    5
    4
    24
  • Sample Output 1
    0
  • Explanation
    24 in base 5, is 14 in decimal. 42 in base 5, is 22 in decimal. For in both cases the number is not divisible by 4. So the answer is 0
#include <bits/stdc++.h>
using namespace std;

int main()
{
int y,k,m,ans=0;
string s;
cin>>y>>k>>s;
sort(s.begin(),s.end());
m=stoull(s,0,y);
if(m%k==0) ans++;
while(next_permutation(s.begin(),s.end()))
{
m=stoull(s,0,y);
if(m%k==0) ans++;
}
cout<<ans;
}
from itertools import permutations 
y=int(input())
k=int(input())
s=input()
ans=0

p=permutations(s)
L=set(p)
pp=list(L)
for i in list(pp):
a=''.join(i)
aa=int(a,y)
if aa%k==0:
ans+=1

print(ans)