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
3. Add x to ans .
4. 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]