# Cognizant GenC Next Coding Questions

## GenC Next Coding Challenge 2023

Cognizant GenC Next Coding Questions round details are explained in this article. Cognizant has announced its Cognizant GenC Next Hiring for 2023 batch graduates. In this hiring test, coding round is the most important round. It is the second round of the hiring test, and will be conducted through Hackerrank. In this round there will be 5 – 6 questions based on

• Data Structures
• Algorithms
• Competitive Coding
• SQL
• JDBC

For  preparing this round we suggest you to practice medium to high difficulty questions of Hackerrank. Here below we have listed some questions based on the pattern of hackerrank and GenC Next, make sure you practice all of them while preparing for GenC Next Coding Round ### Cognizant GenC Next Coding Questions : Detailed Analysis

Cognizant GenC SectionNo. of questionsTotal Time
MCQ20-2540 mins
Coding Challenge5-6140 mins

## Practice Questions for Cognizant GenC Next Coding Challenge

### Question 1

Problem statement-: Elliot made a KeyLogger for his friend Romero, so that he can see the passwords of his friend. Keylogger is a software that can tell you the buttons pressed in the keyboard without the consent of the user, and hence unethical. Elliot made it to hack Romero’s passwords. The one problem is, Romero writes the passwords in lowercase characters only, and the keylogger only takes the values of the keys. Like, for a it takes 1, for b 2, and for z 26. For a given number Elliot produces all combinations of passwords in a dictionary and starts a dictionary based password attack. For a given number, print all the possible passwords in a lexicographic order.

Input Format:

• One line, denoting the value given by the keylogger

Output Format:

• All possible combinations of keyloggers in new lines are lexicographically ordered.

Constraints:

• 2<=Number of digit in input<=1000

Sample Input:

1234

Sample Output:

abcd

awd

lcd

Explanation:

For 12, you can take 1,2 that is ab, or you can take l.

`#include<bits/stdc++.h>using namespace std;string ss;vector<string> v; void fun(int i, string s){    //cout<<i<<s<<endl;    if(i==ss.length()) {v.push_back(s);return;}    if(i>ss.length()) return;    if(ss[i]=='0') return;    char c='a'+(ss[i]-'1');    fun(i+1,s+c);    if(i!=s.length()-1)    if( ss[i]<'3' && ss[i+1]<'7')    {        int a=(ss[i]-'1'+1),b=(ss[i+1]-'0');        c=('a'+(10*a+b-1));//cout<<a<<b<<endl;        fun(i+2,s+c);    }} int main(){    cin>>ss;    fun(0,"");    sort(v.begin(),v.end());    for(auto i:v) cout<<i<<endl;}`
`import java.util.*;class Solution{    static String str;    static ArrayList < String > list = new ArrayList < String > ();    public static void func (int i, String res)    {        if (i == str.length ())        {        	list.add (res);	        return;        }        if (i > str.length ())            return;        if(str.charAt (i) == '0')            return;        char ch = (char) ('a' + (str.charAt (i) - '1'));                func (i + 1, res + ch);            if (i != str.length () - 1)        if (str.charAt (i) < '3' && str.charAt (i + 1) < '7')	    {            int a = (str.charAt (i) - '1' + 1), b = (str.charAt (i + 1) - '0');	        ch = (char) ('a' + (10 * a + b - 1));	        func (i +     2, res + ch);	    }    }    public static void main (String[]args)    {        Scanner sc = new Scanner (System.in);        str = sc.next ();        String res = "";        func (0, res);            Collections.sort (list);        for (int i = 0; i < list.size (); i++)              System.out.println (list.get (i));    }}`

### Question 2

Problem Statement- Ramesh went to a bookshop to buy books. There is a list of books with their value and price. Now Ramesh has limited money but he wants maximum value possible. Now there are 2 kinds of books, one is denoted with 1, that is independent, another one is denoted as 2, which you have to buy in double, that means you can not buy a single or odd number of those books.

Print the maximum value Ramesh can extract from the books.

Input Format:

• First line contains two integers, n (Number of books) and T, total money he has.
• Then n lines, 4 variables in each line,
• The serial number of the book
• The value of the book
• The price of the book
• The marking (1 or 2)

Output Format:

• Maximum value possible to be bought.

Constraints:

• Number of books: <=100
• Maximum Money with Ramesh <=1000
• Max price of a book<=1000

Sample Input:

5 20

1 3 7 0

3 9 10 1

2 4 3 1

7 3 2 0

22 7 7 0

Sample Output:

20

Explanation:

It will be the 1st book,2nd and the third book

`#include<bits/stdc++.h>using namespace std;int n,w;int *a,*b,*c; int fun(int i,int cb,int t,int ww){    if(i==n){        if(cb&1) return 0;        else return t;    }    if(ww+b[i]<=w) return max(fun(i+1,cb+c[i],t+a[i],ww+b[i]),fun(i+1,cb,t,ww));    return fun(i+1,cb,t,ww);} int main(){   cin>>n>>w;   int tt;   a=new int(n);   b=new int(n);   c=new int(n);   for(int i=0;i<n;i++)   cin>>tt>>a[i]>>b[i]>>c[i];   cout<<fun(0,0,0,0);}`
`import java.util.*;class Solution {    static int n, w;    static int a[];    static int b[];    static int c[];     public static int func (int i, int cb, int t, int ww)     {        if (i == n)        {            if ((cb & 1) != 0)                return 0;        	else                return t;        }        if (ww + b[i] <= w)            return Math.max (func (i + 1, cb + c[i], t + a[i], ww + b[i]),func (i + 1, cb, t, ww));        return func (i + 1, cb, t, ww);    }    public static void main (String[]args)     {        Scanner sc = new Scanner (System.in);        n = sc.nextInt ();        w = sc.nextInt ();        int t;        a = new int[n];        b = new int[n];        c = new int[n];                for (int i = 0; i < n; i++)        {            t = sc.nextInt ();            a[i] = sc.nextInt ();            b[i] = sc.nextInt ();            c[i] = sc.nextInt ();        }                 System.out.println (func (0, 0, 0, 0));    } }`

### Question 3

Problem Statement-  A taxi can take multiple passengers to the railway station at the same time.On the way back to the starting point,the taxi driver may pick up additional passengers for his next trip to the airport.A map of passenger location has been created,represented as a square matrix.

The Matrix is filled with cells,and each cell will have an initial value as follows:

• A value greater than or equal to zero represents a path.
• A value equal to 1 represents a passenger.
• A value equal to -1 represents an obstruction.

The rules of motion of taxi are as follows:

• The Taxi driver starts at (0,0) and the railway station is at (n-1,n-1).Movement towards the railway station is right or down,through valid path cells.
• After reaching (n-1,n-1) the taxi driver travels back to (0,0) by travelling left or up through valid path cells.
• When passing through a path cell containing a passenger,the passenger is picked up.once the rider is picked up the cell becomes an empty path cell.
• If there is no valid path between (0,0) and (n-1,n-1),then no passenger can be picked.
• The goal is to collect as many passengers as possible so that the driver can maximize his earnings.

Sample Input 0

4

0 0 0 1

1 0 0 0

0 0 0 0

0 0 0 0

Sample Output 0

2

Explanation 0

The driver can contain a maximum of 2 passengers by taking the following path (0,0) → (0,1) → (0,2) → (0,3) → (1,3) → (2,3) → (3,3) → (3,2) → (3,1) → (3,0) → (2,0) → (1,0)  → (0,0)

Sample Input 1

3

3

0 1 -1

1 0 -1

1 1 1

Sample Output 1

5

Explanation 1

The driver can contain a maximum of 5 passengers by taking the following path (0,0) → (0,1) → (1,1) → (2,1) → (2,2) → (2,1) → (2,0) → (1,0) → (0,0)

`#include <bits/stdc++.h>using namespace std;int n, m;int mat;map<pair<int, pair<int, int>>, int> dp;bool isValid(int i, int j){    if (mat[i][j] == -1)        return false;    if (i < 0 || i >= n)        return false;    if (j < 0 || j >= m)        return false;    return true;}int solve(int i, int j, int x, int y){    if (!isValid(i, j))    {        return INT_MIN;    }    if (!isValid(x, y))    {        return INT_MIN;    }    if (i == n - 1 && x == n - 1 && j == m - 1 && y == m - 1)    {        if (mat[i][j] == 1)        {            return 1;        }        else        {            return 0;        }    }    if (dp.find({i, {j, x}}) != dp.end())        return dp[{i, {j, x}}];     int cur = 0;    if (i == x && j == y)    {        if (mat[i][j] == 1)            cur = 1;    }    else    {        if (mat[i][j] == 1)            cur++;        if (mat[x][y] == 1)            cur++;    }     int op1 = solve(i + 1, j, x + 1, y);    int op2 = solve(i, j + 1, x, y + 1);    int op3 = solve(i + 1, j, x, y + 1);    int op4 = solve(i, j + 1, x + 1, y);     int ans = cur + max(op1, max(op2, max(op3, op4)));     return dp[{i, {j, x}}] = ans;}int main(){    cin >> n >> m;     for (int i = 0; i < n; i++)        for (int j = 0; j < m; j++)            cin >> mat[i][j];    int ans = solve(0, 0, 0, 0);    if (ans >= 0)        cout << solve(0, 0, 0, 0) << endl;    else        cout << -1 << endl;     return 0;}`
`import java.util.*;class Solution{  public static int cost (int grid[][], int row1, int col1, int row2,			  int col2)  {    if (row1 == row2 && col1 == col2)      {	if (grid[row1][col1] == 1)	  return 1;	return 0;      }    int ans = 0;    if (grid[row1][col1] == 1)      ans++;    if (grid[row2][col2] == 1)      ans++;    return ans;  }  public static int solve (int n, int m, int grid[][], int dp[][][], int row1,			   int col1, int row2)  {    int col2 = (row1 + col1) - (row2);    if (row1 == n - 1 && col1 == m - 1 && row2 == n - 1 && col2 == m - 1)      return 0;    if (row1 >= n || col1 >= m || row2 >= n || col2 >= m)      return -1 * Integer.MAX_VALUE;    if (dp[row1][col1][row2] != -1)      return dp[row1][col1][row2];    int ch1 = -1 * Integer.MAX_VALUE, ch2 = -1 * Integer.MAX_VALUE;    int ch3 = -1 * Integer.MAX_VALUE, ch4 = -1 * Integer.MAX_VALUE;    if (grid[row1][col1 + 1] != -1 && grid[row2 + 1][col2] != -1)      ch1 =	cost (grid, row1, col1 + 1, row2 + 1, col2) + solve (n, m, grid, dp,							     row1, col1 + 1,							     row2 + 1);    if (grid[row1][col1 + 1] != -1 && grid[row2][col2 + 1] != -1)      ch2 =	cost (grid, row1, col1 + 1, row2, col2 + 1) + solve (n, m, grid, dp,							     row1, col1 + 1,							     row2);    if (grid[row1 + 1][col1] != -1 && grid[row2][col2 + 1] != -1)      ch3 =	cost (grid, row1 + 1, col1, row2, col2 + 1) + solve (n, m, grid, dp,							     row1 + 1, col1,							     row2);    if (grid[row1 + 1][col1] != -1 && grid[row2 + 1][col2] != -1)      ch4 =	cost (grid, row1 + 1, col1, row2 + 1, col2) + solve (n, m, grid, dp,							     row1 + 1, col1,							     row2 + 1);    return dp[row1][col1][row2] =      Math.max (ch1, Math.max (ch2, Math.max (ch3, ch4)));  }  public static void initializeDp (int dp[][][], int item)  {    for (int i = 0; i < 5; i++)      {	for (int j = 0; j < 5; j++)	  for (int k = 0; k < 5; k++)	    dp[i][j][k] = item;      }  }  public static int collectMax (int n, int m, int grid[][])  {    int ans = 0;    int dp[][][] = new int;    initializeDp (dp, -1);    if (grid[n - 1][m - 1] == -1 || grid == -1)      ans = -1 * Integer.MAX_VALUE;    if (grid == 1)      ans++;    grid = 0;    if (grid[n - 1][m - 1] == 1)      ans++;    grid[n - 1][m - 1] = 0;    ans += solve (n, m, grid, dp, 0, 0, 0);    return Math.max (ans, 0);  }  public static void main (String[]args)  {    Scanner sc = new Scanner (System.in);    int n = sc.nextInt ();    int m = sc.nextInt ();    int arr[][] = new int[n + 1][m + 1];    for (int i = 0; i < n; i++)      for (int j = 0; j < n; j++)	arr[i][j] = sc.nextInt ();    System.out.println (collectMax (n, m, arr));  }}`

### Question 4

Problem Statement – Ratan is a crazy rich person. And he is blessed with luck, so he always made the best profit possible with the shares he bought. That means he bought a share at a low price and sold it at a high price to maximize his profit. Now you are an income tax officer and you need to calculate the profit he made with the given values of stock prices each day. You have to calculate only the maximum profit Ratan earned.

Note that:

• Ratan never goes into loss.

Example 1

• Price=[1,6,2]
• Ratan buys it on the first day and sells it on the second.

Example 2

• Price=[9,8,6]

The Price always went down, Ratan never bought it.

Input Format:

• First line with an integer n, denoting the number days with the value of the stack
• Next n days, telling the price of the stock on that very day.

Output Format:

• Maximum profit done by Ratan in a single line.

Constraints:

• Number of days <=10^8

Sample Input for Custom Testing

STDIN

———–

7

11

2

Sample Output

10

Explanation

The maximum profit possible is when Ratan buys it in 1 rupees and sells it in 11.

`#include <bits/stdc++.h>using namespace std;int solve (vector < int >v){  int n = v.size ();  if (n == 0)    return 0;  int mx = v;  for (int i = 1; i < n; i++)    mx = max (mx, v[i]);  if (mx <= 0)    return 0;  int mxSum = 0;  int cSum = 0;  for (int i = 0; i < n; i++)    {      cSum += v[i];      if (cSum < 0)	cSum = 0;      mxSum = max (mxSum, cSum);    }  return mxSum;}int main (){  int n;  cin >> n;  int price[n];  for (int i = 0; i < n; i++)    cin >> price[i];  vector < int >diff;  for (int i = n - 2; i >= 0; i--)    diff.push_back (price[i + 1] - price[i]);  int ans = solve (diff);  if (ans < 0)    cout << 0 << endl;  else    cout << ans << endl;}`
`import java.util.*;public class PrepInsta{  public static void main (String[]args)  {    Scanner sc = new Scanner (System.in);    int n = sc.nextInt ();    int price[] = new int[n];    for (int i = 0; i < n; i++)      {	price[i] = sc.nextInt ();      }    Vector < Integer > diff = new Vector <> ();    for (int i = n - 2; i >= 0; i--)      {	diff.add (price[i + 1] - price[i]);      }    int ans = solve (diff);    if (ans < 0)      {	System.out.println (0);      }    else      {	System.out.println (ans);      }  }  private static int solve (Vector < Integer > v)  {    int n = v.size ();    if (n == 0)      {	return 0;      }    int mx = v.get (0);    for (int i = 1; i < n; i++)      {	mx = Math.max (mx, v.get (i));      }    if (mx <= 0)      {	return 0;      }    int mxSum = 0, csum = 0;    for (int i = 0; i < n; i++)      {	csum += v.get (i);	if (csum < 0)	  csum = 0;	mxSum = Math.max (csum, mxSum);      }    return mxSum;  }}`
`def func(diff):    n=len(diff)    if n==0:        return 0    mx=max(diff)    if mx<=0:        return 0    mxS=0    cS=0    for i in diff:        cS+=i        if cS<=0:            cS=0        mxS=max(cS,mxS)    return mxS   n=int(input())arr=[]diff=[]ans=for i in range(n):    arr.append(int(input()))for i in range(n-1):    diff.append(arr[i+1]-arr[i])ans=func(diff)if ans<0:    print("0")else:    print(ans)`

### Question 5

Problem Statement – Codu is given a string and he thinks the letters that are repeated do have more power. He gathers only the repeating characters and keeps them as the most powerful to least powerful manner. Now it is your turn to write a code that will help Codu to do that.

Note that: only lowercase alphabets are accepted in input.

Input Format:

• A string in a single line

Output Format:

• A string made of only the repeated characters as sorted their frequency reducin, if the same the lower ascii value comes before.

Constraints:

• Length of string<=10^5

Sample Input:

abcdefghaabca

Sample Output:

abc

`#include<bits/stdc++.h>using namespace std;map<char,int> m;string ss;bool cmp(pair<char, int>& a,         pair<char, int>& b){    return a.second > b.second;} void sort(map<char,int>& M){    vector<pair<char, int> > A;    for (auto& it : M)        A.push_back(it);    sort(A.begin(), A.end(), cmp);    for (auto& it : A) ss+=it.first;} int main(){  string s;  getline(cin,s);  for(auto i:s)  m[i]++;  sort(m);   for(auto i:ss)  if(m[i]>1)  cout<<i;}`
`import java.util.*;public class StringReduction{  public static void main (String[]args)  {    Scanner sc = new Scanner (System.in);    String str = sc.next ();      TreeSet < Character > list = new TreeSet < Character > ();    for (int i = 0; i + 1 < str.length (); i++)      {	String prefix = str.substring (0, i);	String suffix = str.substring (i + 1, str.length ());	char ch = str.charAt (i);	if (prefix.indexOf (ch) != -1 || suffix.indexOf (ch) != -1)	    list.add (ch);      }    if (str.substring (0, str.length () - 1).	indexOf (str.charAt (str.length () - 1)) != -1)        list.add (str.charAt (str.length () - 1));    Iterator itr = list.iterator ();    while (itr.hasNext ())      {	System.out.print ((Character) itr.next ());      }  }}`

### Question 6

Problem Statement – How will we represent a binary tree? We can use a bracket structure for all of the edges, like (Parentnode , Childnode). Now if we use a node in a child node more than once, the tree can not be valid. Same for the parent node, a node can not be taken more than twice in  a graph as a parent node.

Suppose we see this one graph

(P,Q)(P,R)(Q,T)(R,W)(U,V)(Q,S)(R,U)(U,Z)(S,I)(W,Y)

A tree with those edges may be illustrated in many ways.Here are two:

P                            P

/    \                        /     \

Q      R                   Q      R

/   \     /    \               /   \    /  \

S   T   U   W           S    T  U  W

\        / \     \          /          / \      \

I     V  Z    Y      I         Z  V    Y

The following is a recursive definition for the S-expression of a tree.

S-exp(node)=(node->val(S-exp(node->first_child))(S-exp(node->second_child))),if node

!NULL=””,node= =NULL

Where first_child->val<second _child->val(first_child->val is lexicographically than second_child->val)

This tree can be represented in S-expression in multiple ways.The lexicographically smallest way of expressing it as follows:

P(Q(S(I))(T))(R(U(V)(Z))(W(Y))))

Translate the node-pair representation into its lexicographically smallest S-expression or report any errors that do not conform to the definition of the binary tree.

The List of errors with their codes is as follows:

Error                               Reason

Code Stopped1                More than 2 children

Code Stopped2                Duplicate Edges

Code Stopped3                Cycle Present(node is direct descendant of more than one node)

Code Stopped4                Multiple Roots

Code Stopped5                Any other error

Functional Description

Complete the function sExpression in the editor below.

• The function must return either the lexicographically lowest S-expression or the lexicographically lowest error code as a string.

sExpression has the following parameter(s):

• Nodes:a string of space-separated parenthetical elements,each of which contains the name of two nodes connected by a comma.

Constraints:

1. All node names are single characters in the range ascii[A-Z].
2. The maximum node count is 26.
3. There is no specific order to the input (parent,child) pairs.

>Input Format for Custom Testing

>Sample Case 0

Sample Input 0

(B,D) (D,E) (A,B) (C,F) (E,G) (A,C)

Sample output 0

(A(B(D(E(G))))(C(F)))

Explanation 0

A representation of tree is as follows:

A

/    \

B      C

/         \

D           F

/

E

/

G

>Sample Case 1

Input:

(C,E)(D,F)(A,B)(A,C)(B,K)

Output:

A(B(K))(C(E)))D(F))

`#include <bits/stdc++.h>using namespace std;string s, ans = "";unordered_map < char, int >root, child, flag;	//rootOf,childOfmap < pair < char, char >, int >duplicateedgecheck;	//Duplicate edge checkunordered_map < char, char >par, ch, monitor;charfind (char c){  if (monitor[c])    return monitor[c];  if (root[c] == 0)    return monitor[c] = c;  return monitor[c] = find (par[c]);}voidmakeans (char c){  if (flag[c] == 0)    {      ans += c;      flag[c]++;      if (child[c] == 2)	{	  ans += '(';	  makeans (min (ch[c], ch[c]));	  ans += '(';	  makeans (max (ch[c], ch[c]));	}      else	for (int i = 0; i < child[c]; i++)	  {	    ans += '(';	    makeans (ch[i][c]);	  }      ans += ')';    }}intmain (){  getline (cin, s);  for (int i = 0; i < 26; i++)    {      root['A' + i] = -5;    }  for (int i = 0; i < s.length (); i++)    if (s[i] == '(')      {	child[s[i + 1]]++;	root[s[i + 3]] = root[s[i + 3]] == -5 ? 1 : root[s[i + 3]]++;	duplicateedgecheck[			    {			    min (s[i + 1], s[i + 3]), max (s[i + 1], s[i + 3])}	]++;	root[s[i + 1]] == -5 ? root[s[i + 1]] = 0 : 1;	ch[s[i + 1]] == '\0' ? ch[s[i + 1]] =	  s[i + 3] : ch[s[i + 1]] = s[i + 3];	par[s[i + 3]] = s[i + 1];	if (child[s[i + 1]] > 2)	  {	    cout << "Code Stopped1";	    return 0;	  }	if (duplicateedgecheck[				{				min (s[i + 1], s[i + 3]), max (s[i + 1],							       s[i + 3])}	    ] > 1)	  {	    cout << "Code Stopped2";	    return 0;	  }	if (find (s[i + 1]) == find (s[i + 3]) && s[i + 1] != par[s[i + 3]])	  {	    cout << "Code Stopped3";	    return 0;	  }	if (root[s[i + 3]] > 1)	  {	    cout << "Code Stopped4";	    return 0;	  }	if (s[i + 4] != ')' || s[i + 2] != ',')	  {	    cout << "Code Stopped5";	    return 0;	  }	//i+=5;      }  for (int i = 0; i < 26; i++)    {      if (root['A' + i] == 0)	makeans ('A' + i);    }  cout << ans;}`

### Question 7

Problem Statement – Sahil watches TV all day and gets bored. He started playing this dumb game of identifying minimum number of inputs needed to reach a channel. As his cousin, you have to help him, but you live far from his house. So you decide to write a code that will ask Sahil for some inputs and give outputs respectively.

Here are the problems you need to keep in mind,

• There are 13 buttons on his remote: 10 buttons for the numbers (0-9) to form integers denoting respective channel index, “Up channel” button and  “ Down channel” button for going i +1th channel and i-1th channel from i respectively, and  a “Last viewed” button to see what’s the last channel before it.
• The number buttons allow you to jump directly to a specific channel  (Ex: to go to channel 172 by typing 1,7,2).
• If the channel which you are in is ith and that is the max channel index possible, by Up channel, you will reach the first channel possible. Same goes for the down channel button. You can go to the highest channel possible if you go down from the lowest channel possible.

Sahil can get from one channel to the next in one of the two ways.

Sahil’s parents have set some parental control on some channels on Aniruth’s television. The “Up Channel “ and “Down buttons” buttons skip these channels as these channels are not viewable.

Given a list of channels to view, the lowest channel, the highest channel, and a list of blocked channels, your program should return the minimum number of clicks necessary to get through all the shows that Anirudh would like to match.

Input Format

• First line is the lowest Channel
• Second-line is the highest Channel
• Followed by a number of blocked channels B,
• and the next B lines contain the actual blocked channels.
• Followed by the number of Channels to view V, and the next V lines contain the actual channels to view.

Constraints

• The lowest channel on the television will be greater than 0. and less than or equal to 10,000.
• The highest channel on the television will be greater than or equal to the lowest channel. and less than or equal to 10.000.
• The list of channels that are blocked on Anirudh’s television. All the channels in this list will be valid channels (greater than or equal to lowest channel, less than or equal 1 to highest channel). Duplicates may be Ignored. The blocked list can be a maximum of 40 channels.
• The sequence that Sahil must view contains between 1 and 50 elements. inclusive. All channels in this sequence are not in the blocked list and are between lowest channel and highest channel. Inclusive.

Sample Input 0:

1

20

2

18

19

5

15

14

17

1

17

Sample output 0:

7

`#include<bits/stdc++.h>using namespace std; unordered_map<int,int> m;int l,u;int util(int a,int b){    if(a==b) return 0;    if(m[a]) return util(a+1,b);    return 1+util(a+1,b);} int func(int b,int prev){    if(b<prev) return min(util(prev,u)+util(l,b)+1,util(b,prev));    else return min(util(prev,b),util(l,b)+util(prev,u)+1);} int main(){    int flag=0,ans=0,prev,prev2;    cin>>l>>u;    int bn,b; cin>>bn;    while(bn--){cin>>b;m[b]++;}    cin>>bn;    while(bn--)    {        cin>>b;        if(b>9 && flag==0) {ans+=2;flag++;prev=b;}        else if(flag==0) {ans+=1;flag++;prev=b;}        else if(prev2==b) {prev2=prev;prev=b;ans++;}        else        {            ans+=min(b>9?2:1,func(prev,b));prev2=prev;prev=b;        }    }     cout<<ans;}`
```import java.util.*;
public class  GameOfClicks
{
public static void main(String[] args)
{
Scanner sc=new Scanner(System.in);
int l=sc.nextInt();
int h=sc.nextInt();
int b=sc.nextInt();
List<Integer>bl=new ArrayList<>();
for(int i=0;i<b;i++){
}
int v=sc.nextInt();
List<Integer>vl=new ArrayList<>();
for(int i=0;i<v;i++){
}
Set<Integer>sl=new HashSet<>();
int res=0;
for(Integer i:vl){
if(bl.contains(i))
continue;
}
for(Integer i:sl){
String s=i+"";
res+=s.length();
}
System.out.println(res);

}
}```
`def prev(now,l,h,blocked):    if now!=l:        if (now-1) not in blocked:            return (now-1)        else:            return prev(now-1,l,h,blocked)            else:        if h not in blocked:            return h        else:            return prev(h,l,h,blocked)def next(now,l,h,blocked):    if now!=h:        if (now+1) not in blocked:            return (now+1)        else:            return next(now+1,l,h,blocked)            else:        if l not in blocked:            return l        else:            return next(l,l,h,blocked)def digits(n):    count=0    while n>0:        n=n//10        count+=1            return countfor i in range(2):    if i==0:        l=int(input())    else:        h=int(input())b=int(input())blocked=[]for i in range(b):    blocked.append(int(input()))        back=-1now=-1c=int(input())k=0for i in range(c):    n=int(input())    n1=digits(n)    if now==-1:        now=n        k+=n1        continue        if back==n:        k+=1        back,now=now,back        continue        pf=0    pb=0    now1=now    prev1=now    for j in range(n1):        if j==(n1-1):            pf=n1            pb=n1            break        else:            now1=next(now1, l, h, blocked)            pf+=1            prev1=prev(prev1, l, h, blocked)            pb+=1            if now1==n:                break            if prev1==n:                break    k+=pf    back=now    now=n print(k)`

### Question 8

Problem Statement –  A company has a list of jobs to perform. Each job has a start time, end time and profit value. The manager has asked his employee Anirudh to pick jobs of his choice. Anirudh being greedy wants to select jobs for him in such a way that would maximize his earnings.

Given a list of jobs how many jobs and total earning are left for other employees once Anirudh

Picks jobs of his choice.

Note: Anirudh can perform only one job at a time.

Input format:

• Each Job has 3 pieces of info – Start Time,End Time and Profit
• The first line contains the number of Jobs for the day. Say ‘n’. So there will be ‘3n lines following as each job has 3 lines.
• Each of the next ‘3n’ lines contains jobs in the following format:
• start_time
• end-time
• Profit

start-time and end-time are in HHMM 24HRS format i.e. 9am is 0900 and 9PM is 2100

Constraints

• The number of jobs in the day i.e’ is less than 10000
• 0<_n<_10000
• start-time is always less than end time.

Output format :-

• Program should return an array of 2 integers where
• 1st one is number of jobs left and earnings of other employees

Sample Input 1 :

4

0200

0300

10

0400

0700

20

0300

0800

30

0900

1000

50

Sample Output 1:

1

20

Sample Explanation 1

Chooses 1st, 3rd and 4th job cause they don’t overlap. So only second job is remaining.

Sample Input 2:

5

0805

0830

100

0835

0900

100

0905

0930

100

0935

1000

100

1005

1030

100

Sample output 2:

0

0

Sample Explanation 2:

Anirudh can work on all appointments as there are none overlapping.

Hence 0 appointments and 0 earnings for other employees.

`#include <bits/stdc++.h>using namespace std;class job{public:    int st, ed, cost;};int getTime(string s){    int hr = (s - '0') * 10 + (s - '0');    int min = (s - '0') * 10 + (s - '0');     return hr * 60 + min;}bool compare(job A, job B){    return A.ed < B.ed;}int searchJob(job arr[], int st, int ed, int key){    int ans = -1;    while (st <= ed)    {        int mid = (st + ed) / 2;        if (arr[mid].ed <= key)        {            ans = mid;            st = mid + 1;        }        else        {            ed = mid - 1;        }    }    return ans;}pair<int, int> solve(job arr[], int n){    int dp[n] = {0};    int numOfJobs[n] = {0};     dp = arr.cost;    numOfJobs = 1;     for (int i = 1; i < n; i++)    {        int cur = arr[i].cost;        int num = 1;        int idx = searchJob(arr, 0, i - 1, arr[i].st);         if (idx != cur)        {            cur += dp[idx];            num += numOfJobs[idx];        }        if (cur > dp[i - 1])        {            dp[i] = cur;            numOfJobs[i] = num;        }        else        {            dp[i] = dp[i - 1];            numOfJobs[i] = numOfJobs[i - 1];        }    }    return {numOfJobs[n - 1], dp[n - 1]};}int main(){    int n;    cin >> n;     job arr[n];    int cost;    string st, ed;    int total = 0;     for (int i = 0; i < n; i++)    {        cin >> st >> ed >> cost;        arr[i].st = getTime(st);        arr[i].ed = getTime(ed);        arr[i].cost = cost;        total += cost;    }    sort(arr, arr + n, compare);     pair<int, int> res = solve(arr, n);     cout << n - res.first << endl;    cout << total - res.second << endl;     return 0;}`
`import java.util.Arrays;import java.util.Comparator;import java.util.Scanner;class Job{	public Integer st;	public Integer ed;	public Integer cost;		public Job() {		super();	}	public Job(Integer st, Integer ed, Integer cost) {		super();		this.st = st;		this.ed = ed;		this.cost = cost;	}}class Pair{	public Integer first;	public Integer second;	public Pair() {		super();	}	public Pair(Integer first, Integer second) {		super();		this.first = first;		this.second = second;	}}class SortingJobs implements Comparator<Job>{	@Override	public int compare(Job o1, Job o2) {		if(o1.ed<o2.ed) {			return 1;		}else {			return 0;		}	}	}public class Application3 {	public static void main(String[] args) {		Scanner sc = new Scanner(System.in);		int n = sc.nextInt();		Job[] arr=new Job[n];		int cost;		String st,ed;		int total=0;		for(int i=0;i<n;i++) {			st=sc.next();			ed=sc.next();			if(st.length()<4) {				while(st.length()!=4) {					st+="0";				}			}			if(ed.length()<4) {				while(ed.length()!=4) {					ed+="0";				}			}			cost=sc.nextInt();			arr[i] = new Job();			arr[i].st = getTime(st);			arr[i].ed = getTime(ed);			arr[i].cost = cost;			total += cost;		}		Arrays.sort(arr,new SortingJobs());		Pair res = new Pair();		res = solve(arr,n);		if(res==null) {			System.out.println(0);		}else {			System.out.println(n-res.first);			System.out.println(total-res.second);		}			}	private static Pair solve(Job[] arr, int n) {		if(n==0) {			return null;		}		int dp[]=new int[n];		int numOfJobs[]=new int[n];		for(int i=0;i<n;i++) {			dp[i]=0;			numOfJobs[i]=0;		}		dp = arr.cost;		numOfJobs=1;		for(int i=1;i<n;i++) {			int curr=arr[i].cost;			int num=1;			int idx=searchJob(arr,0,i-1,arr[i].st);			if(idx!=curr && idx!=-1) {				curr+=dp[idx];				num+=numOfJobs[idx];			}			if(curr>dp[i-1]) {				dp[i]=curr;				numOfJobs[i]=num;			}else {				dp[i]=dp[i-1];				numOfJobs[i]=numOfJobs[i-1];			}		}		return new Pair(numOfJobs[n-1],dp[n-1]);	}	private static int searchJob(Job[] arr, int st, int ed, int key) {		int ans=-1;		while(st<=ed) {			int mid=(st+ed)/2;			if(arr[mid].ed<=key) {				ans=mid;				st=mid+1;			}else {				ed=mid-1;			}		}		return ans;	}	private static int getTime(String st) {		int hr = (st.charAt(0)-'0')*10 + (st.charAt(1)-'0');		int min = (st.charAt(2)-'0')*10 + (st.charAt(3)-'0');		return hr*60 + min;	}}`

### Question 9

Problem Statement : Given two integers, the task is to find the hamming distance between two integers. Hamming Distance between two integers is the number of bits that are different at the same position in both numbers.

Example :

Input 1:

a= 10 , b =8

Output 1:

1

Explanation: 10= 1010 , 8=1000 , No of different bits=1.

Input 2:

a=9, b=14

Output 2:

3

Explanation: 9=1001 , 14=1110  , No. of different bits=3.

`import java.util.*;class Solution {    public static int hammingDistance (int a, int b)     {        int max = a > b ? a : b;        int count = 0;        while (max > 0)        {            if ((a & 1) != (b & 1))                count++;            a = a >> 1;            b = b >> 1;            max = max >> 1;        }        return count;    }      public static void main (String[]args)     {        Scanner sc = new Scanner (System.in);        int a = sc.nextInt ();        int b = sc.nextInt ();        System.out.println (hammingDistance (a, b));    } }`
`#include<bits/stdc++.h>using namespace std;int hammingDistance (int a, int b){  int max = a > b ? a : b;  int count = 0;  while (max > 0)    {      if ((a & 1) != (b & 1))	  count++;            a = a >> 1;      b = b >> 1;      max = max >> 1;    }    return count;}int main (){  int a, b;  cin >> a >> b;  cout << hammingDistance (a, b);  return 0;}`

### Question 10

Problem Statement: Given boolean 2D matrix , find the number of islands. A group of connected 1s form an island. For example, the below matrix contains 5 islands.

Example :

m =5, n=5

1  1  0  0  0

0  1  0  0  1

1  0  0  1  1

0  0  0  0  0

1  0  1  0  1

Output :

5

Explanation:  There are total 5 island in the matrix.

`import java.util.*;class Solution{  private int directions[][] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };  public static int countIsland (int[][]arr)  {    if (arr == null || arr.length == 0)      return 0;    int islandId = 2, m = arr.length, n = arr.length;    Map < Integer, Integer > map = new HashMap ();    for (int i = 0; i < m; i++)      {	for (int j = 0; j < n; j++)	  {	    if (arr[i][j] == 1)	      {		int size = getIslandSize (arr, i, j, islandId);		map.put (islandId++, size);	      }	  }      }    return map.size ();  }  private static int getIslandSize (int[][]grid, int i, int j, int islandId)  {    if (i < 0 || j < 0 || i >= grid.length || j >= grid.length	|| grid[i][j] != 1)      return 0;    grid[i][j] = islandId;    int left = getIslandSize (grid, i, j - 1, islandId);    int right = getIslandSize (grid, i, j + 1, islandId);    int up = getIslandSize (grid, i - 1, j, islandId);    int down = getIslandSize (grid, i + 1, j, islandId);    int a = getIslandSize (grid, i - 1, j - 1, islandId);    int b = getIslandSize (grid, i + 1, j + 1, islandId);    int c = getIslandSize (grid, i + 1, j - 1, islandId);    int d = getIslandSize (grid, i - 1, j + 1, islandId);    return left + right + up + down + 1 + a + b + c + d;  }  public static void main (String[]args)  {    Scanner sc = new Scanner (System.in);    int m = sc.nextInt ();    int n = sc.nextInt ();    int arr[][] = new int[m][n];    for (int i = 0; i < m; i++)      for (int j = 0; j < n; j++)	arr[i][j] = sc.nextInt ();    System.out.println (countIsland (arr));  }}`

### One comment on “Cognizant GenC Next Coding Questions”

• Itika

Code for qs 10
#include
int main(){
int r,c,i,j,count=0,final;
scanf(“%d %d”, &r, &c);
int arr[r][c];
for(i=0; i<r; i++){
for(j=0; j<c; j++){
scanf("%d", &arr[i][j]);
}
}
for(i=0; i<r; i++){
for(j=0; j<c; j++){
if(arr[i][j]==1){
count++;
}
}
}
final=count/2;
printf("%d", final);
return 0;
} 5