Path Crossing

Path Crossing

What is this problem about?

The Path Crossing problem asks whether a path described by a string of directions ('N','S','E','W') crosses itself — i.e., revisits a position it has already been at. This easy coding problem uses a hash set to track visited positions. The hash table and string interview pattern is demonstrated.

Why is this asked in interviews?

Yandex, Amazon, Google, and Adobe ask this as a quick screening problem testing coordinate tracking with a hash set. It validates that candidates can simulate movement, encode positions as hashable keys, and detect revisits.

Algorithmic pattern used

Coordinate hash set. Start at (0,0). Add initial position to visited set. For each direction: update (x,y) based on direction. If (x,y) already in visited, return true. Add (x,y) to visited. Return false after processing all directions.

Example explanation

path="NES". Start at (0,0).

• N: (0,1). Not in {(0,0)}. Add.
• E: (1,1). Not in visited. Add.
• S: (1,0). Not in visited. Add. No revisit → false.

path="NESWW": (0,0)→(0,1)→(1,1)→(1,0)→(0,0)→(-1,0). At (0,0) again → true.

Common mistakes candidates make

• Not including the starting position (0,0) in the visited set initially.
• Using a list instead of a set (O(n) lookup instead of O(1)).
• Incorrect direction mappings (N=+y, S=-y, E=+x, W=-x).
• Checking revisit before or after adding position (check BEFORE adding, then add).

Interview preparation tip

Path tracking with hash sets is a standard coordinate problem. Use tuples (x,y) as hash set keys. Always include the starting position. Direction mappings: N=(0,+1), S=(0,-1), E=(+1,0), W=(-1,0) — or any consistent convention. Practice similar problems: "robot on 2D grid," "walking path self-intersection," "spiral path tracking." All use the same coordinate-hash-set pattern.