Determine Reachability for a Chinese-Chess Horse with Blocked Legs

Question

The question asks the candidate to determine the reachable positions of a Chinese-Chess horse given its movement constraints due to blocked legs.

Codemia · Accepted Answer

To solve the problem, we first need to understand the movement capabilities of the Chinese-Chess horse. The horse moves in an 'L' shape, similar to a knight in Western chess, but with the added complexity of blocked legs that restrict certain movements. Our goal is to determine all the positions the horse can reach from its starting position, taking into account these blocked legs.

We can use a breadth-first search (BFS) approach to explore all reachable positions. The BFS will start from the horse's initial position and explore all possible moves, marking positions as visited to avoid cycles. The horse can move to a position (x + 2, y + 1), (x + 2, y - 1), (x - 2, y + 1), (x - 2, y - 1), (x + 1, y + 2), (x + 1, y - 2), (x - 1, y + 2), and (x - 1, y - 2), but we must check if these positions are blocked or out of bounds.

The time complexity of this algorithm is O(N), where N is the number of positions the horse can potentially reach. This is because each position is visited at most once. The space complexity is also O(N) due to the storage of visited positions and the queue used in BFS.

Here is a sample implementation of the algorithm in Python:

```python
from collections import deque

def reachable_positions(start, blocked):
    moves = [(2, 1), (2, -1), (-2, 1), (-2, -1), (1, 2), (1, -2), (-1, 2), (-1, -2)]
    visited = set()
    queue = deque([start])
    visited.add(start)
    
    while queue:
        current = queue.popleft()
        for move in moves:
            next_pos = (current[0] + move[0], current[1] + move[1])
            if next_pos not in blocked and next_pos not in visited:
                visited.add(next_pos)
                queue.append(next_pos)
    return visited
```

This code initializes a queue for BFS, explores all reachable positions, and returns a set of visited positions.

When implementing this solution, we should consider edge cases such as starting positions near the edges of the board, positions that are completely blocked, and ensuring that the horse cannot move outside the board boundaries. Handling these conditions will ensure our solution is robust.

Determine Reachability for a Chinese-Chess Horse with Blocked Legs

eBay

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Approach

Algorithm

Submit Your Answer

eBay Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string