# Goldman Sachs Coding Questions

## Goldman Sachs Coding Questions for 2022 freshers

Goldman Sachs coding round consists of 2 advance coding questions, mostly based on HackerRank Platform. The difficulty level of these coding questions is higher and total time given to solve these questions is 30 mins ## Goldmann Sachs Coding Round Pattern

Coding QuestionMarks allotedDifficulty level
Question 120medium
Question 230high

### Question : 1

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.

For example consider the following grid,

0      1
-1     0

Start at top left corner.Move right one collecting a passenger. Move down one to the destination.Cell (1,0) is blocked,So the return path is the reverse of the path to the airport.All Paths have been explored and one passenger is collected.

Returns:

• Int:maximum number of passengers that can be collected.

Sample Input 0

• 4  -> size n = 4
• 4 -> size m = 4
• 0 0 0 1 -> mat
• 1 0 0 0
• 0 0 0 0
• 0 0 0 0

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

STD IN                  Function

————              ————-

•    3     →  size  n=3
•    3    →  size m=3
•    0 1 -1 → mat
•    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 Main {    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 : 2

You are given a list of daily prices of a stock. You can buy a stock on one day and sell it later on another day after the day you bought the stock. You can perform the above operation only once. What is the maximum loss possible?

Example

Prices=[10,4,2,9]

The greatest loss is incurred when you buy at a price of 10 and sell at a price of 2.Return the difference:9.

Example

Price=[1,2,3,4]

The Price went up everyday.Return 0.

Sample Input for Custom Testing

STDIN                   Function

———–               ————–

•    7   →     prices []  size n=7
•    1 →       prices =[1,8,4,2,10,3,2]
•    8
•    4
•    2
•   10
•    3
•    2

Sample Output

•   8

Explanation

Using zero-based index notation,the correct answer is a-a=10-2=8.There is a greater difference between 10 and 1 but that would imply selling before buying,and short selling is not allowed in this problem.

`#include <bits/stdc++.h>#define ll long longusing 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] - price[i+1]);    int ans = solve(diff);    if(ans<0)    {        cout<<0<<endl;    }    else    {        cout<<ans<<endl;    }        return 0;}`
`n=int(input())arr=[]ans=for i in range(n):    arr.append(int(input()))for i in range(n-1):     x=min(arr[i+1:])-arr[i]    if x<0:        ans.append(x)print(-1*min(ans))`
`import java.util.*;class Solution {    public static int solve (ArrayList < Integer > list)     {        int n = list.size ();        if (n == 0)            return 0;        int max = list.get (0);        for (int i = 1; i < n; i++)            max = Math.max (max, list.get (i));        if (max <= 0)            return 0;        int maxSum = 0;        int sum = 0;            for (int i = 0; i < n; i++)        {            sum = sum + list.get (i);            if (sum < 0)                sum = 0;            maxSum = Math.max (maxSum, sum);        }        return maxSum;    }      public static void main (String[]args)     {        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 ();        ArrayList < Integer > list = new ArrayList ();                for (int i = n - 2; i >= 0; i--)            list.add (arr[i] - arr[i + 1]);        int res = solve (list);            if (res < 0)            System.out.println (0);        else            System.out.println (res);    }}`

### Question : 3

Fountains are installed at every position along a one-dimensional garden of length n. Array locations[] represents the coverage limit of these fountains. The ith fountain (where 1sisn) has a coverage limit of locations[i] that can range from the position max((i – locations[i]), 1) to min((i + locations[i]), n ). In other words, the h fountains do not reach outside the boundaries of the garden. In the beginning,all the fountains are switched off. Determine the minimum number of fountains that need to be activated to cover the n length garden by water.

Example

• n = 3
• locations[] = {0, 2, 13, then
• For position 1: locations = 0, max((1 – 0),
• 1) to mini (1+0), 3) gives range = 1 to 1
• For position 2: locations = 2, max((2-2),
• 1) to min( (2+2), 3) gives range = 1 to 3
• For position 3: locations = 1, max( (3-1),
• 1) to min( (3+1), 3) gives range = 2 to 3

For the entire length of this garden to be covered, only the fountain at position 2 needs to be activated.

Function Description

Complete the function fountainActivation in the editor below.

fountainActivation has the following Parameter:

• int locations[n]: the fountain locations

Returns

• int: the minimum number of fountains that must be activated

Constraints

• 1<_n<_ 10^5
•  O<_locations[i] <_ mini (n,100) (where 1 <_1<_10^5)

► Input Format For Custom Testing

Sample Case 0

Sample Input For Custom Testing

• 3 ->locations[] size n = 3
• 1 ->locations[] [1, 1, 1
• 1 ->Sample Output

Sample Output

• 1

Explanation

Here, locations = {1, 1, 13

• For position 1: locations = 1, maxi (1 -1), 1) to min((1+1), 3) gives range = 1 to 2
• For position 2: locations = 1, max( (2 -1), 1) to min( (2+1), 3) gives range = 1 to 3
• For position 3: locations = 1, max((3 -1), 1) to min((3+1), 3) gyes range = 2 to 3

If the 2nd fountain is active, the range from position 7 to 3 will be covered. The total number of fountains needed is 1.

`#include <bits/stdc++.h>#define ll long longusing namespace std;bool compare(pair<int, int> A, pair<int, int> B){    if (A.first = B.first)        return A.second < B.second;    return A.first < B.first;}int solve(int location[], int n){    pair<int, int> range[n];    for (int i = 0; i < n; i++)    {        int id = i + 1;        range[i].first = max(1, id - location[i]);        range[i].second = min(n, id + location[i]);    }    sort(range, range + n, compare);    int i = 0;    int ans = 0;    while (i < n)    {        pair<int, int> p = range[i];        ans++;        while (i + 1 < n && range[i].first == range[i + 1].first)        {            p.second = max(p.second, range[i + 1].second);            i++;        }        //cout<<p.second<<" "<<i<<endl;        while (i < n && range[i].second <= p.second)            i++;        //cout<<p.second<<" "<<i<<endl;    }    return ans;}int main(){    int n;    cin >> n;    int location[n];    for (int i = 0; i < n; i++)        cin >> location[i];    cout << solve(location, n) << endl;    return 0;}`
`import java.util.*;class Pair{    Integer a;    Integer b;        Pair ()    {    }    Pair (Integer a, Integer b)    {        this.a = a;        this.b = b;    }      public Integer getA ()    {        return a;    }      public void setA (Integer a)    {        this.a = a;    }     public Integer getB ()    {        return b;    }      public void setB (Integer b)    {        this.b = b;    } } class SortingPair implements Comparator <Pair>{     @Override     public int compare (Pair o1, Pair o2)    {        if (o1.getA () == o2.getA ())        {            if (o1.getB () < o2.getB ())	        {                return 1;            }    	    else    	    {                return 0;            }        }        if (o1.getA () < o2.getA ())        {            return 1;        }        else        {            return 0;        }    }}public class Solution{      public static void main (String args[])    {        Scanner sc = new Scanner (System.in);        int n = sc.nextInt ();        int location[] = new int[n];        for (int i = 0; i < n; i++)        {            location[i] = sc.nextInt ();        }         System.out.println (solve (location, n));    }     private static int solve (int[]location, int n)    {        Pair range[] = new Pair[n];        for (int i = 0; i < n; i++)        {            int id = i + 1;            range[i] = new Pair ();            range[i].setA (Math.max (1, id - location[i]));            range[i].setB (Math.min (n, id + location[i]));        }         Arrays.sort (range, new SortingPair ());        int i = 0, ans = 0;        while (i < n)        {            Pair p = range[i];            ans++;            while (i + 1 < n && range[i].getA () == range[i + 1].getA ())	        {                p.b = Math.max (p.getB (), range[i + 1].getB ());                i++;            }            while (i < n && range[i].getB () <= p.getB ())	        {                i++;            }        }        return ans;    }}`

### Question : 4

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 :

• 3
• 0900
• 1030
• 100
• 1000
• 1200
• 500
• 53
• 1100
• 1200
• 300

Sample Output 1:

• 2
• 400

Sample Explanation 1

Anirudh chooses 1000-1200 jobs. His earnings is 500. The 1st and 3rd jobs ie 0900-1030 and 1100-1200 respectively overlap with the 2nd jobs. But profit earned from them will be 400 only. Hence Anirudh chooses 2nd one. Remaining 2 Jobs & 400 cash for other employees

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.*;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 Main{    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 5:

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 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->valval(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

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,childOf
map<pair<char,char>,int> duplicateedgecheck;//Duplicate edge check
unordered_map<char,char> par,ch,monitor;
char find(char c)
{
if(monitor[c]) return monitor[c];
if(root[c]==0return monitor[c]=c;
return monitor[c]=find(par[c]);
}

void makeans(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+=‘)’;}
}

int main()
{
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 6:

Ajay has a flight to catch in an hour. So he has to reach the airport as fast at possible. He hires a taxi and promises the taxi driver that if he reaches the airport within k minutes he would pay the taxi driver double the amount.

The city description is as follows –

The taxi is at point 0,0  & airport is at (n-1,m-1) in a 2 – D grid of n rows and m columns. The grid has some blocked (represented as’#’) and some unblocked (represented as’.’) cells.

The starting position of the taxi is in the top – left corner of the grid. It is guaranteed that the starting position & ending positions are not blocked. Each cell of the grid is connected with its right ,left,top,bottom cells (if those cells exist ). It takes 1 second for a taxi to move from a cell to its adjacent cell.

If the taxi can reach the bottom-right (airport) corner of the grid within  k seconds, return the string ‘Yes’. Otherwise , return the string ‘No’.

Example

rows =3

grid =[‘..##’,’#.##’,’#…’]

maxTime =5

..##

#.##

#…

It will take the taxi 5 seconds to reach the bottom right corner. As long as k>_5,return

‘Yes’.

Returns:

String;the final string; either ‘yes’ or ‘ No’

Constraints

• 1<_rows<_500
• 0<_maxTime<_10^6

Input Format For Custom Testing

• The first line contains an integer,rows that denotes the number of rows of the 2-D grid
•  In each of the next rows lines, the i^th line contains a string denoting the configuration of the i^th row of the grid.
• The last line contains an integer, maxTime ,that represents the maximum time in seconds the taxi has to reach the bottom right cell.

Example

• Sample Input 0
2 -> size of grid[] rows =2
.. -> grid = [‘..’,’..’]
..
3 -> maxTime = 3

• Sample Output 0
Yes

Explanation

The grid has 2 rows and 2 columns and the time within which the taxi needs to reach the bottom-right cell in 3 seconds. Starting from the top-left cell, the taxi can either move to the top-right unblocked

#python Program

#Rishikesh

from collections import deque

def shortestPath(grid, k):

#print(grid)

n, m = len(grid), len(grid)

queue = deque([(0, 0,0)])

visited = {(0, 0)}

while queue:

x, y,dist = queue.popleft()

if (x, y) == (n-1, m-1):

return dist

else:

for dx, dy in ((-1, 0), (+1, 0), (0, –1), (0, +1)):

nx, ny = x + dx, y + dy

key = (nx, ny)

if not (0 <= nx < n and 0 <= ny < m) or key in visited:

continue

if grid[nx][ny] == ‘.’:

queue.append((nx, ny,dist + 1))

return1

n=int(input())

ar=[]

for i in range(n):

s=list(input())

ar.append(s)

k=int(input())

#a=(shortestPath(ar,k))

print(a)

if(a<=k):

print(‘YES’)

else:

print(‘NO’)

`import java.util.*;public class Main{     public static void main (String[]args)     {        Scanner sc = new Scanner (System.in);        int n = sc.nextInt ();        char matrix[][] = new char[n][n];        for (int i = 0; i < n; i++)            for (int j = 0; j < n; j++)                matrix[i][j] = sc.next().charAt (0);        int dp[][] = new int[n][n];        for (int i = 0; i < n; i++)            for (int j = 0; j < n; j++)                dp[i][j] = Integer.MAX_VALUE;            long maxTime = sc.nextInt ();        dp = 0;        for (int i = 1; i < n; i++)        {            if (matrix[i] == '#')                break;            dp[i] = dp[i - 1] + 1;        }            for (int i = 1; i < n; i++)        {            if (matrix[i] == '#')                break;            dp[i] = dp[i - 1] + 1;        }            for (int i = 1; i < n; i++)        {            for (int j = 1; j < n; j++)    	    {                if (matrix[i][j] == '#')                    continue;                dp[i][j] = Math.min (dp[i - 1][j], dp[i][j - 1]) + 1;            }        }                if (dp[n - 1][n - 1] < maxTime)            System.out.println ("Yes");        else            System.out.println ("No");    }}  `

### Question 7:

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.

Examples

• 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;
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 Solution {    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++)        {            bl.add (sc.nextInt ());        }         int v = sc.nextInt ();        List < Integer > vl = new ArrayList <> ();            for (int i = 0; i < v; i++)        {            vl.add (sc.nextInt ());        }         Set < Integer > sl = new HashSet <> ();        int res = 0;          for (Integer i:vl)        {            if (bl.contains (i))                continue;            sl.add (i);        }         for (Integer i:sl)        {            String s = i + "";            res += s.length ();        }        System.out.println (res);    }}`

### Question 8:

Anirudh loves to play games but his father is very strict. But one day his father agreed to get him a new game if he solves the following problem –

Given an array of Integers, determine the number of moves to make all elements equal. Each move consists of choosing  all but 1 element and Incrementing their values by 1. Can you help Anirudh?

Example

numbers= [3, 4, 6, 6, 3]

Choose 4 of the 5 elements during each move and Increment each of their values by one. Indexing begins at 1. It takes 7 moves as follows:

 iteration array 0 [3,4,6,6,3] 1 [4,5,7,6,4] 2 [5,6,7,7,5] 3 [6,7,8,7,6] 4 [7,8,8,8,7] 5 [8,9,9,8,8] 6 [9,9,10,9,9] 7 [10,10,10,10,10]

Returns: long: the minimum number of moves required

Constraints

1<=n<=10^5

1<=numbers(i)<=10^6

Sample case 0:

Sample input 0:

5 → size of numbers[]

3 → numbers[]=[3,4,6,6,3]

4

6

6

3

Sample output 0:

7

Sample input 1:

4

4

3

4

Sample Output 1:

2

def minMoves(n,nums):
s=0
i = nums.index(min(nums))
for j in range(n):
if(i==j):
continue
else:
s= s+nums[j]-nums[i]
return s

n=int(input())
numbers=[]
for i in range(n):
numbers.append(int(input()))
print(minMoves(n,numbers))
#include <bits/stdc++.h>
using namespace std;

int main() {
// your code goes here
int t;
t = 1;
while (t) {
int n;
cin >> n;
int arr[n];
for (int i = 0; i < n;i++) cin >> arr[i];
int min_element = INT_MAX;
long long int sum = 0;
for (int i = 0; i < n;i++) {
min_element = min(min_element,arr[i]);
sum += arr[i];
}
cout << sum – n * min_element << endl;

}
return 0;
}
`import java.util.*;class Solution {    public static void main (String[]args)     {        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 ();        int min = Integer.MAX_VALUE;        int sum = 0;        for (int i = 0; i < n; i++)        {            min = Math.min (min, arr[i]);            sum += arr[i];        }         System.out.println (sum - n * min);    } }`

### Question 9:

A stream of n data packets arrives at a server. This server can only process packets that are exactly 2^n units long for some non-negative integer value of n (0<=n).

All packets are repackaged in order to the 1 largest possible value of 2^n units. The remaining portion of the packet is added to the next arriving packet before it is repackaged. Find the size of the largest repackaged packet in the given stream.

Example arriving Packets = [12, 25, 10, 7, 8]

The first packet has 12 units. The maximum value of 2^n that can be made has 2^n = 2^3 = 8 units because the next size up is 2^n = 2^4 = 16 (16 is greater than 12).

12 – 8 = 4 units are added to the next packet. There are 4 + 25 = 29 units to repackage, 2^n = 2^4 = 16 is the new size leaving 9 units (29-16 = 9)

Next packet is 9 + 10 = 29 unists & the maximum units(in 2^n) is 16 leaving 3 units.

3 + 7 = 10 , the max units is 8 Leaving 2 units, and so on.

The maximum repackaged size is 16 units.

Returns:

Long : the size of the largest packet that is streamed

Constraints :

• 1<=n<=10^5
• 1<=arriving Packets[i] size<=10^9

Sample case0

Sample input 0:

5 → number of packets=5

12 → size of packets=[13,25,12,2,8]

25

10

2

8

Sample output 0:

16

def largeRepackagedPacket(arr):
twoP=[int(2**i) for i in range(31)]
x=0
ans=0
for i in arr:
i=i+x
for j in range(31):
if i<twoP[j]:
break
x=i-twoP[j-1]
if ans<=twoP[j-1]:
ans=twoP[j-1]
return ans

Packets=[]
for i in range(int(input())):
Packets.append(int(input()))
print(largeRepackagedPacket(Packets))
`import java.util.*;class Solution {    public static void main (String[]args)     {        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 ();                int max = Integer.MIN_VALUE;        int j = 1, temp = 0;            for (int i = 0; i < n - 1; i++)        {            j = 1;            temp = 0;            while ((int) Math.pow (2, j) < arr[i])    	    {                temp = (int) Math.pow (2, j);                j++;            }             if (temp > max)                max = temp;            arr[i + 1] += arr[i] - temp;        }        j = 1;        temp = 0;        while ((int) Math.pow (2, j) < arr[j])        {            temp = (int) Math.pow (2, j);            j++;        }         if (temp > max)            max = temp;        System.out.println (max);    }}`

### Question 10:

Anirudh is attending an astronomy lecture. His professor who is very strict asks students to

Write a program to print the trapezium pattern using stars and dots as shown below . Since Anirudh is not good in astronomy can you help him?

Sample Input:

N = 3

Output:

**.**

*…*

…..

*…*

**.**

#include <stdio.h>
int main()
{
int i,j,n;
scanf(%d,&n);
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(j<n-i-1)
printf(“*”);
else
printf(“.”);
}
for(j=0;j<n-1;j++)
{
if(j<i)
printf(“.”);
else
printf(“*”);
}
printf(\n);
}

for(i=2;i<=n;i++)
{
for(j=0;j<n;j++)

{
if(j<i-1)
printf(“*”);
else
printf(“.”);

}
for(j=0;j<n-1;j++)
{
if(j<n-i)
printf(“.”);
else
printf(“*”);
}
printf(\n);
}
return 0;
}

`import java.util.*;class Solution {    public static void main (String[]args)     {        Scanner sc = new Scanner (System.in);        int n = sc.nextInt ();        int i, j;        for (i = 0; i < n; i++)        {            for (j = 0; j < n; j++)    	    {                if (j < n - i - 1)                    System.out.print ("*");        	    else                    System.out.print (".");            }            for (j = 0; j < n - 1; j++)        	{                   if (j < i)                    System.out.print (".");        	    else                    System.out.print ("*");            }            System.out.println ();        }        for (i = 2; i <= n; i++)        {            for (j = 0; j < n; j++)    	    {                if (j < i - 1)                    System.out.print ("*");        	    else                    System.out.print (".");            }            for (j = 0; j < n - 1; j++)    	    {                if (j < n - i)                    System.out.print (".");        	    else                    System.out.print ("*");            }            System.out.println ();        }    }}`

## Analyze your prepration with PrepInsta Prime Mock

100+ Topic-Wise Mocks

• All Mocks are based on Goldman Sachs Previous Year Papers
• Detailed analytics and Smart Dashboard 