Uber onsite: Points make valid relations? | LeetCode Discuss
This is just a variation of the Course Schedule problem. Basically you want to build a graph from the relations, and then find if a cycle exists in the directed graph.
Do you mean the following?
For each direction E,W,N,S
We create directed graphs and check if there is a cycle (DFS for example)
For example :
aNbNcNdNa - has a cycle
kNfNs - no cycle
bSaSgShSf - no cycle
it comes from the fact that if we have some points c,b,d,f to the north of the other a: aNbNcNdNf, it is not possible b,c,d,f to be to the north of a
Yes, the question description did not mention if b N a, does that mean b can be anywhere north of a? And does north mean absolute north?
If this assumption is true, then I guess in your example both "c W a" and "c N a" are incorrect.
apparently it means anywhere in NW .. doesn't has to be absolute North.
it makes sense ... its creating graph out of EACH direction. We can start with say North, found cycle return, and do same for other edges. Why I couldn't think of this!
Read full article from Uber onsite: Points make valid relations? | LeetCode Discuss
Given points and relationship matrices , determine if they make valid relations
Where points could be a,b,c ...
relationship is : direction: North, East, South, West
a N b: a is north to b
b S a: b is South to a
This is valid relation.
But a N b, b N a. Not valid.
There could be n # of points. First he asked me wether there are any other
violation that I can see. After A WHILE I figured for 3 also it could be problem.
Then he asked: do u have to check for 2, 3 points, and like that how many
points I should be checking.
At the end: how can I write algorithm to do so.
Not such a good interview experience (that hour) .. I couldn't figured out, and he didn't give any hint either. I still need to figure out solution for that.
Where points could be a,b,c ...
relationship is : direction: North, East, South, West
a N b: a is north to b
b S a: b is South to a
This is valid relation.
But a N b, b N a. Not valid.
There could be n # of points. First he asked me wether there are any other
violation that I can see. After A WHILE I figured for 3 also it could be problem.
Then he asked: do u have to check for 2, 3 points, and like that how many
points I should be checking.
At the end: how can I write algorithm to do so.
Not such a good interview experience (that hour) .. I couldn't figured out, and he didn't give any hint either. I still need to figure out solution for that.
This is just a variation of the Course Schedule problem. Basically you want to build a graph from the relations, and then find if a cycle exists in the directed graph.
Do you mean the following?
For each direction E,W,N,S
We create directed graphs and check if there is a cycle (DFS for example)
For example :
aNbNcNdNa - has a cycle
kNfNs - no cycle
bSaSgShSf - no cycle
it comes from the fact that if we have some points c,b,d,f to the north of the other a: aNbNcNdNf, it is not possible b,c,d,f to be to the north of a
Yes, the question description did not mention if b N a, does that mean b can be anywhere north of a? And does north mean absolute north?
If this assumption is true, then I guess in your example both "c W a" and "c N a" are incorrect.
apparently it means anywhere in NW .. doesn't has to be absolute North.
it makes sense ... its creating graph out of EACH direction. We can start with say North, found cycle return, and do same for other edges. Why I couldn't think of this!
Read full article from Uber onsite: Points make valid relations? | LeetCode Discuss
