Programming
Aptitude
Syllabus
Interview Preparation
Interview Exp.
Off Campus
Advance Coding Question section is an additional section in the Round 2 of Goldman Sachs hiring process. This section is an additional section after the basic coding round. This round is fairly difficult that the first round, and the questions asked in this round are from dynamic programming or greedy approach, unlike data structures which are asked in the first round.
No. of Question
1 Question
Difficulty
High
Time Limit
30 mins
Importance
High
Question 1
You have a positive integer m and a non-negative integer s. Your task is to find the smallest and the largest of the numbers that have length m and sum of digits s. The required numbers should be non-negative integers written in the decimal base without leading zeroes.
Input
Output
Examples
n,s=map(int,input().split())
if(n>1 and s==0):
print(-1 , -1)
elif(n==1 and s==0):
print(0, 0)
else:
br=[0]*n
i=0
brk=0
while(s>0):
if(i<n):
br[i]=min(9,s)
s=s-br[i]
i=i+1
else:
print(-1, -1)
brk=1
break
if(brk==0):
maxm=0
i=10
j=0
while(j<n):
maxm=maxm*i + br[j]
j+=1
#print(maxm)
minm=0
j=n-1
i=10
f=0
while(j>=0):
if(j==n-1 and br[j]==0):
minm=minm+1
f=1
else:
if(br[j]>0 and f==1):
minm=minm*i + br[j]-1
f=0
else:
minm=minm*i + br[j]
#print('h')
j=j-1
print(minm,maxm)
import java.util.*;
class Solution
{
public static void solve(int m,int s)
{
int sum=s-1;
if(m!=-1&&s==0 || s>9*m)
{
System.out.println("-1 -1");
return;
}
String res1="",res2="";
for(int i=0;i<m;i++)
{
res1+=Math.min(s,9);
s=s-Math.min(9,s);
}
for(int i=0;i<m-1;i++)
{
res2+=Math.min(sum,9)+res2;
sum=sum-Math.min(9,sum);
}
res2=(sum+1)+res2;
System.out.println(res2+ " "+res1);
}
public static void main(String[] args)
{
Scanner sc=new Scanner(System.in);
int m=sc.nextInt();
int s=sc.nextInt();
solve(m,s);
}
}
#include<bits/stdc++.h>
using namespace std;
void number (int m, int s)
{
int sum = s;
string mini = "", maxi = "";
if ((m != -1 and s == 0) or s > 9 * m)
{
cout << "-1 -1";
return;
}
for (int i = 0; i < m; i++)
{
int x = min (9, s);
maxi += to_string (x);
s = s - x;
}
for (int i = 0; i < m - 1; i++)
{
int x = min (9, sum);
mini += to_string (x);
sum -= x;
}
mini = to_string (sum) + mini;
cout << mini << " " << maxi;
return;
}
int main ()
{
int m, s;
cin >> m >> s;
number (m, s);
return 0;
}
Question 2
Karan got bored, so he invented a game to be played on paper. He writes n integers a1, a2, …, an. Each of those integers can be either 0 or 1. He’s allowed to do exactly one move: he chooses two indices i and j (1 ≤ i ≤ j ≤ n) and flips all values ak for which their positions are in range [i, j] (that is i ≤ k ≤ j). Flip the value of x means to apply operation x = 1 – x.
The goal of the game is that after exactly one move to obtain the maximum number of ones. Write a program to solve the little game of Iahub.
Input
Output
Examples
Note
n=int(input())
ar=list(map(int,input().split()))
if(n==1):
if(ar[0]==1):
print(0)
else:
print(1)
else:
br=[0]*n
for i in range(n):
if(ar[i]==0):
br[i]=1
else:
br[i]=-1
maxms=0
maxm=0
end=0
start=0
j=0
for i in range(n):
maxms+=br[i]
if(maxm<maxms):
maxm=maxms
end=i
if(j>start):
start=j
if(maxms<0):
maxms=0
j=i+1
for i in range(start,end+1):
if(ar[i]==0):
ar[i]=1
else:
ar[i]=0
if(ar.count(1)==n and maxm==0):
print(ar.count(1)-1)
else:
print(ar.count(1))
import java.util.*;
public class Solution
{
public static void main (String[]args)
{
Scanner sc = new Scanner (System.in);
int n = sc.nextInt ();
int countZero = 0, countOne = 0, max = -1;
while (n-- > 0)
{
int temp = sc.nextInt ();
if (temp == 1)
{
countOne++;
if (countZero > 0)
countZero = countZero - 1;
}
else
{
countZero++;
if (countZero > max)
max = countZero;
}
}
System.out.println (countOne + max);
}
}
#include<bits/stdc++.h>
using namespace std;
int main ()
{
int n;
cin >> n;
int ones = 0;
int a[n];
for (int i = 0; i < n; i++){
cin >> a[i];
if (a[i] == 1){
ones++;
a[i] = -1;
}
else a[i] = 1;
}
if(ones == n)
{
cout << n - 1;
}
else
{
int max_sum = 0, curr_sum = 0;
for (int i = 0; i < n; i++)
{
curr_sum += a[i];
max_sum = max (max_sum, curr_sum);
if (curr_sum < 0)
curr_sum = 0;
}
cout << ones + max_sum;
}
return 0;
}
Question 3
Rahul has an array a, consisting of n integers a1, a2, …, an. The boy cannot sit and do nothing, he decided to study an array. Rahul took a piece of paper and wrote out m integers l1, l2, …, lm (1 ≤ li ≤ n). For each number li he wants to know how many distinct numbers are staying on the positions li, li + 1, …, n. Formally, he want to find the number of distinct numbers among ali, ali + 1, …, an.?
Rahul wrote out the necessary array elements but the array was so large and the boy was so pressed for time. Help him, find the answer for the described question for each li.
Input
Output
Examples
n,m=map(int,input().split())
ar=list(map(int,input().split()))
a=set()
l=[0]*n
for i in range(n-1,-1,-1):
a.add(ar[i])
l[i]=len(a)
#print(l)
for i in range(m):
lx=int(input())
print(l[lx-1])
#include<bits/stdc++.h>
using namespace std;
int main ()
{
int n, m;
cin >> n >> m;
int a[n], b[m];
for (int i = 0; i < n; i++)
cin >> a[i];
for (int i = 0; i < m; i++)
cin >> b[i];
set < int >st;
int check[n] = { 0 };
for (int i = n - 1; i >= 0; i--)
{
st.insert (a[i]);
check[i] = st.size ();
}
for (int i = 0; i < m; i++)
cout << check[b[i] - 1] << 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 m = sc.nextInt ();
int a[] = new int[n];
int l[] = new int[m];
for (int i = 0; i < n; i++)
a[i] = sc.nextInt ();
for (int j = 0; j < m; j++)
l[j] = sc.nextInt ();
int dp[] = new int[n];
HashSet < Integer > s = new HashSet < Integer > ();
for (int i = n - 1; i >= 0; i--)
{
s.add (a[i]);
dp[i] = s.size ();
}
for (int j = 0; j < m; j++)
System.out.println (dp[l[j] - 1]);
}
}
Question 4
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.
Function Description
Returns
int: the minimum number of street lights that must be activated
Constraints
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
#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<<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;
}
Question 5
You just received another bill which you cannot pay because you lack the money.
Unfortunately, this is not the first time to happen, and now you decide to investigate the cause of your constant monetary shortness. The reason is quite obvious: the lion’s share of your money routinely disappears at the entrance of party localities.
You make up your mind to solve the problem where it arises, namely at the parties themselves. You introduce a limit for your party budget and try to have the most possible fun with regard to this limit.
You inquire beforehand about the entrance fee to each party and estimate how much fun you might have there. The list is readily compiled, but how do you actually pick the parties that give you the most fun and do not exceed your budget?
Write a program which finds this optimal set of parties that offer the most fun. Keep in mind that your budget need not necessarily be reached exactly. Achieve the highest possible fun level, and do not spend more money than is absolutely necessary.
Input
Output
Example
def knapSack(W, wt, val, n):
K = [[0 for x in range(W + 1)] for x in range(n + 1)]
for i in range(n + 1):
for w in range(W + 1):
if i == 0 or w == 0:
K[i][w] = 0
elif wt[i-1] <= w:
K[i][w] = max(val[i-1]
+ K[i-1][w-wt[i-1]],
K[i-1][w])
else:
K[i][w] = K[i-1][w]
res = K[n][W]
res1=res
x=0
w = W
for i in range(W+1):
if(K[n][i]==res):
x=i
break
print(x , res1)
b,n=map(int,input().split())
fun=[]
cost=[]
for i in range(n):
x,y=map(int,input().split())
fun.append(y)
cost.append(x)
(knapSack(b,cost,fun,n))
import java.util.*;
class Solution
{
public static void main (String[]args)
{
Scanner sc = new Scanner (System.in);
while (true)
{
int budget = sc.nextInt ();
int n = sc.nextInt ();
if (budget == 0 && n == 0)
break;
int cost[] = new int[n + 1];
int fun[] = new int[n + 1];
int arr[][] = new int[n + 1][budget + 1];
for (int i = 0; i < n; i++)
{
cost[i] = sc.nextInt ();
fun[i] = sc.nextInt ();
}
for (int i = 0; i <= n; i++)
for (int j = 0; j <= budget; j++)
arr[i][j] = 0;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= budget; j++)
if (cost[i - 1] <= j)
arr[i][j] =Math.max (fun[i - 1] + arr[i - 1][j - cost[i - 1]],arr[i - 1][j]);
else
arr[i][j] = arr[i - 1][j];
}
int c = 0;
for (int i = 0; i <= budget; i++)
{
if (arr[n][i] == arr[n][budget])
{
c = i;
break;
}
}
System.out.println (c + " " + arr[n][budget]);
}
}
}
#include<bits/stdc++.h>
using namespace std;
int main ()
{
int w, n;
x:cin >> w >> n;
if (w == 0 and n == 0)
goto r;
else{
int ct[n], val[n];
for (int i = 0; i < n; i++)
{
cin >> ct[i] >> val[i];
}
int t[n + 1][w + 1];
for (int i = 0; i <= n; i++){
for (int j = 0; j <= w; j++)
t[i][j] = 0;
}
for (int i = 1; i <= n; i++){
for (int j = 1; j <= w; j++){
if (ct[i - 1] <= j)
t[i][j] = max (val[i - 1] + t[i - 1][j - ct[i - 1]], t[i - 1][j]);
else
t[i][j] = t[i - 1][j];
}
}
int cost = 0;
for (int i = 0; i <= w; i++){
if (t[n][i] == t[n][w]){
cost = i;
break;
}
}
cout << cost << " " << t[n][w] << endl;
goto x;
}
r:return 0;
}
The following are not the actual questions of Goldman Sachs, these are just practice questions created by the PrepInsta team
internally and are the original creation of PrepInsta, created in fair use as per the Govt of India fair use.
100+ Topic-Wise Mocks
Login/Signup to comment