Quali sono i programmi di codifica chiesti nel processo di reclutamento JUSPAY?

Totalmente 3 domande, e che devono essere completate in 1 ora e 30 minuti

Domanda n: 1

===================

Ti viene data una foresta (può contenere un singolo albero o più di un albero) con N nodi.

Ogni nodo ha un valore intero da 0 a (N-1).

Devi trovare:

===================

La profondità della foresta alla quale è presente il numero massimo di nodi.

N può essere molto grande. Si cerchi un algoritmo con una complessità temporale di O(N).

FORMATO DI INGRESSO

=================

Un numero intero T, che denota il numero di testcase, seguito da 2T linee, poiché ogni testcase conterrà 2 linee.

La prima linea di ogni testcase ha il valore di N.

Seconda linea di ogni testcase ha una lista di N valori dove il numero all'indice i è il genitore del nodo i. Il genitore di root è -1. ( The index has the range [0, N­-1] ).

OUTPUT FORMAT

===============

For each testcase given, output a single line that has the depth of forest at which maximum number of nodes are present. If multiple depths has same number of nodes, then deepest depth should be selected.

SAMPLE INPUT

==============

2

6

5 -1 1 1 5 2

13

4 3 -1 -1 1 2 7 3 1 4 2 1 2

SAMPLE OUTPUT

====================

3

1

(the above diagram is common for all 3 questions)

===============

question no 2:

==================

You are given a forest (it may contain a single tree or more than one tree) with N nodes.

Each node is given an integer value 0 to (N­-1).

You have to find:

==================

Level order traversal: print nodes at every level of the forest.

N can be very large. Aim for an algorithm with a time complexity of O(N).

INPUT FORMAT

==============

An integer T, denoting the number of testcases, followed by 2T lines, as each testcase will contain 2 lines.

First line of each testcase has the value of N.

Second line of each testcase has list of N values where the number at index i is the parent of node i. The parent of root is -1. ( The index has the range [0, N­-1] ).

OUTPUT FORMAT

================

For each testcase given, Suppose m is the height of tree, then next m lines must contain the nodes of that level in ascending order separated by space. After printing level order traversal of each testcase, print a new line.

SAMPLE INPUT

================

2

6

5 -1 1 1 5 2

13

4 3 -1 -1 1 2 7 3 1 4 2 1 2

SAMPLE OUTPUT

===============

1

2 3

5

0 4

2 3

1 5 7 10 12

4 6 8 11

0 9

—————

• Question 03:

-------------

You are given a forest (it may contain a single tree or more than one tree) with N nodes.

Each node is given an integer value 0 to (N­-1).

You have to find:

==================

Nearest common ancestor of two given nodes x1 and x2.

N can be very large. Aim for an algorithm with a time complexity of O(N).

INPUT FORMAT

-------------

An integer T, denoting the number of testcases, followed by 3T lines, as each testcase will contain 3 lines.

First line of each testcase has the value of N.

Second line of each testcase has list of N values where the number at index i is the parent of node i. The parent of root is -1. ( The index has the range [0, N­-1] ).

Third line for each testcase contains two integers within the range of [0,N­-1] whose common ancestor you have to find.

OUTPUT FORMAT

==============

For each testcase given, output a single line that has the nearest common ancestor to two given nodes x1 and x2. If a common ancestor is not present then output '-1'.

SAMPLE INPUT

-------------

2

6

5 -1 1 1 5 2

0 3

13

4 3 -1 -1 1 2 7 3 1 4 2 1 2

8 5

SAMPLE OUTPUT

================

1

-1