Solve multiple algorithmic interview questions

Below are several independent coding tasks. For each task, implement a function that returns the required output.

Assume:

• Arrays/lists are 0-indexed.
• Strings contain ASCII letters/spaces unless stated otherwise.
• Aim for efficient time complexity (typically (O(n\log n)) or better when possible).

1) Compare counts above/below a target

Input: integer target, integer array arr

Output:

• Return the string:
• "greater" if count(x > target) is larger than count(x < target)
• "smaller" if count(x < target) is larger than count(x > target)
• "tie" if they are equal

Notes:

• Values equal to target are ignored.

2) Moon phase after a given date (8-day cycle)

There are 8 moon states in a fixed cycle, labeled 0..7. The moon advances by 1 state each day (mod 8).

Input:

• initial_state (0..7): the moon state on Jan 1 of a given (non-leap) year
• month (1..12), day (1..31): a calendar date in the same year (assume standard month lengths)

Output: the moon state (0..7) on the given month/day.

3) Apply commands to a matrix

Given an n x m integer matrix and a list of string commands, apply them in order and return the final matrix.

Commands:

• "reverseRow r": reverse the elements in row r
• "swap r1 r2": swap row r1 and row r2
• "rotate": rotate the entire matrix 90° clockwise (dimensions become m x n)

Input: matrix grid, list commands

Output: final matrix after all commands.

4) Longest consecutive sequence length after each insertion

Process a list of integers from left to right. After each new number is added to the seen set, output the length of the longest consecutive-integer sequence that can be formed from all numbers seen so far.

Input: integer array nums

Output: integer array ans of the same length where ans[i] is the longest consecutive length after processing nums[0..i].

Example:

• Input: [2, 3, 0, 4]
• Output: [1, 2, 2, 3]

5) Count ordered pairs whose concatenation equals target

Given an integer array numbers and an integer target, count the number of ordered pairs (i, j) with i != j such that concatenating their decimal representations equals the target’s decimal representation.

Formally, count pairs where:

• str(numbers[i]) + str(numbers[j]) == str(target)

Input: numbers, target

Output: count of valid ordered pairs.

Example:

• numbers = [1, 212, 12, 12], target = 1212
• Valid ordered pairs: (0,1), (2,3), (3,2) → output 3

6) Maximum value of a valid expression along right/down paths in a grid

You are given an n x m grid of characters. Each cell is either:

• a digit '0'..'9', or
• an operator '+' or '-'.

You may choose any starting cell and move only right or down to form a sequence of visited cells (a path). The concatenation of characters along the path must form a valid expression under these rules:

• A valid expression is either a single digit, or alternates strictly: digit (op digit)*
• Therefore:
• two consecutive digits are invalid
• two consecutive operators are invalid

The value of an expression is evaluated left-to-right with + and -.

Task: Return the maximum value among all valid expressions obtainable from any right/down path in the grid.

7) Simulate a multi-step array reduction and return the total

Given a non-negative integer array nums, repeatedly apply the following procedure until all values are 0:

1. Find the leftmost index i such that nums[i] != 0. Let x = nums[i].
2. Starting from i and moving right, for each k >= i:

• if nums[k] >= x, set nums[k] = nums[k] - x and continue
• if nums[k] < x, stop this pass immediately

1. Add x to ans.
2. If all elements are now 0, return ans; otherwise repeat from step 1.

Input: nums

Output: the final ans.

Example:

• nums = [3, 5, 5, 1] → output 6

8) Text justification with 2D input (paragraph blocks)

You are given a 2D list blocks, where each inner list represents a “block” that must start on a new line. Each element of a block is a string that may itself contain multiple words separated by single spaces.

You must produce fully justified lines of width maxWidth:

• Words cannot be split.
• You place words left-to-right into the current line until adding the next word would exceed maxWidth, then you start a new line.
• If a block contains a string with multiple words, you may split that string into words and continue packing them across lines.
• When justifying a line, distribute spaces between words (do not insert spaces inside a word). If extra spaces remain, distribute them from left to right.

Input: blocks: List[List[str]], integer maxWidth

Output: list of justified strings (each exactly length maxWidth).

9) Count symmetric triplets in a string (case-insensitive)

Given a string s, consider every contiguous substring of length 3 (a “triplet”). A triplet is symmetric if its first and third characters are the same, ignoring case.

Input: string s

Output: number of symmetric triplets.

Examples:

• "axA" → 1 ("a x a")
• "cxcbdb" → 2

10) A/P replacement rounds until termination

Given an array arr containing only characters 'A' and 'P', and an integer rate (replacement rate), repeatedly perform rounds as follows:

In each round:

1. If arr ends with at least rate consecutive 'P' characters, remove exactly rate trailing 'P' characters.
2. If arr still contains any 'A', change the last 'A' in the array to 'P'.
3. If step (1) cannot remove (not enough trailing P) and step (2) cannot change (no A exists), stop.

Input: arr, integer rate

Output: number of rounds performed until stopping.

Example: rate = 3, ['A','A','P'] evolves:

• ['A','A','P'] → ['A','P','P'] → ['P','P','P'] → [] So output is 3 rounds.

11) Minimum value difference with index-distance constraint

Given an integer array nums and an integer distance, find two indices i, j such that:

• |i - j| >= distance

Among all such pairs, minimize:

• |nums[i] - nums[j]|

Input: nums, integer distance

Output: the minimum absolute difference achievable (assume a valid pair exists).

12) Split array into two groups using “greater-than counts” rule

You process array A from left to right and assign each element a to group B or group C using this rule:

Let:

• gB(a) = number of elements in B strictly greater than a
• gC(a) = number of elements in C strictly greater than a

Assignment:

1. If gB(a) > gC(a), put a into B.
2. If gB(a) < gC(a), put a into C.
3. If tied, put a into the currently shorter group.
4. If still tied (same length), put a into B.

Input: integer array A

Output: the final groups B and C after processing all elements.

Example:

• Input: [1,2,3,4,5]
• One valid output: B = [1,3,5], C = [2,4]