Katkat
Back

Solve OA tasks on string, grid path, subarrays

Capital OneMachine Learning Engineer · Online Assessment
EasyMachine Learning EngineerOnline AssessmentCoding & Algorithms

Last updated

This problem tests proficiency in string manipulation, grid traversal with condition-based movement, and linear-time subarray analysis.

Part 1: String Alternation

Given a string s, determine the minimum number of character deletions required to make the string alternating such that no two adjacent characters are identical. Return the resulting string.

Part 2: Grid Path with Constraints

You are given a 2D grid of size m x n containing non-negative integers. Starting from (0, 0), find the path to (m-1, n-1) that minimizes the sum of visited cells, with the constraint that you can only move right or down if the value of the next cell has a different parity (odd/even) than your current cell.

Part 3: Parity Subarrays

Given an integer array nums, count the number of subarrays where the elements alternate between odd and even parity. A subarray [a, b, c] is alternating if parity(a) != parity(b) and parity(b) != parity(c).

Examples

Part 1: s = "aaabbb" -> Output: "abab" (Removed two 'a' and one 'b').

Part 2: Grid [[1, 2], [4, 5]]. Path (0,0)->(0,1)->(1,1) is 1->2->5. Parities: 1(O) -> 2(E) -> 5(O). Valid. Path (0,0)->(1,0)->(1,1) is 1->4->5. Parities: 1(O) -> 4(E) -> 5(O). Valid.

Constraints

  • 1 <= m, n <= 100
  • 1 <= len(s) <= 1000
  • 1 <= len(nums) <= 10^5
  • All integers are within [0, 1000].

Hints

Hint 1

For string alternation, iterate through the string and keep a character only if it differs from the last character added to your result builder.

Hint 2

For the grid, use dynamic programming where `dp[i][j]` stores the minimum cost to reach `(i, j)`, but only update from neighbors that satisfy the parity constraint.

Hint 3

For the subarray problem, use a sliding window or a single-pass counter: if `nums[i] % 2 != nums[i-1] % 2`, the current alternating subarray length increases.

Follow-up questions

  • How would the grid path complexity change if you were allowed to move in four directions (up, down, left, right) instead of just right and down?
  • Can you optimize the space complexity of the subarray counting problem to O(1)?
  • How would you modify the string problem if you were asked to minimize deletions to make the string a palindrome instead of alternating?