Scribd
Upload
20 views4 pages

Yash Kshatriya A Thinkschool

The document contains solutions to 3 coding questions - 1) validating brackets in a string, 2) finding the maximum sum subarray using Kadane's algorithm, and 3) finding the top 3 players and their prize money based on total points. For each question, the code, approach, and sample inputs/outputs are provided.

Uploaded by

Yash kshatriya
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
20 views4 pages

Yash Kshatriya A Thinkschool

The document contains solutions to 3 coding questions - 1) validating brackets in a string, 2) finding the maximum sum subarray using Kadane's algorithm, and 3) finding the top 3 players and their prize money based on total points. For each question, the code, approach, and sample inputs/outputs are provided.

Uploaded by

Yash kshatriya
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
You are on page 1/ 4

Name : Yash Kshatriya

Exam set : A
Location : Baner Pune Maharashtra
language : C++

question no 1 : Validate input string

problem understanding : I will be given a string containing different types of


opening and closing brackets . I have to write the code to determine weather
it's a valid sequence of parenthsis or not.
each opening bracket should have closing brackey in right
sequence ;

code:

bool isValid(string &s){

stack<char>st;

int n=s.size();

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

if(s[i]=='(' || s[i]=='{' || s[i]=='['){


st.push(s[i]);
}else{
if(!st.empty()){
if(s[i]==')' && st.top()=='('){
st.pop();
}else{
return false;
}
if(s[i]=='}' && st.top()=='{'){
st.pop();
}else{
return false;
}
if(s[i]==']' && st.top()=='['){
st.pop();
}else{
return false;
}

}else{
return false;
}

}
}
if(st.size()==0){
return true;
}
return false;
}

approach:

we will traverse a whole string using a while loop;


1-> when we will be getting the opening bracket we will push it into the stack .
2-> when we will get a closing bracket we will se that the topm element of the
stack is having the opening bracket of same type;
if yes -> the we will pop that element since we get the pair for that type of
bracket
if no -> then we are not having a opening bracket for the this type then we
will return false;
3-> at the end when we finish travesring the whole string we will see that the
stack is empty or not
if yes -> we are having closing bracket for each opening bracket hence string
is valid
if no-> string is not valid

output : 1-> {[()]}-> valid 2-> (){) not valid

question no 2 : find the max sum sub array -> (kadnes algorithm)

code :

problem understanding : I will be given an array which contains positive as well as


negative integers i have to find the subarray which has sum of its's
elements max among all the possible subarrays ;

int maxSum(vector<int>&arr){
int n=arr.size();
int sum_max=INT_MIN;
int total=0;
int min_element=INT_MAX;

for(int i=0;i<n;i++){
min_element=min(min_element,arr[i]);
int total=total+arr[i];
if(total<0)
total=0;
}
sum_max=max(sum_max,total);
}
if(max_sum==INT_MIN){
return min_element;
}
return max_sum;
}

Approach :

we will start traversing array

1-> we will maintain two variables i) total ii) max_sum


2-> we will add each element of the array to the variable total
if total<0
the element we are taking is making out sub array sum negative so we we
will consider a new subarray starting from the next index
of this element . Hence we are making our total equal to 0;
else
we are getting positive value of sum of subarray and this possibly can
be our ans hence we will store that sum in max_sum;
3-> at last if we are getting our max_sum to be INT_MAX then we are clear that we
are having no subarray with sum positive hence we can return the minimum
negative element in the array because this will be the sub array with the max
sum;

output == [-10,-1,-10,,-6] ans -> -1


[10,-100,10,5,7,-1] ans -> 22

question no 3 : find the names and the prize money of top three players

problem understanding : I will be given a number of players and the points they
scored in respective games . Then according to the total number of points
that player has scored in tournament i have to decide the ranking
of top 3 players and allocate prizes accordingly.

code :

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

int main(){
int n;
cin>>n;
vector<pair<int,string>>players;
vector<int>prize(3);
map<string,int>mp;
for(int i=0;i<n;i++){
string name;
int p;
cin>>name>>p;
mp[name]=mp[name]+p;

}
for (auto i mp){
players.push_back({i.second,i.first});
}
for(int i=0;i<3;i++){
cin>>prize[i];
}
sort(players.rbegin(),players.rend());
for(int i=0;i<3;i++){
cout<<players[i].second<<endl;;
}
for(int i=0;i<3;i++){
cout<<prize[i]<<endl;
}
return 0;
}

1-> we will take the input of number of players which is n


2-> will maintain
vector-> stores pair of int and string
vector-> stores int -> prize money
map-> stores points scored by each player in all different games ;
3-> will run a loop for n times and will take the name as well as the points that
the player has scored and store points scored by each player in map;
4-> will make a pair of points and name {points , name } by traversing map and
push it to the vector players;
5-> after pushing all the players and their points pair to the vector we will sort
the vector in the reverse order
this vector will be sorted on the integer value at the first position in
pair in reverse order
6-> now we can run a loop of 3 and print the names of top 3 players having max
points
7-> run the loop and print the prizes valuw for top three players from prize vector

Thinking -> if the problem also contains the case where the platyers can have a tie
in points then we can also maintion a number of different games played
by each player and then we can give a prize to a player having more
points in less games ;

output : prizes 3000 2000 1000


yash 10
swapnil 20
sarthak 30
satyam 100
yash 150
swapnil 110
sarthak 80

ans -> yash swapnil sarthak 3000 2000 1000

You might also like