Goldman Sachs Advance Coding Questions

September 27, 2024

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

Java

C++

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

Java

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

C++

#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

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

Java

C++

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(maxmstart):
                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))

Java

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

C++

#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

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

C++

Java

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

C++

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

Java

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

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

C++

C++

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

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:
50 29
48 32

Python

Java

C++

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

Java

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

C++

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

}

Question 6

Raman was playing a game, he starts with x coins. Now in every step, he wins and loses and he has to get the money or pay the money as needed. He came in contact with a psychic who can see the future and the Psychic predicted the outcomes after each step. Now Raman wants to start the game with the minimum wage where he doesn’t run out of money. Help Raman to find what money he should start with. The only rule to keep playing is not going in a credit situation.

Input Format:

First line with n, number of steps in the game
Next n lines, n integers denoting outcomes of every game. Positive means winning and negative means losing that money.

Output Format:

One single integer denoting the minimum amount to start with

Constraints:

Number of steps<=10^9
-1000<=Money needed in each step<=1000

Sample Input:

4
2
-9
15
2

Sample Output:

7

Explanation:

If he starts with 7 rupees, then after steps : 7 ->9 -> 0-> 15 -> 17.

C++

Java

Python

C++

Run

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

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

Java

Run

import java.util.*;
public class Main
{
  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 sum=0,ans=0;
   for(int i=0;i<n;i++)
    {
        sum+=arr[i];
        if(sum<1)
        {
            sum=-sum;
            ans+=sum+1;
            sum=1;
        }
    }
  System.out.println(ans);
}
}

Python

Run

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) 
        s=0 
print(a)

Question 7

Problem statement: Rocky is a software engineer and he is creating his own operating system called “myFirst os”. myFirst os is a GUI (Graphical user interface) based operating system where everything is stored in files and folders. He is facing issues on creating unique folder names for the operating system . Help rocky to create the unique folder name for it’s os.If folder name already exists in the system and integer number is added at the name to make it unique. The integer added starts with 1 and is incremented by 1 for each new request of an existing folder name. Given a list of folder names , process all requests and return an array of corresponding folder names.

Example

n=5
foldername= [‘home’ , ‘myfirst’ ,’downloads’, ‘myfirst’, ‘myfirst’]
Foldername[0] = ‘home’ is unique.
Foldername[1] = ‘myfirst’ is unique.
foldername [2] =’downloads’ is unique.
Foldername[3] =’myfirst’ already exists in our system. So Add1 at the end of the folder name i.e foldername[3] =”myfirst1″
Foldername[4 ]=’myfirst’ also already exists in our system.So add 2 at the end of the folder name i.e. foldername[4]=”myfirst2″.

Function description

Complete the function folderNameSystem In the editor below
folderNameSystem has the following parameters
string foldername[n]: an array of folder name string in the order requested

Returns:

String[n]: an array of strings usernames in the order assigned

Constraints

1<=n<=10^4
1<=length of foldername[i]<20
foldername[i] contains only lowercase english letter in the range ascii[a-z]

Input Format:

The first line contains an integer n , denoting the size of the array usernames Each line i of the n subsequent lines (where i<=0<=n) contains a string usernames[i] representing a username request in the order received.

Sample case 0

4
home
download
first
first

Sample Output 0

home
download
first
first1

Explanation 0

foldername[0] = ‘home’ is unique
foldername[1]=’download’ is unique
foldername[2]= ‘first’ is unique
foldername[3]=’first’ is already existing . so add 1 to it and it become first1

C++

Java

Python

C++

Run

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

int main(){
    int n;
    cin>>n;
    vector v(n);
    
    for(int i=0;i<n;i++) cin>>v[i];
    
    map<string,int> m;
    for(auto i:v){
        if(m[i]) 
            cout<<i<<m[i]<<endl;
        else 
            cout<<i<<endl;
        m[i]++;
    }
}

Java

Run

import java.util.*;

public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    LinkedHashMap<String, Integer> map=new LinkedHashMap<>();
    for(int i=0;i<n;i++){
        String str=sc.next();
        if(map.containsKey(str)){
            int count=map.get(str);
            count = count+1;
            map.put(str,count);
        }  
        else
            map.put(str,1);
        }

    Set s = map.entrySet();
    Iterator itr = s.iterator();

    while(itr.hasNext()){
        Map.Entry m=(Map.Entry)itr.next();
        int value=(Integer)m.getValue();
        System.out.println(m.getKey());
        value--;
        for(int i=1;i<=value;i++){
            System.out.println(m.getKey()+""+i);
            value--;  
        }
    }
  }
}

Python

Run

n=int(input())
arr = []
ans = ""
for i in range(n):
    arr.append(input())
print()
for i in range(n):
    if arr[:i+1].count(arr[i])>1:
        ans = arr[i]+str(arr[:i+1].count(arr[i])-1)
    else:
        ans = arr[i]
    print(ans)

Question 8 :

Problem Statement :

Rahul is playing a game, wherein he has multiple coloured wooden blocks, stacked one above the other, his task is to remove all the wooden blocks from the stack, without letting it fall and in the minimum number of steps. He can remove one block of a colour at a time, but he can remove multiple blocks of the same colour together. Determine the minimum number of steps in which he can perform this task.

For example, if you remove [red,red] from (white,red,red,white), the resulting array is [white,white].

Note- there are only two colour blocks – red and white

Function description :

Complete the minMoves function in the provided editor. It contains the following parameters:

Parameters:

Name	Type	Description
N	Integer	No. of Wooden blocks
Array[ ]	Integer Array	Array of Blocks.

Input format :

The first line contains an integer n denoting the number of blocks. Each n line denotes the colour of the wooden block .

Constraints :
1<=n<=700
0<=a[i]<=1

Sample input 1 :

4
red
white
white
red

Sample Output 2 :

2

Explanation :

Remove [white,white] first The array will be [red,red] The remaining numbers can be removed in one strap .

Sample Input 1:

4
white
red
white
red

Sample Output 1:

3

Sample Explanation:
0
The steps are [white,red,white,red]->[red,white,red]->[red,red]->[]. Therefore the answer is 3.

C++

JAVA

Python

C++

Run

#include <bits/stdc++.h>

using namespace std;
int main() {
    int n;
    cin >> n;

    vector < string > arr(n);
    for (int i = 0; i < n; i++) cin >> arr[i];

    int a = 0, b = 0;
    bool start = false;
    for (int i = 0; i < n; i++) {
        if (arr[i] == "white") {
            if (!start) {
                start = true;
            }
        } else {
            if (start) {
                a++;
                start = false;
            }
        }
    }
    if (start) a++;
    start = false;
    for (int i = 0; i < n; i++) {
        if (arr[i] == "red") {
            if (!start) {
                start = true;
            }
        } else {
            if (start) {
                b++;
                start = false;
            }
        }
        if (start) b++;
    }

    cout << min(a + 1, b + 1) << endl;

    return 0;
}

JAVA

Run

import java.util.*;
public class Main {
    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 < n; i++)
            arr[i] = sc.next();
        int a = 0, b = 0;
        boolean flag = false;
        for (int i = 0; i < n; i++) {
            if (arr[i].equals("white")) {
                if (!flag)
                    flag = true;
            } else {
                if (flag) {
                    a++;
                    flag = false;
                }
            }
        }
        if (flag)
            a++;
        flag = false;
        for (int i = 0; i < n; i++) {
            if (arr[i].equals("red")) {
                if (!flag)
                    flag = true;
            } else {
                if (flag) {
                    b++;
                    flag = false;
                }
            }
            if (flag)
                b++;
        }
        System.out.println(Math.min(a + 1, b + 1));
    }
}

Python

Run

n = int(input())
arr = []
for i in range(n):
    arr.append(input())
a, b = 0, 0
start = False
for i in range(n):
    if arr[i] == "white":
        if not start:
            start = True
    else:
        if start:
            a += 1
            start = False
if start:
    a += 1
start = False
for i in range(n):
    if arr[i] == "red":
        if not start:
            start = True
    else:
        if start:
            b += 1
            start = False
    if start:
        b += 1


print(min(a + 1, b + 1))

Question 9

Problem Statement :

You’re given a string, you’ve to print additional characters needed to make that string a palindrome.

A Palindrome is a sequence of characters that has the property of reading the same in either direction.

Input :
abede
Output :
ba

Sample Input :
abcfe

Sample output :
fcba

C++

JAVA

Python

C++

Run

#include <bits/stdc++.h>

using namespace std;

bool Pal(string s) {
    string s1 = s;
    reverse(s1.begin(), s1.end());
    return s1 == s;
}

int main() {
    string s;
    getline(cin, s);
    int i;
    for (i = 0; i < s.length() - 1; i++)
        if (Pal(s.substr(i, s.length() - i))) break;
    s = s.substr(0, i);
    reverse(s.begin(), s.end());
    cout << s;
}

JAVA

Run

import java.util.*;
public class Main {
  public static boolean isPalindrome(String str) {
    char arr[] = str.toCharArray();
    for (int i = 0, j = arr.length - 1; i < j; i++, j--)
      if (arr[i] != arr[j])
        return false;
    return true;
  }
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String str = sc.next();
    String res = "";
    for (int i = 0; i < str.length(); i++) {
      if (isPalindrome(str.substring(i, str.length()))) {
        res = str.substring(0, i);
        break;
      }
    }
    System.out.println(new StringBuilder(res).reverse());
  }
}

Python

Run

def ispalindrome(s):
    return s == s[::-1]

def solve(s):
    if ispalindrome(s):
        return None
    for i in range(len(s)):
        x = s[:i][::-1]
        if ispalindrome(s + x):
            return x

s = input()
print(solve(s))

Question 10

Problem Statement :

Semester exams are going on for university students. Examiners noticed that a group of people are trying to cheat. They marked students of that group as ‘1’ and students of another group ( who are not cheating ) as ‘0’

We can reduce cheating by not allowing students from group 1 to sit together, means no two students from group 1 can sit together. Seatings are marked using above conditions. Your task is to give the seating placement of nth possibility Possibility order from 1 to 10 is given below

[1 10 100 101 1000 1001 1010 10000 10001 10010]

Sample input :

3 → number of test cases

4

6

9

Sample output :

101

1001

10001

Explanation :

4th possibility is 101

6th possibility is 1001

9th possibility is 10001

C++

JAVA

Python

C++

Run

#include<bits/stdc++.h>

using namespace std;

int main() {
    int n, m, Max = 0;
    cin >> n;
    vector < int > v(n);
    vector < string > arr;
    for (int i = 0; i < n; i++) { cin >> v[i];
        Max = max(Max, v[i]);
    }
    queue < string > q;
    q.push("1");
    int i = 1;
    arr.push_back("1");
    while (!q.empty()) { 
     cout<<"TEST"<<endl; string a = q.front(); q.pop(); q.push(a + "0"); arr.push_back(a + "0"); i++; if (a[a.length() - 1] == '0') { q.push(a + "1"); arr.push_back(a + "1"); i++; } if (i > Max) break;
    }
    for (int i = 0; i < n; i++) {
        cout <<  arr[v[i] - 1] << endl;
    }
}

JAVA

Run

import java.util.*;
class Main {
    public static void possibilities(int n) {
        int c = 0;
        String b = "";
        for (int i = 1; n != c; i++) {
            String s = Integer.toString(i, 2);
            if (!s.contains("11")) {
                c++;
                b = s;
            }
        }
        System.out.println(b);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int tc = sc.nextInt();
        int[] a = new int[tc];
        for (int i = 0; i < tc; i++) {
            a[i] = sc.nextInt();
        }
        for (int i = 0; i < tc; i++) {
            possibilities(a[i]);
        }
    }
}

Python

Run

t = int(input())
a = []
m = -1
m1 = -1
for i in range(t):
    m1 = int(input())
    a.append(m1)
    m = max(m, m1)
k2 = 2
n = m + 1
k1 = ["0"] * (n)
k1[1] = "1"
a1 = 1
while k2 < (n): if k1[a1][-1] == "0": k1[k2] = k1[a1] + "0" k2 += 1 if k2 >= (n):
            break
        k1[k2] = k1[a1] + "1"
        k2 += 1
        if k2 >= (n):
            break
        a1 += 1
    elif k1[a1][-1] == "1":
        k1[k2] = k1[a1] + "0"
        k2 += 1
        if k2 >= (n):
            break
        a1 += 1
for i in a:
    print(k1[i])

Paid Material Coding Questions for Goldman Sachs

×

30+ Companies are Hiring

Get Hiring Updates right in your inbox from PrepInsta