# Goldman Sachs Coding Questions

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

### Question : 2

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

Example

Prices=[10,4,2,9]

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

Example

Price=[1,2,3,4]

The Price went up everyday.Return 0.

Sample Input for Custom Testing

STDIN                   Function

———–               ————–

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

Sample Output

•   8

Explanation

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

### Question : 3

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

Example

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

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

Function Description

Complete the function fountainActivation in the editor below.

fountainActivation has the following Parameter:

• int locations[n]: the fountain locations

Returns

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

Constraints

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

► Input Format For Custom Testing

Sample Case 0

Sample Input For Custom Testing

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

Sample Output

• 1

Explanation

Here, locations = {1, 1, 13

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

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

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

### Question 5:

How will we represent a binary tree? We can use a bracket structure for all of the edges, like (Parentnode , Childnode). Now if we use a node in child node more than once, the tree can not be valid. Same for the parent node, a node can not be taken more than twice in  a graph as a parent node.

Suppose we see this one graph

(P,Q)(P,R)(Q,T)(R,W)(U,V)(Q,S)(R,U)(U,Z)(S,I)(W,Y)

A tree with those edges may be illustrated in many ways.Here are two:

P                            P

/    \                        /     \

Q      R                   Q      R

/   \     /    \               /   \    /  \

S   T   U   W           S    T  U  W

\        / \     \          /          / \      \

I     V  Z    Y      I         Z  V    Y

The following is a recursive definition for the S-expression of a tree.

S-exp(node)=(node->val(S-exp(node->first_child))(S-exp(node->second_child))),if node

!NULL=””,node= =NULL

Where first_child->valval(first_child->val is lexicographically than second_child->val)

This tree can be represented in S-expression in multiple ways.The lexicographically smallest way of expressing it as follows:

P(Q(S(I))(T))(R(U(V)(Z))(W(Y))))

Translate the node-pair representation into its lexicographically smallest S-expression or report any errors that do not conform to the definition of the binary tree.

The List of errors with their codes is as follows:

Error                               Reason

Code Stopped1                More than 2 children

Code Stopped2                Duplicate Edges

Code Stopped3                Cycle Present(node is direct descendant of more than one node)

Code Stopped4                Multiple Roots

Code Stopped5                Any other error

Constraints:

1. All node names are single characters in the range ascii[A-Z].
2. The maximum node count is 26.
3. There is no specific order to the input (parent,child) pairs.

>Input Format for Custom Testing

>Sample Case 0

Sample Input 0

• (B,D) (D,E) (A,B) (C,F) (E,G) (A,C)

Sample output 0

• (A(B(D(E(G))))(C(F)))

Explanation 0

A representation of tree is as follows:

A

/    \

B      C

/         \

D           F

/

E

/

G

>Sample Case 1

Input:

• (C,E)(D,F)(A,B)(A,C)(B,K)

Output:

• A(B(K))(C(E)))D(F))

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

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

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

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

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

**.**

*…*

…..

*…*

**.**

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

### 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 = 0, max((1 – 0),

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

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

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

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

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

For the entire length of this 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

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

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

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

**.**

*…*

…..

*…*

**.**

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

Sample output

3

Explanation

The subarrays of size x = 1 are ,,,, and ,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

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

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

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

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

Sample Output:
c

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

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