## Ankita

BAN USER- 1of 1 vote

AnswersGiven multiple tuples in the form of (A,B) where A is the parent and B is the child in a binary tree, find if the input is valid or not. 4 error conditions were provided:

- Ankita in United States

1. If a parent has more than 2 children,

2. If duplicate tuples entered,

3. If the tree has a cycle,

4. If more than one root possible.

For violation of multiple validity conditions, print the condition coming first in the above order.

If the input is valid, print the tree in a serial representation. For eg: If input is (A,B), (B,C), (A,D), (C,E) , output: (A(B(C(E)))(D))| Report Duplicate | Flag | PURGE

Starup SDE-2 Algorithm Problem Solving - 0of 0 votes

AnswersIf we have telephone directory with 1,00,000 entries,which sorting algorithm is best?

- Ankita in India| Report Duplicate | Flag | PURGE

Algorithm

Thanks for sharing !

Here you have done is split in two cases:

- If two intervals do not intersect,then either consider it or do not consider it

- If they intersect,then without considering

Please let me know if I understood your logic right.

Also , time complexity will be 2^n of recursive algo, right?

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

Open Chat in New Window

Thank you for such awesome solution.

- Ankita October 19, 2018If I am not wrong,the time complexity of finding cycle will be O(nlogn) as for each child node it traverses upwards and in worst case O(n^2)..

I was thinking of using graph(DFS) to solve this:

- while adding edges (addEdge(a,b)), I will check two conditions ,whether it already has 2 child nodes and if the the tuple is duplicate

- after this ,DFS of graph to check if there is a cycle, whose time complexity will be O(no of vertices)

But I am not able to check the last condition : finding more than one root.

Any suggestions here how to do that?

Thanks again