Coding Questions Collection
Assessment Problems with Sample Cases
Q1 – Decryption: Largest Subset of Binary Strings
A network security company's new decryption algorithm takes a list of binary strings (consisting only of 0s
and 1s) and two integers X and Y. It finds the largest subset from the list that has at most X zeros and at
most Y ones.
Input Format
• Line 1: Integer str_size – total number of encrypted strings (N).
• Line 2: N space-separated binary strings.
• Line 3: Integer zeros_count – maximum allowed 0s.
• Line 4: Integer ones_count – maximum allowed 1s.
Output Format
Print an integer: the size of the largest subset with at most X zeros and at most Y ones.
Note
• A set A is a subset of B if all elements of A are also elements of B.
• A binary string consists only of 0s and 1s.
• The size is the total count of binary strings in the subset.
Sample Case
Input:
6
1 0 10 111 1100 1000
2
2
Output:
3
Explanation: The largest subset with at most 2 zeros and 2 ones is {"0", "1", "10"}, giving size = 3.
Q2 – Transmitter: Maximum Distortions Cleaned by Filter A
A transmitter receives N signals per day. Filters A and B alternate picking from the front or back of the
signal sequence. Filter A maximises its total; Filter B minimises Filter A's total. Find the maximum
distortions cleaned by Filter A (which starts first).
Input Format
• Line 1: Integer signal_size – total signals (N).
• Line 2: N space-separated integers – distortion values.
Output Format
Print an integer: maximum distortions cleaned by Filter A. If not possible, print nothing.
Constraints
0 ≤ signal_size ≤ 106, 0 ≤ signal values ≤ 106
Sample Cases
Input 1:
6
1 4 2 8 3 6
Output 1:
18
Explanation: Filter A picks 6, 8, 4 → 6 + 8 + 4 = 18
Input 2:
7
5 10 8 11 6 2 3
Output 2:
21
Explanation: Filter A picks 5, 8, 6, 2 → 5 + 8 + 6 + 2 = 21
Q3 – Scrambled String
Given two strings of equal length, s1 and s2, determine if s2 is a scrambled form of s1. A string can be
scrambled by recursively splitting it into two non-empty substrings and either swapping them or keeping
them in order. Print 1 if s2 is a scrambled string of s1, else print 0.
Algorithm Steps
1. If the length of the string is 1, stop.
2. If lengths of s1 and s2 are not equal, return 0.
3. Split the string at a random index into two non-empty substrings x and y.
4. Decide randomly whether to swap the two parts or keep them in order.
5. Apply step 1 recursively on each of the substrings x and y.
Input Format
Input contains two strings s1 and s2 of equal length, space-separated on one line.
Output Format
Print 1 if s2 is a scrambled string of s1, else 0.
Sample Case
Input:
great rgeat
Output:
1
Explanation: rgeat is a scrambled form of great via valid recursive splits/swaps.
Q4 – Russian Doll Envelopes
Given a 2D array of integers where envelopes[i] = [wi, hi] represents the width and height of an envelope,
find the maximum number of envelopes you can Russian-doll (put one inside another). One envelope fits
inside another only if both its width and height are strictly greater. You cannot rotate envelopes.
Constraints
• 1 ≤ [Link] ≤ 105
• envelopes[i].length = 2
• 1 ≤ wi, hi ≤ 105
Input Format
Line 1: integer n (number of envelopes). Next n lines: two integers wi hi.
Output Format
A single integer: the maximum number of envelopes that can be Russian-dolled.
Sample Cases
Input 1:
4
6 4
6 4
6 7
2 3
Output 1:
3
Explanation: [2,3] → [6,4] → [6,7] (chain of 3)
Input 2:
3
2 2
2 2
2 2
Output 2:
1
Explanation: No envelope strictly fits inside another; max chain = 1.
Q5 – Who Is Your Roommate
Start with 0. Each day the number doubles automatically. On any day you can add 1 any number of times.
Find the minimum number of times you need to add 1 to reach N.
Input Format
Line 1: integer T (number of test cases). Next T lines: each contains integer N.
Output Format
For each test case, print the minimum number of times 1 must be added.
Constraints
1 ≤ T ≤ 100, 1 ≤ N ≤ 109
Sample Case
Input:
2
8
5
Output:
1
2
Explanation:
N=8: Add 1 once → double → 2 → double → 4 → double → 8. (1 addition)
N=5: Add 1 once → 2 → 4 → add 1 → 5. (2 additions)
Quick Reference Summary
# Problem Core Concept Key Constraint
Q1 Decryption Subset 2D DP (0/1 Knapsack) ≤X zeros, ≤Y ones
Q2 Filter A/B Signals Minimax / Prefix Sums N ≤ 10■
Q3 Scrambled String Recursive + Memoization Equal length strings
Q4 Russian Doll Envelopes LIS + Sorting N ≤ 10■
Q5 Who Is Your Roommate Bit counting (popcount) N ≤ 10■