9 weeks ago

John 910

Hyderabad

Question 1

One day the manager at a fintech company decides to create a team for the next project. There are a total of n employees and the skill-level of ith employee is Ai.

He thinks that the more employees a project has, the easier it gets to work and the project would be finished in fewer days. So he decides to create a team with the maximum number of employees possible. But there must be a balance factor within the team, so the manager decides to create a team in such a way that the skill-level of each pair of employees within the team would differ by no more than 5.

Your task is to help the manager find the maximum number of employees that could be accommodated in the team.

Example 1:

n = 8

4 17 8 24 6 10 12 9

In the example above, there can be a maximum of 4 members in the team, the team can comprise of employees with skill-level 4 8 6 9, i.e, employees with indices 1, 3, 5, 8.

Function Description

You will be given the size of the array and the array consisting of the skill level of the employees in the company. You'll have to write a function computeMaximumTeamMembers in the editor below. The function must return an integer denoting the maximum number of employees that could be accommodated in the team.

computeMaximumTeamMembers has the following parameters:

number_of_employees: the size of the array or the total number of employees in the company.

skill_level: an array of integers, where each A[i] is the skill level of the employee i.

Constraints

• 1 <= n <= 10000
• 1 <= Ai <= 10^9

Sample Input

6

1 10 17 12 15 2

Sample Output

3

Explanation

The manager can create a team with skills [17, 12, 15].

Question 2

You are in a corporate and you need to communicate about a strategic mission in-person to all the people in your company. This information can NOT be broadcasted so you have to tell it to each person in a 1-1 session. It takes 1 hour to communicate the information from one person to another. At any given point of time, a manager can communicate this vital strategic information to one of his/her direct reports. Let us say we have the following reporting structure: Find out the minimum number of hours in which the information can be communicated to all the members of the organization.

In the above tree,

At the end of hour 1, 'A' will pass the info to 'B'.

At the end of hour 2, 'A' will pass the info to 'E'; 'B' will pass the info to 'H'.

At the end of hour 3, 'A' will pass the info to 'G'; 'B' will pass the info to 'l'; 'E' will pass the info to 'K' ... and so on.

Find the minimum number of hours in which all the people in the organization are informed of the strategic mission.

Input: Each line in the input represents an edge between two nodes in the tree separated by a comma.

A,B

A,C

A,D

A,E

A,F

A,G

B,H

B,1

B,J

H,N

H,0

E,K

E,L

K,P

L,Q

G,M

8 months ago

Shikhar Mehrotra 480

Chennai

Q1)

Solution

Aim : We want to select a subset of maximum size such that difference between each pair's skill is at most 5.

• If we have difference between the maximum element and minimum element to be at most 5 then it will be valid for us to form company .
  Why? If we have chosen a subset {a1<=a2<=...<=ak} and if ak-a1<=5 then since the maximum difference is at most ak-a1 and choosing any pair gives difference less than ak-a1 . Hence we just need to maintain max_element - min_element to be < =5.

Implementation steps

• Sort the array (skill[1] < =skill[2] ... < =skill[n])
• Then if we chose skill[i] to be the minimum element than we need to find the maximum position j such that element(skill[j]>=skill[i]) such that skill[j]-skill[i] < =5.
• Finding the optimal j can be done either by Binary Search or Two pointers
• Then the answer would be taking all the elements from [ i .... j ] i.e taking j-i+1 elements to form the company.

Pseudo Code(Binary Search)

skill.sort()
answer=0;
for i in range(0...n-1)
{
//binary search for j such that skill[j] < =skill[i]+5
start=i,end=n-1;
while(start < =end)
{
mid=(start+end)/2
if(skill[mid]<=skill[i]+5)
beg=mid+1;
else
end=mid-1
 } 
 answer=max(answer,end-i+1);
}
return answer

Pseudo Code(Two pointers)
//skill array is sorted

int i=0,j=0,ans=0;
for(int i=0;i < n;i++)  
{
while((j < n) and (skill[j]-skill[i] < =5))
    j=j+1;

ans=max(ans,j-i);
}
return ans

8 months ago

Shikhar Mehrotra 480

Chennai

Q2)
Assuming tree of 1 < =N < =1e5 nodes and nodes are numbered from 1 to N and the node numbered 1(root) has the information initially if according to samples the nodes are string you could use map and bring it down to nodes numbered 1 to N.

Solution

• Hint : Try DP dp[X] representing minimum time such that all nodes have the information if we know that node X has the information initially and it takes time=0 for the information to be known by node X
• We know that if it takes T time for node X to give information to every nodes in it's subtree if node X has the information initially and if node X get the information in P time then the time taken for information to be conveyed to subtree nodes of node X is P+T time.
• Let's suppose if node X has children {c1,c2....,ck}(any arbitrary order of child node) and we know dp[c1],dp[c2],...,dp[ck] and since we currently know it takes 0 time for information to be conveyed to node X and we have to allot/time taken for information to it's children {1,2,...,k} to {c1,c2...ck} in such a way that time taken is minimized.
• So our target is to minimize the maximum(dp[d1]+1,dp[d2]+2,...,dp[dk]+k) Remember d1,d2...,dk is arbitrary order of child nodes
• So it's always optimal to allot more time to that one which takes less time to convey to it's subtree and less time to that one which takes more time to convey to it's subtree.
• Let's suppose dp[c1]>=dp[c2]>=dp[c3]....>=dp[ck] where k is number of child of X Then we allot 1 to c1 , 2 to c2....
  Therefore dp[X] = max(dp[c1]+1,dp[c2]+2,...dp[ck]+k) after sorting descending order of children dp's dp[c1]>=dp[c2]>=dp[c3]....>=dp[ck] and if node has no children then obviously dp[node]=0 for that node.

Pseudo Code

void dfs(int X,int parent)
{
  list children_dps;
  for(childen c of s)
  {
   dfs(c,s);
   children_dps.push(dp[c]);
  }
  children_dps.sort_descending()
  dp[X]=0 //initialize to 0
  time = 1
  for(dps in children_dps)
  {
  dp[X]=max(dp[X],dps+time);
  time=time+1 //for next children allot next time
  }
}