## Ankita

BAN USER- 1of 1 vote

AnswersGiven an integer S, you have to count the total number of integral solutions of the equation a+b^2+c^3+d^4<=S, such that 0<=a,b,c,d<=10000 and 0<S<10^15

- Ankita in United States

Edit: Here value can be less than or equal to S, so if input S= 2 ,then output=12

i.e we can consider 0,0,0,1 and 0,0,0,0 etc also as sum will be less than S(i.e 2)| Report Duplicate | Flag | PURGE

SDE1 Algorithm - 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

Thank you for such awesome solution.

If 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

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

Thanks Peyar! It worked.

- Ankita January 15, 2019One more question,for ranges of the loop of b,c,d, can't we directly do like @hrabryi has done or like you did in your previous answer of O(n^4)? I am not able to understand the use of root function here