Grid Paths Avoiding a Closed Point
Updated
Problem statement
You walk on grid points from (0, 0) to (width, height). Each step moves one unit right, which adds 1 to the first coordinate, or one unit up, which adds 1 to the second coordinate. So every path has exactly width + height steps.
The point (px, py) is closed: a path may not visit it. If the closed point is the start or the end, no path can avoid it.
Return the number of paths from (0, 0) to (width, height) that never visit (px, py).
Function
countPathsAvoidingPoint(width: int, height: int, px: int, py: int) → longExamples
Example 1
width = 6height = 4px = 3py = 2return = 110This is the interview grid, with the center point (3, 2) closed. Every path has 6 right steps and 4 up steps, so there are C(10, 4) = 210 paths in total.
A path through (3, 2) first goes from (0, 0) to (3, 2) in one of C(5, 2) = 10 ways, then from (3, 2) to (6, 4) in one of C(5, 2) = 10 ways. That gives 10 * 10 = 100 paths through the closed point. The answer is 210 - 100 = 110.
Example 2
width = 2height = 2px = 1py = 1return = 2There are C(4, 2) = 6 paths. The closed center (1, 1) is reached in 2 ways and left in 2 ways, so 4 paths use it. Only the two paths along the edges are left: right, right, up, up and up, up, right, right. The answer is 2.
Example 3
width = 2height = 1px = 1py = 0return = 1The three paths are right-right-up, right-up-right and up-right-right. The first two step on (1, 0) right away. Only up-right-right avoids it, so the answer is 1.
Example 4
width = 3height = 1px = 3py = 1return = 0The closed point is the end point (3, 1). Every path must finish there, so no path avoids it. The answer is 0.
Constraints
1 <= width, height <= 250 <= px <= width0 <= py <= height
More Susquehanna International Group (SIG) Online Assessment questions
- Catch Fish with Reusable BaitsOA · Seen Nov 2026
- Bold Play to Reach a GoalOA · Seen Nov 2026
- Cats, Truth and Who Has MoreOA · Seen Nov 2026
- Counting Cows by Their LegsOA · Seen Nov 2026
- Enough Muffins for the LineOA · Seen Nov 2026
- Expected Consecutive Pairs Among Chosen NumbersOA · Seen Nov 2026
- Four-by-Four Boundary GridOA · Seen Nov 2026
- Frog Paths Without Long RunsOA · Seen Nov 2026
- Higher Roll, or Lose the SumOA · Seen Nov 2026
- Is a Popular Story Fake?OA · Seen Nov 2026
Similar questions at other companies
- Count Nondecreasing Digit-Sum ArraysMicrosoft · OAMicrosoft interview questions
- Stable Workload Redistribution TreesTower Research Capital · OA
- Count Valid A-B-C Sequences Under a Modulo-Four RuleInfosys · OAInfosys interview questions
- Count Shipment SchedulesMorgan Stanley · OAMorgan Stanley interview questions
- Count Permutations Without Three Equal Parities in a RowGoogle · OAGoogle interview questions
- Find Encrypted NumberAmazon · OA
- Valid PasswordsMathWorks · OAMathWorks interview questions
- Coloring HousesSnowflake · OASnowflake interview questions
- Find Maximum Number of StringsMoveworks · OAMoveworks interview questions
- Count Distinct Binary Search TreesC3.ai · OAC3.ai interview questions