Question

You are given a maze of n cells, each cell may have multiple entry points but not more than one exit. Find nearest meeting cell: given any two cells-C1, C2, find the closest cell Cm that can be reached from both c1 and c2

Answer 1

Answer: as explained

Explanation:

Given as a node in the graph, there is this unique maximal path that will be starting from it since there is at most one exit from any node. It may or may not result in a cycle.

function largestCycle(edges)

{

var result, visitedFrom, startCell, cell, cells;

result = [];

visitedFrom = Array(edges.length).fill(-1);

for (startCell = 0; startCell<edges.length; startCell++)

{

cells = [];

for

(cell=startCell;cell>-1&&visitedFrom[cell]===-1; cell = edges[cell])

{

visitedFrom[cell] = startCell;

cells.push(cell);

}

if (cell > -1 && visitedFrom[cell] ===startCell)

{

cells =cells.slice(cells.indexOf(cell));

if (cells.length > result.length) result= cells;

}

}

return result;

}

var input = document.querySelector('textarea');

var output = document.querySelector('span');

(input.oninput = function () {

varedges=input.value.trim().split(/\s+/).map(Number);

var cycle = largestCycle(edges);

output.textContent = cycle.length + ': ' + JSON.stringify(cycle); })();

This is complexity with O(N) runtime where each edge of which there's at most N nodes is followed at most 3 times in the graph and the cache is updated exactly once for each and every node in the graph. It's uses O(N) additional storage.

Answer 2

Answer:

1

23

4 4 1 4 13 8 8 8 0 8 14 9 15 11 -1 10 15 22 22 22 22

22 21

9 2