Facebook Interview Question Software Engineer / Developers
Country: United States
Interview Type: Phone Interview
If it is null-terminated, then finding a cycle means we can't reach all cells. Otherwise, the cycle must be of length "nxn". Also, we must make sure the traversal takes "nxn", i.e., the graph is connected or technically every vertex is reachable from (0, 0).
I guess we can also do this in O(n^2) time with O(1) extra space. It is similar to finding a cycle in a sequence (Floyd's cycle finding algorithm = hare-tortoise).
If there is a cycle then is has to be of length "nxn".
If there are no cycles, then the tortoise has to have walked "nxn" cells.
You don't need extra space. You can use the same matrix. Set the entry to (n+1,m+1) once you visit it. If you ever encounter an entry with(n+1,m+1), break the traversal. Then check every entry of matrix. If all of them are (n+1, m+1), you have traversed every entry otherwise no.
aj's solution is correct. But the final traversal to check whether all cells have been visited is not necessary. We can maintain a variable 'count' to hold the number of visited cells. When we encounter a visited cell, just check 'count==M*N'
$A = array(
array(
array(0,1),array(1,2),array(3,3)
),
array(
array(1,1),array(3,3),array(3,2)
),
array(
array(3,0),array(1,3),null
),
);
$hasBeen = array();
$rootPosition = array(0,0);
$total = 0;
var_dump(func($A,$rootPosition,$total,$hasBeen));
function func($A,$position,$total,$hasBeen) {
$item = $A[$position[0]][$position[1]];
if ($item == null) {
return $total == count($A)*count($A);
}
$hasBeen []= $position;
$nextPosition = array($item[0],$item[1]);
if (!in_array($nextPosition,$hasBeen)) {
return func($A,$nextPosition,$total+1,$hasBeen);
}
return false;
}
Just like a graph traversal using a same size matrix with initial value set to -1. Mark the position you visited and, if you see a cycle (not -1 value), you know you will not be able to visit all the cells.
- qxixp February 06, 2014time complexity nxn and space complexity nxn