question:was asked in deshaw online round
after an earthquake a few rooms have been destroyed and others have remained the same.
A women can travel between rooms that are undestroyed return the maximum coins she can collect if each undestroyed room has one coin.
Each undestroyed room can only be visited once.
can only travel from undestroyed room to another undestroyed room through a common wall.
input was array of string
1 for undestroyed room
0for destroyed room
eg:
[“10”],[“10”]
output:2
my approach:
do depth first search from all four sides, during each dfs keep track of previous room in seen(set()) so as to avoid infinite recursion and return the maximum, But I was only passing 4/13 testcases.
anyone know where my approach was failing?
Can he travel from an undestroyed room to a destroyed room and vice versa , and can he visit an undestroyed room more than once .
@dhruv788 Each undestroyed room can only be visited once.
can only travel from undestroyed room to another undestroyed room through a common wall.
Do you have link to the question ? , And if not can you tell the Constraints of the array of string and also that the output for
00111000
11101111
00111000
It is 11 or 13?
@dhruv788 it was a question asked in deshaws online round so i dont have a link to the question.
time limit was 5 seconds string len <=10^5 and array size <=10^5
and the output for your case would be 11
Are you sure that constraints are right because taking input of size 10^5*10^5 is 10^10 which will take more time that 5 seconds
@dhruv788 i am sure about string size and time limit but I cannot remember the array constraint.
My approach was giving TLE for 4 test cases
You can use this approach-
Find an undestroyed room first. Run a dfs from it. Find the room which is at the maximum distance from this room. Run a dfs again from this farthest room. The maximum depth that you will get is the answer.
Now if there are are different connected components in the graph, then you have to do this for each component and find the maximum.
To my knowledge it should work, even though i am not a 100% sure about it.
@tamo11 this is not the right way , it is used for Maximum distance in tree and can’t be used for Graph just look at this example
00111000
11101111
00111000
If we run DFS from 5,2 (1 based indexing) we get the farthest point as 1,2 , and from 1,2 we get farthest point as 8,2 or 3,3 or 1,3 which will give answer as 10 but it is 11
I tried to look for the solution of Longest path in a graph and found that it is a NP- Hard problem
Have a look at this .
The code I had in mind wouldn’t have chosen (5,2) as the point to start with, but I get what you are implying. Yup, there can be cases where my solution will fail.