SDE - 1

You are given an array ‘ARR’ of size ‘N’ containing each number between 1 and ‘N’ - 1 at least once. There is a single integer value that is present in the array twice. Your task is to find the duplicate integer value present in the array.

For example:

Consider ARR = [1, 2, 3, 4, 4], the duplicate integer value present in the array is 4. Hence, the answer is 4 in this case.

Note :

A duplicate number is always present in the given array.

You are given a list/array of strings which denotes the contacts that exist in your phone directory. The search query on a string ‘str’ which is a query string displays all the contacts which are present in the given directory with the prefix as ‘str’. One special property of the search function is that when a user searches for a contact from the contact list then suggestions (contacts with prefix as the string entered so for) are shown after the user enters each character.

Note :

If no suggestions are found, return an empty 2D array.

For Example :

In the above example everytime we enter a character, a few suggestions display the strings which contain the entered string as prefixes.

You have been given an array/list ‘EDGES’ of size (N - 1) x 2 representing the undirected connected tree with ‘N’ nodes from 0…’N’ - 1 and ‘N’ - 1 edges such that the i’th edge connects ‘EDGES[i][0]’ node with ‘EDGES[i][1]’ node.

You need to print an array/list ‘ANS’, where ANS[i] is the sum of the distances between node ‘i’ and all other nodes.

For example:

For ‘N’ = 6 and ‘EDGES’ = [ [0,1], [0, 2], [2, 3], [2, 4], [2, 5] ], see the below picture for reference:

1. For node 0:
   a. Distance from node 0 to node 1 is 1.
   b. Distance from node 0 to node 2 is 1.
   c. Distance from node 0 to node 3 is 2.
   d. Distance from node 0 to node 4 is 2.
   e. Distance from node 0 to node 5 is 2.
   So the sum of all the distances is 8.

2. For node 1:
   a. Distance from node 1 to node 0 is 1.
   b. Distance from node 1 to node 2 is 2.
   c. Distance from node 1 to node 3 is 3.
   d. Distance from node 1 to node 4 is 3.
   e. Distance from node 1 to node 5 is 3.
   So the sum of all the distances is 12.

3. For node 2:
   a. Distance from node 2 to node 0 is 1.
   b. Distance from node 2 to node 1 is 2.
   c. Distance from node 2 to node 3 is 1.
   d. Distance from node 2 to node 4 is 1.
   e. Distance from node 2 to node 5 is 1.
   So the sum of all the distances is 6.

4. For node 3:
   a. Distance from node 3 to node 0 is 2.
   b. Distance from node 3 to node 1 is 3.
   c. Distance from node 3 to node 2 is 1.
   d. Distance from node 3 to node 4 is 2.
   e. Distance from node 3 to node 5 is 2.
   So the sum of all the distances is 6.

5. For node 4:
   a. Distance from node 4 to node 0 is 2.
   b. Distance from node 4 to node 1 is 3.
   c. Distance from node 4 to node 2 is 1.
   d. Distance from node 4 to node 3 is 2.
   e. Distance from node 4 to node 5 is 2.
   So the sum of all the distances is 6.

6. For node 5:
   a. Distance from node 5 to node 0 is 2.
   b. Distance from node 5 to node 1 is 3.
   c. Distance from node 5 to node 2 is 1.
   d. Distance from node 5 to node 3 is 2.
   e. Distance from node 5 to node 4 is 2.
   So the sum of all the distances is 6.

So, ‘ANS’ for the above example will be [8, 12, 6, 10, 10, 10].

Previous company experience

Who is your role model?

What are your hobbies?