Goldman Sachs Advance Coding Questions

February 18, 2021

Goldman Sachs Advanced Coding Questions And Answers

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.

Goldman Sachs Practice Coding Questions

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

The single line of the input contains a pair of integers m, s (1 ≤ m ≤ 100, 0 ≤ s ≤ 900) — the length and the sum of the digits of the required numbers.

Output

In the output print the pair of the required non-negative integer numbers — first the minimum possible number, then — the maximum possible number. If no numbers satisfying conditions required exist, print the pair of numbers “-1 -1” (without the quotes).

Examples

Input 1
2 15
Output 1
69 96

Input 2
3 0
Output 2
-1 -1

Python

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)

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

The first line of the input contains an integer n (1 ≤ n ≤ 100). In the second line of the input there are n integers: a1, a2, …, an. It is guaranteed that each of those n values is either 0 or 1.

Output

Print an integer — the maximal number of 1s that can be obtained after exactly one move.

Examples

Input
5
1 0 0 1 0
Output
4

Input
4
1 0 0 1
Output
4

Note

In the first case, flip the segment from 2 to 5 (i = 2, j = 5). That flip changes the sequence, it becomes: [1 1 1 0 1]. So, it contains four ones. There is no way to make the whole sequence equal to [1 1 1 1 1].
In the second case, flipping only the second and the third element (i = 2, j = 3) will turn all numbers into 1.

Python

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

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

The first line contains two integers n and m (1 ≤ n, m ≤ 105). The second line contains n integers a1, a2, …, an (1 ≤ ai ≤ 105) — the array elements.
Next m lines contain integers l1, l2, …, lm. The i-th line contains integer li (1 ≤ li ≤ n).

Output

Print m lines — on the i-th line print the answer to the number li.

Examples

Input
10 10
1 2 3 4 1 2 3 4 100000 99999
1
2
3
4
5
6
7
8
9
10
Output
6
6
6
6
6
5
4
3
2
1

Python

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

Question 4

Given a string consisting of the letters a,b and c, we can perform the following operation:

Take any two adjacent distinct characters and replace them with the third character.

Find the shortest string obtainable through applying this operation repeatedly.

For example, given the string aba we can reduce it to a 1 character string by replacing ab with c and ca with b : .
aba -> ca -> b

Function Description

Complete the stringReduction function in the editor below. It must return an integer that denotes the length of the shortest string obtainable.

stringReduction has the following parameter:

– s: a string

Input Format

The first line contains the number of test cases .
Each of the next lines contains a string to process.

Constraints

1 <= t <= 100
1 < |s| <= 100

Output Format

For each test case, print the length of the resultant minimal string on a new line.

Example

Sample Input
3
cab
bcab
ccccc
Sample Output
2
1
5

Explanation

For the first case, there are two solutions: cab -> cc or cab -> bb .
For the second case, one optimal solution is: bcab -> aab -> ac -> b.
For the third case, no operations can be performed so the answer is 5.

C++

Java

Python

#include <stdio.h>
#include <string.h>

int min( int a, int b ) { return a < b ? a : b; }

int T, n;
char s[ 105 ];

int a[ 105 ][ 105 ];
int b[ 105 ][ 105 ];
int c[ 105 ][ 105 ];
int f[ 105 ][ 105 ];

int len, i, l, r, m;

int main()
{
  scanf( "%d", &T );
  
  while( T-- ) {
    scanf( "%s", s );
    n = strlen( s );

    for( i = 0; i < n; ++i ) {
      if( s[i] == 'a' ) a[i][i] = 1; else a[i][i] = 0;
      if( s[i] == 'b' ) b[i][i] = 1; else b[i][i] = 0;
      if( s[i] == 'c' ) c[i][i] = 1; else c[i][i] = 0;
      f[i][i] = 1;
    }
    
    for( len = 2; len <= n; ++len ) {
      for( l = 0; l+len <= n; ++l ) {
        r = l + len - 1;
        
        f[l][r] = f[l][r-1]+1;
        a[l][r] = b[l][r] = c[l][r] = 0;
        
        for( m = l; m < r; ++m ) {
          c[l][r] |= ( a[l][m] && b[m+1][r] || b[l][m] && a[m+1][r] );
          b[l][r] |= ( a[l][m] && c[m+1][r] || c[l][m] && a[m+1][r] );
          a[l][r] |= ( c[l][m] && b[m+1][r] || b[l][m] && c[m+1][r] );
          f[l][r] |= min( f[l][r], f[l][m] + f[m+1][r] );
        }

        
        if( a[l][r] || b[l][r] || c[l][r] ) f[l][r] = 1;
      }
    }
    
    printf( "%d\n", f[0][n-1] );
  }  

  return 0;
}

C++

#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<string>
#include<list>
#include<deque>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<utility>
using namespace std;

int main() {
	string s;
	int T=0, res=0;
	int tab[3];

	cin >> T;

	for (int t = 0; t < T; t++) {
		s.clear();
		tab[0] = 0;
		tab[1] = 0;
		tab[2] = 0;
		res = 0;

		cin >> s;
		for (unsigned int i = 0; i < s.size(); i++) {
			if (s[i] == 'a') tab[0]++;
			else if(s[i] == 'b') tab[1]++;
			else if(s[i] == 'c') tab[2]++;
			else cerr << "dupa!" << endl;
		}

		sort(tab, tab+3);

		while (tab[1] > 0) {
			tab[2]--;
			tab[1]--;
			tab[0]++;
			sort(tab, tab+3);
		}

		cout << tab[2] << endl;
	}


	return 0;
}

Java

import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;

public class Solution {
	public static void main(String[] args) throws IOException {
		StreamTokenizer in = new StreamTokenizer(new InputStreamReader(System.in));
		in.nextToken();
		int T = (int) in.nval;

		int ans;

		for (int test = 0; test < T; test++) {
			in.nextToken();
			char[] c = in.sval.toCharArray();
			int[] n = new int[3];
			for (int i = 0; i < c.length; i++)
				n[c[i] - 'a']++;
			int x = (n[0] + n[1]) * (n[1] + n[2]) * (n[2] + n[0]);
			if (x == 0)
				ans = c.length;
			else if ((n[0] + n[1]) % 2 == 0 && (n[1] + n[2]) % 2 == 0 && (n[2] + n[0]) % 2 == 0)
				ans = 2;
			else
				ans = 1;

			System.out.println(ans);
		}
	}
}

Python

def solution(cases):
    result = []
    for s in cases:
        tab = {'a': 0, 'b': 0, 'c': 0}
        for c in s:
            tab[c] += 1
        if tab['a'] * tab['b'] == 0 and tab['b'] * tab['c'] == 0 and tab['c'] * tab['a'] == 0:
            result.append(tab['a'] + tab['b'] + tab['c'])
        elif tab['a'] % 2 == tab['b'] % 2 == tab['c'] % 2:
            result.append(2)
        else:
            result.append(1)
    return result


n = int(raw_input())

cases = []
for i in xrange(0, n):
    cases.append(raw_input())

result = solution(cases)

for r in result:
    print r

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

The first line of the input specifies your party budget and the number n of parties.
The following n lines contain two numbers each. The first number indicates the entrance fee of each party. Parties cost between 5 and 25 francs. The second number indicates the amount of fun of each party, given as an integer number ranging from 0 to 10.
The budget will not exceed 500 and there will be at most 100 parties. All numbers are separated by a single space.
There are many test cases. Input ends with 0 0.

Output

For each test case your program must output the sum of the entrance fees and the sum of all fun values of an optimal solution. Both numbers must be separated by a single space.

Example

Sample input:
50 10
12 3
5 8
16 9
16 6
10 2
21 9
18 4
12 4
17 8
18 9
50 10
13 8
19 10
16 8
12 9
10 2
12 8
13 5
15 5
11 7
16 2
0 0

Sample output:
49 26
48 32

Python

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

Get PrepInsta Prime Course

Get finely crafted PrepInsta Prime Subscription to ease your preparation!

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

Prepinsta Prime

Prepinsta Prime

Goldman Sachs Advance Coding Questions

Goldman Sachs Advanced Coding Questions And Answers

Goldman Sachs Practice Coding Questions

Get PrepInsta Prime Course

Get finely crafted PrepInsta Prime Subscription to ease your preparation!

Analyze your prepration with PrepInsta Prime Mock

Paid Material Coding Questions for Goldman Sachs