UST Global Coding Questions and Answers
Sample UST Global Coding Questions with Solution
UST Global Coding Questions and Answers is a part of Online Test and Technical Interview conducted by UST Global to hire freshers for various technical domains through their recruitment Drive.
At the end of this page, you’ll get FAQ’s related to UST Global Hiring Process that will help you to prepare for UST Global Recruitment Drives.
Question 1: Nearest smaller Tower
Given an array representing the heights of towers, the task is to find, for each tower, the index of the nearest tower that is shorter than it.
The search for a shorter tower can be performed by looking to the left and right sides of each tower.
The following rules apply:
If there are two or more smaller towers at the same distance from the current tower, choose the tower with the smallest height.
If two towers have the same height, choose the one with the smaller index.
Example 1:
Input : Array: [1, 3, 2]
Output : Indexes: [-1, 0, 0]
Explanation:
For the tower at index 0, there is no tower shorter than it, so the output is -1.
For the tower at index 1 (height 3), there are two towers (heights 1 and 2) at the same distance. Following the rules, we choose the tower with the smallest height, which is at index 0.
For the tower at index 2 (height 2), the only tower shorter than it is at index 0.
Therefore, the final output is the array of indexes: [-1, 0, 0].
Example 2:
Input : Array : [4, 8, 3, 5, 3]
Output : Indexes: [2, 2, -1, 2, -1]
Explanation:
For the tower at index 0 (height 4), the nearest tower shorter than it is at index 2.
For the tower at index 1 (height 8), there are two towers (heights 4 and 3) at the same distance.
Following the rules, we choose the tower at index 2.
For the tower at index 2 (height 3), there is no tower shorter than it.
For the tower at index 3 (height 5), there are two towers (heights 3 and 3) at the same distance.
Following the rules, we choose the tower at index 2 because it has a smaller index.
For the tower at index 4 (height 3), there is no tower shorter than it.
Therefore, the final output is the array of indexes: [2, 2, -1, 2, -1].
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
#include<bits/stdc++.h>
class TowerFinder
{
public:
std::vector findNearestShorterTower(std::vector &towerHeights)
{
int n = towerHeights.size();
std::stack leftStack, rightStack;
std::vector result(n, -1);
for (int i = 0; i < n; i++) { while (!leftStack.empty() && towerHeights[leftStack.top()] >= towerHeights[i])
{
leftStack.pop();
}
if (!leftStack.empty())
{
result[i] = leftStack.top();
}
leftStack.push(i);
}
for (int i = n - 1; i >= 0; i--)
{
while (!rightStack.empty() && towerHeights[rightStack.top()] >= towerHeights[i])
{
rightStack.pop();
}
if (!rightStack.empty())
{
if (result[i] != -1)
{
if (std::abs(result[i] - i) == std::abs(rightStack.top() - i))
{
if (towerHeights[result[i]] > towerHeights[rightStack.top()])
result[i] = rightStack.top();
}
else if (std::abs(result[i] - i) > std::abs(rightStack.top() - i))
result[i] = rightStack.top();
}
else
result[i] = rightStack.top();
}
rightStack.push(i);
}
return result;
}
};
int main()
{
std::vector towerHeights = {4,8,3,5,3};
TowerFinder towerFinder;
std::vector nearestShorterTowers = towerFinder.findNearestShorterTower(towerHeights);
// Print the result
for (int i = 0; i < nearestShorterTowers.size(); i++)
{
std::cout << nearestShorterTowers[i] << " ";
}
std::cout << std::endl;
return 0;
}
class TowerFinder:
def find_nearest_shorter_tower(self, arr):
suff = []
n = len(arr)
find_suff = [0] * n # building suffix
for i in range(n - 1, -1, -1):
if len(suff) == 0:
find_suff[i] = -1
suff.append([arr[i], i])
else:
while suff:
if suff[-1][0] < arr[i]:
find_suff[i] = suff[-1][1]
break
suff.pop()
if len(suff) == 0:
find_suff[i] = -1
suff.append([arr[i], i])
pre = []
find_pre = [0] * n # building prefix
for i in range(n):
if len(pre) == 0:
find_pre[i] = -1
pre.append([arr[i], i])
else:
while pre:
if pre[-1][0] < arr[i]: find_pre[i] = pre[-1][1] break pre.pop() if len(pre) == 0: find_pre[i] = -1 pre.append([arr[i], i]) new = [0] * n # comparing both for i in range(n): if find_suff[i] == -1: new[i] = find_pre[i] continue if find_pre[i] == -1: new[i] = find_suff[i] continue if abs(find_suff[i] - i) == abs(find_pre[i] - i): if arr[find_suff[i]] >= arr[find_pre[i]]:
new[i] = find_pre[i]
else:
new[i] = find_suff[i]
elif abs(find_suff[i] - i) > abs(find_pre[i] - i):
new[i] = find_pre[i]
else:
new[i] = find_suff[i]
return new
# Test the code
tower_heights = [1, 3, 2]
tower_finder = TowerFinder()
nearest_shorter_towers = tower_finder.find_nearest_shorter_tower(tower_heights)
# Print the result
print(nearest_shorter_towers)
import java.util.*;
class Main {
public static int[] findNearestShorterTower(int[] towerHeights) {
int n = towerHeights.length;
Stack leftStack = new Stack<>();
Stack rightStack = new Stack<>();
int[] result = new int[n];
Arrays.fill(result, -1);
for (int i = 0; i < n; i++) { while (!leftStack.empty() && towerHeights[leftStack.peek()] >= towerHeights[i]) {
leftStack.pop();
}
if (!leftStack.empty()) {
result[i] = leftStack.peek();
}
leftStack.push(i);
}
for (int i = n - 1; i >= 0; i--) {
while (!rightStack.empty() && towerHeights[rightStack.peek()] >= towerHeights[i]) {
rightStack.pop();
}
if (!rightStack.empty()) {
if (result[i] != -1) {
if (Math.abs(result[i] - i) == Math.abs(rightStack.peek() - i)) {
if (towerHeights[result[i]] > towerHeights[rightStack.peek()]) {
result[i] = rightStack.peek();
}
} else if (Math.abs(result[i] - i) > Math.abs(rightStack.peek() - i)) {
result[i] = rightStack.peek();
}
} else {
result[i] = rightStack.peek();
}
}
rightStack.push(i);
}
return result;
}
public static void main(String[] args) {
int[] towerHeights = {4,8,3,5,3};
int[] nearestShorterTowers = findNearestShorterTower(towerHeights);
// Print the result
for (int i = 0; i < nearestShorterTowers.length; i++) {
System.out.print(nearestShorterTowers[i] + " ");
}
System.out.println();
}
}
Question 2 : Loki’s Mind Stone
Problem Statement :
Loki, the God of mischief can brainwash any living person by touching him/her with his Mind stone, and has decided to break the avengers (a warrior group) to face into each other, so that they can turn against each other and make Loki’s evil plans easier. Now all the avengers have some amount of strength that is denoted in integers. Loki wants to brainwash the least amount of people possible, because he is lazy. But he wants his team of avengers to win the battle. What is the number of avengers Loki will get brainwashed.
Input Format:
First line contains an integer n, denoting the number of total avengers
the next line contains n space separated integers denoting the power of each avenger.
Output Format:
One line denoting the total number of avengers brainwashed by Loki’s Mind stone.
Constraints:
2<=n<=10^6
Test case:
Sample Input:
6
9 3 1 2 4 2
Sample Output:
2
Output Specifications:
Loki can brainwash the avengers with power 9 and 3, or with 9 and 2, or with 9,4, and the rest will be losing cause cumulative power of rest avengers is less than the brainwashed total power by Loki.
#include <bits/stdc++.h>
using namespace std;
map < int, int > m;
int main() {
int n, sum = 0, sum2 = 0, ans = 0;
cin >> n;
vector < int > v(n);
for (int i = 0; i < n; i++) { cin >> v[i];
sum += v[i];
}
sort(v.begin(), v.end(), greater < int > ());
sum /= 2;
while (sum2 <= sum && ans < n) {
sum2 += v[ans];
ans++;
}
cout << ans;
}
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];
int sum = 0;
for (int i = 0; i < arr.length; i++) { arr[i] = sc.nextInt(); sum = sum + arr[i]; } Arrays.sort(arr); int sum1 = 0, count = 0; for (int i = arr.length - 1; i >= 0; i--) {
sum1 = sum1 + arr[i];
sum = sum - arr[i];
count++;
if (sum1 > sum)
break;
}
System.out.println(count);
}
}
n = int(input())
arr = list(map(int, input().split()))
s = sum(arr)
arr.sort(reverse=True)
dup, sum1, ans = 0, 0, 0
for i in arr:
dup += i
sum1 = s - dup
ans += 1
if sum1 < dup:
break
print(ans)
Question 3: Total Distinct Money
Problem Statement :
You woke up from sleep and found yourself in the 0th row and 0th column of a grid. every other square in a grid has some amount of money kept there. If you are given the matrix with all the values left in the cells, you have to find how many different ways are there to rich the r-1 th , c-1 th cell and the sum of all possible amount of money you will have each time if you bring all the money kept in places in the cell.
Note that, if you are in i,j th cell, either you can go i+1, j th cell or you can go i,j+1 cell.
Again, the 0,0th grid and the n-1,m-1 th grid will have 0 value.
Input Format:
Two integers R and C meaning the number of rows and columns.
Next R lines C space separated integers denoting the total grid.
Output Format:
First Line denoting the distinct ways to rich.
Next line denotes the total money if you use all possible distinct ways (Given that if you take the money from a cell, the money is readded in the cell).
Sample Input:
3 3
0 2 3
1 3 2
1 1 0
Sample Output:
4
21
Explanation:
The all possible totals are:
0 -> 2 -> 3 -> 2 -> 0 Total = 7
0 -> 2 -> 3 -> 2 -> 0 Total = 7
0 -> 2 -> 3 -> 1 -> 0 Total = 6
0 -> 1 -> 3 -> 2 -> 0 Total = 6
0 -> 1 -> 3 -> 1 -> 0 Total = 5
0 -> 1 -> 1 -> 1 -> 0 Total = 3
There are 4 distinct ways and the total is 21
#include<bits/stdc++.h>
using namespace std;
vector < vector < int >> a;
int n, m, t;
int ans = 0, sum = 0;
map < int, int > mm;
void answer(int i, int j, int num, vector < vector < int >> a2) {
if (i == n - 1 && j == m - 1) {
if (mm[num] == 0) {
mm[num] = 1;
ans++;
sum += num;
}
return;
}
if (i == n - 1) {
answer(i, j + 1, num + a2[i][j], a2);
return;
}
if (j == m - 1) {
answer(i + 1, j, num + a2[i][j], a2);
return;
}
answer(i + 1, j, num + a2[i][j], a2);
answer(i, j + 1, num + a2[i][j], a2);
}
int main() {
cin >> n >> m;
vector < vector < int >> arr(n, vector < int > (m));
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) cin >> arr[i][j];
a = arr;
answer(0, 0, 0, a);
cout << ans << endl << sum;
}
import java.util.*;
public class Main {
static ArrayList < ArrayList < Integer >> a;
static int n, m, t;
static int ans = 0, sum = 0;
static Map < Integer, Integer > mm = new HashMap < Integer, Integer > ();
static void answer(int i, int j, int num, ArrayList < ArrayList < Integer >> a2) {
if (i == n - 1 && j == m - 1) {
if (mm.get(num) == null) {
mm.put(num, 1);
ans++;
sum += num;
}
return;
}
if (i == n - 1) {
answer(i, j + 1, num + a2.get(i).get(j), a2);
return;
}
if (j == m - 1) {
answer(i + 1, j, num + a2.get(i).get(j), a2);
return;
}
answer(i + 1, j, num + a2.get(i).get(j), a2);
answer(i, j + 1, num + a2.get(i).get(j), a2);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
ArrayList < ArrayList < Integer >> arr = new ArrayList < ArrayList < Integer >> ();
for (int i = 0; i < n; i++) {
ArrayList < Integer > temp = new ArrayList < Integer > ();
for (int j = 0; j < m; j++) {
temp.add(sc.nextInt());
}
arr.add(temp);
}
a = arr;
answer(0, 0, 0, a);
System.out.println(ans + "\n" + sum);
}
}
from typing import DefaultDict
sum = 0
ans = 0
def answer(i, j, num, a2):
global sum
global ans
if i == n - 1 and j == m - 1:
if mm[num] == 0:
mm[num] = 1
ans += 1
sum += num
return
if i == n - 1:
answer(i, j + 1, num + a2[i][j], a2)
return
if j == m - 1:
answer(i + 1, j, num + a2[i][j], a2)
return
answer(i + 1, j, num + a2[i][j], a2)
answer(i, j + 1, num + a2[i][j], a2)
mm = DefaultDict(int)
n, m = map(int, input().split())
a2 = []
for j in range(n):
a2.append(list(map(int, input().split())))
answer(0, 0, 0, a2)
print(ans)
print(sum)
Question 4: Minimizing a string
Problem Statement :
Given a string, obtain the alphabetically smallest string possible by swapping either
adjacent ‘a’ and ‘b’ characters or adjacent ‘b’ and ‘c’ characters, any number of times.
Note: A string x is alphabetically smaller
than a string y if, for the first index i where x
and y differs, x[i] <y[i].
Example :
s=”abaacbac”
The alphabetically smallest possible string is
obtained by applying the following
operations:
‘c’at index 5 is swapped with ‘b’at index 6. So “abaacbac” becomes “abaabcac”
Then,’b’at index 2 is swapped with ‘a’at index 3. So “abaabcac” becomes “aababcac”.
Finally, ‘b’at index 3 is swapped with ‘a’at index 4 to obtain the final.
answer: “aaabbcac”.
Function Description :
Complete the function smallestString in the
editor below.
smallestString has the following
parameter(s):
string s: the given string
Returns:
string: the lexicographically smallest string obtained after swapping
Constraints :
1 <_ length of s<_ 10^5 s only contains the characters ‘a’, ‘b’, and ‘c’.
#include <bits/stdc++.h>
using namespace std;
//a is the smaller char b is the bigger
void f(string & s, char a, char b) {
int n = s.length();
bool fg = false;
int st = -1;
for (int i = n; i >= 0; i--) {
if (s[i] == b) {
if (fg) {
swap(s[i], s[st]);
st--;
} else {
continue;
}
} else if (s[i] == a) {
if (fg) {
continue;
} else {
fg = true;
st = i;
}
} else {
fg = false;
}
}
}
int main() {
string s;
cin >> s;
int n = s.length();
f(s, 'b', 'c');
f(s, 'a', 'b');
cout << s << endl;
return 0;
}import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str = sc.next();
char arr[] = str.toCharArray();
int count = 0;
for (int i = 0; i < arr.length; i++) {
count = 0;
for (int j = 0; j < arr.length - 1; j++) {
if ((arr[j] - arr[j + 1]) == 1) {
char temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
count++;
}
}
if (count == 0)
break;
}
System.out.println(new String(arr));
}
}
s = list(input())
n = len(s)
af = False
fi = n + 1
for i in range(n - 1, -1, -1):
if s[i] == "c":
if af:
s[i], s[fi] = s[fi], s[i]
fi -= 1
af = False
elif s[i] == "b":
if af:
continue
else:
fi = i
af = True
else:
af = False
af = False
fi = n + 1
for i in range(n - 1, -1, -1):
if s[i] == "b":
if af:
s[i], s[fi] = s[fi], s[i]
fi -= 1
af = False
elif s[i] == "a":
if af:
continue
else:
fi = i
af = True
else:
af = False
print(*s, sep="")
Question 5: Borrow Number
Problem Statement :
You have two numbers number1 and number2, your job is to check the number of borrow operations needed for subtraction of number1 from number2. If the subtraction is not possible then return the string not possible.
Example :
754
658
Answer :
2
654
666
Answer :
Not possible
#include<bits/stdc++.h>
using namespace std;
int main() {
string s1, s2;
int c = 0, f = 0;
cin >> s1 >> s2;
if (stoi(s1) < stoi(s2)) {
cout << "Impossible";
}
reverse(s1.begin(), s1.end());
reverse(s2.begin(), s2.end());
for (int i = 0; i < s1.length(); i++)
if (s1[i] < s2[i]) {
f = 1;
c++;
}
else if (s1[i] == s2[i]) {
if (f == 1) {
c++;
}
f = 0;
} else f = 0;
cout << c;
}
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int number1 = sc.nextInt();
int number2 = sc.nextInt();
int count = 0;
if (number1 < number2) {
System.out.println("Not possible");
} else {
boolean flag = false;
while (number1 != 0 && number2 != 0) {
int temp1 = 0;
int temp2 = number2 % 10;
if (flag)
temp1 = number1 % 10 - 1;
else
temp1 = number1 % 10;
if (temp1 < temp2) {
count++;
flag = true;
} else
flag = false;
number1 = number1 / 10;
number2 = number2 / 10;
}
System.out.println(count);
}
}
}
number1 = int(input())
number2 = int(input())
count = 0
if number1 < number2:
print("Not possible")
else:
flag = 0
while number1 != 0 and number2 != 0:
temp1 = 0
temp2 = number2 % 10
if flag:
temp1 = number1 % 10 - 1
else:
temp1 = number1 % 10
if temp1 < temp2:
count += 1
flag = 1
else:
flag = 0
number1 = number1 // 10
number2 = number2 // 10
print(count)
Question 6: Seating Arrangement in Exam Hall
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
#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;
}
}
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]);
}
}
}
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])
Question 7: Airport Authority
Problem Statement -:
In an airport, the Airport authority decides to charge a minimum amount to the passengers who are carrying luggage with them. They set a threshold weight value, say, T, if the luggage exceeds the weight threshold you should pay double the base amount. If it is less than or equal to threshold then you have to pay $1.
Function Description:
Complete the weightMachine function in the editor below. It has the following parameter(s):
Parameters:
| Name | Type | Description |
| N | Integer | number of luggage |
| T | Integer | weight of each luggage |
| weights[ ] | Integer array | threshold weight |
Returns: The function must return an INTEGER denoting the required amount to be paid.
Constraints:
- 1 <= N <= 10^5
- 1 <= weights[i] <= 10^5
- 1 <= T <= 10^5
Input Format for Custom Testing:
- The first line contains an integer, N, denoting the number of luggage.
- Each line i of the N subsequent lines (where 0 <= i <n) contains an integer describing the weight of ith luggage.
- The next line contains an integer, T, denoting the threshold weight of the boundary wall.
Sample Cases:
- Sample Input 1
4
1
2
3
4
3 - Sample Output 1
5 - Explanation:
Here all weights are less than threshold weight except the luggage with weight 4 (at index 3) so all pays base fare and it pays double fare.
#include <bits/stdc++.h>
using namespace std;
long int weightMachine(long int N,long int weights[],long int T)
{
long int amount=0,i;
for(i=0;i<N;i++) { amount++; if(weights[i]>T)
{
amount++;
}
}
return amount;
}
int main()
{
long int N,i,T;
cin>>N;
long int weights[N];
for(i=0;i<N;i++) { cin>>weights[i];
}
cin>>T; cout<<weightMachine(N,weights,T);
return 0;
}
import java.util.*;
class Main
{
static int weightMachine (int N, int weights[],int T)
{
int amount = 0, i;
for (i = 0; i < N; i++) { amount++; if (weights[i] > T)
{
amount++;
}
}
return amount;
}
public static void main (String[]args)
{
Scanner sc = new Scanner (System.in);
int n = sc.nextInt ();
int weights[]= new int[n];
for(int i=0; i<n; i++)
weights[i] = sc.nextInt();
int t = sc.nextInt ();
System.out.println (weightMachine(n, weights, t));
}
}
def weightMachine(N,weights,T):
amount=0
for i in weights:
amount+=1
if(i>T):
amount+=1
return amount
N=int(input())
weights=[]
for i in range(N):
weights.append(int(input()))
T=int(input())
print(weightMachine(N,weights,T))
Question 8: Parallel Columbus
Problem Statement – Nobel Prize-winning Austrian-Irish physicist Erwin Schrödinger developed a machine and brought as many Christopher Columbus from as many parallel universes as he could. Actually, he was quite amused by the fact that Columbus tried to find India and got America. He planned to dig it further.
Though totally for research purposes, he made a grid of size n X m, and planted some people of America in a position (x,y) [in 1 based indexing of the grid], and then planted you with some of your friends in the (n,m) position of the grid. Now he gathered all the Columbus in 1,1 positions and started a race.
Given the values for n, m, x, y, you have to tell how many different Columbus(s) together will explore you as India for the first time.
Remember, the Columbus who will reach to the people of America, will be thinking that as India and hence wont come further.
Function Description:
Complete the markgame function in the editor below. It has the following parameter(s):
Parameters:
| Name | Type | Description |
| n | Integer | The number of rows in the grid. |
| m | Integer | The number of columns in the grid. |
| x | Integer | The American cell’s Row. |
| y | Integer | The American cell’s Column. |
Constraints:
- 1 <= n <= 10^2
- 1 <= m <= 10^2
- 1 <= x <= n
- 1 <= y <= m
Input Format:
- The first line contains an integer, n, denoting the number of rows in the grid.
- The next line contains an integer m, denoting the number of columns in the grid.
- The next line contains an integer, x, denoting the American cell’s row.
- The next line contains an integer, y, denoting the American cell’s column.
Sample Cases
Sample Input 1
2
2
2
1
Sample Output 1
1
Explanation
The only way possible is (1,1) ->(2,1) -> (2,2), so the answer is 1.
#include<bits/stdc++.h>
using namespace std;
unordered_map<int,long long int> f;
long long int Fact(int n)
{
if(f[n]) return f[n];
return f[n]=n*Fact(n-1);
}
int main()
{
int n,m,x,y; cin>>n>>m>>x>>y;
n-=1;m-=1;x-=1;y-=1;
f[0]=f[1]=1;
int p=(Fact(m+n)/(Fact(m)*Fact(n)));
int imp=((Fact(x+y)/(Fact(x)*Fact(y)))*(Fact(m-x+n-y)/(Fact(m-x)*Fact(n-y))));
cout<<p-imp;
}
import math n = int(input()) - 1 m = int(input()) - 1 x = int(input()) - 1 y = int(input()) - 1 ans = math.factorial(n + m) ans = ans // (math.factorial(n)) ans = ans // (math.factorial(m)) ans1 = math.factorial(x + y) ans1 = ans1 // (math.factorial(x)) ans1 = ans1 // (math.factorial(y)) x1 = n - x y1 = m - y ans2 = math.factorial(x1 + y1) ans2 = ans2 // (math.factorial(x1)) ans2 = ans2 // (math.factorial(y1)) print(ans - (ans1 * ans2))
import java.util.*;
class Main
{
static int f[] = new int[1000];
static int Fact(int n)
{
if(f[n]==1) return f[n];
return f[n]=n*Fact(n-1);
}
public static void main (String[]args)
{
Scanner sc = new Scanner (System.in);
int n = sc.nextInt ();
int m = sc.nextInt ();
int x = sc.nextInt ();
int y = sc.nextInt ();
n-=1;m-=1;x-=1;y-=1;
f[0]=f[1]=1;
int p=(Fact(m+n)/(Fact(m)*Fact(n)));
int imp=((Fact(x+y)/(Fact(x)*Fact(y)))*(Fact(m-x+n-y)/(Fact(m-x)*Fact(n-y))));
System.out.println(p-imp);
}
}
Question 9:
Problem Statement : 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
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;
}
Question 10:
Problem Description
Question – : Juan Marquinho is a geologist and he needs to count rock samples in order to send it to a chemical laboratory. He has a problem: The laboratory only accepts rock samples by a range of its size in ppm (parts per million).
Juan Marquinho receives the rock samples one by one and he classifies the rock samples according to the range of the laboratory. This process is very hard because the number of rock samples may be in millions.
Juan Marquinho needs your help, your task is to develop a program to get the number of rocks in each of the ranges accepted by the laboratory.
Input Format: An positive integer S (the number of rock samples) separated by a blank space, and a positive integer R (the number of ranges of the laboratory); A list of the sizes of S samples (in ppm), as positive integers separated by space R lines where the ith line containing two positive integers, space separated, indicating the minimum size and maximum size respectively of the ith range.
Output Format: R lines where the ith line contains a single non-negative integer indicating the number of the samples which lie in the ith range.
Constraints:
- 10 <= S <= 10000
- 1 <= R <= 1000000
- 1<=size of Sample <= 1000
Example 1
- Input: 10 2
- 345 604 321 433 704 470 808 718 517 811
- 300 350
- 400 700
Output: 2 4
Explanation:
There are 10 samples (S) and 2 ranges ( R ). The samples are 345, 604,811. The ranges are 300-350 and 400-700. There are 2 samples in the first range (345 and 321) and 4 samples in the second range (604, 433, 470, 517). Hence the two lines of the output are 2 and 4
Example 2
- Input: 20 3
- 921 107 270 631 926 543 589 520 595 93 873 424 759 537 458 614 725 842 575 195
- 1 100
- 50 600
- 1 1000
Output: 1 12 20
Explanation:
There are 20 samples and 3 ranges. The samples are 921, 107 195. The ranges are 1-100, 50-600 and 1-1000. Note that the ranges are overlapping. The number of samples in each of the three ranges are 1, 12 and 20 respectively. Hence the three lines of the output are 1, 12 and 20.
#include<bits/stdc++.h>
using namespace std;
int main()
{
int a[1000],s,i,j,t,l1,l2,c=0;
cout<<("Enter the number of elements : "); cin>>s;
cout<<("Enter the number of ranges : "); cin>>t;
cout<<("Enter the elements : ");
for(i=0;i<s;i++) cin>>a[i];
cout<<("Enter the range : ");
for(i=0;i<t;i++) { cin>>l1>>l2;
for(j=0;j<s;j++) { if((a[j]>=l1)&&(a[j]<=l2))
c++;
}
cout<<("The desired output %d ",c);
c=0;
}
return 0;
}
Output Enter the number of elements : 10 Enter the number of ranges : 2 Enter the elements : 345 604 321 433 704 470 808 718 517 811 Enter the ranges : 300 350 400 700 The desired Output : 2 4
import java.util.Scanner; class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int[] a = new int[1000]; int s,i,j,t,l1=0,l2=0,c=0; System.out.println("Enter the no of sample"); s = sc.nextInt(); System.out.println("Enter the no of range"); t = sc.nextInt(); System.out.println("Enter the numbers"); for (i = 0; i < s; i++) { a[i] = sc.nextInt(); } for (i = 0; i< t; i++) { System.out.println("Enter the max and min range"); l1 = sc.nextInt(); l2 = sc.nextInt(); for (j = 0; j < s; j++) { if((a[j]>=l1)&&(a[j]<=l2)) c++; } System.out.println(c); c=0; } } }
samples, ranges =[int(i) for i in input().split()] count = 0 final = [] arr = list(map(int, input().split())) for i in range(0, ranges): range1, range2 = [int(i) for i in input().split()] for j in range(0, samples): if range1 <= arr[j] <= range2: count = count + 1 final.append(count) count = 0 for i in range(0, len(final)): print(final[i], end=" ")
Output 10 2 345 604 321 433 704 470 808 718 517 811 300 350 400 700 2 4
FAQs related to UST Global Coding Questions
Question 1: What is the selection process for UST Global ?
The Walmart Selection Process involves:
- Online Aptitude Assessment
- Online Technical Assessment
- Group Discussions
- HR Interview
Question 2: What is the eligibility criteria for UST Global?
The UST Global Eligibility Criteria is mentioned as follows:
- Eligible candidates should have degree like B.E/ BTech, M.E/ MTech, MS, MSc, MCA, or BCA from a recognized Institute/ College.
- Minimum 60 % or equivalent CGPA throughout the academics.
Question 3: What is the salary package in UST Global?
For Software Development Engineer and Test Engineer roles, UST Global offers 8 – 10 LPA for applicants having experience of 0 – 2 years.
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
