I wanted to share my experience from the SOTI coding round with you all which was conducted on 28th Aug 2024. It was an intense and rewarding challenge that tested my problem-solving skills across a range of difficulties.
Here are the three problems I tackled:
Problem 1: Amplifier Array (Easy)
Problem Statement:
You are given an array of integers 'A' of length 'M', representing amplifiers. Each amplifier 'A[i]' amplifies the input signal such that:
Output signal = A[i] * input signal
Amplifiers can only be connected to adjacent amplifiers in 'A'. The task is to select the maximum number of amplifiers to amplify a signal of strength 1 to exactly 'S'. Return the number of amplifiers used, or -1 if it is not possible.
Example:
-
Input: M = 3, A = {2, 3, 4}, S = 123
-
Output: -1
-
Input: M = 5, A = {1, 2, 3, 4, 6}, S = 12
-
Output: 2
-
Input: M = 5, A = {2, 1, 3, 4, 6}, S = 12
-
Output: 3
Problem 2: Scrambled Binary Message (Medium)
Problem Statement:
You are given a binary message 'S' of length 'N', which is an encoded version of a lowercase alphabetic string. You also have an array 'A' of 'M' binary strings, each representing a 5-bit binary string of a lowercase alphabet. The message 'S' arrived in a scrambled manner. The task is to find the lexicographically smallest possible lowercase alphabetic string that the message could represent.
Example:
-
Input:
-
S = "0000100101"'
-
N = 10
-
A = {"00000", "00001", "00010", "00011"}'
-
M = 4
-
Output: 'bd'
-
Input:
-
S = "0000100101"'
-
N = 10
-
A = {"01010", "10000", "01100", "00000"}'
-
M = 4
-
Output: 'ab'
Problem 3: Rectangle Stacking Problem (Hard)
Problem Statement:
Given a list of rectangles with width and height, the task was to stack these rectangles to maximize the height of the stacked rectangles. Each rectangle must have a width and height less than or equal to the rectangle below it.
Example:
-
Input: Rectangles = [(1, 2), (2, 3), (3, 4), (4, 5)]
-
Output: 4
-
Input: Rectangles = [(1, 2), (2, 1), (3, 4), (4, 3)]
-
Output: 2
Participating in the SOTI coding round was a fantastic learning experience. Each problem presented unique challenges and required different strategies to solve.