Solve four OA algorithm problems
Quick Overview
This multi-part exercise evaluates algorithmic problem-solving across combinatorics and geometry (counting axis-aligned square subgrids), string reordering under adjacency constraints (minimum adjacent swaps to form a palindrome), deterministic grid-walk simulation with teleportation and cycle detection, and prefix-sum based range optimization for arrays, and it belongs to the Coding & Algorithms domain. These problems are commonly asked to assess efficiency under large constraints, correctness in handling edge cases and invariants, and the ability to blend conceptual understanding with practical algorithm design, requiring both conceptual reasoning and applied implementation skills.
You are given four independent coding questions.
1) Count square subgrids (multiple queries)
For each query, you are given two integers R and C representing an R × C grid of unit cells.
Return the total number of axis-aligned square subgrids (of all possible side lengths) that can be formed inside the grid.
-
Input:
qqueries, each query containsR, C. - Output: For each query, output the number of square subgrids.
-
Constraints (typical):
1 ≤ q ≤ 2e5,1 ≤ R, C ≤ 1e9.
2) Minimum adjacent swaps to make a palindrome
You are given a string s of length n (in the OA it may be a binary string such as only 'O' and 'I', but assume it can be any characters).
In one move, you may swap two adjacent characters.
Return the minimum number of adjacent swaps needed to rearrange s into a palindrome.
-
If it is impossible to form a palindrome, return
-1.
3) Row-major grid walk with obstacles, teleports, and loop detection
You are given an n × m grid. You start at the top-left cell (0,0) and want to reach the bottom-right cell (n-1,m-1).
Movement rule (row-major walk):
-
From
(r,c), your next step is normally:-
(r, c+1)ifc+1 < m -
otherwise wrap to the start of the next row
(r+1, 0)ifr+1 < n
-
Additional rules:
-
Some cells are
blocked
(obstacles). If you ever step onto a blocked cell, stop and return
-1. -
Some cells are
teleporters
. If you step onto a teleporter cell, you are immediately moved to its paired destination cell.
- Treat teleporting as part of the same “step”: each transition (including landing on a teleporter and being transported) counts as one step total .
-
If the process enters a cycle and will never reach the target, return
-2.
Return the number of steps to reach (n-1,m-1) if reachable.
4) Longest subarray under a prefix-sum inequality
You are given an array a of length n (assume a[i] ≥ 0) and an integer k.
Let prefix sums be:
-
pref[0] = 0 -
pref[i+1] = pref[i] + a[i]
Find the maximum length of a subarray [l, r) (with 0 ≤ l < r ≤ n) such that:
Return this maximum length.