ur2cdanger
BAN USER- 1of 1 vote
Answersthere are a million nodes, it is a DAG, a startpoint is a node with no edges into it and an endpoint is a node with no edges out of it. Each query asks the question - is there a path between a specified pair of start and endpoint nodes. To perform a thousand such queries on a graph that has million nodes, using DFS/BFS is order (1000 * 1000000). I was asked for a solution with better runtime than that.
- ur2cdanger in United States| Report Duplicate | Flag | PURGE
Software Engineer / Developer Algorithm - 2of 2 votes
AnswersA graph contains one start node with no out-edges and a ending node with no in-edges. Such graph contains, say 10 million nodes. Question is how to find out effectively if two nodes are connected. The graph is a directed, unweighted and acyclic graph.
- ur2cdanger in United States
Additional Information : the graph will be queried for such connectivity queries at least a million times.
I was able to come up with building a transitive closure. But the space requirements ( O(10million * 10 million ) is huge.
2) I suggested BFS but it would be O( million * 10 million ), so that also was rejected.
Is there any other effective way ?. Practically I couldn't think of any other way.| Report Duplicate | Flag | PURGE
Software Engineer / Developer Algorithm - -1of 1 vote
AnswersGiven an array of strings. Find the common combination of the strings in the array. Given : There is one combination of the strings in the array that uses all the elements in the array.
- ur2cdanger in United States
For example : Array a = { "abc","efgh","abcde","fgh","abcd","defgh"}; ans = abcdefgh ; Because "abc"+"defgh" = "abcdefgh",
""abcd"+"efgh" = "abcdefgh"
"abcde"+"fgh" = "abcdefgh"| Report Duplicate | Flag | PURGE
Software Engineer / Developer Algorithm
The question to be exact is find all pairs of strings in an array that when concatenated gives the same string. Condition is there are N elements(N is even) and there are definitely N/2 pairs. We need to find all the pairs and all pairs when concatenated with each other will give the same string.
For example : Array a = { "abc","efgh","abcde","fgh","abcd","defgh"};
Expected output : ("abc","defgh") , ("abcde","fgh") , ( "abcd","efgh")
@ZhenyilLuo Your solution seems pretty interesting. How will I do this incase the nodes does not numbers but have strings. How will I check the divisibility?
- ur2cdanger January 20, 2014