Quais são os programas de codificação solicitados no processo de recrutamento da JUSPAY?

Totalmente 3 perguntas, e que devem ser completadas em 1 hora e 30 minutos

questão nº: 1

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

Você recebe uma floresta (pode conter uma única árvore ou mais de uma árvore) com Nodos.

Cada nó recebe um valor inteiro 0 a (N-1).

Você tem que encontrar:

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

A profundidade da floresta na qual o número máximo de nós está presente.

N pode ser muito grande. Aponte para um algoritmo com uma complexidade temporal de O(N).

INPUT FORMAT

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

Um T inteiro, denotando o número de casos de teste, seguido por 2T linhas, pois cada caso de teste conterá 2 linhas.

A primeira linha de cada caso de teste tem o valor de N.

Segunda linha de cada caso de teste tem uma lista de N valores onde o número no índice i é o pai do nó i. O pai da raiz é -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