PracHub
QuestionsCoachesLearningGuidesInterview Prep

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.

  • hard
  • Snowflake
  • Coding & Algorithms
  • Software Engineer

Solve four OA algorithm problems

Company: Snowflake

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

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:** `q` queries, each query contains `R, 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)` if `c+1 < m` - otherwise wrap to the start of the next row `(r+1, 0)` if `r+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: \[ \text{pref}[r] - 2\cdot\text{pref}[l] \le k \] Return this maximum length.

Quick Answer: 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.

Count Square Subgrids (Multiple Queries)

For each query you are given two integers `R` and `C` describing an `R x C` grid of unit cells. Return, for each query, the total number of axis-aligned square subgrids of every possible side length that fit inside the grid. A square of side `k` can be placed in `(R - k + 1) * (C - k + 1)` positions when `1 <= k <= min(R, C)`. The answer for a single query is the sum of that count over all valid `k`. Input: a list `queries`, where each element is a pair `[R, C]`. Output: a list of integers, one per query, giving the number of square subgrids. Because `R` and `C` can be as large as 1e9 and there can be up to 2e5 queries, each query must be answered in O(1) using closed-form summation (the answer can be astronomically large, so use big integers / 64-bit-safe math).

Constraints

  • 1 <= q <= 2 * 10^5
  • 1 <= R, C <= 10^9
  • Answers can exceed 64 bits for large grids; use big-integer arithmetic where the language requires it.

Examples

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

Expected Output: [5, 1, 8]

Explanation: 2x2: four 1x1 plus one 2x2 = 5. 1x1: one square. 3x2: six 1x1 plus two 2x2 = 8.

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

Expected Output: [1]

Explanation: A single cell contains exactly one 1x1 square.

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

Expected Output: [14]

Explanation: nine 1x1 + four 2x2 + one 3x3 = 14.

Input: ([[5, 3], [4, 4]],)

Expected Output: [26, 30]

Explanation: 5x3: 15 (1x1) + 8 (2x2) + 3 (3x3) = 26. 4x4: 16 + 9 + 4 + 1 = 30.

Input: ([],)

Expected Output: []

Explanation: No queries means an empty result list.

Input: ([[1000000000, 1000000000]],)

Expected Output: [333333333833333333500000000]

Explanation: Large-grid stress test; the answer overflows 64 bits, confirming big-integer math is required.

Hints

  1. A k x k square fits in (R - k + 1) * (C - k + 1) positions, valid for 1 <= k <= min(R, C).
  2. Sum that product over k. Expand it and use closed forms: sum of 1..m = m(m+1)/2 and sum of squares = m(m+1)(2m+1)/6 to get O(1) per query.
  3. Let a = R+1, b = C+1, m = min(R,C). Then the answer is a*b*m - (a+b)*S1 + S2 where S1 and S2 are those two closed forms.

Minimum Adjacent Swaps to Make a Palindrome

You are given a string `s`. In one move you may swap two adjacent characters. Return the minimum number of adjacent swaps needed to rearrange `s` into a palindrome, or `-1` if no palindrome can be formed. A palindrome is possible only if at most one character has an odd count (exactly zero odd counts for even length, exactly one for odd length). The greedy strategy fixes the string from the outside in: for the left pointer `i`, find the nearest matching character from the right end and bubble it into the symmetric position, counting the swaps. The lone odd-count character is bubbled toward the center. This is the classic minimum-adjacent-swaps-to-palindrome problem; the greedy two-pointer answer provably matches the true minimum.

Constraints

  • 0 <= len(s); the string may contain any characters (the OA used binary 'O'/'I').
  • Return -1 when the character multiset cannot form a palindrome.
  • At most one character may have an odd frequency for a palindrome to exist.

Examples

Input: ("OIIO",)

Expected Output: 0

Explanation: Already a palindrome, so zero swaps.

Input: ("OOI",)

Expected Output: 1

Explanation: Swap the last two characters to get 'OIO'.

Input: ("mamad",)

Expected Output: 3

Explanation: Classic case; three adjacent swaps yield 'madam'.

Input: ("aabb",)

Expected Output: 2

Explanation: Two swaps produce 'abba' (or 'baab').

Input: ("ab",)

Expected Output: -1

Explanation: Two distinct single characters can never form a palindrome.

Input: ("a",)

Expected Output: 0

Explanation: A single character is already a palindrome.

Input: ("OIOII",)

Expected Output: 2

Explanation: Odd length with one odd-count character; the greedy minimum is two swaps.

Hints

  1. First check feasibility: count characters with odd frequency. Even-length strings need zero; odd-length strings need exactly one.
  2. Work from both ends inward. For the left character s[i], scan leftward from the right pointer to find its nearest twin, then bubble that twin to position j with adjacent swaps.
  3. If s[i] is itself the unique odd character (no twin to its right), swap it one step toward the center and retry; this defers it to the middle.

Row-Major Grid Walk with Obstacles, Teleporters, and Loop Detection

You stand on the top-left cell `(0,0)` of an `n x m` grid and want to reach the bottom-right cell `(n-1, m-1)`. Movement is a fixed row-major walk: from `(r,c)` the next cell is `(r, c+1)` if `c+1 < m`, otherwise it wraps to `(r+1, 0)` if `r+1 < n`. Two extra rules apply on the cell you land on: - Blocked cells (obstacles): stepping onto one stops you immediately; return `-1`. - Teleporters: stepping onto a teleporter instantly moves you to its paired destination, and this whole transition counts as a single step. (If the destination is blocked, that also returns `-1`.) Each transition costs one step. If the walk enters a cycle and can never reach the target, return `-2`. Otherwise return the number of steps to reach `(n-1, m-1)`. Input: `n`, `m`, `blocked` (a list of `[r, c]` blocked cells), and `teleports` (a list of `[[sr, sc], [dr, dc]]` source/destination pairs). The starting cell is also subject to its teleporter, if any, before the first step is counted.

Constraints

  • 1 <= n, m.
  • Stepping onto a blocked cell (including a teleporter destination) returns -1.
  • A teleport happens on landing and is part of the same step.
  • If a cell is revisited (cycle) without reaching the target, return -2.

Examples

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

Expected Output: 3

Explanation: Row-major path (0,0)->(0,1)->(1,0)->(1,1) takes 3 steps.

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

Expected Output: -1

Explanation: The first step lands on the blocked cell (0,1).

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

Expected Output: 0

Explanation: Start cell is already the target, so zero steps.

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

Expected Output: 1

Explanation: Step onto teleporter (0,1) and warp to target (1,1) in a single step.

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

Expected Output: -2

Explanation: Teleporter on (0,1) sends you back to (0,0), an already-visited cell -> cycle.

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

Expected Output: 8

Explanation: Row-major sweep over all nine cells reaches (2,2) in 8 steps.

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

Expected Output: -1

Explanation: The walk reaches the blocked center cell (1,1) and stops.

Hints

  1. Store blocked cells in a set and teleporters in a dict mapping source -> destination for O(1) lookups.
  2. Simulate one step at a time following the row-major rule; after landing, check 'blocked' first, then apply the teleport (which may land on another blocked cell).
  3. Keep a visited set of post-teleport positions. Re-landing on a visited cell means an inescapable cycle -> return -2; running off the end of the grid without reaching the target is also -2.

Longest Subarray Under a Prefix-Sum Inequality

You are given a non-negative array `a` of length `n` and an integer `k`. Define prefix sums `pref[0] = 0` and `pref[i+1] = pref[i] + a[i]`. Find the maximum length `r - l` of a subarray `[l, r)` with `0 <= l < r <= n` such that: pref[r] - 2 * pref[l] <= k Return that maximum length, or `0` if no valid subarray exists. Because every `a[i] >= 0`, the prefix array is non-decreasing. Rewriting the constraint as `2 * pref[l] >= pref[r] - k`, the smallest valid `l` for a given `r` is non-decreasing as `r` grows, which makes a single forward two-pointer sweep solve it in O(n).

Constraints

  • a[i] >= 0 for all i, so the prefix sums are non-decreasing.
  • k may be negative, in which case some or all subarrays can be invalid.
  • 0 <= l < r <= n; return 0 when no subarray satisfies the inequality.

Examples

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

Expected Output: 2

Explanation: Subarray [1,3) has pref[3]-2*pref[1]=6-2=4<=5 with length 2; no length-3 window qualifies.

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

Expected Output: 1

Explanation: Only single-element windows where pref[r]-2*pref[l]<=0 work; max length is 1.

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

Expected Output: 3

Explanation: All prefix sums are 0, so the whole array satisfies 0<=0; length 3.

Input: ([5], 4)

Expected Output: 0

Explanation: pref[1]-2*pref[0]=5>4, so no valid subarray; answer 0.

Input: ([5], 5)

Expected Output: 1

Explanation: pref[1]-2*pref[0]=5<=5, so the single element qualifies; length 1.

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

Expected Output: 2

Explanation: The best feasible window has length 2 under the constraint.

Input: ([], 0)

Expected Output: 0

Explanation: Empty array has no subarray; answer 0.

Hints

  1. Build the prefix-sum array and rewrite the constraint as 2*pref[l] >= pref[r] - k.
  2. Since a[i] >= 0, pref is non-decreasing, so as r increases the minimal feasible l never decreases - a textbook two-pointer setup.
  3. For each r, advance l until the inequality holds, then the candidate length is r - l; keep the maximum. If l reaches r, no subarray ending at r works.
Last updated: Jun 26, 2026

Loading coding console...

PracHub

Master your tech interviews with 8,000+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • AI Coding Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.

Related Coding Questions

  • Implement a JSON Parser - Snowflake (hard)
  • Solve Matrix and Array Distance Problems - Snowflake (medium)
  • Solve Array Distance and Wiki Navigation - Snowflake (medium)
  • Implement Document Predicate APIs - Snowflake (medium)
  • Find Shortest Wiki Click Path - Snowflake (medium)