InfyTQ Final round Coding Questions

InfyTQ Final Round Coding Questions 2022

InfyTQ Final Round Coding Questions and Solutions 2022-21

Infosys Competition test has two rounds.

  • Qualifier Round
  • Final Round

The first round is the qualifier round which consists of mcq questions and the second round is the final round which consists of domain specific mcq questions and coding questions. Clearing this round will get you placed in Infosys at a package of 3.5LPA to 4LPA. The difficulty level of Final Round of Infytq is higher than the qualifier round.

Pattern analysis for InfyTQ Final Round

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

InfyTQ Final Round Practice Coding Questions for Freshers

Question 1: Four in a line

Problem Statement -: Given a m x n matrix inmatrix of positive integers, print an integer outnum based on the below logic: 

  • Identify all possible sets in inmatrix that contain at least four consecutive elements of the same value val, either horizontally, vertically, or diagonally 
  • If only one set of consecutive elements is identified, store the value val in outnum 
  • If more than one set of consecutive elements is identified, find the smallest value and store it in outnum 
  • If no set of four consecutive elements of the same value is identified either horizontally, vertically, or diagonally, print -1 

Assumption: 

  • m and n will be greater than 3 

Input format: 

  • First line will contain number of rows m of inmatrix
  • The next m lines will contain the elements of inmatrix. Each line will have n elements separated by space.
  • Read the input from the standard input stream. 

Output format: 

  • Print outnum to the standard output stream. 

 

  • Sample Input 1
    5
    0 1 6 8 8 9
    5 6 1 6 8 9 
    6 5 6 1 1 9
    1 6 6 1 1 9
    6 3 3 3 3 9
  • Sample Output 1
    1
  • Explanation 1
    Following elements are present consecutively at least four times: Element 3 horizontally in the 5th row. Element 1 diagonally starting from the 2nd column in the first row. Element 6 diagonally starting from the 4th column in the second row. Element 9 vertically in the 6th column. As element 1 is the smallest value of the four identified sets of consecutive values, the output is 1  



  • Sample input 2
    5
    0 1 6 8 6 0
    5 5 2 1 8 2
    6 5 6 1 1 9
    1 5 6 1 4 0
    3 7 3 3 4 0 
  • Sample Output 2
    -1
  • Explanation 2
    Here there are no sets of four consecutive elements of the same value either horizontally, vertically,or diagonally  hence output is -1
#include <bits/stdc++.h>
using namespace std;

int main()
{
int m,ans=INT_MAX,I=-1,J=-1;
cin>>m;
vector<vector<int>> mat(m,vector<int>());
cin.ignore();
for(int i=0;i<m;i++)
{
string s;
getline(cin,s);
istringstream ss(s);
while(ss)
{
string w;
ss>>w;
if(w=="") break;
mat[i].push_back(stoi(w));
}
}
int n=mat[0].size();
vector<vector<int>> Ans1(m,vector<int>(n,1));
vector<vector<int>> Ans2(m,vector<int>(n,1));
vector<vector<int>> Ans3(m,vector<int>(n,1));
vector<vector<int>> Ans4(m,vector<int>(n,1));

for(int i=0;i<m-1;i++)
for(int j=0;j<mat[i].size();j++)
if(mat[i][j]==mat[i+1][j])
Ans1[i+1][j]=Ans1[i][j]+1;

for(int i=0;i<m;i++)
for(int j=0;j<mat[i].size() -1;j++)
if(mat[i][j]==mat[i][j+1])
Ans2[i][j+1]=Ans2[i][j]+1;

for(int i=0;i<m-1;i++)
for(int j=0;j<mat[i].size()-1;j++)
if(mat[i][j]==mat[i+1][j+1])
Ans3[i+1][j+1]=Ans3[i][j]+1;

for(int i=0;i<m-1;i++)
for(int j=1;j<mat[i].size();j++)
if(mat[i][j]==mat[i+1][j-1])
Ans4[i+1][j-1]=Ans4[i][j]+1;

for(int i=0;i<m;i++)
for(int j=0;j<mat[i].size();j++)
{
if(Ans1[i][j]>=4 && ans>mat[i][j])
{ans=mat[i][j];I=i;J=j;}
if(Ans2[i][j]>=4 && ans>mat[i][j])
{ans=mat[i][j];I=i;J=j;}
if(Ans3[i][j]>=4 && ans>mat[i][j])
{ans=mat[i][j];I=i;J=j;}
if(Ans3[i][j]>=4 && ans>mat[i][j])
{ans=mat[i][j];I=i;J=j;}
}
if(I==-1)cout<<-1;
else cout<<ans<<endl;

}
r=int(input())
a=[]
for i in range(r):
b=list(map(int,input().split()))
a.append(b)

c=len(a[0])
ans=set()
i=0
while i<r:
j=0
while j<(c-3):
if a[i][j]==a[i][j+1] and a[i][j]==a[i][j+2] and a[i][j]==a[i][j+3]:
ans.add(a[i][j])
j+=4

else:
j+=1

i+=1

j=0
while j<c:
i=0
while i<(r-3):
if a[i][j]==a[i+1][j] and a[i][j]==a[i+2][j] and a[i][j]==a[i+3][j]:
ans.add(a[i][j])
i+=4

else:
i+=1

j+=1

for i in range(r):
i1=i
j=0
while (i1+3)<r and (j+3)<c:
if a[i1][j]==a[i1+1][j+1] and a[i1][j]==a[i1+2][j+2] and a[i1][j]==a[i1+3][j+3]:
i1+=4
j+=4
ans.add(a[i1][j])

else:
i1+=1
j+=1

for j1 in range(1,c):
j=j1
i1=0
while (i1+3)<r and (j+3)<c:
if a[i1][j]==a[i1+1][j+1] and a[i1][j]==a[i1+2][j+2] and a[i1][j]==a[i1+3][j+3]:
ans.add(a[i1][j])
i1+=4
j+=4

else:
i1+=1
j+=1

for i in range(r):
i1=i
j=(c-1)
while (i1+3)<r and (j-3)>=0:
if a[i1][j]==a[i1+1][j-1] and a[i1][j]==a[i1+2][j-2] and a[i1][j]==a[i1+3][j-3]:
i1+=4
j-=4
ans.add(a[i1][j])

else:
i1+=1
j-=1

for j1 in range(c-2,-1,-1):
j=j1
i1=0
while (i1+3)<r and (j-3)>=0:
if a[i1][j]==a[i1+1][j-1] and a[i1][j]==a[i1+2][j-2] and a[i1][j]==a[i1+3][j-3]:
ans.add(a[i1][j])
i1+=4
j-=4

else:
i1+=1
j-=1

if len(ans)>=1:
print(min(ans))

else:
print(-1)

Question 2 : Identify Palindrome

Problem Statement-: For a given positive number num, identify the palindrome formed by performing the following operations-

  • Add num and its reverse 
  • Check whether the sum is palindrome or not. If not, add the sum and its reverse and repeat the process until a palindrome is obtained 

For example: 

If original integer is 195, we get 9,339 as the resulting palindrome after the fourth addition: 

   195

+ 591

————–

   786

+ 687

————–

   1473

+ 3741

————–

   5214

+ 4125

———-

  9339

Input format: 

  • Read num from the standard input stream. 

Output format: 

  • Print the palindrome calculated to the standard output stream. 

Sample Test Cases

  • Sample Input 1
    124 

  • Sample Output 1
    545 

  • Explanation 1
    The sum of 124 and its reverse 421 is 545 which is a palindrome. 

 

 

  • Sample input 1
    4

  • Sample output 1
    8

  • Explanation 1
    The sum of 4 and its reverse 4 is 8 which is a palindrome.
#include <bits/stdc++.h>
using namespace std;

string Add(string s1,string s2)
{
int i=stoi(s1)+stoi(s2);
return to_string(i);
}

string rev(string s)
{
reverse(s.begin(),s.end());
return s;
}

bool Palindrome(string s1)
{
return s1==rev(s1);
}

int main()
{
string s;
cin>>s;
while(1)
{
string s1=Add(s,rev(s));
//cout<<s1<<endl;
if(Palindrome(s1)){cout<<s1;return 0;}
s=s1;
}
}
def isPalindrome(n):
return str(n)[::-1]==str(n)
def rev(n):
return int(str(n)[::-1])
n=int(input())
while(1):
n=n+rev(n)
if(isPalindrome(n)):
print(n)
break

Question 3: Minimum Withdrawals

Problem Statement-: There is a unique ATM in Wonderland. Imagine this ATM as an array of numbers. You can withdraw cash only from either ends of the array. Sarah wants to withdraw X amount of cash from the ATM. What is the minimum number of withdrawals Sarah would need to accumulate X amount of cash. If it is not possible for Sarah to withdraw X amount, return -1. 

Input Format 

  • The first line contains an integer, N, denoting the number of elements in ATM. 
  • Each line i of the N subsequent lines (where 0 <= i < N) contains an integer describing the cash in the ATM. 
  • The next line contains an integer, X, denoting the total amount to withdraw. 

Constraints 

  • 1 <= N <= 10^5 
  • 1 <= ATM [i] <= 10^5 
  • 1 <= X <= 10^5 

Sample Test Cases

  • Sample Input
    2
    1
    1
  • Sample Output
    -1 
  • Explanation
    The total amount of cash in the ATM is 2, hence Sarah cannot withdraw an amount of 3.
#include <bits/stdc++.h>
using namespace std;
int l;

int fun(int s,int e,int k,vector<int> a)
{
if(k==0) return 0;
if(s>e || k<0) return l;
return min(1+fun(s+1,e,k-a[s],a),1+fun(s,e-1,k-a[e],a));
}

int main()
{
int n;cin>>n;
vector<int> a(n);
for(int i=0;i<n;i++) cin>>a[i];
l=pow(10,9);
int k;cin>>k;
int kk=fun(0,n-1,k,a);
if(kk>=l){cout<<-1;}
else cout<<kk;
}
n=int(input())
a=[]
for i in range(n):
a.append(int(input()))

def answer(s,e,k):
if k==0:
return 0

if s>e or k<0:
return 10**9

else:
return min(1+answer(s+1,e,k-a[s]),1+answer(s,e-1,k-a[e]))

k=int(input())
k1=answer(0,n-1,k)
if k1>=(10**9):
print(-1)

else:
print(k1)

Question 4: Team Division

Problem Statement -: Consider an array inarr containing at least two non-zero positive integers ranging between 1 to 300 (inclusive of the boundary values). Divide the integers in inarr into two groups based on the below rules:

  1. Each of the integers should belong to either of the two groups
  2. The total sum of integers in each of the groups must be as nearly equal as possible
  3. The total number of integers between the two groups should not differ by more than 1

Print, outnum1 and outnum2, the sum of the integers of two groups separated by a space. If outnum1 and outnum2 are not equal, then print the smaller sum followed by the larger sum.

Input Format:

  • Read the array inarr elements separated by (‘,’) comma.
  • Read the input from the standard input stream.

Output Format:

  • Print outnum1 and outnum2 in the required order separated by a space.
  • Print the output to the standard output stream.

 

Sample Test Cases

  • Sample Input
    87,100,28,67,68,41,67,1

  • Sample Output
    229 230

 

Explanation

For the given input, the two groups that can be formed following the mentioned rules are:

  1. Group 1: 87 100 41 1
  2. Group 2: 28 67 68 67

The total sum of integers in each of the groups which is as nearly equal as possible is:

  1. Group 1-Total Sum:229
  2. Group 2-Total Sum:230

The total number of integers between group 1 and 2 differ by O integer.

#include <bits/stdc++.h>
using namespace std;
vector<int> v;
int ans(int i,int n,float s)
{
if(i<n-1) return INT_MAX;
if(n==0) return abs(s);
return min(ans(i-1,n-1,s-v[i-1]),ans(i-1,n,s));
}

int main()
{
string s;
cin>>s;
int c=0;
for(int i=0;i<s.length();i++)
{
if(s[i]==',') {v.push_back(stoi(s.substr(c,i-c)));
c=i+1;}
}
v.push_back(stoi(s.substr(c,s.length()-c)));
//for(int i=0;i<v.size();i++) cout<<v[i];
int ss=0;
for(int i=0;i<v.size();i++) ss+=v[i];
int n1=v.size();
int n2=n1/2;
float su=ss/2;
int k=ans(n1-1,n2,su);
cout<<ss-su-k<<" "<<su+k;

}
a=list(map(int,input().split(',')))
n1=len(a)
n2=n1//2
su=sum(a)/2
dp=[[-1 for i in range(n2+1)] for j in range(n1)]
def answer(i,n,s):
if i<(n-1):
return float('inf')
if n==0:
return abs(s)
else:
return min(answer(i-1,n-1,s-a[i-1]),answer(i-1,n,s))

k=answer(n1-1,n2,su)
print(int(su-k),int(su+k))

Question 5: Mark’s Game

Problem Statement-:  Mark is playing a game on a 2D map. The 2D map is a rectangle of size n*m, where n is the number of rows, and m is the number of columns. The cell (1,1) is located at the top left corner of the map, and the cell (n,m) is located at the bottom right corner.

In one step, Mark can move from any cell to any of the adjacent cells (UP, DOWN, RIGHT, or LEFT). There’s also a blocked cell (x,y) which Mark can’t pass on. Mark can’t go off the map.

The goal of the game is to reach the cell (n,m). Mark is initially at cell (1,1) and he wants to achieve the goal of the game in the minimum number of steps. Now he’s wondering how many paths he can take such that the number of steps is minimized and he gets to cell (n,m). Can you help him find this number?

It is guaranteed that both cells (1,1) and (n,m) are NOT blocked.

 

Function Description:

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


Parameters: 

NameTypeDescription
nIntegerThe number of rows in the map.
mIntegerThe number of columns in the map.
xIntegerThe blocked cell’s row.
yIntegerThe blocked cell’s column.

Constraints:

  • 1 <= n <= 10^2
  • 1 <= m <= 10^2
  • 1 <= x <= n
  • 1 <= y <= m

 

Input Format:

  • The first line contains an integer, n, denoting the number of rows in the map.
  • The next line contains an integer m, denoting the number of columns in the map.
  • The next line contains an integer, x, denoting the blocked cell’s row.
  • The next line contains an integer, y, denoting the blocked cell’s column.

Sample Test Cases

  • Sample Input 1
    2
    2
    2
    1
  • Sample Output 1
    1
#include <bits/stdc++.h>
using namespace std;
unordered_map<int,long long int> f;

long long int Fact(int n)
{
if(f[n]) return f[n];
return f[n]=n*Fact(n-1);
}


int main()
{
int n,m,x,y;
cin>>n>>m>>x>>y;
n-=1;m-=1;x-=1;y-=1;
f[0]=f[1]=1;
int p=(Fact(m+n)/(Fact(m)*Fact(n)));
int imp=((Fact(x+y)/(Fact(x)*Fact(y)))*(Fact(m-x+n-y)/(Fact(m-x)*Fact(n-y))));
cout<<p-imp;
}
import math

n=int(input())-1
m=int(input())-1
x=int(input())-1
y=int(input())-1

ans=math.factorial(n+m)
ans=ans//(math.factorial(n))
ans=ans//(math.factorial(m))

ans1=math.factorial(x+y)
ans1=ans1//(math.factorial(x))
ans1=ans1//(math.factorial(y))

x1=n-x
y1=m-y

ans2=math.factorial(x1+y1)
ans2=ans2//(math.factorial(x1))
ans2=ans2//(math.factorial(y1))

print(ans-(ans1*ans2))

Question 6 : Santa and Gifts

Problem statement-:   Christmas is here! Santa has already prepared the gifts for all children all around the world, however, he hasn’t picked them yet. Santa has N gifts, their sizes are given in an array, A, and he also has N boxes, their sizes are given in an array, B.

Santa packs the gifts in the boxes in the following way:

  1. He tries to put the gifts inside boxes from left to right.
  2. He goes through the boxes from left to right until he finds the first empty box that fits the current gift (the box’s size should be larger or equal to the current gift’s size), and Santa puts the current gift in that box.
  3. Santa moves to the next gift to the right.

You need to find the number of gifts which won’t be packed following Santa’s algorithms in packing the gifts.

Function Description:

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

Parameters:

NameTypeDescription
nInteger

The number of gifts and boxes

aInteger arrayThe size of gifts
bInteger arrayThe size of the boxes

Return:

The function must return an INTEGER denoting the number of gifts which won’t be packed.

Constraints:

  • 1 <= N <= 10^3
  • 1 <= A[i] <= 10^5
  • 1 <= B[i] <= 10^5

Input Format for Custom Testing:

  • 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 Ai.
  • Each line i of the N subsequent lines (where 0 <= i <= N) contains an integer describing Bi.

Sample Test Cases

  • Sample Input 1
    2
    4
    5
    10
    4
  • Sample Output 1
    1
#include <bits/stdc++.h>
using namespace std;

string Add(string s1,string s2)
{
int i=stoi(s1)+stoi(s2);
return to_string(i);
}

string rev(string s)
{
reverse(s.begin(),s.end());
return s;
}

bool Palindrome(string s1)
{
return s1==rev(s1);
}

int main()
{
int n; cin>>n;
vector<int> p(n),h(n);
for(int i=0;i<n;i++) cin>>p[i];
for(int i=0;i<n;i++) cin>>h[i];
int c=0;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
if(p[i]>h[j])
{
c++;h[j]-=1;break;
}
cout<<n-c;
}
N=int(input())
people=[]
house=[]
#to read data of people and house arrays
for i in range(N): people.append(int(input()))
for i in range(N): house.append(int(input()))
count=0
for i in range(N):
for j in range(N):
if(people[i]<house[j]):
count+=1
house[j]=-1
break
print(N-count)