Goldman Sachs Coding Questions

September 7, 2023

Goldman Sachs Coding Questions for 2023 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

Goldman Sachs Practice Coding Questions

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)

C++

C++

Java

C++


#include<bits/stdc++.h>
using namespace std;
int n, m;
int mat[105][105];
map>, 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;

}

C++


#include<bits/stdc++.h>
using namespace std;
int n, m;
int mat[105][105];
map>, 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;

}

Java

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[6][6][6];
    initializeDp(dp, -1);
    if (grid[n - 1][m - 1] == -1 || grid[0][0] == -1)
      ans = -1 * Integer.MAX_VALUE;
    if (grid[0][0] == 1)
      ans++;
    grid[0][0] = 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[4]-a[6]=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.

C

Python

Java

C

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int solve(vector v)
{
    int n = v.size();
    if (n == 0)
        return 0;
    int mx = v[0];
    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 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;
}

Python

n=int(input())
arr=[]

ans=[0]

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))

Java

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[1] = 0, max((1 – 0),
  - 1) to mini (1+0), 3) gives range = 1 to 1
- For position 2: locations[2] = 2, max((2-2),
  - 1) to min( (2+2), 3) gives range = 1 to 3
- For position 3: locations[3] = 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] = 1, maxi (1 -1), 1) to min((1+1), 3) gives range = 1 to 2
For position 2: locations[2] = 1, max( (2 -1), 1) to min( (2+1), 3) gives range = 1 to 3
For position 3: locations[3] = 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.

C++

Java

C++

#include<bits/stdc++.h>

#define ll long long

using 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<> n;

  int location[n];

  for (int i = 0; i < n; i++)

    cin >> location[i];

  cout << solve(location, n) << endl;

  return 0;

}

Java

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 {

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

C++

Java

C++

#include<bits/stdc++.h>

using namespace std;
class job {
  public: int st,
  ed,
  cost;
};
int getTime(string s) {
  int hr = (s[0] - '0') * 10 + (s[1] - '0');
  int min = (s[2] - '0') * 10 + (s[3] - '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[0] = arr[0].cost;
  numOfJobs[0] = 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;
}

Java

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[0] = arr[0].cost;
    numOfJobs[0] = 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:

All node names are single characters in the range ascii[A-Z].
The maximum node count is 26.
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))

C++

C++

#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[2], monitor;

char find(char c)

{

  if (monitor[c]) return monitor[c];

  if (root[c] == 0) return 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[0][c], ch[1][c]));
      ans += '(';
      makeans(max(ch[0][c], ch[1][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[0][s[i + 1]] == '\0' ? ch[0][s[i + 1]] = s[i + 3] : ch[1][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

Java

Python

#python Program
#Rishikesh 
from collections import deque
def shortestPath(grid, k):
    #print(grid)
    n, m = len(grid), len(grid[0])
    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] == '.':
                    visited.add(key)
                    queue.append((nx, ny,dist + 1))
    return -1 

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')

Java

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][0] = 0;

    for (int i = 1; i < n; i++)

    {

      if (matrix[0][i] == '#')

        break;

      dp[0][i] = dp[0][i - 1] + 1;

    }

    for (int i = 1; i < n; i++)

    {

      if (matrix[i][0] == '#')

        break;

      dp[i][0] = dp[i - 1][0] + 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

C++

Java

C++

#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;
}

Java

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

Python

c++

Java

Python

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))

c++

#include<bits/stdc++.h>

using namespace std;

int main() {
  
  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;
}

Java

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

Python

Java

Python

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))

Java

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:

**.**

*…*

…..

*…*

**.**

C

C

#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;
}

Question 11:

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)

C++

Java

C++

#include <bits/stdc++.h>
using namespace std;
int n, m;
int mat[105][105];
map>, 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;
}

Java

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[6][6][6];
  initializeDp(dp,-1);
 if (grid[n - 1][m - 1] == -1 || grid[0][0] == -1)
		ans = -1 * Integer.MAX_VALUE;

	if (grid[0][0] == 1)
		ans++;
	grid[0][0] = 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

Question 12 :

Street Lights are installed at every position along a 1-D road of length n. Locations[] (an array) represents the coverage limit of these lights. The ith light has a coverage limit of locations[i] that can range from the position max((i – locations[i]), 1) to min((i + locations[i]), n ) (Closed intervals). Initially all the lights are switched off. Find the minimum number of fountains that must be switched on to cover the road.

Example

n = 3

locations[] = {0, 2, 13}then

For position 1: locations[1] = 0, max((1 – 0),

1) to mini (1+0), 3) gives range = 1 to 1

For position 2: locations[2] = 2, max((2-2),

1) to min( (2+2), 3) gives range = 1 to 3

For position 3: locations[3] = 1, max( (3-1),

1) to min( (3+1), 3) gives range = 2 to 3

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

Returns:

int : the minimum number of street lights that must be activated

Constraints :

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

Sample Input For Custom Testing :

3 ->locations[] size n = 3

1 ->locations[] [1, 1, 1]

1 ->Sample Output

Sample Output :

1

C++

Python

Java

C++

#include <bits/stdc++.h>
#define ll long long
using namespace std;
bool compare(pair A, pair B)
{
    if (A.first = B.first)
        return A.second < B.second;
    return A.first < B.first;
}
int solve(int location[], int n)
{
 
    pair 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 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<> n;
    int location[n];
    for (int i = 0; i < n; i++)
        cin >> location[i];
 
    cout << solve(location, n) << endl;
    return 0;
}

Python

def Sort_Tuple(tup): 
      
    # getting length of list of tuples
    lst = len(tup) 
    for i in range(0, lst):
        for j in range(0, lst-i-1): 
            if (tup[j][1] > tup[j + 1][1]): 
                temp = tup[j] 
                tup[j]= tup[j + 1] 
                tup[j + 1]= temp 
    return tup 
 
 
def solve(l,n):
    rang=[[0,0]for i in range(n)]
    #print(rang)
    for i in range(n):
        id=i+1
        rang[i][0]=max(1,id-l[i])
        rang[i][1]=min(n,id+l[i])
 
    Sort_Tuple((rang))
 
    i=0
    ans=0
    while ip[1]:
                break
            i+=1
 
    return ans
n=int(input())
l=[]
for i in range(n):
    l.append(int(input()))
print(solve(l,n))

Java

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
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{

	@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 Application2 {
	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 13 :

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 is less than 10000 i.e. 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 i.e. 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.

C++

Java

C++

#include <bits/stdc++.h>
using namespace std;
class job
{
public:
    int st, ed, cost;
};
int getTime(string s)
{
    int hr = (s[0] – ‘0’) * 10 + (s[1] – ‘0’);
    int min = (s[2] – ‘0’) * 10 + (s[3] – ‘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 solve(job arr[], int n)
{
    int dp[n] = {0};
    int numOfJobs[n] = {0};
 
    dp[0] = arr[0].cost;
    numOfJobs[0] = 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 res = solve(arr, n);
 
    cout << n – res.first << endl;
    cout << total – res.second << endl;
 
    return 0;
}

Java

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{

	@Override
	public int compare(Job o1, Job o2) {
		if(o1.eddp[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 14 :

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 case :

Sample input :
5 → number of packets=5
12 → size of packets=[13,25,12,2,8]
25
10
2
8
Sample output :
16

Python

Java

Python

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))

Java

import java.util.*;
public class NetworkStream
{
  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 temp=1,max=Integer.MIN_VALUE; 
  for(int i=0;i<n-1;i++)
 {
    temp=1;
    while(2*temp<=arr[i])
      temp=temp*2;
   max=Math.max(temp,max);
  arr[i+1]+=arr[i]-temp;  
}
temp=1;
while(2*temp<=arr[n-1])
 temp=temp*2;
 max=Math.max(temp,max);
 System.out.println(max);
}
}

Question 15 :

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:

**.**

*…*

…..

*…*

**.**

C

Python

Java

C

#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;
}

Python

n=int(input())
for i in range(n):
    print(“*”*(n-1-i)+“.”*(2*i+1)+“*”*(n-1-i))
for i in range(n-1):
    print(“*”*(i+1)+“.”*(2*(n-2-i)+1)+“*”*(i+1))

Java

import java.util.*;
class Trapezium
{
  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();
     }
 }
}

Question 16 :

You are given an array, You have to choose a contiguous subarray of length ‘k’, and find the minimum of that segment, return the maximum of those minimums.

Sample input 0

1 → Length of segment x =1

5 → size of space n = 5

1 → space = [ 1,2,3,1,2]

2

3

1

2

Sample output

3

Explanation

The subarrays of size x = 1 are [1],[2],[3],[1], and [2],Because each subarray only contains 1 element, each value is minimal with respect to the subarray it is in. The maximum of these values is 3. Therefore, the answer is 3

C++

Python

Java

C++

#include<bits/stdc++.h>
using namespace std;
vector arr;
int prevmin=-1;
int flag=0;
int x,n,q;

int sorting(int start,int end)
{
    if(start+1==n) {start=0;end=end-n;}
    if(start==end) return arr[start];
    return min(arr[start],sorting(start+1,end));
}

int func(int start,int end)
{
    if(flag==0) {flag++;return prevmin=sorting(start,end);}
    if(arr[start-1]==prevmin) return prevmin;
    return prevmin=(arr[end]<=prevmin)?prevmin:sorting(start,end);

}

int main()
{
    cin>>x>>n;
    int ans=0;
    for(int i=0;i>q;arr.push_back(q);}
    for(int i=0;i< n;i++)
    {
       ans=max(ans,func(i,i+x-1));
    }
    cout<< ans;
}

Python

s=int(input())
n=int(input())
a=[]
for i in range(n):
    a.append(int(input()))
   

def min_in_segment(start,end,prev,s,prev_min):
    if s==1:
        return a[start]
    else:
        if prev==-1 or prev_min==-2:
            return min(a[start:end+1])
        elif prev_min!=-2:
            if prev!=prev_min:
                if a[end]

Java

import java.util.*;
class DiskSpace
{
  public static void main(String[] args)
{
  Scanner sc=new Scanner(System.in);
  int x=sc.nextInt();
  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 max=Integer.MIN_VALUE;

  for(int i=0;i<=n-x;i++)
 {
    min=Integer.MAX_VALUE;
    for(int j=i;j<(i+x);j++)
     min=Math.min(min,arr[j]);
   max=Math.max(min,max);     
 }
 System.out.println(max);
}
}

Question 17 :

Kochouseph Chittilappilly went to Dhruv Zplanet , a gaming space, with his friends and played a game called “Guess the Word”.

Rules of games are –

Computer displays some strings on the screen and the player should pick one string / word if this word matches with the random word that the computer picks then the player is declared as Winner.
Kochouseph Chittilappilly’s friends played the game and no one won the game. This is Kochouseph Chittilappilly’s turn to play and he decided to must win the game.
What he observed from his friend’s game is that the computer is picking up the string whose length is odd and also that should be maximum. Due to system failure computers sometimes cannot generate odd length words. In such cases you will lose the game anyways and it displays “better luck next time”. He needs your help. Check below cases for better understand

Sample input :
5 → number of strings
Hello Good morning Welcome you
Sample output :
morning

Explanation:

Hello → 5
Good → 4
Morning → 7
Welcome → 7
You → 3

First word that is picked by computer is morning

Sample input 2 :
3
Go to hell

Sample output 2:
Better luck next time

Explanation:
Here no word with odd length so computer confuses and gives better luck next time

Java

Python

Java

import java.util.*;
public class OddLength
{
    public static void main(String[] args)
    {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        String arr[]=new String[n];
        
        for(int i=0;i  oddLength=new ArrayList();
        for(int i=0;imax)
                {
                    res=temp;     
                    max=temp.length(); 
                }
             }
            System.out.println(res);
        }
    }
}

Python

n=int(input())
sentence=input().split()
length=[]
for i in sentence:
    L=len(i)
    if L%2==1:
        length.append(len(i))
    else:
        length.append(0)
if max(length)==0:
    print("Better Luck next Time")
else:
    print(sentence[length.index(max(length))])

Question 18 :

Raman was playing a game, in starting he has x coins at some point of the game he has to pay some coins to get into the next level of the game, during each game he can collect some coins. If at anypoint of the game numbers of coins of Raman is less than one he will lose the game. Find the minimum value of x such that Raman wins.

C++

Python

C++

#include<iostream>
using namespace std;
 
int main() {
    int n; cin>>n;
    int a[n];
    for(int i=0;i>a[i];
    int sum=0,ans=0;
    for(int i=0;i< n;i++)
    {
        sum+=a[i];
        if(sum<1)
        {
            sum=-sum;
            ans+=sum+1;
            sum=1;
        }
    }
    cout<< ans<< endl;
}

Python

n=int(input())
arr=[]
for i in range(n):
    arr.append(int(input()))
s,a=0,0
for i in arr:
    s=s+i   
    if(s<1):
        a=a+(-1*s)+1 
        s=1 
print(a)

Question 19 :

The math assignment says you will be given numbers, mostly with imaginary additions, that means complex numbers, and you need to add them and tell the answer in your answer script. You told your friend John that you don’t know the addition of complex numbers, so John will write a program, which you can write in order to get the results of addition.

John knows Object oriented programming enough to complete the task.

Input Format:
Three integers a b and c
Output format:
First print the complex number a+bi
Next line print a + bi + c as i2.
Next line i2+a+bi

Sample Input:
4 5 2

Sample Output:
4 + 5i
6 + 5i
10 + 10i

C++

Java

C++

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

class Complex //Writing the variables and the functions together, but cant be changed globally -> Encapsulation
{
    private:
    int r,i; //Data Abstraction
    public:
    Complex(){r=i=0;}
    Complex(int f,int k)
    {
        r=f;i=k;
    }
    void show()
    {
        cout<>a>>b>>c;
    Complex i1(a,b);
    i1.show();
    Complex i2;
    i2=i1+c; //Operator Overloading -> Polymorphism
    i2.show();
    (i1+i2).show();

}

Java

import java.util.*;
 class ComplexNumber{
   int real, img;
	
   ComplexNumber(int r, int i){
	this.real = r;
	this.img = i;
   }
	
   public static ComplexNumber sum(ComplexNumber c1, ComplexNumber c2)
   {
        ComplexNumber temp = new ComplexNumber(0, 0);

        temp.real = c1.real + c2.real;
        temp.img = c1.img + c2.img;
        
        return temp;
    }
    public static void main(String args[]) {
          Scanner sc=new Scanner(System.in);
          int a=sc.nextInt();
          int b=sc.nextInt();
          int c=sc.nextInt();
         ComplexNumber c1 = new ComplexNumber(a, b);
          System.out.println(c1.real+" + "+c1.img +"i"); 
         ComplexNumber c2 = new ComplexNumber(c,0);
         ComplexNumber c3 = sum(c1, c2);
         System.out.println(c3.real+" + "+c3.img +"i");
         ComplexNumber c4=sum(c3,c1);
         System.out.println(c4.real+" + "+c4.img+"i");
     }
}

Question 20 :

Given a sting , return the character that appears the minimum number of times in the string. The string will contain only ascii characters, from the ranges (“a”-”z”,”A”-”Z”,0-9), and case matters . If there is a tie in the minimum number of times a character appears in the string return the character that appears first in the string.

Input Format:
Single line with no space denoting the input string.

OutputFormat:
Single character denoting the least frequent character.

Constraints:
Length of string <=10^6

Sample Input:
cdadcda

Sample Output:
c

Explanation:
C and A both are with minimum frequency. So c is the answer because it comes first with less index.

C++

Python

Java

C++

include<bits/stdc++.h>
using namespace std;
 
map ma;
 
int main()
{
    string s;int m=INT_MAX;
    cin>>s;
    for(int i=s.length()-1;i>=0;i--)
    {
        ma[s[i]]++;
        m=min(m,ma[s[i]]);
    }
    for(int i=0;i< s.length();i++)
    if(ma[s[i]]==m) {cout<< s[i];break;}
}

Python

s=input()
ans=[]
for i in s:
    ans.append(s.count(i))
print(s[ans.index(min(ans))])

Java

import java.util.*;
class MinimumOccurence
{
  public static void main(String[] args)
{
   Scanner sc=new Scanner(System.in);
   String str=sc.next();
   char arr[]=str.toCharArray();
   int temp[]=new int[256];
    for(int i=0;i<arr.length;i++)
   {
        temp[arr[i]]++;
   }
   int min=Integer.MAX_VALUE;
   int index=0; 
   for(int i=255;i>=0;i--)
    {
       if(temp[i]==0)
        continue;
       min=Math.min(min,temp[i]);
      } 
    for(int i=0;i<arr.length;i++)
   {
       if(min==temp[arr[i]])
     {
        System.out.println(arr[i]);  
        break;
     }
  }
}
}

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

Paid Material Coding Questions for Goldman Sachs

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription

×

30+ Companies are Hiring

Get Hiring Updates right in your inbox from PrepInsta