UST Global Coding Questions and Python Solutions
This document contains all 10 UST Global coding questions and answers. Each question includes the full problem statement, all
input/output specifications, examples with explanations, any special rules, and a complete Python solution.
Question 1: Nearest Smaller Tower
Problem Statement:
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].
Python Solution:
def find_nearest_shorter_tower(tower_heights):
n = len(tower_heights)
result = [-1] * n
left_stack = []
right_stack = []
# Left search
for i in range(n):
while left_stack and tower_heights[left_stack[-1]] >= tower_heights[i]:
left_stack.pop()
if left_stack:
result[i] = left_stack[-1]
left_stack.append(i)
# Right search
for i in range(n-1, -1, -1):
while right_stack and tower_heights[right_stack[-1]] >= tower_heights[i]:
right_stack.pop()
if right_stack:
if result[i] != -1:
left_dist = abs(result[i] - i)
right_dist = abs(right_stack[-1] - i)
if left_dist == right_dist:
if tower_heights[result[i]] > tower_heights[right_stack[-1]]:
result[i] = right_stack[-1]
elif left_dist > right_dist:
result[i] = right_stack[-1]
else:
result[i] = right_stack[-1]
right_stack.append(i)
return result
Question 2: Loki’s Mind Stone
Problem Statement:
Loki, the God of mischief, wants to brainwash the minimum number of avengers so that their team’s combined power is strictly
greater than the rest. Each avenger’s power is given in a list.
Input Format:
First line contains an integer (number of avengers).
Second line contains space separated integers (powers).
Output Format:
Minimum number of avengers to brainwash.
Constraints:
Example:
Input:
6
931242
Output:
2
Explanation:
If Loki brainwashes the avengers with power 9 and 3 (or 9 and 4, or 9 and 2, or 9,4), the sum of these is greater than the sum of the
rest.
Python Solution:
n = int(input())
powers = list(map(int, input().split()))
total_sum = sum(powers)
[Link](reverse=True)
half_sum = total_sum // 2
brainwashed_sum = 0
count = 0
while brainwashed_sum <= half_sum and count < n:
brainwashed_sum += powers[count]
count += 1
print(count)
Question 3: Total Distinct Money
Problem Statement:
You are in cell (0,0) in a R x C grid. Each cell (except (0,0) and (R-1,C-1)) contains some amount of money. Find:
The number of distinct ways to reach (R-1,C-1) moving only right or down.
The sum of all possible total money collected from all distinct paths.
Input Format:
First line: two integers R and C (rows, cols)
Next R lines: C integers per line (the grid)
Output Format:
1st line: number of distinct ways
2nd line: sum of all money for all unique path totals
Example:
Input:
33
023
132
110
Output:
4
21
Explanation:
All possible totals:
0-2-3-2-0 = 7
0-2-3-1-0 = 6
0-1-3-2-0 = 6
0-1-1-1-0 = 3
(Total sums = 7+6+6+3=22, but output expects sum of unique totals)
Python Solution:
def find_paths(i, j, n, m, grid, current_sum, visited_sums):
if i == n - 1 and j == m - 1:
if current_sum not in visited_sums:
visited_sums[current_sum] = 0
visited_sums[current_sum] += 1
return
if i == n - 1:
find_paths(i, j + 1, n, m, grid, current_sum + grid[i][j], visited_sums)
return
if j == m - 1:
find_paths(i + 1, j, n, m, grid, current_sum + grid[i][j], visited_sums)
return
find_paths(i + 1, j, n, m, grid, current_sum + grid[i][j], visited_sums)
find_paths(i, j + 1, n, m, grid, current_sum + grid[i][j], visited_sums)
n, m = map(int, input().split())
grid = [list(map(int, input().split())) for _ in range(n)]
visited_sums = {}
find_paths(0, 0, n, m, grid, 0, visited_sums)
print(len(visited_sums))
print(sum(visited_sums.keys()))
Question 4: Minimizing a String
Problem Statement:
Given a string consisting only of the characters 'a', 'b', and 'c', obtain the alphabetically smallest string possible by swapping adjacent
‘a’ and ‘b’ or adjacent ‘b’ and ‘c’ characters, any number of times.
Input:
A string only containing ‘a’, ‘b’, and ‘c’.
Output:
The lexicographically smallest possible string after allowed swaps.
Example:
Input: abaacbac
Output: aaabbcac
Explanation: Swap 'c' with 'b' at index 5-6 and so on until results match.
Python Solution:
def minimize_string(s, smaller, larger):
s = list(s)
n = len(s)
flag = False
start = -1
for i in range(n - 1, -1, -1):
if s[i] == larger:
if flag:
s[i], s[start] = s[start], s[i]
start -= 1
elif s[i] == smaller:
if not flag:
flag = True
start = i
else:
flag = False
return ''.join(s)
s = input()
s = minimize_string(s, 'b', 'c')
s = minimize_string(s, 'a', 'b')
print(s)
Question 5: Borrow Number
Problem Statement:
Given two numbers as strings, count the number of borrow operations needed to subtract the second from the first digit-wise. If not
possible, print "Not possible".
Input:
Two strings, number1 and number2.
Output:
Number of borrow operations, or "Not possible" if number1 < number2.
Example:
Input:
754
658
Output:
2
Input:
654
666
Output:
Not possible
Python Solution:
s1 = input()
s2 = input()
if int(s1) < int(s2):
print("Not possible")
else:
s1 = s1[::-1]
s2 = s2[::-1]
count = 0
flag = 0
for i in range(len(s1)):
if i < len(s2):
if s1[i] < s2[i]:
flag = 1
count += 1
elif s1[i] == s2[i]:
if flag == 1:
count += 1
flag = 0
else:
flag = 0
print(count)
Question 6: Seating Arrangement in Exam Hall
Problem Statement:
Given the number of test cases, for each test case output the nth valid seating arrangement in an exam hall, where no two students
of group 1 ('1's) can sit together.
Input Format:
First line: Integer T (number of test cases)
Next T lines: each contains the value n for the nth arrangement
Sample Input:
3
4
6
9
Sample Output:
101
1001
10001
Python Solution:
from collections import deque
n = int(input())
positions = [int(input()) for _ in range(n)]
max_pos = max(positions)
arrangements = []
queue = deque(['1'])
[Link]('1')
count = 1
while queue and count < max_pos:
current = [Link]()
[Link](current + '0')
[Link](current + '0')
count += 1
if count >= max_pos:
break
if current[-1] == '0':
[Link](current + '1')
[Link](current + '1')
count += 1
for pos in positions:
print(arrangements[pos - 1])
Question 7: Airport Authority
Problem Statement:
Given N luggages and their weights, and a threshold T, charge $1 for each luggage if its weight is ≤ T, else $2. Output the total
charge.
Input Format:
First line: N
Next N lines: weight of each luggage
Next line: T
Sample Input:
4
1
2
3
4
3
Sample Output:
5
Python Solution:
def weight_machine(n, weights, threshold):
amount = 0
for weight in weights:
amount += 1
if weight > threshold:
amount += 1
return amount
n = int(input())
weights = [int(input()) for _ in range(n)]
threshold = int(input())
print(weight_machine(n, weights, threshold))
Question 8: Parallel Columbus
Problem Statement:
Given a grid of size n x m, and one special (x,y) American cell, count how many Columbus's will reach (n,m) without passing through
(x,y).
Input:
n
m
x
y
Sample Input:
2
2
2
1
Sample Output:
1
Python Solution:
import math
def factorial(n, memo):
if n in memo:
return memo[n]
if n <= 1:
return 1
memo[n] = n * factorial(n - 1, memo)
return memo[n]
n = int(input())
m = int(input())
x = int(input())
y = int(input())
n -= 1
m -= 1
x -= 1
y -= 1
memo = {0: 1, 1: 1}
total_paths = factorial(m + n, memo) // (factorial(m, memo) * factorial(n, memo))
blocked_paths = (factorial(x + y, memo) // (factorial(x, memo) * factorial(y, memo))) * \
(factorial(m - x + n - y, memo) // (factorial(m - x, memo) * factorial(n - y, memo)))
print(total_paths - blocked_paths)
Question 9: Party Budget Optimization
Problem Statement:
Given a budget and a list of parties (each with fee and fun value), find the set of parties with maximum total fun without exceeding the
budget. Output minimal fee and maximum fun value.
Input:
First line: Budget and number n
Next n lines: fee and fun for each party
Sample Input:
50 10
12 3
58
16 9
16 6
10 2
21 9
18 4
12 4
17 8
18 9
Sample Output:
50 29
Python Solution:
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]
for i in range(W + 1):
if K[n][i] == res:
x = i
break
print(x, res)
b, n = map(int, input().split())
fun = []
cost = []
for i in range(n):
x, y = map(int, input().split())
[Link](y)
[Link](x)
knapSack(b, cost, fun, n)
Question 10: Rock Sample Classification
Problem Statement:
Given S rock samples and R ranges, output for each range how many samples fall in that range.
Input:
First line: S R
Second line: S sample sizes (space separated)
Next R lines: two integers (min, max of each range)
Sample Input:
10 2
345 604 321 433 704 470 808 718 517 811
300 350
400 700
Sample Output:
2
4
Python Solution:
S, R = map(int, input().split())
samples = list(map(int, input().split()))
ranges = [tuple(map(int, input().split())) for _ in range(R)]
for l1, l2 in ranges:
count = sum(1 for x in samples if l1 <= x <= l2)
print(count)