PRODUCTIVE SPACE

DSA Assessment Test - Arrays & Strings (Set 2)

Attempt all 10 questions in your answer copy — mention Q. No., approach, dry run, final code, and Time/Space
Complexity for each. Duration: 3 Hours | Total Marks: 100 | No mobiles/smartwatches/external help.

Name: _______________________ Batch: ______________ Roll No: __________

Section A – Arrays: 6 Qs (2 Easy + 3 Medium + 1 Hard) = 60 Marks | Section B – Strings: 4 Qs (2 Easy + 1 Medium +
1 Hard) = 40 Marks

SECTION A: ARRAYS

Q1. Merge Sorted Array Easy [5 Marks]

Topic: Arrays - Two Pointers
Problem Statement: You are given two sorted integer arrays nums1 and nums2, and the number of actual
elements m and n in each respectively. Merge nums2 into nums1 in-place so that it becomes one sorted array.
nums1 has a length of m + n, with the last n slots initially empty (treated as placeholders).

Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3

Output: [1,2,2,3,5,6]

Explanation: Merging [1,2,3] and [2,5,6] in sorted order fills nums1 in-place, using its extra
trailing space.

Constraints: [Link] == m + n, [Link] == n, 0 ≤ m, n ≤ 200

Also answer: An interviewer would ask: why is it better to merge starting from the back of the arrays (largest
elements first) rather than from the front? What extra work would a front-to-back in-place merge require?

Q2. Majority Element Easy [5 Marks]

Topic: Arrays - Boyer-Moore Voting
Problem Statement: Given an array nums of size n, return the majority element — the element that appears
more than n/2 times. You may assume the array is non-empty and the majority element always exists.

Input: nums = [2, 2, 1, 1, 1, 2, 2]

Output: 2

Explanation: 2 appears 4 times out of 7 elements, which is more than 7/2, so 2 is the
majority element.

Constraints: 1 ≤ [Link] ≤ 5*10^4, -10^9 ≤ nums[i] ≤ 10^9

Also answer: A hashmap-counting solution works but uses O(n) space. Can you solve this in O(1) extra space using
the Boyer-Moore Voting technique? Explain in your own words why a running 'candidate + count' can never lose track
of the true majority element.

PRODUCTIVE SPACE | DSA Assessment - Arrays & Strings (Set 2) Page 1

PRODUCTIVE SPACE DSA Test - Arrays & Strings (Set 2)

Q3. Sort Colors (Dutch National Flag) Medium [10 Marks]

Topic: Arrays - Three-Way Partitioning
Problem Statement: Given an array nums containing only the values 0, 1, and 2 (representing red, white, and
blue), sort the array in-place so that all 0s come first, then all 1s, then all 2s — in a single pass, without using a
sorting library.

Input: nums = [2, 0, 2, 1, 1, 0]

Output: [0, 0, 1, 1, 2, 2]

Explanation: All 0s are grouped first, followed by all 1s, followed by all 2s.

Constraints: 1 ≤ [Link] ≤ 300, nums[i] is 0, 1, or 2

Also answer: This is solved with three pointers (low, mid, high) in one pass — explain why the mid pointer only
advances immediately after a swap with low or when it reads a 1, but not right after swapping with high.

Q4. Container With Most Water Medium [10 Marks]

Topic: Arrays - Two Pointers
Problem Statement: You are given an array height of n non-negative integers, where each represents a vertical
line at that index. Find two lines that, together with the x-axis, form a container that holds the most water. Return
the maximum amount of water the container can store.

Input: height = [1, 8, 6, 2, 5, 4, 8, 3, 7]

Output: 49

Explanation: The lines at index 1 (height 8) and index 8 (height 7) form the widest high
container: width 7 * min(8,7) = 49.

Constraints: 2 ≤ [Link] ≤ 10^5, 0 ≤ height[i] ≤ 10^4

Also answer: An interviewer would ask: why does moving the pointer at the shorter line inward always give the
algorithm a chance at a better answer, while moving the taller line's pointer never can? Prove your intuition with the
given example.

Q5. Product of Array Except Self Medium [10 Marks]

Topic: Arrays - Prefix / Suffix Products
Problem Statement: Given an integer array nums, return an array answer such that answer[i] is equal to the
product of all elements of nums except nums[i]. You must write an algorithm that runs in O(n) time without using
the division operator.

Input: nums = [1, 2, 3, 4]

Output: [24, 12, 8, 6]

Explanation: answer[0] = 2*3*4 = 24, answer[1] = 1*3*4 = 12, and so on, computed without
ever dividing the total product by nums[i].

Constraints: 2 ≤ [Link] ≤ 10^5, -30 ≤ nums[i] ≤ 30

Also answer: Your first working version may use two extra arrays (prefix and suffix products). Can you reduce this to
O(1) extra space (excluding the output array)? Walk through how the output array itself can double as the prefix array.

PRODUCTIVE SPACE | DSA Assessment - Arrays & Strings (Set 2) Page 2

PRODUCTIVE SPACE DSA Test - Arrays & Strings (Set 2)

Q6. Find the Duplicate Number Hard [20 Marks]

Topic: Arrays - Floyd's Cycle Detection
Problem Statement: Given an array nums containing n + 1 integers where each integer is in the range [1, n]
inclusive, there is exactly one repeated number. Find that duplicate number without modifying the array and
using only O(1) extra space.

Input: nums = [1, 3, 4, 2, 2]

Output: 2

Explanation: 2 is the only number that appears twice in the array.

Constraints: 1 ≤ n ≤ 10^5, [Link] == n + 1, 1 ≤ nums[i] ≤ n

Also answer: A frequency-array or sorting approach breaks the O(1) space / no-modification rule. Explain how
treating the array as a linked list (where index i points to nums[i]) turns this into a cycle-detection problem, and why
Floyd's Tortoise and Hare algorithm is guaranteed to find the cycle's entry point (the duplicate).

SECTION B: STRINGS

Q7. Longest Common Prefix Easy [5 Marks]

Topic: Strings - Vertical Scanning
Problem Statement: Given an array of strings strs, find the longest common prefix string shared by all the
strings in the array. If there is no common prefix, return an empty string "".

Input: strs = ["flower", "flow", "flight"]

Output: "fl"

Explanation: "fl" is the longest prefix common to all three words; the 3rd character differs
("o" vs "i"), so scanning stops there.

Constraints: 1 ≤ [Link] ≤ 200, 0 ≤ strs[i].length ≤ 200

Also answer: An interviewer would ask: instead of comparing character-by-character across all strings, could you
sort the array first and only compare the first and last strings? Explain why that would be sufficient.

Q8. Reverse Words in a String Easy [5 Marks]

Topic: Strings - Parsing / In-place Manipulation
Problem Statement: Given an input string s, reverse the order of the words. A word is defined as a sequence of
non-space characters. Return a string with the words in reverse order, separated by a single space, with no
leading, trailing, or extra inner spaces — even if the input has irregular spacing.

Input: s = " the sky is blue "

Output: "blue is sky the"

Explanation: Extra leading, trailing, and multiple inner spaces are all collapsed, and the
words appear in reverse order.

Constraints: 1 ≤ [Link] ≤ 10^4, s contains English letters, spaces, and digits

Also answer: Can you solve this using only O(1) extra space beyond the output (i.e. without using split() and
reversing a list)? Describe the in-place approach: reverse the whole string first, then reverse each word back.

PRODUCTIVE SPACE | DSA Assessment - Arrays & Strings (Set 2) Page 3

PRODUCTIVE SPACE DSA Test - Arrays & Strings (Set 2)

Q9. Group Anagrams Medium [10 Marks]

Topic: Strings - Hashing
Problem Statement: Given an array of strings strs, group the anagrams together. You can return the answer in
any order. Two strings are anagrams if one can be formed by rearranging the letters of the other.

Input: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]

Output: [["eat","tea","ate"], ["tan","nat"], ["bat"]]

Explanation: "eat", "tea", and "ate" all contain the same letters, as do "tan" and "nat"; "bat"
has no anagram partner in the list.

Constraints: 1 ≤ [Link] ≤ 10^4, 0 ≤ strs[i].length ≤ 100, lowercase English letters only

Also answer: What key do you use to group anagrams into the same bucket in your hashmap — a sorted version of
the string, or a character-frequency signature? Which one avoids an O(k log k) sort per string, and what does that do
to your overall time complexity?

Q10. Implement strStr() using KMP Hard [20 Marks]

Topic: Strings - KMP Pattern Matching
Problem Statement: Given two strings text and pattern, return the index of the first occurrence of pattern in text
using the Knuth-Morris-Pratt (KMP) algorithm. If pattern does not occur in text, return -1. A brute-force O(n*m)
solution will receive partial marks only — you must build and use the pattern's LPS (Longest Prefix Suffix) array.

Input: text = "ababcababcabc", pattern = "ababcabc"

Output: 5

Explanation: The pattern "ababcabc" first occurs starting at index 5 in the text.

Constraints: 1 ≤ [Link] ≤ 10^5, 1 ≤ [Link] ≤ 10^5

Also answer: Explain what each value in the LPS array represents (in your own words, not just 'longest prefix suffix'),
and walk through why — when a mismatch occurs — the algorithm never needs to move the text pointer backward.
What is the overall time complexity, and why?

PRODUCTIVE SPACE | DSA Assessment - Arrays & Strings (Set 2) Page 4