Graph Problem (Asked in Infosys Interview)

Problem: Chair Game – Minimum Jumps

You are given N chairs arranged in a circle, numbered from 0 to N-1.
Each chair i has an associated value A[i], which represents the exact number of positions a person can jump from that chair — either to the left or to the right.

Because the chairs form a circle:

Jumping right from chair (i) goes to (i + A[i]) % N

Jumping left from chair (i) goes to (i - A[i] + N) % N

Bob starts at chair number X, and wants to reach chair number Y.

Your task is to determine the minimum number of jumps Bob needs to reach from chair X to chair Y.
If it is not possible, return -1.

Question

Graph Problem (Asked in Infosys Interview)

Problem: Chair Game – Minimum Jumps

You are given N chairs arranged in a circle, numbered from 0 to N-1.
Each chair i has an associated value A[i], which represents the exact number of positions a person can jump from that chair — either to the left or to the right.

Because the chairs form a circle:

Jumping right from chair (i) goes to (i + A[i]) % N

Jumping left from chair (i) goes to (i - A[i] + N) % N

Bob starts at chair number X, and wants to reach chair number Y.

Your task is to determine the minimum number of jumps Bob needs to reach from chair X to chair Y.
If it is not possible, return -1.

Sigiloso · Accepted Answer

I first attempted a brute-force DFS/backtracking approach, exploring all possible left and right jumps from each chair. This worked for a few test cases but wasn’t efficient enough for larger inputs.

I knew the optimal method was to treat the chairs as nodes in a graph and use BFS to find the shortest number of jumps, since each move has equal weight. However, I wasn’t able to implement the optimal approach correctly within the given time, so only some of my test cases passed.

Infosys

Pergunta de entrevista da empresa Infosys

Resposta da entrevista

Empresas seguidas

Buscas de vagas