How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Take-home Project rounds at Pika.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Pika during technical interviews.

Implement text formatter and sum subarray products

Quick Overview

This question evaluates algorithmic problem-solving and implementation skills across string formatting (line breaking and space management) and array-based combinatorial computation (sum of subarray products), emphasizing correctness, edge-case handling, and analysis of time and space complexity.

Company: Pika

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Take-home Project

1) Text formatter (LC-inspired variant): Given an array of words and an integer maxWidth W >= 1, break the words into lines so that the total length of words on each line plus spaces is at most W. For every line except the last, place exactly one space between adjacent words, then append all remaining padding spaces after the final word so the line length is exactly W. The last line should be left-justified with single spaces between words and any remaining spaces appended at the end to reach W. Do not split words. Return the list of lines as strings and explain your algorithm and its time/space complexity. 2) Sum of subarray products: Given an integer array items[0..n-1], compute S = ∑_{i=0}^{n-1} ∑_{j=i}^{n-1} (∏_{k=i}^{j} items[k]). Return S.

Quick Answer: This question evaluates algorithmic problem-solving and implementation skills across string formatting (line breaking and space management) and array-based combinatorial computation (sum of subarray products), emphasizing correctness, edge-case handling, and analysis of time and space complexity.

Left-Justified Text Formatter

Given an array of words and an integer maxWidth W (W >= 1), break the words into lines so that the total length of the words on each line, plus the single spaces between adjacent words, is at most W. Place exactly one space between adjacent words on every line, then append all remaining padding spaces after the final word so the line length is exactly W (this applies to every line, including the last). A word is never split across lines, and you greedily pack as many words as fit onto each line before moving on. Return the list of formatted lines. Example: words = ["This", "is", "an", "example", "of", "text", "justification."], W = 16 returns ["This is an ", "example of text ", "justification. "].

Constraints

1 <= maxWidth <= 1000
0 <= number of words <= 10^4
1 <= len(word) <= maxWidth for every word (no word is longer than the line width)
Words contain non-space printable characters

Examples

Input: (["This", "is", "an", "example", "of", "text", "justification."], 16)

Expected Output: ["This is an ", "example of text ", "justification. "]

Explanation: "This is an" (10 chars) fits; adding "example" would need 18 > 16, so it starts line 2. "example of text" is 15 chars; "justification." would push it over 16. Each line is padded with trailing spaces to width 16.

Input: ([], 5)

Expected Output: []

Explanation: No words yields no lines.

Input: (["word"], 4)

Expected Output: ["word"]

Explanation: A single word exactly filling the width needs no padding.

Input: (["a", "b", "c", "d"], 3)

Expected Output: ["a b", "c d"]

Explanation: "a b" is 3 chars and full; "c" cannot fit (3+1+1=5>3), so it begins the next line which becomes "c d".

Input: (["hello"], 10)

Expected Output: ["hello "]

Explanation: One word padded with 5 trailing spaces to reach width 10.

Input: (["a", "bb", "ccc"], 3)

Expected Output: ["a ", "bb ", "ccc"]

Explanation: No two words fit together within width 3, so each word is on its own line, padded with trailing spaces to width 3.

Hints

Greedily pack words: keep adding the next word to the current line while the running length plus one space plus the next word still fits within maxWidth.
Join the chosen words with single spaces, then append (maxWidth - currentLength) trailing spaces so every line is exactly maxWidth characters.
Because every line (including the last) is left-justified with the same padding rule, you do not need a special case for the final line.

Sum of All Subarray Products

Given an integer array items[0..n-1], compute the sum over every contiguous subarray of the product of that subarray's elements: S = sum over i from 0..n-1 of ( sum over j from i..n-1 of ( product of items[k] for k from i..j ) ) Return S. The array may contain zeros and negative numbers, and an empty array sums to 0. Example: items = [1, 2, 3]. The six subarrays are [1]=1, [2]=2, [3]=3, [1,2]=2, [2,3]=6, [1,2,3]=6, so S = 1+2+3+2+6+6 = 20.

Constraints

0 <= n <= 10^5
items[k] may be negative, zero, or positive
The final sum fits in a 64-bit signed integer for the given limits (use long / long long in Java / C++)

Examples

Input: ([1, 2, 3],)

Expected Output: 20

Explanation: Subarrays: [1]=1, [2]=2, [3]=3, [1,2]=2, [2,3]=6, [1,2,3]=6; total 20.

Input: ([2, 3],)

Expected Output: 11

Explanation: [2]=2, [3]=3, [2,3]=6; total 11.

Input: ([5],)

Expected Output: 5

Explanation: Only subarray is [5]=5.

Input: ([],)

Expected Output: 0

Explanation: No subarrays; the sum is 0.

Input: ([-1, -2, -3],)

Expected Output: -4

Explanation: [-1]=-1, [-2]=-2, [-3]=-3, [-1,-2]=2, [-2,-3]=6, [-1,-2,-3]=-6; total = -1-2-3+2+6-6 = -4.

Input: ([1, 0, 2],)

Expected Output: 3

Explanation: Any subarray containing the 0 has product 0, so only [1]=1 and [2]=2 contribute; total 3.

Input: ([2, 2, 2, 2],)

Expected Output: 52

Explanation: Products by length: four singles 2*4=8, three pairs 4*3=12, two triples 8*2=16, one quad 16*1=16; total 52.

Hints

Let suffix(i) be the sum of products of all subarrays that START at index i. Then suffix(i) = items[i] * (1 + suffix(i+1)): items[i] alone contributes items[i]*1, and extending each subarray starting at i+1 by items[i] contributes items[i]*suffix(i+1).
Process the array from right to left, maintaining a single 'running' value equal to suffix(i), and add it to the total at each step. This gives an O(n) one-pass solution.
Be careful with zeros (a subarray containing a zero contributes 0) and negatives (products can flip sign) — the recurrence handles both automatically; no special-casing is needed.

Quick Overview