Infosys Digital Specialist Engineer Coding Questions

February 14, 2022

Infosys Digital Specialist Engineer Programming Questions and Solutions

Infosys has started hiring for its new role of Digital Specialist Engineer, which was earlier also known as System Engineer Specialist(SES). This role is different from the normal ASE or SE roles of Infosys. The Infosys Digital Specialist Engineer test pattern consists of 3 coding questions.
Here in this article we have tried to explain various different coding questions based on the pattern of Infosys Digital Specialist Engineer test, make sure you go through all of them if you are preparing for the DSE role.

How To Get DSE Role in Infosys

The DSE role of Infosys is for the students who are proficient with their technical knowledge

Digital Specialist Engineer works on different projects across Infosys Business Unit to develop integrated applications and bring agility in development with DevSecOps culture.
The Package for Digital Specialist Engineer(DSE) 6.25 LPA

The test for DSE and SP role is also known as advance test as the package is high for this profile.

Exam Pattern	for DSE Role
Online Test	Coding Test
No of Ques	3 Questions
Types of Ques	1 Easy + 1 Medium + 1 Hard

Question 1

Problem Statement :

Khaled has an array A of N elements. It is guaranteed that N is even. He wants to choose at most N/2 elements from array A. It is not necessary to choose consecutive elements. Khaled is interested in XOR of all the elements he chooses. Here, XOR denotes the bitwise XOR operation.

For example:

If A=[2,4,6,8], then khaled can choose the subset [2,4,8] to achieve XOR=(2 XOR 4 XOR 8)=14.

Khaled wants to maximize the XOR of all the elements he chooses. Your task is to help khaled to find the max XOR of a subset that he can achieve by choosing at most N/2 elements?

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 Ai.

Constraints

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

Sample Input 1

2
1
2
Sample Output 1
2

Explanation:

N=2, A=[1,2] khaled can choose the subset[2]. The xor of the elements in the subset is 2. And the number of elements in the subset is 1 which is less than N/2.

Sample Input 2

4
1
2
4
7

Sample Output 2

Explanation:

N=4, A=[1,2,4,7] Khaled can choose the subset [7]. The xor of the elements in the subset is 7, and the number of elements in the subset is 1 which is less than N/2.

C++

Java

Python

C++

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

int main ()
{
  int n;
  cin >> n;
  
  int arr[n];
  
  for (int i = 0; i < n; i++) cin >> arr[i];
  
  int M = 1 << 20;
  int dp[M];
  char res[M];
  
  for (int i = 1; i < M; i++)
    dp[i] = INT_MAX;
  
  for (int i = 0; i < n; i++)
    {
      if (arr[i] == 0)
	   continue;
      
      for (int j = 0; j < M; j++)
	    res[j] = 0;
      
      for (int k = 0; k < M; k++) { if (res[k] == 1) continue; if (dp[k] > dp[k ^ arr[i]])
	       dp[k] = dp[k ^ arr[i]] + 1;
	  
         else if (dp[k ^ arr[i]] > dp[k])
	       dp[k ^ arr[i]] = dp[k] + 1;
	     
	     res[k ^ arr[i]] = 1;
	      
	  }
    }
  
 int j = M - 1, k = n >> 1;
  
  while (dp[j] > k)
    j--;
  
  cout << j;
  
  return 0;

}

Java

import java.util.*;
class Main
{
  public static void main (String[]args)
  {
    final int N = 120, M = 1 << 20;
    int dp[] = new int[M];
    char res[] = new char[M];

    Scanner sc = new Scanner (System.in);
    int n = sc.nextInt ();
    int arr[] = new int[n];

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

    for (int i = 1; i < M; i++)
        dp[i] = Integer.MAX_VALUE;

    for (int i = 0; i < n; ++i)
      {
	if (arr[i] == 0)
	  continue;
	for (int j = 0; j < M; ++j)
	  res[j] = 0;

	for (int k = 0; k < M; ++k)
	  {
	    if (res[k] == 1)
	      continue;
	    if (dp[k] > dp[k ^ arr[i]])
	      dp[k] = dp[k ^ arr[i]] + 1;
	      
	    else if (dp[k ^ arr[i]] > dp[k])
	      dp[k ^ arr[i]] = dp[k] + 1;

	    res[k ^ arr[i]] = 1;
	  }
      }

    int j = M - 1, k = n >> 1;
    while (dp[j] > k)
      --j;
    System.out.println (j);
  }
}

Python

from itertools import combinations


def fun(arr, N):
   sub = []
   max_xor = max(arr)
   for i in range(1, N // 2):
       comb = combinations(arr, i + 1)
       for i in comb:
           sub.append(list(i))
   for a in sub:
       z = 0
       for b in a:
           z = z ^ b
       if z > max_xor:
           max_xor = z
   return max_xor


N = int(input("Enter Length : "))
arr = []
for i in range(N):
   arr.append(int(input(f"Enter {i+1} Element : ")))
if N < 3:
   print("Output :", max(arr))
else:
   print("Output :", fun(arr, N))

Question 2

Problem Statement :
A subarray of array A is a segment of contiguous elements in array A.
Given an array A of N elements, you can apply the following operations as many times as you like:
– Choosing a subarray [L, R] and subtracting 1 from each element in this subarray. The cost of this operation is X.
– Choosing an index i such that A[i] is positive, and setting A[i] = 0. The cost of this operation in Y.

Your task is to make all the elements equal to 0 and find the minimum cost to do so.

Input Format

The first line contains an integer, N., denoting the number of elements in A.
The next line contains an integer, X, denoting the cost of the first operation.
The next line contains an integer. Y, denoting the cost of the second operation
Each line i of the N subsequent lines (where 1 <=i<= N) contains an Integer describing Ai.

Constraints

1<=N<=10^5
1<=X<=10
1<=Y<=10^4
1<=A[i]<=10^8

Sample Input 1

1
1
10
1

Sample Output 1

Explanation:

N=1 X=1 Y=10 A=[1]. The optimal solution is to perform one operation of the first type on the subarray [1,N].

Sample Input 2

3
1
1
1
1
1

Sample Output 2

Explanation:

N=3 X=1 Y=1 A=[1,1,1] The optimal solution is to perform one operation of the first type on the subarray[1,N];

C++

Java

Python

C++

#include <iostream>
using namespace std;
int main ()
{
  int arr[] = { 1, 1, 1 };

  int X = 1;
  int Y = 1;
  int ans = 0;
  int arrSize = sizeof (arr) / sizeof (arr[0]);

  for (int i = 0; i < arrSize; i++)
    {
      arr[i]--;
    }
  ans = ans + X;

  for (int i = 0; i < arrSize; i++)
    {
      if (arr[i] != 0)
	    {
	     arr[i] = 0;
	    ans = ans + Y;
    	}
    }
  cout << ans;
  return 0;
}

Java

public class Main
{
  public static void main (String[]args)
  {

    int[] arr = { 1, 1, 1 };

    int X = 1;
    int Y = 1;
    int ans = 0;

    for (int i = 0; i < arr.length; i++)
      {

	arr[i]--;

      }
    ans = ans + X;

    for (int i = 0; i < arr.length; i++)
      {
	if (arr[i] != 0)
	  {
	    arr[i] = 0;
	    ans = ans + Y;
	  }
      }
    System.out.println (ans);
  }
}

Python

n = 1
x = 1
y = 10
arr = [1]
ans = 0
arrSize = len(arr)
for i in range(arrSize):
   arr[i] = arr[i] - 1

ans = ans + x
for i in range(arrSize):
   if arr[i] != 0:
       arr[i] = 0
       ans = ans + y
print(ans)

Question 3

Problem Statement :

One of the first lessons IT students learn is the representation of natural numbers in the binary number system (base 2) This system uses only two digits, 0 and 1. In everyday life we use for convenience the decimal system (base 10) which uses ten digits, from 0 to 9. In general, we could use any numbering
system .

Computer scientists often use systems based on 8 or 16. The numbering system based on K uses K digits with a value from 0 to K-1. Suppose a natural number M is given, written in the decimal system To convert it to the corresponding writing in the system based on K, we successively divide M by K until we reach a quotient that is less than K

The representation of M in the system based on K is formed by the final quotient (as first digit) and is followed by the remainder of the previous divisions

For example :

If M=122 and K=8, 122 in base 10= 172 in base 8 This means that the number
In decimal system = 172 in octal system.
172 in base 8 = 1*8^2 + 7*8 + 2 = 122

You made the following observation in applying the above rule of converting natural numbers to another numbering system

In some cases in the new representation all the digits of the number are the same. For example 63 in base 10= 333 in base 4

Given a number M in its decimal representation, your task is find the minimum base B such that in the representation of M at base B all digits are the same.

Input Format

The first line contains an integer, M, denoting the number given

Constraints

1 <= M = 10^12

Sample Input 1 :

Sample Output 1 :

Explanation :

Here 41 in base 40. will be 11 so it has all digits the same, and there is no smaller base satisfying the requirements

Sample Input 2 :

34430

Sample Output 2 :

312

Explanation :

Here 34430 in base 312 will have all digits the same and there is no smaller base satisfying the requirements

C++

JAVA

Python

C++

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


bool converted (int M, int base)
{
  int rem = M % base;
  M /= base;

  while (M >= base)
    {
      if (M % base != rem)
	return 0;

      M /= base;
    }

  if (M == rem)
    return 1;

  return 0;
}

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

  int base = 2;

  while (converted (M, base) != 1)
    {
      base++;
    }

  cout << base;

  return 0;
}

JAVA

import java.util.*;
class Main
{
  public static boolean convertBase (int m, int base)
  {

    int rem = m % base;
      m = m / base;

    while (m >= base && (m % base == rem))
      m = m / base;

    if (m == rem)
      return true;

      return false;
  }

  public static void main (String[]args)
  {
    Scanner sc = new Scanner (System.in);
    int m = sc.nextInt ();
    int base = 2;

    while (convertBase (m, base) != true)
      base++;

    System.out.println (base);

  }

}

Python

def convertBase(m, base):
   rem = m % base
   m = m // base
   while m >= base and (m % base == rem):
       m = m // base
   if m == rem:
       return True
   return False


m = int(input())
base = 2
while not convertBase(m, base):
   base = base + 1
print(base)

Question 4

Problem Statement :

Given an array A of N elements. You should choose a value B such that (B>=0), and then for each element in A set A[i]=A[i](+)B where is the bitwise XOR.
Print the minimum number of inversions in array A that you can achieve after choosing the value of B optimally and setting A[i] = A[i] (+) B. Since the answer might be large, print it modulo (10^9+7)

Input Format

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

Input :

4
1 0 3 2

Output
1

C++

#include <bits/stdc++.h>
#define sz(x) ((int)(x).size())
#define inf mod

using namespace std;

const int maxn = (int) 5e6 + 100;
int n, t[2][maxn], id = 1;
int dp[2][30];
vector < int >g[maxn];

void add (int x, int pos)
{
  int v = 0;
  for (int i = 29; i >= 0; i--)
    {
      int bit = ((x >> i) & 1);
      if (!t[bit][v])
	t[bit][v] = id++;
      v = t[bit][v];
      g[v].push_back (pos);
    }
}

void go (int v, int b = 29)
{
  int l = t[0][v], r = t[1][v];
  if (l)
    go (l, b - 1);
  if (r)
    go (r, b - 1);
  if (!l || !r)
    return;
  int res = 0;
  int ptr = 0;
for (auto x:g[l])
    {
      while (ptr < sz (g[r]) && g[r][ptr] < x)
	ptr++;
      res += ptr;
    }
  dp[0][b] += res;
  dp[1][b] += sz (g[l]) * 1ll * sz (g[r]) - res;
}


int main ()
{
  cin >> n;
  for (int i = 1; i <= n; i++)
    {
      int x;
      cin >> x;
      add (x, i);
    }
  go (0);
  int inv = 0;
  int res = 0;
  for (int i = 0; i <= 29; i++)
    {
      inv += min (dp[0][i], dp[1][i]);
      if (dp[1][i] < dp[0][i])
	res += (1 << i);
    }
  cout << inv;
}

Question 5

Problem Statement :

Andy wants to go on a vacation to de-stress himself. Therefore he decides to take a trip to an island. It is given that he has as many consecutive days as possible to rest, but he can only make one trip to the island. Suppose that the days are numbered from 1 to N. Andy has M obligations in his schedule, which he has already undertaken and which correspond to some specific days. This means that ith obligation is scheduled for day Di. Andy is willing to cancel at most k of his obligations in order to take more holidays.

Your task is to find out the maximum days of vacation Andy can take by canceling at most K of his obligations.

Input Format

The first line contains an integer N, denoting the total number of days
The next line contains an integer M denoting the total number of obligations.
The next line contains an integer K denoting the largest number of obligations he could cancel
Each line i of the M subsequent lines (where 0<=i<=M) contains an integer describing Di.

Constraints

1<=N<=10^6
1<=M<=2*10^6
1<=K<=2*10^6
1<=D[i]<=10^6

Sample Input 1:

10
5
2
6
9
3
2
7

Sample Output 1 :

Explanation:

Here he could cancel his 3rd and 4th obligation which makes vacation length 5.

Sample input 2:

7
2
0
3
4

Sample Output 2:

Explanation:

Here he could not cancel any obligation since K=0, so the vacation length is 3.

C++

Java

Python

C++

#include<bits/stdc++.h>
using namespace std;
unordered_map < int, int >L;

int main ()
{

  int n, m, k;
  cin >> n >> m >> k;

  vector < int >v (m);

  for (int i = 0; i < m; i++) cin >> v[i];

  sort (v.begin (), v.end ());

  int st = 0, en = k, ans;
  if (k > m)
    {
      cout << n;
      return 0;
    }

  if (k < m)
    ans = v[en] - 1;

  for (int j = en + 1; j < m; j++)
    {
      ans = max (ans, v[j] - v[st] - 1);
      st++;
    }

  ans = max (ans, n - v[st]);
  cout << ans;
}

Java

import java.util.*;
class Main
{
  public static void main (String[]args)
  {

    Scanner sc = new Scanner (System.in);
    int n = sc.nextInt ();
    int m = sc.nextInt ();
    int k = sc.nextInt ();

    int arr[] = new int[n];

    for (int i = 0; i < m; i++)
        arr[i] = sc.nextInt ();
    int ans = 0;
      Arrays.sort (arr);

    if (k > 0)
      {
	for (int i = k + 1; i <= m + 2; i++)
	  ans = Math.max (ans, arr[i] - arr[i - k - 1] - 1);
      }
    else
      {
          int j = 0;
          while (arr[j] == 0)
          j++;
          int count = 0;
          
          for (int i = 1; i <= n; i++)
          {
              count++;
              if (j < n && (i == arr[j]))
              {
                  count = 0;
                  j++;
              }
              ans = Math.max (count, ans);
              
          }
      }
    System.out.println (ans);
  }
}

Python

n = int(input())
m = int(input())
k = int(input())
arr = [0] * n
for i in range(m):
   arr[i] = int(input())
ans = 0
arr.sort()
if k > 0:
   for i in range(k + 1, m + 3, 1):
       ans = max(ans, arr[i] - arr[i - k - 1] - 1)
else:
   j = 0
   while arr[j] == 0:
       j = j + 1
   count = 0
   for i in range(1, n + 1, 1):
       count += 1
       if j < n and (i == arr[j]):
           count = 0

           j += 1
       ans = max(count, ans)
print(ans)