Self Crossing

Self Crossing

What is this problem about?

The Self Crossing interview question gives you an array of distances representing movements on a 2D plane. You start at the origin and move north, west, south, east, north, west, ... in sequence. Each movement covers the given distance. Determine whether the path crosses itself at any point. This is a pure geometry and math problem requiring careful case analysis.

Why is this asked in interviews?

Zomato asks this HARD problem because it tests geometric reasoning and pattern recognition under a strict movement structure. Candidates must identify the exact three cases where self-crossing can occur: the current segment crosses the segment three steps back, four steps back, or five steps back. This requires translating geometric intersection conditions into algebraic inequalities — a skill valuable in computational geometry, game development, and robotics path planning.

Algorithmic pattern used

The pattern is case analysis with geometric conditions. For each new segment x[i] (i ≥ 3), check three crossing scenarios:

1. 3-step back: x[i] >= x[i-2] and x[i-1] <= x[i-3] — the current segment overlaps the segment 3 steps back.
2. 4-step back: x[i-1] == x[i-3] and x[i] + x[i-4] >= x[i-2] — the current segment touches the segment 4 steps back.
3. 5-step back: x[i] + x[i-4] >= x[i-2] and x[i-1] <= x[i-3] and x[i-1] + x[i-5] >= x[i-3] and x[i-2] >= x[i-4] — spiral inward crossing.

If any case is true, return true (path crosses). Otherwise return false.

Example explanation

Distances: [2, 1, 1, 2].

Movement trace: go N 2, go W 1, go S 1, go E 2.

At step i=3 (go E 2): x[3]=2 >= x[1]=1 (segment 3 steps back is 1 unit wide), and x[2]=1 <= x[0]=2 (segment 2 steps back is smaller). Crossing detected → return true.

Distances: [1, 1, 2, 2, 3, 3, 4, 4, 10, 4] — spiral outward, no crossing → false.

Common mistakes candidates make

• Only checking one or two of the three crossing cases — all three must be checked for correctness.
• Confusing the spiral-inward (case 3) with the direct overlap (case 1) — they require different inequalities.
• Using floating-point arithmetic for positions instead of integer distance comparisons — integer comparisons are sufficient and more robust.
• Not handling the base case when i < 3 (first 3 segments can never cross).

Interview preparation tip

For the Self Crossing coding problem, the array and geometry math interview pattern requires memorizing the three crossing case formulas. This is one of the rare problems where the algorithm is essentially the case analysis itself — understanding why each case causes a crossing (draw the geometry!) is more important than the code. Zomato interviewers value geometric intuition. Before coding, sketch each of the three cases on paper and derive the inequalities yourself — this builds intuition that's hard to forget.