## 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")

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

@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